BB Sudoku V1.0

briturner · Posted: Sun Oct 11, 2009 5:53 pm Post subject: BB Sudoku V1.0

Greetings,

Here is the latest BB Sudoku release. This was mainly driven by a request to clarify the copyright so others can use this in their own programs. I clarified this with allowing this code to be freely used for personal, educational, or non-commercial uses (providing the notice is kept).

There are a few minor changes, and gfs suggested a change to the makeGuess routine that provided around a 10% improvement.

The files are available at http://sites.google.com/site/bbsudokufiles (thanks to lkSudoku for setting up the easier download site)

wapati · Posted: Sun Oct 11, 2009 9:38 pm Post subject:

For big changes I get hardware. Niggles, who cares?

Adak · Posted: Mon Oct 12, 2009 6:38 am Post subject:

I have version 0.5 of your solver (with just a few tweaks), running with my grid searcher program. It may not be the fastest version, but it does a fine job, running 24/7 on a Win 7 pc.

Congratulations Brit, on improving your already awesome solver, yet again.

PIsaacson · Posted: Tue Oct 13, 2009 7:09 am Post subject:

Brian,

Thanks for releasing the code to the general public. The first adaptation is probably going to be used for producing a minimal puzzle generator that has controlled bias. I posted for our Sudoku Players' Forum the following link containing mods to make your solver code a callable library for one of our generic generators: http://pisaacson.fileave.com/Sudoku/suexg-cb.zip

If you want to follow the thread to see how your code is being used, it's http://www.sudoku.com/boards/viewtopic.php?t=14615

sudoking · Posted: Tue Oct 20, 2009 11:28 am Post subject:

An interesting algorithm. However, when I loaded it into a .net 1.1 project it wouldn't compile. Then I saw this line:

sudoking · Posted: Tue Oct 20, 2009 12:37 pm Post subject:

I also get the following warning when I compile:

bb_sudoku_solver.cpp(702) : warning C4146: unary minus operator applied to unsigned type, result still unsigned

This occurs in the "MakeGuess" function. Here's the line in question:

humble_programmer · Posted: Tue Oct 20, 2009 12:38 pm Post subject:

sudoking · Posted: Tue Oct 20, 2009 1:31 pm Post subject:

lkSudoku · Posted: Tue Oct 20, 2009 5:22 pm Post subject:

Including C file sources is not something I encounter often

While it is true that in some cases, optimization is done on single files (such as call tail or inline optimizations etc), in modern compilers and linkers there is an option to perform optimization on multiple files

In microsoft MSVC this is the Whole Program Optimization option, or LTCG flag

Other compilers and linkers have their specifc flags

briturner · Posted: Tue Oct 20, 2009 9:27 pm Post subject:

Greetings,

I can address the 2 issues raised:

1) The include of .cpp file : This was on purpose, and, while it may or may not help with the optimization, it was really for simplicity's sake. I did not want to include a make file, so this method allowed me to still compile with a simple command line like "gcc -O3 -lrt -xc -obb_sudoku.out bb_sudoku.cpp". I thought I made this clear in the comments, right after the file list, but I should have made it more clear at the include point.

2) v = v & -v; is correct. It is a bit twiddle method for finding a set bit. The '-' is really being used to gets the 2s compliment of the binary value, and not really the negative of the value. Therefore, you can ignore the error.

brit

sudoking · Posted: Wed Oct 21, 2009 10:37 am Post subject:

sudoking · Posted: Thu Oct 22, 2009 1:12 pm Post subject: Another performance improvement.

I changed the following macro, and yielded another increase in performance of about 7%.

From:

JasonLion · Posted: Thu Oct 22, 2009 7:04 pm Post subject:

That code is not portable. There is no guarantee of when the post increments will happen, they could all happen after the assignments, which would cause incorrect results.

sudoking · Posted: Thu Oct 22, 2009 8:26 pm Post subject:

JasonLion · Posted: Fri Oct 23, 2009 1:58 am Post subject:

The order of execution of post-increments relative to the expression they are in is explicitly not defined and the compiler is allowed to do it in a number of different ways. The old Borland C compiler would delay all post increments until the very end of the expression (after the assignments).

As a practical matter, most modern x86 compilers will do what you expect them to do. On other architectures, the results are less likely to be suitable. But there are no guarantees.

Writing code like this tends to cause trouble. It might work for now, but it could stop working at any time in the future. Some minor change to the compilers optimizer could change the results. If that happened, it would take quite a while before you could pin down what had gone wrong with the code.

I haven't seen anything in briturner's code that has a similar problem. There are portability issues with some of the includes and the timing routines, but they are obvious and easily fixed. Introducing an undefined order of execution issue could cause much trickier problems that would be difficult to pin down without completely understanding what the code was intended to do.

I am fairly sure that there is another way to write it which will get the speedup, without introducing order of execution ambiguity. But it will take some experimenting with the compiler to find out what it is.