« WikiMedia | Main | Who owns God's communications? »

January 23, 2006

Suduku puzzles

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 AM

TechnoratiTags:

Trackback Pings

TrackBack URL for this entry:
http://liferoads.reighley.net/mt/mt-tb.cgi/427.

Comments

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: Site icon Joe [TypeKey Profile Page] 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.)


Remember me?