4 ms·

When I wrote a Sudoku solver I was disappointed to find that backtracking worked maybe too well; that is, I coded in the minimum constraints to follow the rules

by Isamu 8y ago

When I wrote a Sudoku solver I was disappointed to find that backtracking worked maybe too well; that is, I coded in the minimum constraints to follow the rules of the game and then added backtracking and voila, it found solutions quickly enough. Why was I disappointed? Because initially I wanted to write a solver that inferred more, that used the inferences that I made when solving Sudoku. Sadly once the solver worked, I kinda lost interest. I hate backtracking myself and it should only be necessary at a certain Sudoku hardness level - every puzzle below that level of hardness should be solvable without backtracking.

deleted 8y ago
[deleted]
saurabh20n 8y ago
You are absolutely right. Punching "extra holes" in puzzles of certain hardness should make backtracking not as viable. But we'll loose the unique solution property. Might make it more interesting? And maybe even bias it towards human-abilities. I think intuitively we're better at solving when the possibilities are more than 1 (just a conjecture.)
- wiredfool 8y ago
  My soduku solver from ca~10 years back ran the "hardest" soduku puzzles in < 10 seconds on a netbook atom processor. IIRC, the hardest one that I ever threw at it had 7 levels of backtracking. It's just not that hard of a problem compared to the speed of computers.
daxfohl 8y ago
You can make it harder by using 16x16, 25x25, 36x36 etc boards, and see how fast you can make it. There are lots of known patterns to allow for elimination of options http://www.sudokuwiki.org/Getting_Started http://www.sudokuwiki.org/Getting_Started, of different computation complexity relative to each other, and all faster than regular backtracking. So the goal is to find the order at which to apply them for maximum speed and minimal need to backtrack. You can also try to multithread and use GPU, or FPGA if you're nuts. All that said, it's all still pretty mechanical. So if you're looking for something more inferential, then another game would be better.
LanceH 8y ago
My first attempt did no backtracking at all. It would guess randomly, propagate constraints and continue. If it got stuck, it would just start again. The most it ever took to solve a puzzle was 2100 attempts. Sure it wasn't guaranteed to solve a puzzle in finite time, but it worked well enough for something written during one of those endless big-corp conference calls.
- karmakaze 8y ago
  Technically, this is backtracking... to move 1.
dahart 8y ago
Yep, backtracking works fine. If you only want the solution, then you don't need complex rules. But, you really want more than just the solution. Check out http://sudokuwiki.com/sudoku.htm http://sudokuwiki.com/sudoku.htm This solver (and the whole site) is the best one I know of, and it will solve a puzzle by using rules in order of difficulty, to guarantee it tries the simple rules you know before resorting to backtracking. The benefits of this are that you can grade the difficulty of a sudoku board. You can also solve a puzzle up to the "crux" and then work on only the hard moves manually. I like doing that so I can skip the hours of boring stuff and practice doing the more tricky inferences. Andrew's site is a window into how big of a rabbit hole Sudoku can be...
- akbo 8y ago
  If you are interested in grading Sudokus by the difficulty of the human solving techniques required, you might want to check out the following two books: - "Sudoku Programming with C" [https://www.apress.com/de/book/9781484209967 https://www.apress.com/de/book/9781484209967] where a Sudoku solver and grader is implemented. - "A to Z of Sudoku" [https://www.wiley.com/en-us/A+to+Z+of+Sudoku-p-9781847040008 https://www.wiley.com/en-us/A+to+Z+of+Sudoku-p-9781847040008] where many human solving techniques are described and rated by their difficulty.
posterboy 8y ago
this comment made me lose interested, too, even my interest in the article.
pdwetz 8y ago
Backtracking as a strategy definitely seems... underwhelming. But it does have its uses. I wrote a few solvers, and they all served a different purpose. One was based on Norvig's python post on the subject; I used that to generate many puzzles very quickly. Then I used a backtracker (using Knuth's Dancing Links) to reduce the set to puzzles with only a single solution. The last solver was a "human" solver that used various known strategies; this let me grade difficulty without having to manually attempt every puzzle (although I still found it useful in my app UI to tag puzzles as being too hard/easy). The human solver is incredibly inefficient, but the one with the most room for growth (new strats, etc).

