Sudoku

[Les Hammer]

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, leavingthe 0's in the places where the puzzle has blanks.  Click the run arrow to findthe solution.
 
Theory of operation:
Each cell is given a hexidecimal code.  If the cell value is known then the codeis simply the U16 for that number (0x0001 to 0x0009).  If unknown (initially 0in the array) it is coded with 0x7FC0 - one bit for each possible value, with0x0040 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 foundin 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 withthe value 1 through 9.  The array is then rescanned to see if any more cells havehad 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 hexidecimalvalue of only 2 bits.  Since those 2 bits must be in one or the other of thosetwo 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 forsingle bits.
If no more single bits or two of 2 bit values are found, the vi then goes into aguessing mode.  The 9x9 array of values is saved.  A cell with more than onebit 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 nextbit.  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 selectedfor the guessing game.  The process is continued until all cells have values inthe 1 - 9 range.
Les HammerSmart Sensor Systems<a href="mailto:***@SmartSensorSystems.com" target="_blank">***@SmartSensorSystems.com</a>


Sudoku.vi:
http://forums.ni.com/attachments/ni/170/153770/1/Sudoku.vi

[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&nbsp;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&nbsp;could find for these&nbsp;is <a href="http://www.djape.net/sudoku/wp/?page_id=38" target="_blank">here</a>. 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 <a href="http://www.maa.org/editorial/mathgames/mathgames_09_05_05.html" target="_blank">here</a>, 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.


Killer.llb:
http://forums.ni.com/attachments/ni/170/153794/1/Killer.llb

[Les Hammer]

&gt; 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.
&nbsp;
Attached.&nbsp; Now all you have to do is save it with&nbsp;LabVIEW run-time and enjoy the cookies or chocolate cake.&nbsp; :-)
&nbsp;
--Les


Sudoku_7.vi:
http://forums.ni.com/attachments/ni/170/153859/1/Sudoku_7.vi

[Sheldon Stokes]

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

&nbsp;

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

&nbsp;
I wrote it to wring out my algorithm, rather than as a finished application. &nbsp;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.&nbsp; I have been using websudoku but with only one per page, it?s a pain to print out, and a waste of paper.&nbsp;
&nbsp;
Sheldon

[jdebuhr]

Sheldon Stokes wrote:

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

&nbsp;

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

&nbsp;
I wrote it to wring out my algorithm, rather than as a finished application. &nbsp;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.&nbsp; I have been using websudoku but with only one per page, it?s a pain to print out, and a waste of paper.&nbsp;
&nbsp;
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,
Your program didn't work for me.&nbsp; It immediately filled in the grid without any opportunity to plant the seeds first.&nbsp; 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.&nbsp; You don't have to be a member or log in to use it.
<a href="http://www.uclick.com/client/aap/sudoc/" target="_blank">http://www.uclick.com/client/aap/sudoc/</a>
BTW, I&nbsp;agree that there's no point in using a program to solve the puzzle, but it&nbsp;sure is a nice challenge.
&nbsp;
Mcsynth

[Les Hammer]

&gt; Your program didn't work for me.&nbsp; 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.&nbsp; When the program is started it immediately does a "solve."&nbsp; And it solves a completely blank (all zero) problem with the first solution that fits.
&gt;&nbsp; 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.&nbsp; Originally I had all the cells at the default - left justified.&nbsp; That let me "easily" enter the numbers, but didn't present a good looking display.&nbsp; So I switched the cells to "center justify."&nbsp; 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.&nbsp; (Maybe this is a Windows problem.).
~~Les

[mcsynth]

Les,
This weekend I wrote a helper application for Sudoku puzzles (LV 7.1).&nbsp; It doesn't fully solve the puzzle, but it keeps track of the remaining possibilities in each cell.&nbsp; 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.&nbsp; I would only use it to help break a deadlock.
It is not complete, and requires a few more hours to clean it up.&nbsp; First off, after you must&nbsp;key in&nbsp;each number, you must click OUTSIDE the table.&nbsp; 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.&nbsp; 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.&nbsp; 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
&nbsp;


SUDOKU Helper.llb:
http://forums.ni.com/attachments/ni/170/156474/1/SUDOKU Helper.llb

[Les Hammer]

