3.77us Solver(2.8G CPU, TestCase:17Sodoku)

Programs which generate, solve, and analyze Sudoku puzzles

Re: 3.77us Solver(2.8G CPU, TestCase:17Sodoku)

Postby champagne » Thu Feb 21, 2019 4:14 am

Hi emerentius
Serg is testing the 32 bits version of the same code (BF128 changed as described above)

here is the last result i got from him

So, I was forced to call C++ compiler:
g++ -march=native sk_t.cpp sk_bitfields.cpp main.cpp sk_bforcev32.cpp
This time file "a.exe" was produced. It was successfully executed by command
a -c11 –ibenchmark.txt 1> out.txt
"out.txt" file's content:
brute force Go_10 entry benchmark.txt input
count 0;0;10000
total elapsed time 0s 203ms

So, It works!



The same command with sk_bforce2 instead of sk_bforcev32 should do the same in your case

I see 2 possible problems in your situation

the 64 bits instructions not supported by your g++
additional parameters creating problem -O2 ???
champagne
2017 Supporter
 
Posts: 6979
Joined: 02 August 2007
Location: France Brittany

Re: 3.77us Solver(2.8G CPU, TestCase:17Sodoku)

Postby blue » Thu Feb 21, 2019 3:46 pm

Hi champagne,

I had the same problem as emerentius_, using "-O2".

I discovered that somehow the 'zhou_i' initialization that's done in ZH_GLOBAL::ZH_GLOBAL(),
either wasn't working, or the result was somehow being trashed.
[ 'zhou_i.cells_unsolved' was set to zero at the top of main(), but all other fields were as they should be. ]

It doesn't happen without "-O2".
Adding this line at the top of main(), "fixes" the problem:
    "new (&zh_g) ZH_GLOBAL();"
Still no idea why it happens.

I have two other problems, though ...

1) First problem:

For some lists of puzzles, the code gives the proper answers, and for others it doesn't.
It doesn't matter whether I use MSVC or GCC ... I get the same results.

It works fine for the (known) 17's, and for Serg's benchmark puzzles.
One list (for pattern game #340), has with puzzles with 0, 1 and 2+ solutions, and it works fine for those.

For other lists, some multi-solution puzzles are reported as having 0 solutions.
(I haven't seen a problem with a 1-solution puzzle yet, but maybe I haven't done enough testing
    Added: an old list of yours, with 24411 puzzles containing exocets, tests just fine).
Here's a short list of "problem" puzzles.
Hidden Text: Show
Code: Select all
12..........79...27..23.5..21...7...67..29...9...6..573916.2...5679....3..25.3.6.
12....78.45.7.81..78..13...275834..1.31.7.4.88.4..137.3425...17..71...5..183.7...
...4.76894.6.8.327789.6..4...8...4.6.67.4.8.2...6.87.....89.27487.......3.......8
1..45.....5.1....3....6...1...51..4..75..9.1...1......597...16.61..75.9....6917..
123...6.9..61.92377.92631.52.5....9.6.19...52...5327163.2.9..6..6..2.97...7..152.
1.3...689..6189.7.7.9.6.....68.....1..15..9.7.97.31...67..........7.....91....7.5
.....6.8.4.6....9.7.9..2.6......49.6.14..7.........4.1.4789.612.6.24......2....4.
...45.....5....7....926....2.4..1.........49..7...4..........64.4...9...6...45.12
129.5.7...5.78.1.278.2.15..2.51...7.8.752.......86725..72.15..65916.8.27..8.72.15
.2...6......7..13...3...5..2.5....6.3.7..2...8.1..................53.....7.1..8..
1.6...........9...7....25.....94.1.6.6.....9.9..76...........67..2..5....9.....54
12...76..4.6...27.7.92...1.2.174.........81........8...1.......86...1...9...7..21
1.345.....5....3.7.8....5.1..5.3..1...4.7..53.31..5..6.67..18...1........4.5..13.
1....67.94567.9.2.7.9....6.2.....47.6......5..97.61....1....29..6..9..1.97.....4.
1.34576...2.1....77.......127463.1..6.571...3.31....76.67..1....1..2.76....57631.
...75.6..4.6....3.7.9.........6..5..6.......19.7..3.6..7..1..4..9...4.7..64......
..34567.9.56..9...8.9..3.....5..7.6......4....3....4..3.4....575.8...39497.345...
.2..5678..56.8.....8....6.5....6859.56..9782.9.85...6....6.59.869.8...5.845....76
...4.3..94.6.89..2..92....4......9.7...972846947....23..2...76....32.49...4..623.
1.....7.....7892.17..1.2.....891..7.......6..5.....1.26....5.9.8......17...8.1.26
1..45....4.....1.....1325.4.9.8.3.1..48....25.......48...9..8..8.4.....19.2...45.
..34.....456...1.3..91....4..8..5.3....8.....9...4...8.9....81..6..9835.8........
.23....8.....8..26789.3....2.8347....6....8.....6.84.....8.3.47........884..6....
19..5.....5.....3....13.546..7...9.3...9714.5...3.4...6....3..4....9..7..........
13..5....45....132....1.54.........551.......9.43.5....95.2......158.29..42.3..5.
.23...7.....7...3.78923.5.6.6..95..3....73....3.....5.3....7..2...3........5..368
.....6..94.6..9...789....64.9.17.4...3.9......6......1.4...761..1...3....7....84.
...4...8.4..5.9...7...3...4..894.....4.....9....3684.55....4.....4.....3.....3647
...456789456789..2789.2.5462.......4..4....27.......58.9...846.......895......27.
.2....4.9....89..2.89132...2..9......48....9..9......13..26.94.8.4.9.32.9.2......
.2......9....8.2...89312........468.3.8......9.4..........6..4..4.......8..14...3
...4....9456......789.......7.....5.....9..7...4....1...1...8..8.7165........7..1
124...789....891.2.....2...2.....9....89...2.6...2.4....2.9.8.....24.69...7...21.

You should probably test those with your MSVC-compiled code.
I use MSVS 2012 ... and I trust it ... but you have "inttypes.h", so you must be using 2013 or later.
[ The only change I needed, was to use "stdint.h" insted of "inttypes.h" ... "#if (_MSC_VER <= 1700) ... #else ..." ]

2) Second problem:

For one list of puzles (17 clues, multiple solutions) ... the GCC-compiled code crashes on some puzzles.
It only happens for GCC-compiled code, and it doesn't matter whether it's "-O2" or "-O0".
[ The MSVC-compiled code, doesn't crash, it just gives "0 solutions" for some of the puzzles ... 9 of 10000 99 of 10000 ]
    Added: My mistake on the count.
    Also, see next post: crash problem solved !
These are a few of those puzzles that caused (GCC) crashes:
[ There are many more ... in particular, more than the 9 where the MSVC code reported 0-solutions. ]


Hidden Text: Show
Code: Select all
81..3.9........2....4..2......7..8.......4.615..................7.81....9........
...86..........9..4...5.....8......1..2...4..5...1...7....7......1....6.......3.5
...8..5......4............23...9.6..1....7..........9...85.......1....6..4..2.3..
.7..9.3.....8....96..........5..6......4.....34...17.......21..........8...3.....
.7.5.......3.6........1.4.........9...7.2.....4.9...........15...2......8..3....7
....9.....5...72..6....3.7...5....94..7....3...........9..8.......1.......6....2.

For that problem, I was able to catch the crash, by adding lines like these, in (4) places in Zhn_cpp.h
-- places where a structure at "this + 1" is about to be used.

There was one for zh1d[10] slots, and 3 more for "zhou[50]" slots ... assuming I didn't miss anything.
Code: Select all
if (((this + 1) - zh1d) >= sizeof(zh1d) / sizeof(zh1d[0]))
{
   cout << "  *** zh1d depth ***" << endl;
   exit(0);
}

The one for "zh1d[10]" caught the crashes, oddly enough !

For MSVC code, and GCC code for other puzzle lists, and whether I'm getting incorrect results or not ...
none the code above is ever triggered.

---

P.S.: I saw an error in your non-MS code in "sk_bitfields.h".
It was in a routine that isn't used in this app.
I'm sure you can spot it.
Hidden Text: Show
Code: Select all
   inline void SetToBit(const int theBit) {
      if (theBit < 64) {
         bf.u64[1] = (uint64_t)0;
         bf.u64[0]=(uint64_t) 1<< theBit;
      }
      else {
         bf.u64[0] = (uint64_t)1;
         bf.u64[1] = (uint64_t)1 << (theBit-64);
      }
   }
blue
 
Posts: 877
Joined: 11 March 2013

Re: 3.77us Solver(2.8G CPU, TestCase:17Sodoku)

Postby blue » Thu Feb 21, 2019 4:57 pm

For champagne,

blue wrote:For one list of puzles (17 clues, multiple solutions) ... the GCC-compiled code crashes on some puzzles.
It only happens for GCC-compiled code, and it doesn't matter whether it's "-O2" or "-O0".

You need to change your "bitscan..." #defines for non-MS builds:

Code: Select all
#if 0 // original
#define bitscanforward64(res, src) (res = __builtin_ctzll(src))
#define bitscanforward(res, src) (res = __builtin_ctz(src))
#define bitscanreverse64(res, src) (res = __builtin_clzll(src) ^ 63)
#define bitscanreverse(res, src) (res = __builtin_clz(src) ^ 31)
#else // fixed
#define bitscanforward64(res, src) (!(uint64_t)(src) ? 0 : ((res = __builtin_ctzll(src)), 1))
#define bitscanforward(res, src)   (!(uint32_t)(src) ? 0 : ((res = __builtin_ctz(src)), 1))
#define bitscanreverse64(res, src) (!(uint64_t)(src) ? 0 : ((res = __builtin_clzll(src) ^ 63), 1))
#define bitscanreverse(res, src)   (!(uint32_t)(src) ? 0 : ((res = __builtin_clz(src) ^ 31), 1))
#endif

[ For compatibility with "while (bitscanforward(cell, myrow))" in "ZH_1D::Guess()". ]

Added: On the other hand, that's the only place in the code, where you use the return value from a MS "_Bitscan...()" routine.
So for speed elsewhere, it's better to change the code in ZH_1D::Guess(), to "while (myrows) { bitscanforward(cell, myrow); ... }"
It would be good use "(void)_Bitscan...()" for the MS #define's, too ... to guard against future problems.
OK ... that, and use "(void)(res = ...)" for the non-MS #defines.
[ I hope I'm done adding "one more line" to this post. ]
blue
 
Posts: 877
Joined: 11 March 2013

Re: 3.77us Solver(2.8G CPU, TestCase:17Sodoku)

Postby emerentius_ » Thu Feb 21, 2019 9:45 pm

champagne wrote:the 64 bits instructions not supported by your g++
additional parameters creating problem -O2 ???

The first would likely cause a compile time error. -O2 just means optimization level 2. Without that it's an unoptimized debug build.
It seems to work with the clang compiler, even with optimizations. I found that out when I tried to debug the program with clang's undefined behaviour sanitizer (ubsan). it's still possible that the errors under gcc are the result of incorrect code that just happens to work under the other compilers.
emerentius_
 
Posts: 23
Joined: 09 January 2018

Re: 3.77us Solver(2.8G CPU, TestCase:17Sodoku)

Postby champagne » Fri Feb 22, 2019 3:01 am

Hi blue,

many thanks for all these informations.
I have to work on your potst to-day, but 2 quick reactions

blue wrote:I had the same problem as emerentius_, using "-O2".

I discovered that somehow the 'zhou_i' initialization that's done in ZH_GLOBAL::ZH_GLOBAL(),
either wasn't working, or the result was somehow being trashed.
[ 'zhou_i.cells_unsolved' was set to zero at the top of main(), but all other fields were as they should be. ]

It doesn't happen without "-O2".
Adding this line at the top of main(), "fixes" the problem:
    "new (&zh_g) ZH_GLOBAL();"
Still no idea why it happens.



This is a true concern. I use the constructor to be sure to have initialisations done in global data shown as structure. If it creates a problem with gcc, I have to use a safer way.


blue wrote:Hi champagne,

For other lists, some multi-solution puzzles are reported as having 0 solutions.
Here's a short list of "problem" puzzles.
12..........79...27..23.5..21...7...67..29...9...6..573916.2...5679....3..25.3.6.


The first puzzle is in line with my expectations; 2 digits are missing. when I added the check on the number of digit used, It was easier to report the puzzle as "not valid". I never came back on this and in fact, at this early control, I can not exclude the case "0 solution".

I'll see what to do, may be a separate count for these puzzles.

blue wrote:
2) Second problem:

...


For this and following posts, I have to work on your posts,
BTW I have one more reason to look for a good compatibility with LINUX, I hope to catch some free cycles in LINUX to run the 566 656 search of 17 when I am back in France. This code is part of the bigger program.
Last edited by champagne on Fri Feb 22, 2019 7:06 am, edited 1 time in total.
champagne
2017 Supporter
 
Posts: 6979
Joined: 02 August 2007
Location: France Brittany

Re: 3.77us Solver(2.8G CPU, TestCase:17Sodoku)

Postby champagne » Fri Feb 22, 2019 7:03 am

blue wrote:For champagne,

blue wrote:For one list of puzles (17 clues, multiple solutions) ... the GCC-compiled code crashes on some puzzles.
It only happens for GCC-compiled code, and it doesn't matter whether it's "-O2" or "-O0".

You need to change your "bitscan..." #defines for non-MS builds:

Code: Select all
#define bitscanforward64(res, src) (!(uint64_t)(src) ? 0 : ((res = __builtin_ctzll(src)), 1))
#define bitscanforward(res, src)   (!(uint32_t)(src) ? 0 : ((res = __builtin_ctz(src)), 1))
#define bitscanreverse64(res, src) (!(uint64_t)(src) ? 0 : ((res = __builtin_clzll(src) ^ 63), 1))
#define bitscanreverse(res, src)   (!(uint32_t)(src) ? 0 : ((res = __builtin_clz(src) ^ 31), 1))

[ For compatibility with "while (bitscanforward(cell, myrow))" in "ZH_1D::Guess()". ]

Added: On the other hand, that's the only place in the code, where you use the return value from a MS "_Bitscan...()" routine.
So for speed elsewhere, it's better to change the code in ZH_1D::Guess(), to "while (myrows) { bitscanforward(cell, myrow); ... }"
It would be good use "(void)_Bitscan...()" for the MS #define's, too ... to guard against future problems.
OK ... that, and use "(void)(res = ...)" for the non-MS #defines.


Oh thanks again,

no problem with the file on my side.

in the full code, the use of loops like
"while (bitscanforward(cell, myrow))"
are very common, so, I have to go in your direction.
On the other side, adding a front test does not change the overall performance and this is far to be a critical code.
So I'll enter the revised code in sk_t.h ti-day.
champagne
2017 Supporter
 
Posts: 6979
Joined: 02 August 2007
Location: France Brittany

Re: 3.77us Solver(2.8G CPU, TestCase:17Sodoku)

Postby blue » Fri Feb 22, 2019 11:01 am

champagne wrote:
blue wrote:Hi champagne,

For other lists, some multi-solution puzzles are reported as having 0 solutions.
Here's a short list of "problem" puzzles.
12..........79...27..23.5..21...7...67..29...9...6..573916.2...5679....3..25.3.6.


The first puzzle is in line with my expectations; 2 digits are missing.
(...)

Ahh, but of course.
I saw that in the code, and then promptly forgot about it :(

Thanks.
blue
 
Posts: 877
Joined: 11 March 2013

Re: 3.77us Solver(2.8G CPU, TestCase:17Sodoku)

Postby JasonLion » Sat Feb 23, 2019 8:32 pm

champagne wrote:I think that Jasonlion maintains a pure 32 bit version to use it on other chips (to be confirmed by him)

In my work I mostly target iOS, which is currently arm64. While arm64 does have a few 128 bit instructions, they don't have a complete enough set of them for this kind of usage. Thus I focus most of my work on pure 32 or 64 bit algorithms that port well to arm.
User avatar
JasonLion
2017 Supporter
 
Posts: 641
Joined: 25 October 2007
Location: Silver Spring, MD, USA

Re: 3.77us Solver(2.8G CPU, TestCase:17Sodoku)

Postby champagne » Sun Feb 24, 2019 4:04 am

champagne wrote:I promised to produce a new variant of the brute force if I had something of interest.
I already stated that benchmarking of the brute force with small improvements is difficult, however, my feeling is that this version is significantly faster than the previous one.

The original code is located within my new skmpp2 frame, I prepared a stand alone version with (at least in the brute force files) only the necessary code to run a basic brute force;

In this variant, the best improvement is IMO the selection of the bi-value cell to apply.
I introduced also a quite new way to guess, all “one digit” potential solutions.

I suspect that we have still here some room for improvement, but I have to focus on the 17 clues search for the next weeks.

The code is stored in a specific repository here

And I prepared comments on this variant available here

Normally, this code can work with LINUX, but I only verified than gcc can compile it.


Thanks to all contributors to the debugging of this code, especially blue and mathimagics.

To fix the -O2 bug, I replaced the constructor initialisation by a table
And I entered the gcc compatibility rules of blue in sk_t.h

The repository has just been updated
champagne
2017 Supporter
 
Posts: 6979
Joined: 02 August 2007
Location: France Brittany

Re: 3.77us Solver(2.8G CPU, TestCase:17Sodoku)

Postby tdillon » Fri Jun 14, 2019 10:35 am

Hi All,

I've recently caught the Sudoku solver-writing bug and came across this forum looking for something to benchmark against.

I hope my new solver may be of interest to folks here. It was certainly an interesting journey for me.

You can find the code here, and a fairly extensive write up of the Solver's development and design here

To whet your appetite, I offer these results:

Code: Select all
|puzzles2_magictour_top1465            |  puzzles/sec|  usec/puzzle|   %no_guess|  guesses/puzzle|
|--------------------------------------|------------:| -----------:| ----------:| --------------:|
|jczsolve                              |   123,779.7 |         8.1 |       2.3% |          12.53 |
|tdoku_dpll_triad_simd                 |   165,371.1 |         6.0 |       7.9% |           6.13 |


The solver is aimed at harder puzzles, and it gets faster still (relatively speaking) on harder datasets.

Cheers, Tom
tdillon
 
Posts: 20
Joined: 14 June 2019

Re: 3.77us Solver(2.8G CPU, TestCase:17Sodoku)

Postby zhouyundong_2012 » Fri Jun 14, 2019 11:28 am

Do you know the game Chromation?
It seems that I am the only one who have written solver for it.
I'd like to share the source code with you.
As clean as my sudoku solver code, much more excellent.

And, I need your help to make a revolutionary improvements.
zhouyundong_2012
 
Posts: 144
Joined: 10 February 2012

Previous

Return to Software