Sudoku
in [LabView]
|
From: Les Hammer on 27 Nov 2005 16:10 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:Les.Hammer(a)SmartSensorSystems.com" target="_blank">Les.Hammer(a)SmartSensorSystems.com</a> Sudoku.vi: http://forums.ni.com/attachments/ni/170/153770/1/Sudoku.vi
From: tst on 28 Nov 2005 04:40 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 <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
From: Les Hammer on 28 Nov 2005 11:10 > 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 Sudoku_7.vi: http://forums.ni.com/attachments/ni/170/153859/1/Sudoku_7.vi
From: Sheldon Stokes on 28 Nov 2005 11:40 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
From: mcsynth on 5 Dec 2005 10:40
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. <a href="http://www.uclick.com/client/aap/sudoc/" target="_blank">http://www.uclick.com/client/aap/sudoc/</a> BTW, I agree that there's no point in using a program to solve the puzzle, but it sure is a nice challenge. Mcsynth |