The New Sudoku Players' Forum

[Serg]

Hi, Mladen!

This is the comparison of your solver with latest version of fsss2. It is алсо available in the Programmers' forum.

Code: Select all

      17puz48826 1465x20   50000   Tarek  gen_puzzles 38puz540512 hard817681
                                  Pearly       500000
                                    6000

fsss2      0.284   0.913   0.315   0.429        0.239       2.688     78.952
ZSolver    0.203   0.784   0.321   0.527        0.664       2.897     85.800


Congratulations on new effective sudoku solver! What ideas do you implement in it?

Serg

[dobrichev]

Hi Serg,

The code is simple, has comments, and I am sure you can follow it.

Essentially the data model is 9 128-bit values for each digit. Bits 0..80 = 1 if the respective cell has candidate of the respective digit. If the cell is solved and the value is respective digit, the respective bit is cleared. Next 27 bits = 1 if the respective house isn't resolved. The rest bits are unused. Additionally there is one 128-bit value where bits 0..80 = 1 when the cell is solved.
There are 81 128-bit constant masks used to clear the respective candidates and houses when a cell is solved/given.
There are 27 128-bit constant masks used to get candidates for a house.
The naked singles (cells with single remaining candidate) are searched by accumulating duplicates. This algorithm I found in the Brian Turner's solver.
The hidden singles (houses with single remaining candidate for a particular digit) are searched by looping trough digits then trough unsolved houses.
Guessing cell/digit is selected from bi-value cells, in the same way as when searching naked singles but this time by accumulating triplicates - if a cell isn't solved and hasn't candidates in 3 different digits, then it is bi-value. If no bi-value cell is found, then (very rare) a search for digit/house with minimal number of candidates is performed, stopping at first bi-position digit/house. Context of 10 128-bit values (9 for each digit candidates + 1 for the solved_cells) is stored prior to guessing and is restored if necessary.
The sequence of tests (techniques) was obtained empirically.
The trick which accelerated the solver over the zhouyundong_2012's is that digit candidates are cached after unsuccessful check for hidden singles and in later iterations the entire digit isn't checked for hidden singles if the candidates aren't changed. This saves the loop over the unsolved houses.

