The New Sudoku Players' Forum

[champagne]

I loaded on my site an update of the previous zip.file skbf_V1.
the zip file is skbf_V1

The changes are the following
. a bug fixed for files having a '0' for empty cells
. a relocation of the "stop test" improving the results for grids with more solutions than the maximum expected.
. a small optimization of the Update() function giving a 4% improvement using Microsoft Visual C++ to compile.
. a better portability including most of the changes mladen Dobrichev had to to to compile the program.




Mladen Dobrichev made tests on the previous version (having solved several portability problems).

Using his platform, to make it short, fss2 remains competitive towards skbf. The changes made in the new version should not change deeply the scope.Out of the 4% improvements in Update(), changes will affect mainly grids with more than one solution and the minimal check process.

Using Microsoft Visual C++ to compile , skbf is significantly better, showing that we are now highly depending on the compiler optimizations.


Note : Both programs must be run on a 64 bits infrastructure

EDIT 2015_10_12

The file had an old non tested version of Minimal test
The file has been updated with the same name

[zhouyundong_2012]

what's the most inner critical loop ?

you could include some counters at different places in the program
and see, how often each piece is executed in average

then you could write that critical part in assembly
I remember, we did this in CLAX 1-2 decades ago ...

would it be better to use 128-bit-registers ?

in theory they could make a sudoku-processor

if there would be an instruction to calculate shrink algrithm, the macro SHRINK will be much more faster.

[champagne]

if there would be an instruction to calculate shrink algrithm, the macro SHRINK will be much more faster.

so far, all parallel processing using a 128 bits pattern are working on bytes,words or 32 bits sub fields.

So I see no change to use such process in the 27 bits => 3x9 bits fields.

I tested many other possibilities to split the rows, but with no success.

The best I could do is what is in the last version I posted : using a 128 bit field to host the 3 bands and pushing in a separate 128 bits field the unsolved rows indicators.

[zhouyundong_2012]

X + Y + 27, What is X, What is Y?

[champagne]

X + Y + 27, What is X, What is Y?

It is a full scan of a pattern where one band is known (27) and the 2 other bands have respectively X clues and Y clues.
The 27 clues band is one of the 44 possible min lexical possibilities (called "gangsters")

to have one example of the use of that technique, see here
I did not check, but within that thread you surely have pointers to he original discussion about the 44 minlex gangsters

[rjamil]

Hi,

I have downloaded HardestDatabase110626.txt file from this post sometime back. Now, tested with Zhou's ZSolver, provided by Jason in this post, and my Bitwise Sudoku Solver programs. My program solves all 375 Sudoku puzzles whereas ZSolver gives invalid 2 puzzles.

Will someone check and advise which program is correct.

R. Jamil

[JasonLion]

I tried JSolve and ZSolve on my Mac. Both said 375 valid puzzles and 0 invalid.

[m_b_metcalf]

Hi,
I have downloaded HardestDatabase110626.txt file from this post sometime back. Now, tested with Zhou's ZSolver, provided by Jason in this post, and my Bitwise Sudoku Solver programs. My program solves all 375 Sudoku puzzles whereas ZSolver gives invalid 2 puzzles.

For a more comprehensive coverage of all solution paths I recommend that you use the files PG1000.txt or games_sample described in this thread.

Regards,

Mike Metcalf

[rjamil]

Hi,

Following Sudoku puzzles were not solved by ZSolver in my side:

Code: Select all

..34....94...8.1...9.......2...1.8.....3.7.5..75.........2.86......6..146.......8,HardestSudokusThread-01542,eleven,99080,98863,,,,2572,1623
1..........7.8...6.9.3...1...46........7.8..4....4.62.5.........3...59....2.6...7,HardestSudokusThread-01740,eleven,95393,98726,,,,4307,1135

I have consolidated all ZSolver files into one and made some tweaks. See attachment.

Maybe there is some kind of error remain/introduced in my side.

R. Jamil

[rjamil]

Hi Mike Metcalf,

I have tested PG1000.txt Sudoku puzzles with my RJSolBit.CPP program. It solves all of them.

Find attached herewith an output of my program.

R. Jamil
-------------------------------------
C-Free Professional C/C++ IDE
MinGW 5.0
Windows 10 Pro x64
TOSHIBA Satellite C855D

[m_b_metcalf]

I have tested PG1000.txt Sudoku puzzles with my RJSolBit.CPP program. It solves all of them.

Are your timings in s, ms or µs?

Regards,

Mike Metcalf

[rjamil]

Hi Mike Metcalf,

I uses "c = clock();" statement before start solving each Sudoku puzzle and calculate time with "c = (clock () - c) / CLOCKS_PER_SEC * 1000;" statement after completing each puzzle.

Believe to me that PG1000.txt file processed in less than 3 sec, PG26855.txt in less than a min and 17 clue 49157 Sudoku puzzles in less than half min:

Code: Select all

Total Sudoku puzzle read   : 26855
Total time for all puzzles : 57171.000000
Average time per puzzle    : 2.128877
Number of valid puzzles    : 0
Time for valid puzzles     : 0.000000
Average time per valid     : 0.000000
Number of invalid puzzles  : 0
Time for invalid puzzles   : 0.000000
Average time per invalid   : 0.000000
Number of solved puzzles   : 26855
Time for solved puzzles    : 57171.000000
Average time per solved    : 2.128877
Number of unsolved puzzle  : 0
Time for unsolved puzzles  : 0.000000
Average time per unsolved  : 0.000000

Code: Select all

Total Sudoku puzzle read   : 49157
Total time for all puzzles : 18289.000000
Average time per puzzle    : 0.372053
Number of valid puzzles    : 0
Time for valid puzzles     : 0.000000
Average time per valid     : 0.000000
Number of invalid puzzles  : 0
Time for invalid puzzles   : 0.000000
Average time per invalid   : 0.000000
Number of solved puzzles   : 49157
Time for solved puzzles    : 18289.000000
Average time per solved    : 0.372053
Number of unsolved puzzle  : 0
Time for unsolved puzzles  : 0.000000
Average time per unsolved  : 0.000000

Note: DOS command:

Code: Select all

echo.|time & rjsolbit>rj.txt & echo.|time

R. Jamil

[m_b_metcalf]

Believe to me that PG1000.txt file processed in less than 3 sec, PG26855.txt in less than a min and 17 clue 49157 Sudoku puzzles in less than half min:

Thank you. Incidentally, what are the equivalent times for JSolve and ZSolve, just for PG26855?

Regards,

Mike Metcalf

[rjamil]

Hi Mike Metcalf,

Thank you. Incidentally, what are the equivalent times for JSolve and ZSolve, just for PG26855?

My program is not in a position to compare with any solver in terms of speed. But, now it is able to solve all puzzles within reasonable time.

What I need is help to compile Zhou's ZSolver as I did not able to get results from it.

I modified ZSolver.CPP and made some tweaking, now it gets invalid puzzles for above mentioned 2 Sudoku puzzles only out of 375.

R. Jamil

[m_b_metcalf]

Believe to me that PG1000.txt file processed in less than 3 sec, PG26855.txt in less than a min and 17 clue 49157 Sudoku puzzles in less than half min:

Thank you. Incidentally, what are the equivalent times for JSolve and ZSolve, just for PG26855?

Jason, are you in a position to provide this information (to one solution)? Thanks,

Mike