|
I'm curious how it works - I can't tell much from the image.
I got interested in Sudoku, originally, because I wanted to build a solver. At first it worked (usually w/3 or 4 passes), but then more difficult puzzles were introduced and it failed. Adding more algorithms quickly got out of hand with their own complexity.
Looking into it further, it seemed at the time that puzzles were generated (and solved) in a trial-and-error fashion. Very disappointing. Other interesting things were that, at a minimum, seventeen values are required to have a solvable puzzle (necessary, but not necessarily sufficient). Sometime I wonder if a puzzle is actually solvable as given: it's only possible if there's only one solution. The computer method of solving doesn't (didn't) require this.
FWIW: My own personal rules of play require no guessing trials: all values are to be filled in by deduction. (i.e., I do not take a guess, follow through, and if it fails, go back) Also, no notes in empty boxes. Finally, I work in pen. If I mess it up, there's always another bunch available the next day.
"The difference between genius and stupidity is that genius has its limits." - Albert Einstein | "As far as we know, our computer has never had an undetected error." - Weisert | "If you are searching for perfection in others, then you seek disappointment. If you are seek perfection in yourself, then you will find failure." - Balboos HaGadol Mar 2010 |
|
|
|
|
|
|
I looked at the first one on the list: basically it's what I said: trial and error.
I was working on a purely logical solver. The original scanned each location to see if it had only one possible value. If it did, it was entered into the logic, if not, next. With the easy ones (of the day) it was done in 3 or 4 passes. Once they were a bit harder, it failed miserably.
I added some more logic, but it (as I said) quickly scaled in difficulty faster than I had time to commit for recreation. The difficulty was the various ways of implementing an exclusion of all other values when the cell's value wasn't uniquely determined by exclusion of other values. It works fine in my head but translating it in discrete steps was growing ugly. The higher order process (implications of a box have an entire row filled in on values in adjacent boxes parallel with that filled in row, for example).
It's quite possible that, from a computer's point of view, the recursive trial-and-error is the fastest route.
You gave a lot of ref's: I hope I don't get Ahem'd into shame for not checking them all.
"The difference between genius and stupidity is that genius has its limits." - Albert Einstein | "As far as we know, our computer has never had an undetected error." - Weisert | "If you are searching for perfection in others, then you seek disappointment. If you are seek perfection in yourself, then you will find failure." - Balboos HaGadol Mar 2010 |
|
|
|
|
|
The number 217 in the list has the correct answer.
I don't think you can go past some clever brute force ; as you have pointed out, in some tricky situations, the determination by exclusion is not so easy.
On the other side, IRL, I never had to require some more rules than one and only one occurrence of each figure in a line/in a column/in a square, which does not seem to complicated to implement. (I realize these are the complete set of rules of the game, but in some books, they add "tricks" based on assumptions -> what would be in this cell if I put a 1 in this cell -> leads to impossible situation -> so there cannot be a 1 in this cell, etc.... I think this is what you meant with the complicated exclusions).
|
|
|
|
|
A better view of a complicated solution:
A given cell can have any of several non-excluded values.
The other grids on it's row have each have a particular value which excludes all other cells in the grid but the one in question. So, instead of N being the only value that's not excluded from the cell we have that cell as the only cell (in that 3x3) from which N is not excluded.
This, however, may also be implemented wherein of the two 3x3's contributing to exclusion by rows, the value isn't in one (or both), but the row location(s) may be inferred from other 3x3's, carried through to the original cell, and N's only allowed location is defined.
Or - one 3x3 has has three-in-a-row defined. If in another a value is in either of the other rows, it's existence is inferred in the other row, and that can be used to locate it, or mapped to the third.
Etc. Etc. Etc.
All of these have one thing in common: no value is tried. It is either deduced or it is not known. One would never need to undo a step.
Turning the above into code starts to get pretty serious.
"The difference between genius and stupidity is that genius has its limits." - Albert Einstein | "As far as we know, our computer has never had an undetected error." - Weisert | "If you are searching for perfection in others, then you seek disappointment. If you are seek perfection in yourself, then you will find failure." - Balboos HaGadol Mar 2010 |
|
|
|
|
|
This is what I was trying to explain before: I am not sure you need to check for that particular situation, because going through "only one occurence of value v in a row/line/3x3" and "all values from 1 to 9 in a row/line/3x3" was sufficient.
|
|
|
|
|
|
Puzzles and solutions have never been trial and error. The hyper difficult puzzles (which many publications now eschew unfortunately) require no more than a handful of additional algorithms for either hoomins or computers to solve. It seems to me that you are cutting yourself off at the knees if you never allow notes in empty squares. There is certainly a greater sense of satisfaction if you complete a puzzle without them but a blanket ban means that some will go for ever unfinished.
As it's now so difficult to get hold of new truly challenging puzzles and it can get a bit repetitive (to say the least) I really only make the effort to try one a week these days (The Times on a Saturday - I buy it for The Listener crossword really but the Sudoku's there so ... )
As for the programming, the infallible solver was produced in the very first year of the craze and has never been bettered for my money.
|
|
|
|
|
Member 9082365 wrote: some will go for ever unfinished. Yes - and I don't let it bother me at all.
The solver, certainly in the early days, simply rapidly tried various solutions by filling in non-forbidden values. If it reached a conflict then it backed up and tried an alternate route. Since it was recursive, it could back up multiple steps. As for my not marking the boxes, I want to stretch my mind as much as possible when I do the puzzle for the sake of, well, stretching my mind. Very much you should visualize this as though you were stretching out after a good nap and how it adds to the refreshment.
Very unsatisfying for me (as a human) - the pleasures in the solving, not the solution.
There are various puzzles I do as they come by. Sudoku is very abundant so I do a bunch. Unless the others are available for variety. Cryptograms are always given first priority.
"The difference between genius and stupidity is that genius has its limits." - Albert Einstein | "As far as we know, our computer has never had an undetected error." - Weisert | "If you are searching for perfection in others, then you seek disappointment. If you are seek perfection in yourself, then you will find failure." - Balboos HaGadol Mar 2010 |
|
|
|
|
|
I will refuse to vote for anyone who uses post-fix increment operators!
Life is too shor
|
|
|
|
|
Well I told the boss on Friday that I had an offer and was going to accept.
It was pretty much everything you hope won't happen when you put in a notice. He said I was going to ruin my name, I haven't finished the project I'm working on, this is going to ruin him, what is he supposed to do, how could you, etc.
He calmed down, but then we had another meeting later with other people that kinda went the same way. He was just laying on me heavy. Saying this is the worst position he's ever been in, and he didn't know what they were goina do, etc.
So, later, his daughter approached me to see what the issues were and what type of things I would change to make it a place I wanted to stay. We had some really good conversation, and I was actually goina stay. So we ran the ideas past the boss and it was a no go.
I'm not sure if we ended in a good place or not. The last meeting we had just completely showed that I don't fit here. It was calm and I think he got a chance to see how we just don't really see things the same way.
We'll see what this two weeks brings. There's a product opening tomorrow that needs some mods done to it. They've scrapped the entire tablet program, so they gave me that to work on instead. I am pretty sure when I finish that they are just going to have me stop coming in. They've given me hints to that.
I start the new job the 25th. I've negotiated an offer, and got an informal email. I'll be getting the official today or tomorrow.
Elephant elephant elephant, sunshine sunshine sunshine
|
|
|
|
|
Tough situation, you try and do the right thing and give them 3 weeks notification and then they try to hurt you instead. When I was a consultant, I wasn't always given a date when the project would be over, so then I'd be out of a pay check. One of my last projects, I gave 1 day notice. It's lousy, but I don't feel like losing a few grand is worth it.
|
|
|
|
|
Yeah sounds like a typical, you ruined your name and also mine, but i won't give you more so it's attractive for you to stay situation.
People are stupid, if they have problems they blame someone else, in this case you.
Wish you good luck on your last days
if(this.signature != "")
{
MessageBox.Show("This is my signature: " + Environment.NewLine + signature);
}
else
{
MessageBox.Show("404-Signature not found");
}
|
|
|
|
|
Don't worry. It's just a case of hurt feelings. In his eyes the peasants don't run away from him, if at all, he throws them out. Now you have shown how unreliable and treacherous you are, so he does not want to keep you.
I have no idea how well things went before, but now you should be glad to get out of there.
The language is JavaScript. that of Mordor, which I will not utter here
This is Javascript. If you put big wheels and a racing stripe on a golf cart, it's still a f***ing golf cart.
"I don't know, extraterrestrial?"
"You mean like from space?"
"No, from Canada."
If software development were a circus, we would all be the clowns.
|
|
|
|
|
Just walk away.
Once you lose your pride the rest is easy.
In the end, only three things matter: how much you loved, how gently you lived, and how gracefully you let go of things not meant for you. – Buddha
Simply Elegant Designs JimmyRopes Designs
|
|
|
|
|
loctrice wrote: and I was actually goina stay.
After the BS that he put you through? I would have zero tolerance for that crap. Dealt with it once from a job shop that was contracting me out to Citigroup, the guy was a total arse about it and I told him so and hung up the phone on him. These people think that you're their personal slave.
Marc
|
|
|
|
|
So it sounds like it went something like this...
"Boss, I quit. I'm giving you time to do some knowledge transfer and some prep to find a replacement. I know that it is going to be a bit rough but I wanted to give you some warning so you aren't totally screwed. You know, just so things aren't completely in the weeds like when that other guy quit without a word."
PHB, with fingers in the shape of a little pyramid: "You can't quit on me! You're fired!" PHB begins banging his fist on the desk. "I'm going to call the Brute Squad! I'm king of the world! Mwuhahahahaha!" With that he leaps up, grabs a broom, straddles it and dashes out a 10th story window.
Same thing happened to me... they never did locate his body. Weird.
|
|
|
|
|
loctrice wrote: Well I told the boss on Friday that I had an offer and was going to accept.
...
I start the new job the 25th. I've negotiated an offer, and got an informal email. I'll be getting the official today or tomorrow.
Seems like you jumped the gun a bit. Should've waited until you've accepted the official offer at a minimum. Given the way your boss went psycho on you, I really hope the new one doesn't fall through at the last minute.
Did you ever see history portrayed as an old man with a wise brow and pulseless heart, waging all things in the balance of reason?
Is not rather the genius of history like an eternal, imploring maiden, full of fire, with a burning heart and flaming soul, humanly warm and humanly beautiful?
--Zachris Topelius
Training a telescope on one’s own belly button will only reveal lint. You like that? You go right on staring at it. I prefer looking at galaxies.
-- Sarah Hoyt
|
|
|
|
|
I have an official offer from a second company, which is also a great place.
Elephant elephant elephant, sunshine sunshine sunshine
|
|
|
|
|
So you handed in the notice before signing on the line knowing the official offer?
That is a dangerous game to play in these tough economic times. You could have easily handed in your notice and the new employer changes their mind at the last minute for any one of a million reasons.
Anyway, Congrats on the new job! Hope everything works out fine.
|
|
|
|
|
Exactly what loctrice needs, Dave, some reassuring and comforting support
|
|
|
|
|
I have an official offer from a second company, which is also a great place.
Elephant elephant elephant, sunshine sunshine sunshine
|
|
|
|
|
Cool! Sorted then!
|
|
|
|
|
loctrice wrote: I was actually goina stay
No ! I have been in the same situation, and refused (Because why should my job be worth a 20% rise after I first quit ?). They refused to pay my overtime - They actually deleted my hours from the system, and I had to sue them to have them pay the due vacation time I had not taken yet. I was sooooo happy I had refused the proposition of this bunch of clowns...
|
|
|
|
|
Good luck to you.
If the only time you're worth a raise is when you quit then you're in the wrong place.
|
|
|
|
|