Here's escargot, almost solved. We have three unsolved cells and two and six are the only remaining numbers. I've color coded the unsolved cells. Now as I described before here, we can visualize the process of filling in all the remaining cells as a huge directed graph leading us to the final state, where the entire puzzle is solved. So I've done that and attached that image here.

So the idea is that the black circle at the top represents our initial state. Green represents a state where we fill in the green square, red the red square and blue the blue square. The arrow mentions what number we use. The exception to the color rule is the final black square. Depending on which route we take to get there it would have a different color obviously. But thats the state when the puzzle is complete. As discussed previously, there are multiple routes to get from the beginning to the end. Now here's a very simple puzzle where the green square starts off with 2 options and the other squares one option each. This is what the older solver does.

We pick the first cell to play, which is the green square and play two. We reach a dead end, so then we play six. Once we do that the other cells fall into play. Now if we try the newer approach and first play the most constrained cell, it looks like this

So the human tendency to play the cell with the least options first, essentially converts that really complicated graph to a tree with far FEWER branches than if we had played the first cell that was free every turn. As an added bonus, checking for the constraints of every cell each turn is bound to also help detect dead ends or bad branches early. Now in this case we saw one cell with 2 options and the other cells with 1 option. In a complete game the variation is far greater. So let's modify the solver and see how it does.

*Solved hard with 83 moves and 29 rollbacks in 0.098862 secondsSolved evil with 217 moves and 161 rollbacks in 0.249229 secondsSolved escargot with 217 moves and 159 rollbacks in 0.250393 secondsSolved simple with 45 moves and 0 rollbacks in 0.040218 secondsSolved other_hard with 69 moves and 8 rollbacks in 0.106688 secondsAnalyzer::LeastChoicesFirst ran 5 puzzles in 0.745781 seconds with 631 moves and 357 rollbacks*

That's a fantastic improvement. The number of moves has come down to 631 from 36,000. And the time has come down to 0.74 seconds.Which is about nearly 1/10th of the original. Great success! There's more to come though.

Here's the code

class LeastChoicesFirst < analyzer="nil)" cells_with_values =" game.empty_cells.sort.collect{|cell|" possible_values =" cells_with_values.min{|pair_1,"> pair_2[1].length}

end

end

Neat algorithmic stuff. I couldn't be bothered to be clever so I just did a boring brute-force with backtracking recursive implementation in C to solve Sudoku puzzles.

ReplyDeleteThe possibly interesting part is that I used my Sudoku solver to generate Sudoku solutions (by solving an empty board). The resulting Sudoku solution boards were then used to generate Sudoku puzzles for my web implementation at http://this1that1whatever.com/miscellany/sudoku/.

it is amazing how a Sudoku-Lover can turn into a Sudoku-Loather

ReplyDeleteSome guys warned me to don't attempt escargot...

Now I hate sudokus....

I saw tutorials of Advanced techniques and I found out that I knew nothing... And I now hate myself and sudoks...

F***** the people that created sudokus!