Line-box eliminations were implemented in the initial version. The code is fairly easy too. For 17-clue puzzles checking for such eliminations prior to guessing improves the speed (but still zhouyundong_2012's solver is faster there). Checking only once prior to the first guess gave the best balance but I abandoned this technique because it slows down the processing for the hard, invalid, and high-clue puzzles where I am digging recently.

[tarek]

Using a bit-mask that has 81 bits for location and 9 for value will make sudoku solving quicker (fish and sets) you still have 38 more bits to use as well

Tarek

[dobrichev]

Hi tarek,
There is only one mask per 1-rookery and the digit is known by its address - first mask is for digit 1, etc. The solution, if the solver is asked for solution at all, is accumulated in a separate string, setting the value at respective cell at the moment when the cell is set as given or is solved/guessed.
If you have something else in mind, could you rephrase?

[zhouyundong_2012]

No Improvment? That's immposible.

[champagne]

No Improvment? That's immposible.

I don't know if anybody is working on improvements of your code,

On my side, I use it now in my processes, it works, it's fast, it's enough for me.
As I already wrote, the main change I made was to switch to a recursive process in the "guess", but I never tried to see the effect on the performance.

[champagne]

No Improvement? That's impossible.

I recently used the zhouyundong_2012" brute force in a new process submitting to the brute force some non valid puzzles and I had some very bad suprises.

Most of the benchmarks I red in that thread have been made on "valid puzzles".

I sent to the brute force some puzzles with redundant digits in row, column or box.

Nothing is done in the initial process to detect it and the effect can be a very long search to see that the puzzle is not valid.

Same thing can happen (but this is not logically non acceptable unless you want only to check that the puzzle is valid) if you submit a puzzle with several digit missing.

The first case, a true bug in a process to be the most efficient, is easy to fix.

For the second case, users should take care to filter such calls upstream.

[champagne]

more information on the same topic

I used very soon an integrated version derived of the zhouyundong_2012 brute force.
Recently, working on the generation of puzzles having a double symmetry (double diagonal, pi_stick, Rotational 90), I faced unexpected problems showing some weaknesses in that code.
From some private exchanges, I think that this is something mladen Dobrichev already noticed.

The main weakness came when a puzzle showing a contradiction with the basic rules was submitted to the brute force. This is something that we have no chance to see in benchmarks based on valid puzzles.

The second weakness I faced is a kind of "worst case" for that algorithm heavily row oriented.

this is a puzzle not valid.

...12........35......96....3.74.2.9....7.3....1.8.63.7....41......57........89...

... 12. ...
... .35 ...
... 96. ...

3.7 4.2 .9.
... 7.3 ...
.1. 8.6 3.7

... .41 ...
... 57. ...
... .89 ...

One can see immediately that no digit can be assigned to r8c6.

It took 145 milliseconds to my code to tell that.

The main use of the brute force is to check the validity of a given puzzle.
Benchmarks have all been done on valid puzzles, a tiny corner of that problem.

I reworked on the zhouyundong_2012 process trying to find a way to fix the weaknesses with a minimum penalty.

I also revisited some special cases to try to define a kind of "best process" for that situation.

I'll comment on that in several posts.
The code I am using can be downloaded from the file Zhou_use


the main change is in the InitSudoku() function.

My assumption for the "basic" code is the following:

The empty cell (no given) can have any value except '1' to '9'. In the canonical form, the empty cell is '.'
The puzzle can be false against the basic rule (same digit twice in one unit)

the init function includes 3 steps

. create a canonical form of the puzzle
. check for no given against the basic rule
. solve single in cells at the start.

The third point has been added for 2 reasons

. it's nearly for free at that point
. this is something the brute force would not detect.



The second change I introduced is more for calls skipping that new InitSudoku().

zhouyundong_2012 is in average so efficient that any change should be applied when the process appears to enter the "worst case".

Any other point in that code is the high efficiency of the Init() process.
The best trade off I found is valid in the main call looking for {is it a valid sudoku}?

The risk to enter the worst case can be seen in the "guess" function.

The first step, in the guess function is to use a digit bivalue.

If, after "n" guess (n=4 seems to be a good limit), you find no bi-value then, you are in risk to be in the worst case.
Then, the best option in that process seems to switch to the diagonal symmetry, restarting in the very efficient Init() function.

1) you are protected against the worst case,
2) the penalty in the standard process is close to nil.

The next post will summarize the results I got using that strategy.

[champagne]

Basic performance of the code I use.
Having said that a benchmark on valid puzzles is not very efficient (although the order of magnitude remains a good indication), I picked up a small sample of puzzles to give some indications on the global performance.

I used for the tests a processor 3.4 Ghz core i7_4740
(64 bits processor, 32 bits code)
In most cases, other task were running in parallel.

the first sample of valid puzzles is the following (with the 3 serate ratings)

Code: Select all

.1.....2.23.....45...2.5.....67324.....8.6.....79546.....3.8...85.....36.4.....9.;1.20;1.00;1.00   
6....87......4..5....5....6....1..6...34.78...1..2....7....1....2..6......83....5;1.50;1.50;1.50
..9.8.7...6...5.4.3.....6.2.......3.5...7.1...2.......4.7.2...1.3.8...7...1...9..;6.70;6.70;6.70   
98.7.....7.....6....6.5.....4...5.3...79..5......2...1..85..9......1...4.....3.2.;11.90;11.90;11.80
98.7.....6.....87...7.....5.4..3.5....65...9......2..1..86...5.....1.3.......4..2;11.90;11.90;11.60
12..3....4....1.2...52..1..5..4..2......6..7......3..8.5....9....9.7..3......8..6;11.90;11.90;11.30
.......39.....1..5..3.5.8....8.9...6.7...2...1..4.......9.8..5..2....6..4..7.....;11.90;11.90;11.30
.2.4...8.....8...68....71..2..5...9..95.......4..3.........1..7..28...4.....6.3..;11.90;11.90;9.90
........1....23.45..51..2....25...1..6...27..8...9......42....7.3...6...9...8....;11.90;11.90;9.90
12.3.....4.5...6...7.....2.6..1..3....453.........8..9...45.1.........8......2..7;11.90;11.90;2.60
..3..6.8....1..2......7...4..9..8.6..3..4...1.7.2.....3....5.....5...6..98.....5.;11.90;1.20;1.20



