Sudoku

[LesHammer]

I have written a vi that solves the Sudoku number puzzle.  I'm looking for

suggestions for improvement and/or Sudoku fans who have hard to solve

puzzles to check out the operation.

To use the vi fill in the known values, leaving
the 0's in the places where the puzzle has blanks.  Click the run arrow to find
the solution.

Theory of operation:

Each cell is given a hexidecimal code.  If the cell value is known then the code
is simply the U16 for that number (0x0001 to 0x0009).  If unknown (initially 0
in the array) it is coded with 0x7FC0 - one bit for each possible value, with
0x0040 representing that the cell could be a "1", 0x0080 representing "2",
... through 0x4000 representing that the cell could be a "9."

First the array is scanned.  If a single bit (with a value greater than 9) is found
in a cell, then that bit is removed as a possibility for all other cells in that row,
column and 3x3 group of cells.  The cell with the single bit is then recoded with
the value 1 through 9.  The array is then rescanned to see if any more cells have
had all but one bit removed.

If no more cells with single bits are found, the array is searched for a row,
column or 3x3 group of cells in which two cells have the same hexidecimal
value of only 2 bits.  Since those 2 bits must be in one or the other of those
two cells, those bits are removed as possibilities for other cells in that row,
column or 3x3 group of cells.  Then it goes back to the step of looking for
single bits.

If no more single bits or two of 2 bit values are found, the vi then goes into a
guessing mode.  The 9x9 array of values is saved.  A cell with more than one
bit is found.  One of the bits is selected, and the program continues with the
"looking for single bits" mode.  If this track leads to a 0 in a cell the guess
was bad.  The program goes back to the saved array and guesses the next
bit.  If this leads to again having no more single bits or two of 2 bit values
found, then a second level of array saving is done and another cell is selected
for the guessing game.  The process is continued until all cells have values in
the 1 - 9 range.

Les Hammer
Smart Sensor Systems
Les.Hammer@SmartSensorSystems.com

[tst]

I gave up on trying to follow the code about 15 seconds after I first looked at it, so I can't comment on it. You should clean it up and create subVIs if you want to be able to read it yourself in the future. Personally, I don't really like sudoku solvers, because "what's the point?". I mean, the fun is solving puzzles yourself, not having the computer do it for you. I have written a VI which helps in the technical side of solving a sudoku puzzle (i.e. doing it on a screen instead of on paper, and checking it in the end to make sure you didn't make a mistake), but I have also grown tired of it several months ago.

Recently, I've been playing the so-called Killer Sudoku, which is more fun, and I wrote a VI to help me there as well (once again, it doesn't answer anything, but just makes it technically easier). The only regular source I could find for these is here. Once you've mastered it a bit, try the link on the right for the september 27 puzzle. That one which should take you a while. Other sudoko variants can be found here, and it's fun figuring out different techniques for the various puzzles.

I made some quick modifications to the VI I mentioned and I'm attaching it (7.0). I use it to solve the killers that come from the site I linked to to. It has an invisible array that allows writing directly into the image of the puzzle and a temporary array for optional numbers. I also added a tester VI, but I haven't checked it.

[falkpl]

Can you post it for lv 7.0, My mom is addicted to sodoku and I promised he I would write a solver for her, this could save me some time.

[LesHammer]

> Can you post it for lv 7.0, My mom is addicted to sodoku and I promised he I would write a solver for her, this could save me some time.

Attached.  Now all you have to do is save it with LabVIEW run-time and enjoy the cookies or chocolate cake.  🙂

--Les

[Sheldon_Stokes]

I wrote a SuDoku solver this weekend, not specifically to solve them, but to generate new ones.  The first step in generating a puzzle is to fill in the board which is really a “solving” operation.  Then the program removes most of the solved cells and presents it to the user.  I use a tabbed interface with the solution hidden on another tab. 

I have two subVI’s and it’s quite readable.  I can post it when I return from a business trip if there is interest.

I wrote it to wring out my algorithm, rather than as a finished application.  I’m now porting my code to objective-c for a Cocoa Mac OS X application that prints puzzles MxN on a page to be solved.  I have been using websudoku but with only one per page, it’s a pain to print out, and a waste of paper. 

Sheldon

[falkpl]

Thanks

[mcsynth]

Les,

Your program didn't work for me.  It immediately filled in the grid without any opportunity to plant the seeds first.  I also tried seeding the numbers before running the VI, but it kept changing my inputs back to zeros.

There is a good on-screen version at the AARP site.  You don't have to be a member or log in to use it.

http://www.uclick.com/client/aap/sudoc/

BTW, I agree that there's no point in using a program to solve the puzzle, but it sure is a nice challenge.

Mcsynth

[LesHammer]

> Your program didn't work for me.  It immediately filled in the grid without any opportunity to plant the seeds first.

Yes, you must plant the seeds first, then hit the "run" button.  When the program is started it immediately does a "solve."  And it solves a completely blank (all zero) problem with the first solution that fits.

>  I also tried seeding the numbers before running the VI, but it kept changing my inputs back to zeros.

I've noticed that with LabVIEW.  Originally I had all the cells at the default - left justified.  That let me "easily" enter the numbers, but didn't present a good looking display.  So I switched the cells to "center justify."  That makes the display look better, but then LabVIEW insists that you highlight the number and all of the display to the left of it in order to change the number.  (Maybe this is a Windows problem.).

~~Les

[jdebuhr]

---

@sheldon Stokes wrote:

I wrote a SuDoku solver this weekend, not specifically to solve them, but to generate new ones.  The first step in generating a puzzle is to fill in the board which is really a “solving” operation.  Then the program removes most of the solved cells and presents it to the user.  I use a tabbed interface with the solution hidden on another tab. 

I have two subVI’s and it’s quite readable.  I can post it when I return from a business trip if there is interest.

I wrote it to wring out my algorithm, rather than as a finished application.  I’m now porting my code to objective-c for a Cocoa Mac OS X application that prints puzzles MxN on a page to be solved.  I have been using websudoku but with only one per page, it’s a pain to print out, and a waste of paper. 

Sheldon

---

Sheldon,

If you could post the subVIs that would be great, I have a co-worker that is hooked on doing them and this way he could generator new ones.

thanks

Jeff

[mcsynth]

Les,

This weekend I wrote a helper application for Sudoku puzzles (LV 7.1).  It doesn't fully solve the puzzle, but it keeps track of the remaining possibilities in each cell.  It the puzzle is easy, it pretty much solves it for you, but if the puzzle is tough, the VI will still allow you to make most of the choices yourself.  I would only use it to help break a deadlock.

It is not complete, and requires a few more hours to clean it up.  First off, after you must key in each number, you must click OUTSIDE the table.  If you click in another cell, the current Edit Position property will be wrong.

Once you have entered all the clues (I call them "seeds"), click the "Seeded" button.  This changes the color of the entry blocks, blue for seeds and yellow for guesses.

It can still have a little trouble with changing your guess after a number has been entered, especially going from a number back to a blank, but it's almost there.  I also need to change the color scheme to make the grids more defined.

I'd also like to put some import/export capabilities in it to save partial solutions for later retrieval.

Mcsynth