Re: [Bug-apl] Quad-DLX implementation of Sudoku soon

[Juergen Sauermann]

Hi Xtian,

not sure what happens on your side, but my machine finds 309 solutions of your sudoku below
in less than a second:

      ⎕←T1←⎕TS
2016 12 2 19 29 59 744
            solve_sudoku sudoku_Xtian
 21  digits pre-placed
 Number of solutions:  309
first solution:
 ╔═══╤═══╤═══╦═══╤═══╤═══╦═══╤═══╤═══╗  ╔═══╤═══╤═══╦═══╤═══╤═══╦═══╤═══╤═══╗
 ║ 4 │   │ 5 ║   │   │ 2 ║   │ 7 │ 1 ║  ║ 4 │ 6 │ 5 ║ 3 │ 8 │ 2 ║ 9 │ 7 │ 1 ║
 ╟───┼───┼───╫───┼───┼───╫───┼───┼───╢  ╟───┼───┼───╫───┼───┼───╫───┼───┼───╢
 ║   │   │   ║   │   │   ║   │   │   ║  ║ 1 │ 2 │ 7 ║ 6 │ 5 │ 9 ║ 4 │ 3 │ 8 ║
 ╟───┼───┼───╫───┼───┼───╫───┼───┼───╢  ╟───┼───┼───╫───┼───┼───╫───┼───┼───╢
 ║   │   │ 9 ║   │ 4 │   ║   │   │ 6 ║  ║ 3 │ 8 │ 9 ║ 1 │ 4 │ 7 ║ 2 │ 5 │ 6 ║
 ╠═══╪═══╪═══╬═══╪═══╪═══╬═══╪═══╪═══╣  ╠═══╪═══╪═══╬═══╪═══╪═══╬═══╪═══╪═══╣
 ║   │   │   ║ 9 │   │   ║ 8 │   │   ║  ║ 2 │ 5 │ 6 ║ 9 │ 3 │ 4 ║ 8 │ 1 │ 7 ║
 ╟───┼───┼───╫───┼───┼───╫───┼───┼───╢  ╟───┼───┼───╫───┼───┼───╫───┼───┼───╢
 ║   │ 3 │   ║   │   │ 6 ║   │ 4 │   ║  ║ 8 │ 3 │ 1 ║ 2 │ 7 │ 6 ║ 5 │ 4 │ 9 ║
 ╟───┼───┼───╫───┼───┼───╫───┼───┼───╢  ╟───┼───┼───╫───┼───┼───╫───┼───┼───╢
 ║   │   │   ║   │   │   ║ 3 │   │   ║  ║ 7 │ 9 │ 4 ║ 5 │ 1 │ 8 ║ 3 │ 6 │ 2 ║
 ╠═══╪═══╪═══╬═══╪═══╪═══╬═══╪═══╪═══╣  ╠═══╪═══╪═══╬═══╪═══╪═══╬═══╪═══╪═══╣
 ║   │ 1 │   ║   │ 6 │   ║   │ 8 │   ║  ║ 9 │ 1 │ 2 ║ 4 │ 6 │ 3 ║ 7 │ 8 │ 5 ║
 ╟───┼───┼───╫───┼───┼───╫───┼───┼───╢  ╟───┼───┼───╫───┼───┼───╫───┼───┼───╢
 ║   │ 7 │   ║   │ 2 │ 1 ║   │   │   ║  ║ 5 │ 7 │ 3 ║ 8 │ 2 │ 1 ║ 6 │ 9 │ 4 ║
 ╟───┼───┼───╫───┼───┼───╫───┼───┼───╢  ╟───┼───┼───╫───┼───┼───╫───┼───┼───╢
 ║   │   │ 8 ║   │   │   ║   │   │   ║  ║ 6 │ 4 │ 8 ║ 7 │ 9 │ 5 ║ 1 │ 2 │ 3 ║
 ╚═══╧═══╧═══╩═══╧═══╧═══╩═══╧═══╧═══╝  ╚═══╧═══╧═══╩═══╧═══╧═══╩═══╧═══╧═══╝