each puzzle was solved 100 000 times. I compared my old code and the new code with the "safe" InitSudoku().

run times are in milliseconds. The puz/second is with the new process.

Code: Select all

rating  new     old            puz/second
1.2      144     119      694 444
1.5      162     145      617 284
6.7      651     663      153 610
11.9   24861   25204      4022
11.9   12324   12626      8114
11.9   18519   19020      5400
11.9   18541   18477      5393
11.9   33624   33432      2974
11.9    7344    7371      13617
11.9   21579   21830      4634
11.9   12778   12961      7826

Improvements made in the coding erased more or less the penalty of a longer Init() process.
In the high ratings, the switch to the symmetry seems to be slightly better than the classical process, but usually, the symmetry is not applied.

The second lot of bad performance came with puzzles having an empty cell at the start as these

Code: Select all

...12........35......96....2.48.6.9....7.3....1.4.26.8....41......57........89...
...12........35......96....2.48.6.5....7.3....5.4.26.8....41......57........89...
...12........35......96....2.48.6.1....7.3....9.4.26.8....41......57........89...
...12........35......96....3.74.2.9....7.3....1.8.63.7....41......57........89...


again, the timing for 100 000 times the brute force applied (estimate for the "old" code for 100 times run)

Code: Select all

new   old
30   5914000
32   4769000
30   5614000
31   14040000


With the basic code it took 140 milliseconds to see that the last puzzle in that group was not valid. With the new Init(), the default is seen immediately.

Next post will go over the 27 + X + Y issue

[champagne]

Usually, a call to the brute force is made under control of a calling program.
Some classical situations are

the vicinity search,
the X+Y +27 expansion.

I'll take as first example the X+X+27 generation. I done it recently to look for unknown 17 puzzles in the 4+4+27 and in the 3+5+27 configuration.

This is a very very long process (several core*year) made in four steps.

a) find ED patterns of the form X+Y+27 (short task)
b) expand these patterns against "gangsters", the ED minlex forms of the band1 for such a task (44 gangsters)
c) find all puzzles equivalent to the gangster for the solution in b)
d) look for 17 clues in the result of point c).

optimization of the brute force in X+X+27 generation

The endless task is the second one.
for each ED pattern and each gangster, a scan of band2 and band3 clues (8 clues here) has to be done, considering all valid permutations of the ED pattern in bands 2 and 3.

I did it using Blue's provided code. Blue's code filters as much as possible all redundant permutations in bands 2 and 3.
The X+Y clues are then expanded giving a solution usually valid, but not unique.

In that situation,

the overall performance of the InitSudoku() function is a key point.
As the band 1 is fully solved, Update() and Guess() can be reduced to rows 4_9

I tested several possibilities. My best results came in the following conditions:

The Initial status is achieved in 2 steps:
. first the 27 clues of the "gangster" are loaded in the brute force and the BlockMaskSum[3], BlockMask[27] are stored
. the last 8 clues are loaded in once restarting with the values stored

Expansion is done ignoring rows 1_3. (I tried with poor results to use a diagonal symmetry at start to check whether the guess on 9 rows would have a better efficiency)

The optimized code cut by 18% the global run time in a run of 9 hours compared to the code I used in my generation.


Optimization of the code to find equivalent gangster

Using a gangster, we have only one set of mini columns in band1. Having generated a valid puzzle with that reduction, we have to find all perms in minicolumns giving valid puzzles.
To achieve that, the process is the following

. Solve the generated puzzle
. Use band2 band3 of the solution as given and take any minicolumn as complementary given (to avoid morphs through rows permutations in band 1)

At that point, the best is to use directly the brute force to find all valid puzzle. As all rows are solved in bands 2 and 3, you can use a reduced version of Update() and Guess 3 rows to scan.
Applying that process, a file of 17 500 3+5+27 puzzles was extended to 588 700 puzzles in less than 2 seconds
So in the global process point c) is very short;

point d) is more complex and some comments will come in due time in the appropriate thread;

Optimization of the process in a vicinity search.

In a vicinity search (and in a similar way for most of the classical generation problems) splitting the group of clues in 2 groups "untouched in the vicinity", "vicinity explored" makes sense,
In my current process, at that point the generation goes cell by cell. The process used for the gangster equivalence can be considered, but :

