The New Sudoku Players' Forum

[champagne]

I continued to work on zhouyundong_2012's code starting from that position from the last post

a) a file of 4.847.466 puzzles rating 1.2 to 4.4 with a pattern of a past game
fss:1mn 10 against 1mn 18

I made 2 steps of improvement

1) replacing the Update() loop by an expanded code with no overhead load as in the original version
2) Doing a similar step to select in priority a guess of a bi value

The first step pushed down the runtime from 1mn 18 to 53 seconds, now faster than my version of fss
The reduction coming out of the second step was very small (about 1 second)

So the new solver, with that high optimisation of the central loop appears 20% better than fss. I have a slightly better ratio (a little more than 30%) with the file of potential hardest.

I have still some cleaning to do to get my final version in C++, but I am not expecting a significant effect on the performance.

[dobrichev]

What exactly are you testing?
Input file with 81 chars/row, solve up to the second solution, output to other text file 81 chars/row?

I am surprised from the small initial no-difference between fsss and zhou. On my compiler and PC zhou works faster except for the invalid puzzles.

[champagne]

What exactly are you testing?
Input file with 81 chars/row, solve up to the second solution, output to other text file 81 chars/row?

I am surprised from the small initial no-difference between fsss and zhou. On my compiler and PC zhou works faster except for the invalid puzzles.

Input is a 81 chars puzzle. Here all puzzles are valid, so there is only one solution. I'll see later for tests of puzzles invalid or having more than one solution.

For puzzles having more than one solution, the search is supposed to stop at solution 2.

The output is limited to the count of valid puzzles to avoid as much as possible the input output effect. The time is the clock from start to end.

In both cases, I test a function included in my program. But as I used mainly general data, we have IMO the start fix price, the same for both runs.

I think you never tested a downgraded version of the Update() where the "While" loop is a for... calling a function. This is responsible for the 20% to 30% deviation in the results.

The code is already in my google project, but the last changes should be committed to morrow after some cleaning in progress and may be other tests to look for a performance improvement

[champagne]

I continued test on the "zhou" process;

I am now testing the puzzle generation.

I used the puzzle generation in a vicinity 1-3. This for several reasons :

The ratio input to output is relatively high if you start from a seed having a high rating
In my process, I have no filter.

The "zhou" process is used to see if a puzzle is valid, but also to see if the puzzle is minimal, so the performance ratio fss <-> "zhou" can be seen.

I used a seed of 156 puzzles passing the serate dynamic mode, out of the last game.
53181 valid puzzles were created in the +-(1-3) process.

It took

8mn 19 s using fss
3mn 9s using "zhou"


I'll check within the day the same process for a vicinity +-1 out, the second very common generation I use in a game.

When filters are applied, most of the time is dedicated to the quick rating, by far the bottleneck in the process.

[zhouyundong_2012]

any improvement?

[champagne]

any improvement?

Difficult to answer to that.

I changed the process to use a recursive process but I did not make a benchmark against the original code.

I made some adjustments in several processes to switch to some variant of that process. I have no doubt that the overall improvement is important, but giving more details is not easy. Moreover, I have still some tests to run.

[zhouyundong_2012]

Guess(), any analyse? any test?

[zhouyundong_2012]

There must be some way to Guess more effecient

[zhouyundong_2012]

Any Good Idea?

[zhouyundong_2012]

I found a small improvement, I made a mistake at creating TblDoubleMask
f.g. the column mask is 100,110,111
Old: +++,--+,+++

if F[0] is 100,110,111
F[1] is 100,110,111
F[2] is 111,111,111

then F[2] and= TblDoubleMask[100,110,111] = 111,001,111

New:---,--+,+++ ======> ---,---,---
So new F[2] and= TblDoubleMask[100,110,111] = 000,000,000

When calc the shrink of F[2], Old maybe not 0,but New is 0. It can return false more quickly.

[zhouyundong_2012]

void CreateTblMaskDouble()
{
int T[8] = { 0, 0, 0, 4, 0, 2, 1, 7 };
for (int i = 0; i < 512; i++)
{
int t1 = T[i >> 6];
int t2 = T[i >> 3 & 0x7];
int t3 = T[i & 0x7];
if (t1 == 0 || t2 == 0 || t3 == 0)
TblMaskDouble[i] = 0;
else
{
TblMaskDouble[i] = ((t1 << 6) | (t2 << 3) | t3) ^ 0x1FF;
TblMaskDouble[i] = TblCombineMask[TblMaskDouble[i]];
}
}
}
Maybe it should be fix for the sake of U[].

[zhouyundong_2012]

when I test top1465, Timing from 29.3 to 28.9
0.4 / 29.3 * 100% = 1%

What about your test?

[dobrichev]

Hi zhouyundong_2012,

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


The source code is here. If you can't access this repository, I will send it in several private messages.
There's always a bigger fish, who's next?

[champagne]

Hi zhouyundong_2012,

This is the comparison of your solver with latest version of fsss2. It is алсо available in the Programmers' forum.
There's always a bigger fish, who's next?

Hi mladen,

I am not in that fight, and I switched to the zhouyundong_2012 design just because it was not too hard to use it in my program.
I changed the "guess" part of the code, but it is not the key point.
I am now using different functions based on that code in my generation of puzzles and in the serate clone mode (say skfr V2)

One interesting point in your table is the comparison for high ratings.

I have not a stand alone version of the zhouyundong_2012 in the way I use it in my process, but it would not be very hard to built it.
Do you have or can you deliver a win32 version of fss2.

I could then make my own tests with a windows platform

[dobrichev]

Do you have or can you deliver a win32 version of fss2.

No, I still haven't it in win32 form.
The code compiles with GNU C++ but works significantly slower. Haven't tested it with MS. In order to benefit from the algorithm on different compilers/platforms, the code should be rewritten in closer-to-machine form, i.e. virtually in assembler. It isn't much work, but I planned it for after finishing with the logical approaches experimenting.