Sudoku solver

03072019, 02:16 PM
(This post was last modified: 03072019 07:29 PM by Pekis.)
Post: #1




Sudoku solver
The Sudoku solving algorithms are multiple (see Wikipedia) but the most fascinating for me is the one invented by Donald Knuth ("Algorithm X" (see Wikipedia)), with the Sudoku constraints fitted into an Exact cover problem (see Wikipedia).
After creating a big 729 (candidates) x 324 (constraints) sparse matrix and reducing it to a small data structure of linked nodes, that simple algorithm leads to an answer after a fraction of a second, much faster than a naive backtracking algorithm ! Do you think it could be programmable on an HP calc ? Anyway, I made a simple and not recursive Android Java version (check the Solver class and the SatsNodesHandler class). Best regards 

03072019, 03:01 PM
Post: #2




RE: Sudoku solver
Sudoku Solver by David Hayden:
"Sudoku solver written in User RPL, C, and C++. Solves any sudoku with 1 solution in less than 3 seconds on a 50g. Requires a 49g+ or 50g (or other ARMbased model). Includes full source code. Many thanks to Tony Hutchins and his "SUDOKU for the 49g+" for inspiring this program." https://www.hpcalc.org/details/7062 

03072019, 03:55 PM
Post: #3




RE: Sudoku solver
(03072019 03:01 PM)Simone Cerica Wrote: Sudoku Solver by David Hayden: Thanks for this but it looks like he didn't implement the "Algorithm X", according to the included notes. I was wondering if that program quickly displays "No solution" for this useless grid (the naive backtracking algorithm I tried initially was running forever): ....1.... ....2.... ....3.... ......... 123456789 ......... ....7.... ....8.... ....9.... Thanks. 

03072019, 04:58 PM
Post: #4




RE: Sudoku solver
This Wikipedia page covers the modern implementation of "Algorithm X", called "dancing links".


03072019, 06:52 PM
Post: #5




RE: Sudoku solver
(03072019 04:58 PM)John Keith Wrote: This Wikipedia page covers the modern implementation of "Algorithm X", called "dancing links". The "dancing links" implementation seems to me too tricky as the "algorithm X" builtin backtracking already implies a lot of unlink and relink operations between nodes to cover or uncover the same rows and columns in the way. That's why I preferred implementing links, but with a simpler rows and columns handling. 

03072019, 07:28 PM
Post: #6




RE: Sudoku solver
I forgot to mention the "Algorithm X" own page (see Wikipedia) !


03072019, 10:47 PM
Post: #7




RE: Sudoku solver
.
Hi, all (03072019 02:16 PM)Pekis Wrote: The Sudoku solving algorithms are multiple I wrote a Sudoku solver for the HP71B some 1112 years ago (shortly after sudoku puzzles began to appear in some UK publications), which could completely solve many sudokus using just boolean operations on bitmaps without needing recursion most of the time, though recursion would be used if needed to complete the remaining locations after the bitmap operations filled in as many locations as possible. I think I remember that after its publication it did inspire someone to create a RPL version initially based on it, probably for the 48/49g. You can download the full PDF articles (with source code, theory of bitmaps' use, and documentation including many examples with timings) using these links: HP71B Short & Sweet Sudoku Solver HP71B Sudoku Solver's Sublime Sequel Best regards. V . All My Articles & other Materials here: Valentin Albillo's HP Collection 

03082019, 10:02 PM
Post: #8




RE: Sudoku solver
(03072019 10:47 PM)Valentin Albillo Wrote: I think I remember that after its publication it did inspire someone to create a RPL version initially based on it, probably for the 48/49g. You can download the full PDF articles (with source code, theory of bitmaps' use, and documentation including many examples with timings) using these links:One of the "someone"s was me. The 71B version inspired me to develop my own SDK solver: My SuDoKu Solver Be sure to read the SDK48.txt . The run times are in seconds, not minutes;) There were some people developing SDK solvers for different platforms back then, at least one in User RPL for the 49g, and another in RPL for the HP 48 Series. However they all had the same restriction: Slow data handling using matrices or lists.  Ray 

03082019, 10:17 PM
Post: #9




RE: Sudoku solver
(03082019 10:02 PM)Raymond Del Tondo Wrote: There were some people developing SDK solvers for different platforms back then, I setup the structures for one last week. It wasn't the slowness so much but incompatibilities of data types on the HP50g. (Earlier releases didn't seem to have some of these problems though.) First, binary integers cannot be in matrices necessitating lots of conversions in and out. Second, REPL (needed for easy submatrix work) fails when the new item is real. This requires all work to be done in exact integers (though 9bit numbers are sufficient.) I coded around this but the debugging of type changes got tiresome. 

03092019, 02:11 AM
Post: #10




RE: Sudoku solver
Awesome! I wrote one in AWK about a dozen years or so ago. I was about to write one for the hp48gx but got sidetracked and never finished it. I was also going to use bitmaps (which I did in the C version).
https://billduncan.org/awktheoftenign...language/ Looking forward to digging into other solutions! As I recall, someone had done one for the HP41cx which would be interesting.. 

03092019, 07:49 AM
Post: #11




RE: Sudoku solver
(03082019 10:17 PM)ttw Wrote: I setup the structures for one last week. It wasn't the slowness so much but incompatibilities of data types on the HP50g. (Earlier releases didn't seem to have some of these problems though.) First, binary integers cannot be in matrices necessitating lots of conversions in and out. Second, REPL (needed for easy submatrix work) fails when the new item is real. This requires all work to be done in exact integers (though 9bit numbers are sufficient.) I coded around this but the debugging of type changes got tiresome.About data management, please take a look at the "Some Technical Info" and "What you get" parts of SDK48.txt . Here's an excerpt;) Quote:Internally, there are no arrays used in SDK48 for speed and size reasons.The "What you get" part shows some details on the small and fast data access utils.  Ray 