. Each solution must be checked for uniqueness
. we loose the early detection of a puzzle not minimal.

The current process is
. Do Init() and Update() for the first lot (Update() checks for validity in some conditions)
. then cell by cell in the "vicinity lot"
check for early "assigned" => not minimal
assign and do Update() stop if "not valid" seen
. at the end check for final "one solution" and "minimal puzzle"

All this is done directly in the brute force.

[champagne]

I looked again the brute force code to see what could be done using a wider bit field.

I have no fresh idea using a 128 bit field (the last version of fss2 from mladen Dobrichev is not based on the same process).

A 64 bit field can be used instead of the 32 bit field keeping untouched the zhouyundong_2012 process basics.

In that case, the 64 bit field is split in the following way

3x 16 bit fields for the 3 rows
1 x 16 bit field for the 3 flags of unsolved rows.

I have no tool to produce a 64 bits code, so I tested that idea in 32 bits mode. I got more or less the same performance than with the pure 32 bits mode.

IMO, using a 64 bit code, the improvement should be over 20%.

If anybody is interested in that and can produce a 64 bits executable, we can share the code (the main change is a translation of some tables from the 32 bits map to the 64 bits map).

The following change in the #define of the update process (by far the highest frequency) gives an idea of the possible improvement)

================ define in 32 bits (elementary step of the Update process)

