I have added kakuro solver to my collection of sudoku solvers. An interesting thing about this solver is that it generates a small table of possible sums before the search for the solution begins. During the search it uses only bit operations, and it is extremely fast: 0.025s is the longest time taken for the puzzles from the sample puzzles page.
All of sudoku-like puzzles are advertised to be solvable by logic only and that no guessing is neccessary. What does this mean, exactly? I don't know what do the problem-setters mean by this, but to me this means that the game must be solvable with zero lookahead. At any stage while solving the puzzle, from the very beginning, there must exist at least one cell whose contents is uniquely determined only by the current state of the grid. At no point should you have to think about consequences of the move you are about to make.
For example, if your reasoning is "putting 3 at this position will make it impossible to put 7 at some other position afterwards", this is not zero lookahead and it is not logic; it is guessing. Logic is the following reasoning "i must put 3 in this cell because..", where the argument is based only on the current state of the grid, without looking in the future.
Of course, guessing is sometimes easier to the unskilled, but the fundamental question is: can the puzzle be solved with zero lookahead, i.e. by pure deductive logic based on the rules of the game and the current contents of the grid? If the answer to this question is negative, then sudoku (and its variants) are falsely advertised in my view.
Tags: sudoku kakuro logic
Subscribe to:
Post Comments (Atom)
8 comments:
hello, i didn't understand how you did the kakuro solver, e really don't understand anything about C++. My problem is that i have some kakuro puzzels that are almost impossible to solve. I was triyng to get a kakuro solver that give me the solution, but i didn't found it yet. Can you help me? Thanks
P.S. - If you want i can send you a copy of the puzzels, so you can see how hard they are
It's me again. I forgot to give you my contact. If tou have any information for me, you can send me an e-mail. Genivs@iol.pt.
Thanks
Gawsh, can't do this thing at all I need help fast like tommorow or today fast lol. It's for school plz help!. sandrasart@earthlink.net
can't find the server at www.core-dump.com.
can't find the server at www.core-dump.com.hr
The solvers have been migrated to my website: http://zvrba.net (look under software)
You wrote, "At any stage while solving the puzzle, from the very beginning, there must exist at least one cell whose contents is uniquely determined only by the current state of the grid."
I think this is stating it too strongly. (Well, there is one way to interpret the above that makes it trivial... but presumably you didn't mean that.) I think a more reasonable statement would be, "At any stage while solving the puzzle, from the very beginning, there must exist at least one cell whose constraints can be tightened using only the information in the current state of the grid."
I say that because very often during the solving of kakuro puzzles, you can make logical deductions that eliminate some possibilities for a given cell, but that cell's contents are not uniquely determined. After several such steps, you do end up uniquely determining the contents of a cell.
That being said, I have wondered about this claim too. In the end I usually shrug it off as vague, hard-to-falsify and not-very-meaningful marketing. To me, there is not a well-defined line between "pure deductive logic" and "lookahead." For example, if you have two cells that add up to 4, can you really deduce that the first cell cannot contain a 2 without any process that could be called lookahead? Whatever rules you use to make that deduction, are they not derived from rules like what you called guessing above - like, "If I put 2 in the first cell, that will make it impossible to put anything in the second cell that meets both the sum constraint and the all-different constraint"?
As we gain experience, we begin to recognize patterns and formulate and generalize to produce logical rules that reduce the amount of lookahead needed. But in my mind, there really is almost nothing you can deduce in a logic puzzle that cannot be characterized as relying on lookahead, unless you are willing to settle for a fixed set of rules. The creative part of puzzle-solving is not so much in the application of deductive rules, but in the discovery of new rules and new ways to apply them. I usually find that discovering new rules comes through trial and error (a form of lookahead) and recognizing patterns.
Oh, by the way, thanks for posting the code.
Post a Comment