&gt; It doesn't fully solve the puzzle, but it keeps track of the remaining possibilities in each cell.
That looks good.
&gt;&nbsp;but if the puzzle is tough, the VI will still allow you to make most of the choices yourself.&nbsp;
I haven't looked at the details of your solution, but it would be good to have a "go back" capability.&nbsp; That is, have some buttons for "Save 1", "Recall 1", "Save 2", "Recall 2" ...&nbsp; That way if you make a bad choice you don't have to start from scratch.
&gt;&nbsp;I would only use it to help break a deadlock.
Yes -- helps keep the puzzle a puzzle.&nbsp; My solver zips through and solves the puzzle in a matter of seconds -- the only challange was in writing the solver and seeing how quickly I could get it to solve.&nbsp; There's no challange in the puzzle itself since the program does it all.&nbsp; Your program does the tedious stuff while letting the user still have the challange.&nbsp; Good work!
&gt; 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.&nbsp; I also need to change the color scheme to make the grids more defined.
Some other solutions alternate the 3x3 blocks into yellow/grey.&nbsp; It would be good if you can easily correct bad seeds.&nbsp; That is "oops, I put the 3 in cell 6E instead of 7E.&nbsp; How do I clear 6E?"
&nbsp;
~~Les
&nbsp;

[mcsynth]

Les,

It seems as there are some major weak points in my code.&nbsp; It will
take a major re-write to fix, but I won't have time until after
Christmas.&nbsp; It only take a couple of wrong guesses to get
hopelessly scrambled.

It all seems to do with the progressive nature of eliminating possible
numbers from each square.&nbsp; I think that each time a number is
entered, I will need to re-calculate the entire block, row or column
from scratch, rather than sucessively eliminating numbers based only on
the current entry.

Thanks for the yellow/gray block color scheme suggestion.&nbsp; It works much better.

Happy Holidays,
Mcsynth

[mcsynth]

Les,
As promised, I worked on the Sudoku Helper over the holidays, and I think it's complete.&nbsp; There is a Game folder and each game is given a timestamped&nbsp;folder to save game files.&nbsp; You can also&nbsp;and reload intermediate values as you play.&nbsp; It automatically saves the clues when you press the seed button and saves the solution when the puzzle is solved.&nbsp;
I worked out the number logic to make it foolproof, as near as I can tell.&nbsp; Please let me know what you think.
Happy New Year,
Mcsynth


Sudoku.zip:
http://forums.ni.com/attachments/ni/170/158971/1/Sudoku.zip

[Les Hammer]

Good Job.&nbsp;
~~Les

[jdebuhr]

Albert Geven wrote:

Hi
It is easy to get that functionality. Create a property node for "Remain" (this shows the numbers possible for that field).
next step crate a boolean, I always use the classic dialog checkbox withoutt showing the boolean text.
Place this boolean checkbox in a new event frame that handles the change value events of this boolean,and connect the output of this boolean to the property node of Remain.As an extra you could make Remain invisible at startup.
succes

YEp I added the Boolean to the version I downloaded.. it is very cool and well designed, Now I just need to try out some puzzles, although I hear that Sudoku is rather addicting

[Les Hammer]

&gt; Now I just need to try out some puzzles, although I hear that Sudoku is rather addicting
&nbsp;
It is, until you write a program that solves them in seconds.&nbsp; :-(
What's interresting is the difference between puzzles that the book says are difficult, and the ones that my program has to take multiple guesses on.
&nbsp;
~~Les Hammer

[mcsynth]

jdebuhr
&nbsp;
That was a great suggestion about being able to hide the clues.&nbsp; That way you can only use the clues when you really feel stuck.&nbsp; It only took a couple of minutes to&nbsp;implemented, and it puts some of the challange back into the game.

Thanks,
McSynth

[jdebuhr]

No problem, Like I said it is a cool program you have there. I am going to build into an app and install it on my Fathers PC, he does those puzzles and this way if he really gets stuck, he can try out the helper.


mcsynth wrote:
jdebuhr
&nbsp;
That was a great suggestion about being able to hide the clues.&nbsp; That way you can only use the clues when you really feel stuck.&nbsp; It only took a couple of minutes to&nbsp;implemented, and it puts some of the challange back into the game.

Thanks,
McSynth

[mcsynth]

Les
&gt;I haven't looked at the details of your solution, but it would be good to have a "go back" capability.&nbsp; That is, have some buttons for "Save 1", "Recall 1", "Save 2", "Recall 2" ...&nbsp; That way if you make a bad choice you don't have to start from scratch.
That's where the import/export feature will come in handy (If I have enough ambition to write it someday).
&gt;Some other solutions alternate the 3x3 blocks into yellow/grey.&nbsp; It would be good if you can easily correct bad seeds.&nbsp; That is "oops, I put the 3 in cell 6E instead of 7E.&nbsp; How do I clear 6E?"
If you click the "Seeded" button back to False, you can then put in the correct seed, then click back to True.&nbsp; Undoing the incorrect seed usually works, but it's not foolproof.&nbsp; It&nbsp;sometimes requires a bit of trickery (man vs. machine), but I'll see if I can nail that down better.
~~Mcsynth

[Albert Geven]

Compliments for the implementation and the programming style.
Albert