The New Sudoku Players' Forum

[Mathimagics]

Unhappily, I can't do anything

That's quite all right! I have a means by which I can read it, no need for you to do anything.

And I do intend to have a look at your solver(s) as soon as I can spare some time!

Cheers
MM

[Serg]

Hi, 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.

I am using JCZsolve Sudoku solver in my exhaustive search projects for 3 years. It is really fast and works well. Many thanks to Zhou, Jason and you!

It would be interesting to try your SK_BFORCE solver, but I did't managed to understand the way to produce your solver. Too many files are placed in GitHub. What files are necessary for SK_BFORCE? How those files can be loaded? (I have no experience in GitHub usage.)

If I would make your solver, I could compare it with JCZsolve on by own benchmark, containing puzzles from real exhaustive search project (almost all of them have multiple solutions).

Serg

[champagne]

It would be interesting to try your SK_BFORCE solver, but I did't managed to understand the way to produce your solver. Too many files are placed in GitHub. What files are necessary for SK_BFORCE? How those files can be loaded? (I have no experience in GitHub usage.)

If I would make your solver, I could compare it with JCZsolve on by own benchmark, containing puzzles from real exhaustive search project (almost all of them have multiple solutions).

Serg

Hi Serg,

I don't know if you are working in windows or Linux mode.
Anyway, (I am commenting on the SK_BFORCE repository), all files are compulsory and have a design in line with gcc constraints.
Each .cpp file is compiled separatly
Files having mainly code but included in .cpp files have a name xxx_cpp.h

So the project has four separate lots to compile

sk_t.cpp
sk_bitfield.cpp

both general functions or class definitions serving all programs (in the head part of sk_t.h are all the compatibility rules windows/linux)

main.cpp
the common handling of the command line and brute force in my bigger repository SKMPP2

sk_bforce.cpp the commands specific to this program.

For sure, this code should be reoganized differently by a user wanting to merge it with its own code.

If you are working with microsoft visual c++, the project definition is in the repository.

To compile with gcc, I used the command
gcc -march=native sk_t.cpp sk_bitfields.cpp main.cpp sk_bforce.cpp 2> error.txt 1> cout.txt
I did not produce the Linux exec.

So you need all sources of the repository to produce the code. You have in Github the button clone or download to do it.

I can also make my .exe (windows) available somewhere if this can help.

[Mathimagics]

I'm pretty sure that Serg is running Windows on a laptop ...

[champagne]

I'm pretty sure that Serg is running Windows on a laptop ...

In such a case, the quickest way to benchmark this code is surely to get the .exe

[Serg]

Hi, champagne!
Thank you for your help!
I am using Windows 7 (32-bit) in my notebook and I am using gcc (all my code is written on traditional C).

To compile with gcc, I used the command
gcc -march=native sk_t.cpp sk_bitfields.cpp main.cpp sk_bforce.cpp 2> error.txt 1> cout.txt

I downloaded zip-file and got directory "skmpp2-master".
Then I went to this directory (in command line window), executed command

gcc -march=native sk_t.cpp sk_bitfields.cpp main.cpp sk_bforce.cpp

and got error message "gcc: error: CreateProcess: No such file or directory".

