I'm new, here's an overview of how my solver works...

Tim G

Hello, everyone!

I was introduced to Sudoku this Christmas upon receiving a Sudoku puzzle book by Will Shortz. After solving the first ten or so puzzles by hand, I decided that writing software to do the same thing would be a more fun challenge.

For the first phase, my solver works just the way it is done by hand:

For the whole grid, I made a three-dimensional Boolean array indicating what digits were possible (i.e. not yet eliminated) in each of the 81 cells. To make things easier, I also had a two-dimensional array to keep track of the number of possible digits in each cell. I divided the grid into nine rows, nine columns and nine boxes. Each row, column, and box had a ten element Boolean array (zeroeth element unused) to indicate if a particular digit in that row, column or box had been placed. I also divided the grid into 27 sub-rows and 27 sub-columns. For each sub-row and sub-column, I had two one-dimensional arrays indicating whether a particular digit certainly exists inside (not necessarily placed in a particular cell) or certainly does not exist inside (not necessarily eliminated from a particular cell).

The solver then goes through a cycle of updating until either the puzzle is solved or progress is halted. In the book by Will Shortz, the puzzles were divided into four categories: “Light and Easy”, “Moderate”, “Demanding” and “Beware! Very Challenging”. This first phase of my solver was good enough to solve all of the “Moderate” puzzles and 12 of 25 “Demanding” puzzles.

If the first phase fails to solve the puzzle, my solver enters a “what if” phase. It goes though a cycle of suppositions (assuming a digit for a cell). After each supposition, it proceeds the same way as in phase one, but checks for conflicts. A conflict could be 1) all possible digits are eliminated from a particular cell or 2) more than one of a particular digit exists in a row, column or box). If a contradiction arises, the state of the puzzle is restored with the exception that the supposition is eliminated from the three-dimensional Boolean array. The grid then goes though cycles of updates. Suppositions continue until the puzzle is solved.

This second phase was enough to guarantee the solution of the remaining puzzles in the book. The solver was very fast, taking less than a second to solve any of the puzzles in the book. The book also had bonus “Giant Sudoku” section, which I haven’t tackled yet.

In the near future, I may see if I can generate original Sudoku puzzles.

mugnyte · Posted: Wed Jan 11, 2006 1:31 am Post subject:

Well, having posted my own "hello, i am new here..." msg not too long ago, I say Welcome.

Congrats on getting your solver up and running. If you want to see other solvers out there, you can read posts from many authors here and then click on "website" or "profile" to see their goods. (like my own - shameless plug).

The logic you've built seems to be Trial&Error (TE) as it's referred to here. This is great foundation to start with. I started the same way, and then placed a large amount of code into the "look for a move" routine.

This routine then starts the beginning of all the techniques you can find on the web regarding "elimination logic". Look for ones that generalize all others to save coding time. This forum has several posts with great summaries of all them and their consolidation, I've found.

Have fun!
_________________
thanks

Tim G · Posted: Wed Jan 11, 2006 7:45 pm Post subject: Update!

I just finished performing major surgery on my solver.

On my first attempt, I made the conscious decision not to look online for clues on how to write a solver. I used all the techniques that were outlined in the introduction of the book by Will Shortz. Unfortunately, the book introduced only the very basics of Sudoku solving.

My solver now uses hidden pairs, naked pairs, naked triples and naked quads.

Initial results show that I no longer need to resort to the trial and error phase.

I also made my program object oriented, which should make it easier to ugrade. I made cells, rows, columns, boxes, subrows and subcolumns all objects.

After my Sudoku vocabulary has improved, I will be able to participate in discussions.

mugnyte · Posted: Thu Jan 12, 2006 12:17 am Post subject:

Great. I have a few books by Shortz, the puzzles are fun. However, appealing to geek in me was the expansion of the program to solve/generate ever more difficult or interesting puzzles.

If you look online - especially here - you'll find that the math behind Sudoku can be consolidated into several general routines. For example, all subset elimination and grid analysis can be generalized into a single matrix routine, if you want to align it such.

My program is OO based as well, but i use a single object with collections for thhings like values, marks, notes, locks, etc. Anyway, it all starts so simply and gets big quickly...

Jim
_________________
thanks

mikem · Posted: Sun Feb 26, 2006 6:37 pm Post subject: code

hi tim G,

I'm also new to the forum en to sudoku

I was just wondering if you could make your code available to the forum
for a beter understanding.

sorry for my English (moi speak french)

dfhwze · Posted: Thu Mar 02, 2006 5:46 pm Post subject: Re: Update!

gsf · Posted: Thu Mar 02, 2006 6:59 pm Post subject: Re: Update!

eclark · Posted: Sun Mar 05, 2006 12:18 am Post subject:

Also try some from Henk. His puzzles are becomming very interesting.