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

- 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 45

6 789

476 189 52

358

9 273 146

Papy