The New Sudoku Players' Forum

[champagne]

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

[blue]

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]

For champagne,

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. ]

[emerentius_]

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.

[champagne]

Hi blue,

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

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.

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.

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.

[champagne]

For champagne,

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.

[blue]

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.

[JasonLion]

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.

[champagne]

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

[tdillon]

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

[zhouyundong_2012]

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]

I have read your posts for several times, at last I can understand your discussion. I have an idea to improve but I am not sure.

[zhouyundong_2012]

Why record G no matter it will change or not? So it should be recorded dynamically.

[zhouyundong_2012]

NO that is not a good idea. but I have another idea, this maybe good.
abc def hij
klm opq rst
uvw xyz zzz

datastructure
aku
blv
cmw
like this, SHRINK change to COLUMN, COLUMN change to SHRINK, it can reduce those useless check happened in innerloop.

[zhouyundong_2012]

Can AI do better than our cracker?