Maybe gpp is necessary? (I didn't install it.)

Serg

[champagne]

Hi, champagne!
Thank you for your help!
I am using Windows 7 (32-bit) in my notebook and I am using gcc (all my code is written on traditional C).

To compile with gcc, I used the command
gcc -march=native sk_t.cpp sk_bitfields.cpp main.cpp sk_bforce.cpp 2> error.txt 1> cout.txt

I downloaded zip-file and got directory "skmpp2-master".
Then I went to this directory (in command line window), executed command

gcc -march=native sk_t.cpp sk_bitfields.cpp main.cpp sk_bforce.cpp

and got error message "gcc: error: CreateProcess: No such file or directory".

Maybe gpp is necessary? (I didn't install it.)

Serg

Unhappily, I know nothing about Linux.
My son Installed for me Cygwin64 Terminal on my laptop, and this is how I compile for Linux. Mathimagics could help.
I have doubts that "Cygwin64 Terminal " can be run on a 32 bits OS


(BTW, if you have a very old laptop, the -march=native parameter tells you if all intrinsic instructions are valid for your computer)

[Serg]

Hi, champagne!
I looked through your code. It is rather complicated for me. It's very likely that your solver provides extreme performance for modern CPUs only. I have rather out-of-date computer, so I decided not to waste time trying to assemble working in my environment variant of your solver. The best is the enemy of the good - JCZsolver is quite good.

Serg

[champagne]

Hi, champagne!
I looked through your code. It is rather complicated for me. It's very likely that your solver provides extreme performance for modern CPUs only. I have rather out-of-date computer, so I decided not to waste time trying to assemble working in my environment variant of your solver. The best is the enemy of the good - JCZsolver is quite good.

Serg

This makes sense.
I tried so many variants of the brute force that I can mix things, but in your posiion, I woud try to catch the best potential.

The key change is in my opinion in the process
void ZHOU::GuessBivalueInCell()
in JCZsolver, the first bi-value cell is used.
In the released code, the cell is taken in the band having the highest residual count of unsolved cells.

Here is the corresponding code (not granted optimal) in the new guess sequence

Code: Select all

   { // select band with more unsolved cells
      uint32_t nfreecells = 0, nw;
      if (zh_g.pairs.bf.u32[0]) {
         nfreecells = _popcnt32(cells_unsolved.bf.u32[0]);
      }
      if (zh_g.pairs.bf.u32[1]) {
         if (nfreecells) {
            nw = _popcnt32(cells_unsolved.bf.u32[1]);
            if (nw > nfreecells) {
               nfreecells = nw;
               zh_g.pairs.bf.u32[0] = 0;
            }
         }
         else   nfreecells = _popcnt32(cells_unsolved.bf.u32[1]);
      }
      if (zh_g.pairs.bf.u32[2]) {
         if (nfreecells) {
            nw = _popcnt32(cells_unsolved.bf.u32[2]);
            if (nw > nfreecells) {
               nfreecells = nw;
               zh_g.pairs.bf.u32[0] = 0;
               zh_g.pairs.bf.u32[1] = 0;
            }
         }
      }
   }

In fact, the program cleans bands if a better one is seen, and continue with the original process.

You could have a surprisingly good surprise.

The sequence uses here _popctn32 the windows/Linux compatible version of the microsoft visual C++ _popcnt intrinsic .

[Mathimagics]

Hi Serg,

What CPU do you actually have on that laptop??

You can use the free software tool "CPU-Z" to identify it, and that will tell you exactly what instruction sets / extensions that it supports.

Cheers
MM

[emerentius_]

In the released code, the cell is taken in the band having the highest residual count of unsolved cells.

I've adapted this change to my codebase and I'm seeing a slight downgrade for the most part, possibly a sidegrade on some datasets. Are you using the same fallback guessing procedure if no bivalue exists as jczsolve? If you really do get a speedup from that change, I suspect that the change I did to the heuristic in GuessFirstCell has a similar effect on focusing the work on the bands that are most fruitful, at least in the statistical aggregate of many sudokus.

Also, I could compile your new solver, but I can't get it to actually process any sudokus. Is this not the correct syntax?

Code: Select all

sk_bforce -c11 -i30x_hard375.txt

[champagne]

Also, I could compile your new solver, but I can't get it to actually process any sudokus. Is this not the correct syntax?

Code: Select all

sk_bforce -c11 -i30x_hard375.txt

The command is correct if the filename is 30x_hard375.txt

I run a file T_1_313.txt and got the following cout print

brute force Go_10 entry T_1_313.txt input
count 0;32601;0

total elapsed time 0s 611ms

I've adapted this change to my codebase and I'm seeing a slight downgrade for the most part, possibly a sidegrade on some datasets. Are you using the same fallback guessing procedure if no bivalue exists as jczsolve? If you really do get a speedup from that change, I suspect that the change I did to the heuristic in GuessFirstCell has a similar effect on focusing the work on the bands that are most fruitful, at least in the statistical aggregate of many sudokus.

This can be very close to the changes made by you in the guess process. In the released brute force, if no cell bivalue exists, a hidden bivalue is applied (row or box) and the default is the set of" one digit solutions" for the digit with the lowest count.

[emerentius_]

I compiled it without optimizations and now it works. With optimizations, all puzzles are counted in the leftmost column as invalid sudokus.
You may be depending on undefined behaviour somewhere. I'm using g++ version 7.3.0 on Ubuntu.

[Serg]

Hi, Mathimagics!

Hi Serg,

What CPU do you actually have on that laptop??

You can use the free software tool "CPU-Z" to identify it, and that will tell you exactly what instruction sets / extensions that it supports.

This is CPU-Z report:

Code: Select all

Processors Information
-------------------------------------------------------------------------
   Number of cores         2 (max 2)
   Number of threads       2 (max 2)
   Name                    Intel Mobile Core 2 Duo T8300
   Codename                Penryn
   Specification           Intel(R) Core(TM)2 Duo CPU     T8300  @ 2.40GHz
   Package (platform ID)   Socket P (478) (0x7)
   CPUID                   6.7.6
   Extended CPUID          6.17
   Core Stepping           M0
   Technology              45 nm
   Core Speed              2493.6 MHz
   Multiplier x Bus Speed  12.5 x 199.5 MHz
   Base frequency (cores)  199.5 MHz
   Base frequency (ext.)   199.5 MHz
   Rated Bus speed         798.0 MHz
   Stock frequency         2400 MHz
   Instructions sets       MMX, SSE, SSE2, SSE3, SSSE3, SSE4.1, EM64T, VT-x
   Microcode Revision      0x60F
   L1 Data cache           2 x 32 KBytes, 8-way set associative, 64-byte line size
   L1 Instruction cache    2 x 32 KBytes, 8-way set associative, 64-byte line size
   L2 cache                3072 KBytes, 12-way set associative, 64-byte line size
   Max CPUID level         0000000Ah
   Max CPUID ext. level    80000008h
   Cache descriptor        Level 1, D, 32 KB, 1 thread(s)
   Cache descriptor        Level 1, I, 32 KB, 1 thread(s)
   Cache descriptor        Level 2, U, 3 MB, 2 thread(s)
   FID/VID Control         yes
   FID range               6.0x - 12.0x
   Max VID                 1.138 V

   IBRS                    not supported
   IBPB                    not supported
   STIBP                   not supported
   RDCL_NO                 no
   IBRS_ALL                not supported

   Temperature 0           39 degC (102 degF) (Core #0)
   Temperature 1           37 degC (98 degF) (Core #1)
   Clock Speed 0           n.a. (Core #0)
   Clock Speed 1           n.a. (Core #1)

Serg

[Mathimagics]

Serg,

Thanks for that info. Your CPU has SSE4.1 capability, so it is not so ancient, and can most probably run my dSolver (which is based on Mladen's fsss2 solver). It can almost certainly handle champagne's code too.

I won't hijack champagne's thread any further, I will contact you by PM.

But meanwhile install g++, you'll need it to build the solver. You don't need it for anything else, as dSolver has a standard C API, so it is callable from traditional C (gcc) programs.

You can have much better than "quite good", I think. If you wish ...

Cheers
MM