bug-apl
[Top][All Lists]
Advanced

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

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


From: Christian Robert
Subject: Re: [Bug-apl] Quad-DLX implementation of Sudoku soon
Date: Fri, 2 Dec 2016 13:56:33 -0500
User-agent: Mozilla/5.0 (X11; Linux x86_64; rv:45.0) Gecko/20100101 Thunderbird/45.4.0

Wow !  Back to the drawing board.

Xtian.

On 2016-12-02 13:35, Juergen Sauermann wrote:
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.



reply via email to

[Prev in Thread] Current Thread [Next in Thread]