by Isamu 8y ago

deleted 8y ago

[deleted]

saurabh20n 8y ago

You are absolutely right. Punching "extra holes" in puzzles of certain hardness should make backtracking not as viable. But we'll loose the unique solution property. Might make it more interesting? And maybe even bias it towards human-abilities. I think intuitively we're better at solving when the possibilities are more than 1 (just a conjecture.)

wiredfool 8y ago
My soduku solver from ca~10 years back ran the "hardest" soduku puzzles in < 10 seconds on a netbook atom processor. IIRC, the hardest one that I ever threw at it had 7 levels of backtracking. It's just not that hard of a problem compared to the speed of computers.

daxfohl 8y ago

You can make it harder by using 16x16, 25x25, 36x36 etc boards, and see how fast you can make it. There are lots of known patterns to allow for elimination of options http://www.sudokuwiki.org/Getting_Started http://www.sudokuwiki.org/Getting_Started, of different computation complexity relative to each other, and all faster than regular backtracking. So the goal is to find the order at which to apply them for maximum speed and minimal need to backtrack. You can also try to multithread and use GPU, or FPGA if you're nuts. All that said, it's all still pretty mechanical. So if you're looking for something more inferential, then another game would be better.

LanceH 8y ago

My first attempt did no backtracking at all. It would guess randomly, propagate constraints and continue. If it got stuck, it would just start again. The most it ever took to solve a puzzle was 2100 attempts. Sure it wasn't guaranteed to solve a puzzle in finite time, but it worked well enough for something written during one of those endless big-corp conference calls.

karmakaze 8y ago
Technically, this is backtracking... to move 1.

dahart 8y ago

Yep, backtracking works fine. If you only want the solution, then you don't need complex rules. But, you really want more than just the solution. Check out http://sudokuwiki.com/sudoku.htm http://sudokuwiki.com/sudoku.htm This solver (and the whole site) is the best one I know of, and it will solve a puzzle by using rules in order of difficulty, to guarantee it tries the simple rules you know before resorting to backtracking. The benefits of this are that you can grade the difficulty of a sudoku board. You can also solve a puzzle up to the "crux" and then work on only the hard moves manually. I like doing that so I can skip the hours of boring stuff and practice doing the more tricky inferences. Andrew's site is a window into how big of a rabbit hole Sudoku can be...

akbo 8y ago
If you are interested in grading Sudokus by the difficulty of the human solving techniques required, you might want to check out the following two books: - "Sudoku Programming with C" [https://www.apress.com/de/book/9781484209967 https://www.apress.com/de/book/9781484209967] where a Sudoku solver and grader is implemented. - "A to Z of Sudoku" [https://www.wiley.com/en-us/A+to+Z+of+Sudoku-p-9781847040008 https://www.wiley.com/en-us/A+to+Z+of+Sudoku-p-9781847040008] where many human solving techniques are described and rated by their difficulty.

posterboy 8y ago

this comment made me lose interested, too, even my interest in the article.

pdwetz 8y ago

Backtracking as a strategy definitely seems... underwhelming. But it does have its uses. I wrote a few solvers, and they all served a different purpose. One was based on Norvig's python post on the subject; I used that to generate many puzzles very quickly. Then I used a backtracker (using Knuth's Dancing Links) to reduce the set to puzzles with only a single solution. The last solver was a "human" solver that used various known strategies; this let me grade difficulty without having to manually attempt every puzzle (although I still found it useful in my app UI to tag puzzles as being too hard/easy). The human solver is incredibly inefficient, but the one with the most room for growth (new strats, etc).