Threaded Mode | Linear Mode

Pekis · (This post was last modified: 03-07-2019 07:29 PM by Pekis.)

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

Simone Cerica · 03-07-2019, 03:01 PM

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 ARM-based 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

Pekis · 03-07-2019, 03:55 PM

(03-07-2019 03:01 PM)Simone Cerica Wrote: 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 ARM-based 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

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.

John Keith · 03-07-2019, 04:58 PM

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

Pekis · 03-07-2019, 06:52 PM

(03-07-2019 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" built-in 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.

Pekis · 03-07-2019, 07:28 PM

I forgot to mention the "Algorithm X" own page (see Wikipedia) !

Valentin Albillo · 03-07-2019, 10:47 PM

.
Hi, all

(03-07-2019 02:16 PM)Pekis Wrote: The Sudoku solving algorithms are multiple

I wrote a Sudoku solver for the HP-71B some 11-12 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:

HP-71B Short & Sweet Sudoku Solver

HP-71B Sudoku Solver's Sublime Sequel

Best regards.
V
.

Raymond Del Tondo · 03-08-2019, 10:02 PM

(03-07-2019 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:

HP-71B Short & Sweet Sudoku Solver

HP-71B Sudoku Solver's Sublime Sequel

Best regards.
V
.

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.

ttw · 03-08-2019, 10:17 PM

(03-08-2019 10:02 PM)Raymond Del Tondo Wrote: 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.

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 sub-matrix work) fails when the new item is real. This requires all work to be done in exact integers (though 9-bit numbers are sufficient.) I coded around this but the debugging of type changes got tiresome.

Bill Duncan · 03-09-2019, 02:11 AM

Awesome! I wrote one in AWK about a dozen years or so ago. I was about to write one for the hp-48gx but got sidetracked and never finished it. I was also going to use bitmaps (which I did in the C version).

https://billduncan.org/awk-the-often-ign...-language/

Looking forward to digging into other solutions! As I recall, someone had done one for the HP-41cx which would be interesting..

Raymond Del Tondo · 03-09-2019, 07:49 AM

(03-08-2019 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 sub-matrix work) fails when the new item is real. This requires all work to be done in exact integers (though 9-bit 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 only array is the one the user supplies, either from the stack
or interactively from the MatrixWriter call from within the program.
After input, this array is converted to a flat nibble stream.

As calculations are all done on integers, it's a great savings regarding data size
and data access speed to have the data items as tight together as possible.

The "What you get" part shows some details on the small and fast data access utils.

David Hayden · 03-19-2019, 06:38 PM

(03-07-2019 03:01 PM)Simone Cerica Wrote: 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 ARM-based 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

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

Claudio L. · 03-20-2019, 03:03 AM

(03-08-2019 10:17 PM)ttw Wrote:
(03-08-2019 10:02 PM)Raymond Del Tondo Wrote: 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.

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 sub-matrix work) fails when the new item is real. This requires all work to be done in exact integers (though 9-bit numbers are sufficient.) I coded around this but the debugging of type changes got tiresome.

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.

ttw · 03-20-2019, 03:12 PM

I erased that director but I can show some data structures. I was hoping to use 9x9 binary integer arrays for meta-data and for the board. I could have just made a long 81-long 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.

3298 · 03-20-2019, 08:58 PM

(03-20-2019 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:

\<<

  [ [ 1. 2. 3. ] [ 4. 5. 6. ] [ 7. 8. 9.] ]

  { 2. 1. }

  [ [ 10. 11. ] [ 12. 13. ] ]

  REPL

\>>

results in

Code:

[ [ 1. 2. 3. ] [ 10. 11. 6. ] [ 12. 13. 9. ] ]

... as expected. The dots show that we're clearly working with reals. Firmware version 2.15 here, but that shouldn't matter.

ttw · 03-21-2019, 12:29 AM

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.

3298 · 03-21-2019, 09:17 AM

Looking a bit closer at this:

(03-20-2019 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.

David Hayden · 03-24-2019, 03:11 PM

(03-19-2019 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.

Dave

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.

ttw · 03-27-2019, 01:32 PM

(03-20-2019 08:58 PM)3298 Wrote:
(03-20-2019 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:

\<< [ [ 1. 2. 3. ] [ 4. 5. 6. ] [ 7. 8. 9.] ] { 2. 1. } [ [ 10. 11. ] [ 12. 13. ] ] REPL \>>
results in

Code:

[ [ 1. 2. 3. ] [ 10. 11. 6. ] [ 12. 13. 9. ] ]
... as expected. The dots show that we're clearly working with reals. Firmware version 2.15 here, but that shouldn't matter.

I re-derived 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 B-R 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.