03192019, 06:38 PM
Post: #12




RE: Sudoku solver
(03072019 03:01 PM)Simone Cerica Wrote: Sudoku Solver by David Hayden:3 seconds? I think I got it down to 0.25s after using C code to handle the input/output array directly. I'll check when I get home. I'll check the "no solution" case also. Dave 

03202019, 03:03 AM
Post: #13




RE: Sudoku solver
(03082019 10:17 PM)ttw Wrote:(03082019 10:02 PM)Raymond Del Tondo Wrote: There were some people developing SDK solvers for different platforms back then, If you care to share your code, I'd like to give RPL machines a second chance. All the shortcomings mentioned above are vastly improved or eliminated in newRPL, so I'm curious if I can remove all your workarounds and have a clean algorithm written in RPL. Also, to check how slow or fast it actually is. 

03202019, 03:12 PM
Post: #14




RE: Sudoku solver
I erased that director but I can show some data structures. I was hoping to use 9x9 binary integer arrays for metadata and for the board. I could have just made a long 81long array (or even numbers s00 to s88 or s11 to s19 and unroll all loops; that would be fast but tedious). Then the access would have used ROW and ROW+ and COL and COL+ to access rows and columns. To access squares, I used i,j i+2,j+2 SUB to get things and i,j REPL to put things back. Unfortunately, arrays do not support either integers or binary integers and REPL does not work with reals.
In Fortran (if I get interested enough to program on the PC), I would use integer types where the logical operators are defined as masks. In either case, I used the numbers 2,4,8,16,32,64,128,256,512 to represent numbers allowed (or denied; one can complement to get the other). Array (or list) logical operations let one remove possibilities by marking (or erasing) rows, column, and squares. It would be possible (in one of the languages I invented but didn't completely implement) would have objects (I called them "maps") that would be the union of the rows, columns, and squares "seen" by each entry. Few languages allow such structures to be implemented efficiently. I didn't use the brute force stuff (so far) as I wanted to check puzzles against various strategies suggested in the literature. The idea is to call a puzzle difficult if it needs several advanced strategies and insane if it requires a search. In practice, the 9x9 system is small; the "hardness" of Sudoku relates to what happens with 16x16,25x25, etc., puzzles. 

03202019, 08:58 PM
Post: #15




RE: Sudoku solver
(03202019 03:12 PM)ttw Wrote: Unfortunately, [...] REPL does not work with reals.You've made that claim earlier, but I don't believe it. In fact, I just tried it and had no such problem. Code: \<< Code: [ [ 1. 2. 3. ] [ 10. 11. 6. ] [ 12. 13. 9. ] ] 

03212019, 12:29 AM
Post: #16




RE: Sudoku solver
You're right. It seems to work here. I don't know why my particular case failed. Perhaps I should recreate the whole thing (this time in reals) and see what happens (I can do this in a couple of evenings.) All I lack are the logicals however I many be able to get around this.
I used the exact test that you posted and couldn't things to work on two different calculators (it worked on a third with older CAS). Now I have to see where I either tested wrongly or what conditions caused the failure. Just this alone reduces my code length about 1/3 for inner loops. I did have the word size at 9 bits but that seems OK now. Thanks. 

03212019, 09:17 AM
Post: #17




RE: Sudoku solver
Looking a bit closer at this:
(03202019 03:12 PM)ttw Wrote: To access squares, I used i,j i+2,j+2 SUB to get things and i,j REPL to put things back.... suggests you might have had your parameter order wrong in that test. REPL wants the position on level 2, so a SWAP between the i,j and REPL is in order (i,j SWAP REPL). I know it's inconsistent with PUT, STO, UNPICK and so on (those want it on level 1), so it's easy to get confused. 

03242019, 03:11 PM
Post: #18




RE: Sudoku solver
(03192019 06:38 PM)David Hayden Wrote: 3 seconds? I think I got it down to 0.25s after using C code to handle the input/output array directly. I'll check when I get home. I'll check the "no solution" case also.It looks like 3 seconds is accurate. The "no solution" case posted above crashes the calculator. I suspect it runs out of C stack space. 

03272019, 01:32 PM
Post: #19




RE: Sudoku solver
(03202019 08:58 PM)3298 Wrote:(03202019 03:12 PM)ttw Wrote: Unfortunately, [...] REPL does not work with reals.You've made that claim earlier, but I don't believe it. In fact, I just tried it and had no such problem. I rederived my code and now I know why I got the failures. One must do something like generate {# 1010b # 1011b #1100b # 1101b} through computation (direct entry doesn't cause failure) then: B>R EVAL {2 2} >ARRAY REPL Then one gets the failure. I fixed it by doing R>I after the BR then 1.0 * just before REPL. R>I followed by I>R didn't work. It seems that in some cases, logic operations followed by conversion to real doesn't get the type changed quickly. Just typing numbers into the calculator works, but programming fails. I'll post the whole code later. I only need it at one place (putting logical stuff into an array) so it's not too bad. 

« Next Oldest  Next Newest »

User(s) browsing this thread: 1 Guest(s)