January 23, 2006
I have been playing a lot with the Suduku puzzles lately. In the last few days, I have been considering writing a program to solve the puzzles for me. I feel like I am getting pretty good at them, but I am sure that there are methods that I have not thought of yet.
If I proceduralized the process of solving them into a computer program I think I could experiment to figure out which methods tend to be most effective.
I am thinking I will use bitwise flags to store the possibilities. For a nine by nine suduku, I would use the binary number 0000 0001 1111 1111 to represent a cell that has no possibilities eliminated. Each digit represents a possibility 0000 0000 0000 0001 would mean 1 is the only remaining possiblity, 0000 0000 0000 0010 would be 2, 0000 0001 0000 0000 would be 9. 0000 0001 0001 0000 would represent a cell where 9 and 5 are the only possiblities.
The process would work something like this: I would scan through the grid, and for each known value I found I would turn off the appropriate bit for each of the cells in the same row, column and square.
After all of the eliminations where processed I would scan through the grid again, looking for cells that only have one bit left standing. In each of these I would insert the proper number, then I would run the elimination routine again. This process would repeat until the puzzle is solved.
Once I get this running, I could run different procedures to see which methods work best. I can record the number of steps it takes to solve the puzzles, so I can test the algorithms to see which are most efficient.
Binary is really useful. It is kind of fun to make your brain work that way every once in a while just too feel the millions and millions of synapses that you usually don't use flick on and off.
Sorry to be such a nerd. I tried to talk to my wife about this, but she kinda rolled her eyes at me. I had to explain It is like there are 9 light switches in each cell, and you turn them off when you know that their number is eliminated. I think she might have started to get it. (I am not sure she started to care) ;-)
Posted by reighley at January 23, 2006 04:33 AMTechnoratiTags:
TrackBack URL for this entry:
Yeah, man, you're a nerd. I got excited when I saw the title to your post, but binary's over my head. (I know, how can it be over my head if it's just 0's and 1's?)
I love Sudoko but have yet to attain the level of Grand Master. :^)
Posted by: Joe at January 23, 2006 07:10 AM
Post a comment
Thanks for signing in, . Now you can comment. (sign out)(If you haven't left a comment here before, you may need to be approved by the site owner before your comment will appear. Until then, it won't appear on the entry. Thanks for waiting.)