if(CompF[I] != F[I] ) {\
Shrink = (TblShrinkMask[F[I] & 0x1FF] | \
TblShrinkMask[ (F[I]>>9) & 0x1FF]<<3 | \
TblShrinkMask[ (F[I]>>18) & 0x1FF]<<6);\
if ((F[I] &=TblComplexMask[Shrink]) ==0) return 0; \
S = ((F[I] | (F[I] >> 9) | (F[I] >> 18)) & 0x1FF); \
C1=S|((F[J]|(F[J]>>9)|(F[J]>>18))&0x1FF);\
C2=S|((F[K]|(F[K]>>9)|(F[K]>>18))&0x1FF);\
F[K]&=TblMaskSingle[S]&TblMaskDouble[C1];\
F[J]&=TblMaskSingle[S]&TblMaskDouble[C2];\
S=TblRowUniq[TblShrinkSingle[Shrink]&TblColumnSingle[S]];\
if((F[I]>>27)!=S){\
F[I]&=S<<27|BIT_SET_27;cl=~(F[I] & TblRowMask[S]);\
F[P]&= cl;F[Q]&= cl;F[R]&= cl;F[T]&= cl;\
F[U]&= cl;F[V]&= cl;F[W]&= cl;F[X]&= cl;\
}CompF[I] = F[I];\


================ define in 64 bits

if(CFF[I].u64 != FF[I].u64 ) {\
Shrink = (TblShrinkMask[FF[I].u16[0] ] | (TblShrinkMask[ FF[I].u16[1]]<<3) | (TblShrinkMask[FF[I].u16[2]]<<6));\
if ((FF[I].u64 &=ComplexMask64[Shrink]) ==0) return 0;\
S = (FF[I].u16[0] | FF[I].u16[1] | FF[I].u16[2]);\
C1 = S | (FF[J].u16[0] | FF[J].u16[1] | FF[J].u16[2]);\
C2 = S |(FF[K].u16[0] | FF[K].u16[1] | FF[K].u16[2]);\
FF[K].u64 &= (unsigned __int64)(MSingle64[S]&MDouble64[C1]);\
FF[J].u64 &= (unsigned __int64)(MSingle64[S]&MDouble64[C2]);\
S=TblRowUniq[TblShrinkSingle[Shrink]&TblColumnSingle[S]];\
if(FF[I].u16[3]!=S){\
FF[I].u16[3]&=S;cl=~(FF[I].u64 & MaskRow64[S]);\
FF[P].u64&= cl;FF[Q].u64&= cl;FF[R].u64&= cl;FF[T].u64&= cl;\
FF[U].u64&= cl;FF[V].u64&= cl;FF[W].u64&= cl;FF[X].u64&= cl;\
}CFF[I]=FF[I];}


here the 32 bit field F and COMPF are replaced by 64 bit field FF and CFF of that type


typedef union __declspec(intrin_type) _CRT_ALIGN(8) GINT64_t {
unsigned __int64 u64;
unsigned __int32 u32[2];
unsigned __int16 u16[4];
unsigned __int8 u8[8];
} GINT64;

[dobrichev]

Does it mean that you have in hands a 64-bit compiler for Windows?

[champagne]

Does it mean that you have in hands a 64-bit compiler for Windows?

No I don't, that's why I had to run the code in 32 bit mode with relatively poor results. (same performance as the original 32 bits map)
But it seems that the last visual studio free soft could produce a 64 bits code.

I am trying to install the last update of visual studio 2013 that seems to have a 64 bits platform see here

https://msdn.microsoft.com/fr-fr/library/9yb4317s.aspx

(preferably in english I guess)

If this works, I'll make the comparative test

[champagne]

Does it mean that you have in hands a 64-bit compiler for Windows?

I installed the last version of microsoft studio 2013.

I tested the program on which I am working.

I could open a "x64" platform and compile the program with minor warnings.

I did not see a "win64" option in the selection of a platform.

May be this can help

Later to day, I'll test the new .exe

[rjamil]

Have anybody ever try to use new values of TblMaskDouble[512] array as suggested by zhouyundong_2012 on Fri May 23, 2014 at 4:59 am and 5:14 am?

Code: Select all

int TblMaskDouble[512] =
{
   0x0,      0x0,      0x0,      0x0,      0x0,      0x0,      0x0,      0x0,
   0x0,      0x0,      0x0,      0x0,      0x0,      0x0,      0x0,      0x0,
   0x0,      0x0,      0x0,      0x0,      0x0,      0x0,      0x0,      0x0,
   0x0,      0x0,      0x0,      0x0,      0x0,      0x0,      0x0,      0x0,
   0x0,      0x0,      0x0,      0x0,      0x0,      0x0,      0x0,      0x0,
   0x0,      0x0,      0x0,      0x0,      0x0,      0x0,      0x0,      0x0,
   0x0,      0x0,      0x0,      0x0,      0x0,      0x0,      0x0,      0x0,
   0x0,      0x0,      0x0,      0x0,      0x0,      0x0,      0x0,      0x0,
   0x0,      0x0,      0x0,      0x0,      0x0,      0x0,      0x0,      0x0,
   0x0,      0x0,      0x0,      0x0,      0x0,      0x0,      0x0,      0x0,
   0x0,      0x0,      0x0,      0x0,      0x0,      0x0,      0x0,      0x0,
   0x0,      0x0,      0x0,      0x0,      0x0,      0x0,      0x0,      0x0,
   0x0,      0x0,      0x0,      0x0,      0x0,      0x0,      0x0,      0x0,
   0x0,      0x0,      0x0,      0x0,      0x0,      0x0,      0x0,      0x0,
   0x0,      0x0,      0x0,      0x0,      0x0,      0x0,      0x0,      0x0,
   0x0,      0x0,      0x0,      0x0,      0x0,      0x0,      0x0,      0x0,
   0x0,      0x0,      0x0,      0x0,      0x0,      0x0,      0x0,      0x0,
   0x0,      0x0,      0x0,      0x0,      0x0,      0x0,      0x0,      0x0,
   0x0,      0x0,      0x0,      0x0,      0x0,      0x0,      0x0,      0x0,
   0x0,      0x0,      0x0,      0x0,      0x0,      0x0,      0x0,      0x0,
   0x0,      0x0,      0x0,      0x0,      0x0,      0x0,      0x0,      0x0,
   0x0,      0x0,      0x0,      0x0,      0x0,      0x0,      0x0,      0x0,
   0x0,      0x0,      0x0,      0x0,      0x0,      0x0,      0x0,      0x0,
   0x0,      0x0,      0x0,      0x0,      0x0,      0x0,      0x0,      0x0,
   0x0,      0x0,      0x0,      0x0,      0x0,      0x0,      0x0,      0x0,
   0x0,      0x0,      0x0,      0x0,      0x0,      0x0,      0x0,      0x0,
   0x0,      0x0,      0x0,      0x0,      0x0,      0x0,      0x0,      0x0,
   0x0,      0x0,      0x0,      0x4924924,   0x0,      0x48A4522,   0x4864321,   0x49E4F27,
   0x0,      0x0,      0x0,      0x0,      0x0,      0x0,      0x0,      0x0,
   0x0,      0x0,      0x0,      0x4522914,   0x0,      0x44A2512,   0x4462311,   0x45E2F17,
   0x0,      0x0,      0x0,      0x432190C,   0x0,      0x42A150A,   0x4261309,   0x43E1F0F,
   0x0,      0x0,      0x0,      0x4F2793C,   0x0,      0x4EA753A,   0x4E67339,   0x4FE7F3F,
   0x0,      0x0,      0x0,      0x0,      0x0,      0x0,      0x0,      0x0,
   0x0,      0x0,      0x0,      0x0,      0x0,      0x0,      0x0,      0x0,
   0x0,      0x0,      0x0,      0x0,      0x0,      0x0,      0x0,      0x0,
   0x0,      0x0,      0x0,      0x0,      0x0,      0x0,      0x0,      0x0,
   0x0,      0x0,      0x0,      0x0,      0x0,      0x0,      0x0,      0x0,
   0x0,      0x0,      0x0,      0x0,      0x0,      0x0,      0x0,      0x0,
   0x0,      0x0,      0x0,      0x0,      0x0,      0x0,      0x0,      0x0,
   0x0,      0x0,      0x0,      0x0,      0x0,      0x0,      0x0,      0x0,
   0x0,      0x0,      0x0,      0x0,      0x0,      0x0,      0x0,      0x0,
   0x0,      0x0,      0x0,      0x0,      0x0,      0x0,      0x0,      0x0,
   0x0,      0x0,      0x0,      0x0,      0x0,      0x0,      0x0,      0x0,
   0x0,      0x0,      0x0,      0x29148A4,   0x0,      0x28944A2,   0x28542A1,   0x29D4EA7,
   0x0,      0x0,      0x0,      0x0,      0x0,      0x0,      0x0,      0x0,
   0x0,      0x0,      0x0,      0x2512894,   0x0,      0x2492492,   0x2452291,   0x25D2E97,
   0x0,      0x0,      0x0,      0x231188C,   0x0,      0x229148A,   0x2251289,   0x23D1E8F,
   0x0,      0x0,      0x0,      0x2F178BC,   0x0,      0x2E974BA,   0x2E572B9,   0x2FD7EBF,
   0x0,      0x0,      0x0,      0x0,      0x0,      0x0,      0x0,      0x0,
   0x0,      0x0,      0x0,      0x0,      0x0,      0x0,      0x0,      0x0,
   0x0,      0x0,      0x0,      0x0,      0x0,      0x0,      0x0,      0x0,
   0x0,      0x0,      0x0,      0x190C864,   0x0,      0x188C462,   0x184C261,   0x19CCE67,
   0x0,      0x0,      0x0,      0x0,      0x0,      0x0,      0x0,      0x0,
   0x0,      0x0,      0x0,      0x150A854,   0x0,      0x148A452,   0x144A251,   0x15CAE57,
   0x0,      0x0,      0x0,      0x130984C,   0x0,      0x128944A,   0x1249249,   0x13C9E4F,
   0x0,      0x0,      0x0,      0x1F0F87C,   0x0,      0x1E8F47A,   0x1E4F279,   0x1FCFE7F,
   0x0,      0x0,      0x0,      0x0,      0x0,      0x0,      0x0,      0x0,
   0x0,      0x0,      0x0,      0x0,      0x0,      0x0,      0x0,      0x0,
   0x0,      0x0,      0x0,      0x0,      0x0,      0x0,      0x0,      0x0,
   0x0,      0x0,      0x0,      0x793C9E4,   0x0,      0x78BC5E2,   0x787C3E1,   0x79FCFE7,
   0x0,      0x0,      0x0,      0x0,      0x0,      0x0,      0x0,      0x0,
   0x0,      0x0,      0x0,      0x753A9D4,   0x0,      0x74BA5D2,   0x747A3D1,   0x75FAFD7,
   0x0,      0x0,      0x0,      0x73399CC,   0x0,      0x72B95CA,   0x72793C9,   0x73F9FCF,
   0x0,      0x0,      0x0,      0x7F3F9FC,   0x0,      0x7EBF5FA,   0x7E7F3F9,   0x7FFFFFF
};

R. Jamil