last solution:
 ╔═══╤═══╤═══╦═══╤═══╤═══╦═══╤═══╤═══╗  ╔═══╤═══╤═══╦═══╤═══╤═══╦═══╤═══╤═══╗
 ║ 4 │   │ 5 ║   │   │ 2 ║   │ 7 │ 1 ║  ║ 4 │ 8 │ 5 ║ 6 │ 3 │ 2 ║ 9 │ 7 │ 1 ║
 ╟───┼───┼───╫───┼───┼───╫───┼───┼───╢  ╟───┼───┼───╫───┼───┼───╫───┼───┼───╢
 ║   │   │   ║   │   │   ║   │   │   ║  ║ 3 │ 6 │ 1 ║ 7 │ 9 │ 5 ║ 4 │ 2 │ 8 ║
 ╟───┼───┼───╫───┼───┼───╫───┼───┼───╢  ╟───┼───┼───╫───┼───┼───╫───┼───┼───╢
 ║   │   │ 9 ║   │ 4 │   ║   │   │ 6 ║  ║ 7 │ 2 │ 9 ║ 1 │ 4 │ 8 ║ 5 │ 3 │ 6 ║
 ╠═══╪═══╪═══╬═══╪═══╪═══╬═══╪═══╪═══╣  ╠═══╪═══╪═══╬═══╪═══╪═══╬═══╪═══╪═══╣
 ║   │   │   ║ 9 │   │   ║ 8 │   │   ║  ║ 2 │ 5 │ 4 ║ 9 │ 1 │ 3 ║ 8 │ 6 │ 7 ║
 ╟───┼───┼───╫───┼───┼───╫───┼───┼───╢  ╟───┼───┼───╫───┼───┼───╫───┼───┼───╢
 ║   │ 3 │   ║   │   │ 6 ║   │ 4 │   ║  ║ 8 │ 3 │ 7 ║ 2 │ 5 │ 6 ║ 1 │ 4 │ 9 ║
 ╟───┼───┼───╫───┼───┼───╫───┼───┼───╢  ╟───┼───┼───╫───┼───┼───╫───┼───┼───╢
 ║   │   │   ║   │   │   ║ 3 │   │   ║  ║ 1 │ 9 │ 6 ║ 4 │ 8 │ 7 ║ 3 │ 5 │ 2 ║
 ╠═══╪═══╪═══╬═══╪═══╪═══╬═══╪═══╪═══╣  ╠═══╪═══╪═══╬═══╪═══╪═══╬═══╪═══╪═══╣
 ║   │ 1 │   ║   │ 6 │   ║   │ 8 │   ║  ║ 9 │ 1 │ 2 ║ 5 │ 6 │ 4 ║ 7 │ 8 │ 3 ║
 ╟───┼───┼───╫───┼───┼───╫───┼───┼───╢  ╟───┼───┼───╫───┼───┼───╫───┼───┼───╢
 ║   │ 7 │   ║   │ 2 │ 1 ║   │   │   ║  ║ 5 │ 7 │ 3 ║ 8 │ 2 │ 1 ║ 6 │ 9 │ 4 ║
 ╟───┼───┼───╫───┼───┼───╫───┼───┼───╢  ╟───┼───┼───╫───┼───┼───╫───┼───┼───╢
 ║   │   │ 8 ║   │   │   ║   │   │   ║  ║ 6 │ 4 │ 8 ║ 3 │ 7 │ 9 ║ 2 │ 1 │ 5 ║
 ╚═══╧═══╧═══╩═══╧═══╧═══╩═══╧═══╧═══╝  ╚═══╧═══╧═══╩═══╧═══╧═══╩═══╧═══╧═══╝
      ⎕←T2←⎕TS
2016 12 2 19 30 0 572
      0.001×24 60 60 1000⊥¯4↑T2-T1
0.828

/// Jürgen

On 12/02/2016 04:10 AM, Christian Robert wrote:

Not a bug report,


Left  arg of GenGRID is maximum number of seconds to run (arg is optional and default to 30 secs)
Right arg of GenGRID is the target maximum number of non-zero digits in the grid (stopped by timer on the left side)


// generate a random grid and try for the next 60 seconds to reduce it into a 20 non empty cells.

        Display a←60 GenGRID 20

     ╔═══╤═══╤═══╦═══╤═══╤═══╦═══╤═══╤═══╗
     ║ 4 │   │ 5 ║   │   │ 2 ║   │ 7 │ 1 ║
     ╟───┼───┼───╫───┼───┼───╫───┼───┼───╢
     ║   │   │   ║   │   │   ║   │   │   ║
     ╟───┼───┼───╫───┼───┼───╫───┼───┼───╢
     ║   │   │ 9 ║   │ 4 │   ║   │   │ 6 ║
     ╠═══╪═══╪═══╬═══╪═══╪═══╬═══╪═══╪═══╣
     ║   │   │   ║ 9 │   │   ║ 8 │   │   ║
     ╟───┼───┼───╫───┼───┼───╫───┼───┼───╢
     ║   │ 3 │   ║   │   │ 6 ║   │ 4 │   ║
     ╟───┼───┼───╫───┼───┼───╫───┼───┼───╢
     ║   │   │   ║   │   │   ║ 3 │   │   ║
     ╠═══╪═══╪═══╬═══╪═══╪═══╬═══╪═══╪═══╣
     ║   │ 1 │   ║   │ 6 │   ║   │ 8 │   ║
     ╟───┼───┼───╫───┼───┼───╫───┼───┼───╢
     ║   │ 7 │   ║   │ 2 │ 1 ║   │   │   ║
     ╟───┼───┼───╫───┼───┼───╫───┼───┼───╢
     ║   │   │ 8 ║   │   │   ║   │   │   ║
     ╚═══╧═══╧═══╩═══╧═══╧═══╩═══╧═══╧═══╝

Took 60.37293294 secs (failed at reducing to 20, final was 21)

      a
4 0 5 0 0 2 0 7 1
0 0 0 0 0 0 0 0 0
0 0 9 0 4 0 0 0 6
0 0 0 9 0 0 8 0 0
0 3 0 0 0 6 0 4 0
0 0 0 0 0 0 3 0 0
0 1 0 0 6 0 0 8 0
0 7 0 0 2 1 0 0 0
3 0 8 0 0 0 0 0 0

One of the hardest Sudoku you can dream of (I think) but still solvable.

I got Lucky, because very few initial grids can be reduced as much as that ...

Will post my Sudoku workspace later when I'm satisfied with his behavior and speed.


Xtian.