Based on;
THIS
I generalized/modified this algorithm to create filled NxN sudoku's (in the sence that N is the width and height of a box), with no input at all.
This technique is based on DLX.
The time to create just filled sudoku's is very strange, let me explain,
for
d=2 (16 cells total)
d=3 (81 cells)
d=4 (256 cells)
the algorithm is just fine, and works SUPERFAST (millisecond-range)
for
d=5,6,7 (625, 1296,2401 cells respectively) the algorithm is SUPER slow (I'm not sure how long it will take actually to find one, after 8 hours i found none).
Now comes the strange part; when d=8 (4096 cells), the algorithm is superfast again (millisecond range!).
Are there more people experiencing the same thing with their brute force solvers/generaters? Can someone explain the irregularities in this pattern?
Grtz,
SH
Speed Of Generating N-Sudoku Using Downey
8 posts
• Page 1 of 1
Speed Of Generating N-Sudoku Using Downey
by SHuisman » Mon Dec 04, 2006 2:58 pm
- SHuisman
- Posts: 17
- Joined: 23 March 2006
by Ruud » Mon Dec 04, 2006 7:29 pm
you need a considerable sample size to obtain relevant statistics.
I ran into similar problems with the program I use to create overlapping (Gattai) puzzles. Every size increase results in a proportional increase in generation time, but the transition from 13 (Sumo) to 25 (Shaolin) suddenly increases the generation time by a factor 20. I'm using a single DLX grid for the entire puzzle.
I also notice a large variance in generation time for individual Sudokus, even for the standard 3x3 size. Some puzzles balance on the edge and their dequeue size runs into millions. For me, it is faster to abort these processes and restart, but there is no doubt in my mind that I'm missing some very interesting puzzles by doing this.
Ruud
I ran into similar problems with the program I use to create overlapping (Gattai) puzzles. Every size increase results in a proportional increase in generation time, but the transition from 13 (Sumo) to 25 (Shaolin) suddenly increases the generation time by a factor 20. I'm using a single DLX grid for the entire puzzle.
I also notice a large variance in generation time for individual Sudokus, even for the standard 3x3 size. Some puzzles balance on the edge and their dequeue size runs into millions. For me, it is faster to abort these processes and restart, but there is no doubt in my mind that I'm missing some very interesting puzzles by doing this.
Ruud
- Ruud
- Posts: 664
- Joined: 28 October 2005
by Jean-Christophe » Mon Dec 04, 2006 9:06 pm
Hi,
I've read the post you mention. This program in Basic does NOT use DLX but some simple brute force algorithm. Apparently it uses a static cell ordering, always starting with top-left cell to bottom-right cell. This is far from optimized since it may take a looooong path before hitting a contradiction as SHuisman noticed with the test puzzle he posted. This puzzle should solve very fast since it only requires naked and hidden singles.
That said, it may have to to with the pseudo random number generator used. Some poor implementations are producing sequences of numbers with a very predictable pattern, not looking random at all !
Also 8 is some 'native' size for a computer whereas 3, 5 & 7 aren't as 'special'.
Another good place to look is the Sudoku Programmers Forum
I've read the post you mention. This program in Basic does NOT use DLX but some simple brute force algorithm. Apparently it uses a static cell ordering, always starting with top-left cell to bottom-right cell. This is far from optimized since it may take a looooong path before hitting a contradiction as SHuisman noticed with the test puzzle he posted. This puzzle should solve very fast since it only requires naked and hidden singles.
That said, it may have to to with the pseudo random number generator used. Some poor implementations are producing sequences of numbers with a very predictable pattern, not looking random at all !
Also 8 is some 'native' size for a computer whereas 3, 5 & 7 aren't as 'special'.
Another good place to look is the Sudoku Programmers Forum
- Jean-Christophe
- Posts: 149
- Joined: 22 January 2006
Slow Solver
by Papy » Tue Dec 05, 2006 3:23 pm
Some time , in spécific cases , the speed of the code go down.
Wy?
Fisrt for me a DLX code is not a brute force for two reasons
- Recursivity is not a brutal algo . It needs reflexion and adaptation not an 'bestial' algo
- The algo is not a simple test of validit of all the possible solurtions
What is a brute force? An algo that is testing directly the solution one by one just changing ONE data an without searching why the solution is good or false. It a BRUTAL méthode!
for exemple here is a BRUTAL code to gnerate all solution for a gi with 3*3 digits
for i0:=1 to 3 do
for i1:=1 to 3 do
for i2:=1 to 3 do
for i3:=1 to 3 do
for i4:=1 to 3 do
for i5:=1 to 3 do
for i6:=1 to 3 do
for i7:=1 to 3 do
for i8:=1 to 3 do
Grid:=(i0,i1,i2,i3,i4,i5,i6,i7,i8,i9)
No reflexion just the enumeration with double,impossible... but I' m sure that I test ALL the combinations.
For a 9*9 grid it's today impossible to ue a real brute force you have to much possibilities. Each of the 81 cells can have 9 different value!!!
But with recursivity? The problem is the same you must have to test 81 cells 9 times! And more with recursivity at each call you loose time and ram on the stacksolliciting memory manager!
So the solution is to éliminate bad grid as soon as possible for don't test
necessary bad value.
To do that you have to choose at the begining the kind of algo you want: itératif of recursif.
I prefer ,most quick, the iteratif but the public codes' are DLX
The first thing to do is to works not with the nine possible value of a cell but only witjh the pencils
if you, have 1234578. we know that the last digit is necessary a 9 because all the other values(1..8) are present n the row,Column,box
to be efficient you have to must find the best repartition of testing the solution and compute the pencils
Each time you set a cell many pencils change so the best is to compute them at each time!. False if you compute the pencils at each row often each celle you win 8 calls the the pencils calculation.
With a such method you don't need Dancings Lnks(who can explain me what is a dancing link?) You test only POSSIBLE values and go back just as necessary.
More your Pencils cmputing is better more your solver will be speed.
But there one point that ius very important and explain that algo suddenly go down. I have this problem so.
The reason is simple but not the solution. Our friend gsf have beat the problem with canonalize grid
Imagine a grid
with the first row fill with 123456789 or the first box
Is a grid more speed toi solve (with recursif) Yes Witch? The first. Why?
I think that ist" for these reason but I('m not sure it's an possibility
In the first grid the 81 celle on the grid is DIRECTLY on a digit influence
And the second only 3 rows and 3 colums are on influence And for me more you have influence on a cell less you have pencils so less value to test
In the second grid less celles are 'touched' but more value are eiminate
for the blocks. It's true but I think that it's more efficiant to eliminate valuye in a 81n referentiel taht in a 9 value.
If you want that your solver have a standard performance I think that you must cononized the file before calling the solver.I/e transform with rotation the second grid in the first. It's noty always possible but you are sure that the result is the betyter you can have.
123 456 789
476 189 523
589 273 146
Papy
Wy?
Fisrt for me a DLX code is not a brute force for two reasons
- Recursivity is not a brutal algo . It needs reflexion and adaptation not an 'bestial' algo
- The algo is not a simple test of validit of all the possible solurtions
What is a brute force? An algo that is testing directly the solution one by one just changing ONE data an without searching why the solution is good or false. It a BRUTAL méthode!
for exemple here is a BRUTAL code to gnerate all solution for a gi with 3*3 digits
for i0:=1 to 3 do
for i1:=1 to 3 do
for i2:=1 to 3 do
for i3:=1 to 3 do
for i4:=1 to 3 do
for i5:=1 to 3 do
for i6:=1 to 3 do
for i7:=1 to 3 do
for i8:=1 to 3 do
Grid:=(i0,i1,i2,i3,i4,i5,i6,i7,i8,i9)
No reflexion just the enumeration with double,impossible... but I' m sure that I test ALL the combinations.
For a 9*9 grid it's today impossible to ue a real brute force you have to much possibilities. Each of the 81 cells can have 9 different value!!!
But with recursivity? The problem is the same you must have to test 81 cells 9 times! And more with recursivity at each call you loose time and ram on the stacksolliciting memory manager!
So the solution is to éliminate bad grid as soon as possible for don't test
necessary bad value.
To do that you have to choose at the begining the kind of algo you want: itératif of recursif.
I prefer ,most quick, the iteratif but the public codes' are DLX
The first thing to do is to works not with the nine possible value of a cell but only witjh the pencils
if you, have 1234578. we know that the last digit is necessary a 9 because all the other values(1..8) are present n the row,Column,box
to be efficient you have to must find the best repartition of testing the solution and compute the pencils
Each time you set a cell many pencils change so the best is to compute them at each time!. False if you compute the pencils at each row often each celle you win 8 calls the the pencils calculation.
With a such method you don't need Dancings Lnks(who can explain me what is a dancing link?) You test only POSSIBLE values and go back just as necessary.
More your Pencils cmputing is better more your solver will be speed.
But there one point that ius very important and explain that algo suddenly go down. I have this problem so.
The reason is simple but not the solution. Our friend gsf have beat the problem with canonalize grid
Imagine a grid
with the first row fill with 123456789 or the first box
- Code: Select all
123456789 123000000
000000000 560000000
000000000 789000000
000000000 000000000
000000000 000000000
000000000 000000000
000000000 000000000
000000000 000000000
000000000 000000000
Is a grid more speed toi solve (with recursif) Yes Witch? The first. Why?
I think that ist" for these reason but I('m not sure it's an possibility
In the first grid the 81 celle on the grid is DIRECTLY on a digit influence
And the second only 3 rows and 3 colums are on influence And for me more you have influence on a cell less you have pencils so less value to test
In the second grid less celles are 'touched' but more value are eiminate
for the blocks. It's true but I think that it's more efficiant to eliminate valuye in a 81n referentiel taht in a 9 value.
If you want that your solver have a standard performance I think that you must cononized the file before calling the solver.I/e transform with rotation the second grid in the first. It's noty always possible but you are sure that the result is the betyter you can have.
- Code: Select all
Just for the fun:
Is't possible to say if this block is good or false? and Why?
Digits in bold are clues.....
123 456 789
476 189 523
589 273 146
Papy
- Papy
- Posts: 131
- Joined: 15 August 2006
8 posts
• Page 1 of 1
