Bit Based Sudoku Solver (BB_Sudoku) V0.5

briturner · Last edited by briturner on Sat Nov 22, 2008 9:37 pm; edited 1 time in total

Greetings,

I have the source for ver 0.2 of the BB_Sudoku available at http://tttarabians.com/sudoku/BB_Sudoku.cpp

The only real change is that I have added support for linux, including doing usec timings. It has been tested on Windows (compiled with Visual C), and Ubuntu linux (compiled with gcc). There is no real change in the solver (maybe a few more comments added).

I did remove the pretty graphic grids under windows, and reordered the functions so the actual solver procedures are near the top.

Next step will be adding in locked candidates and then subsets.

brit

briturner · Posted: Sat Nov 08, 2008 5:15 pm Post subject:

Greetings,

for people trying to recompile, here are a couple notes:

Visual C : Use .cpp extension, Release candidate for full optimization

gcc : Use .c extension, gcc -O3 -lrt -oBB_Sudoku BB_Sudoku.c

Extensions do matter, unless you want to override the compilation. Easiest just to change the extensions. for gcc, when I use a .cpp extension, I get "error trying to exec 'cclplus': execvp: no such file or directory". Since it does not stop my testing, I have not investigated it any further.

brit

ChPicard · Posted: Tue Nov 11, 2008 6:11 pm Post subject: BB_Sudoku

Hi

Could you compile the solver for Windows and let the executable available for people?

Thank you very much

briturner · Posted: Fri Nov 14, 2008 3:46 am Post subject:

Greetings,

Some good news and some bad news:

Good news:
- I have a version 0.3, which is around 15% faster than the last version. This was done by improvements in the guess choice, resulting in slightly longer time to make a guess, but a better guess, so less iterations.
- The windows executable is here: http://tttarabians.com/sudoku/BB_Sudoku_v0.3.exe
- I started a web page, but I have not gotten far. The beta page is here: http://tttarabians.com/sudoku/BB_Sudoku.htm

Bad news:
- I have lost access to the laptop, I can not run the same comparative timings, and since my backup computer is a dual core AMD, timings are a bit less accurate due to an XP timer bug.
- Since I am now unexpectedly and retroactively unemployed, I need to spend serious time job hunting, so I will not be doing much on this for awhile.

To give you some idea of the timing, top 50000 in 1.4 seconds, top 1465 in 123 milliseconds, Sudoku17 in 1.2 seconds

brit

zerothbase · Posted: Fri Nov 14, 2008 3:47 am Post subject:

instead of:

briturner · Posted: Fri Nov 14, 2008 4:17 am Post subject:

Thanks zerothbase, that small change actually saved around 3 or 4%

I should have my source code posted soon (depending on what happens in the next day or 2). I ended up breaking it into 3 files due to the new tables used for locked candidates.

brit

ChPicard · Posted: Sun Nov 16, 2008 1:53 am Post subject: Congratulations

Hi

Your program is very fast indeed. Congratulations.
I am sure you will find a new good job.

Could you add an option to verify if the input puzzles are valid with only one solution and an option to save the solution in an output file?

Thank you very much

ChPicard from Montreal

JasonLion · Posted: Sun Nov 16, 2008 3:14 am Post subject:

I have a couple of suggestions for possible improvements.

You could be faster at spotting invalid clues if InitGrid checked for obvious conflicts. Right now invalid puzzles like like:

briturner · Posted: Wed Nov 19, 2008 8:21 pm Post subject:

Thanks JasonLion for the suggestions, and zerothbase. I have implemented the above suggestions, along with locked candidates. I now do the 11.... puzzle in no time, compared to something like 25 seconds before. I have only found 1 puzzle out of some 106600+ puzzles posted in various places that takes more then 1 millisecond to solve.

Subsets are not in yet. I can think of 2 ways to do subsets, and I implemented 1, but I want to test out the other method before including that. Free time has been somewhat scarce lately, so progress is slow.

1 question before I release v0.4:
someone was asking about checking uniqueness, so I have 3 options: stop at first, stop at 2nd (verify uniqueness), find all solutions. But, what kind of output are people looking for?

thanks
brit

zerothbase · Posted: Thu Nov 20, 2008 12:00 am Post subject:

From my perspective, I'm usually only interested in 1 full solution, but may want to see 1, 2 or N for the count of solutions. As long as there is the option to change the cutoff point at 1, 2 or all, I think you're fine.

One suggestion - you might want to think about moving some of the code out of the main routine so that it is more like an API that could be used in other programs rather than tangled together and only usable from the command line. That is, only have the timing and file I/O in the main routine which calls other functions. Assuming there isn't a huge speed hit by doing so. I'm just thinking that your code is fast enough to become the new standard in sudoku solvers and thus may be useful to other programmers who want to create larger projects based upon your solver.

Also, I'm seeing some weird issues with the linux timing code. I'm guessing that it is overflowing the variables somewhere. I'm not sure how you feel about the added realtime library (-lrt). As an alternative sys/time.h also contains a function gettimeofday that works pretty well too with no library issues (http://dell5.ma.utexas.edu/cgi-bin/man-cgi?gettimeofday+2). It is also defined in POSIX so it is fairly portable across various *nixes.

briturner · Posted: Thu Nov 20, 2008 3:56 pm Post subject:

Greetings,

I do appreciate everyones suggestions. I had already broken the build into 3 files, 1 for the solver, 1 for tables, and 1 for the interface code that calls the solver.

Here is a link to the code and a windows executable : http://tttarabians.com/sudoku/BB_Sudoku_v04.zip

For my first rev, I just broke 2 seconds on the top 50000. This version is now under 1.4 seconds, so we are looking at a 30% improvement. Improvements is even better on the top_1465 with over a 65% improvement.

Improvements:
- Locked Candidates testing is now preformed
- Process Singles has new tables to not repeat marking cells
- Added error checking to abandon bad grids faster
- The solver code is separated from the calling code
- D2 option is gone (display all solutions)

Removing D2 was needed to allow the solver to be separated into an independent routine. I still display globals, but they are not needed if you want to run the solver separately. This has not been thoroughly tested yet, so if anyone sees anything, let me know.

Now, on timings:
For timings, I found the only reliable method is to run on a dual core intel while plugged in (no power saving mode). There may be other ways, but this is the only reliable method I have here.
- Linux : I tried increasing the priority of the thread, but it was still preempted sometimes, causing unreliable timings of sometimes 20% variations. If someone has a good way around this, I will add it to the code.
- AMD : there is a known bug with XP and the timers that are seen with dual core processors or processors that change frequency when running. This seems to cause negative times for puzzles at times (around 10 out of 100,000 puzzles). I heard it was fixed in Vista, but I do not run that.

Here are my top 3 puzzles for the longest solving time :

JasonLion · Posted: Thu Nov 20, 2008 9:20 pm Post subject:

Here is the code I use for getting the time on Mac/Linux/BSD/Sun:

zhouyundong · Posted: Sat Nov 22, 2008 10:57 am Post subject: very very good sodoku software

I am a Chinese,English is poor! Say Sorry to Reader!
it solve such as follow's
000000010400000000020000000000050407008000300001090000300400200050100000000806000
000000010400000000020000000000050604008000300001090000300400200050100000000807000
000000012000035000000600070700000300000400800100000000000120000080000040050000600
000000012003600000000007000410020000000500300700000600280000040000300500000000000
000000012008030000000000040120500000000004700060000000507000300000620000000100000
060040000700000030000001000000300080010000500000200000300750000009000104000000600
060040000800000030000001000000300080010000500000200000300750000009000104000000600
more than 40000's soduku puzzle, within 20 hours
But here,i found no "upload" button,that means I can not give it to you here.... Crying or Very sad

/******************************************************************
* Author: Zhou Yundong
* Time: 20080516 00:19
******************************************************************/
#include "Stdafx.h"
#include "Think.h"

bool readFile(char* fileName)
{
FILE *fp;
char str[82];
if((fp=fopen(fileName, "r")) == NULL)
{
return false;
}
fgets(str, 82, fp);
for(int i=0, j=0; i<137; i++)
{
if(plusTbl[i] != 0)
{
leftBoard[i] = str[j++] - '0';
}
}
fclose(fp);
return true;
}
Who can help me to "upload" my software here,i say "thanks thanks thanks" to her or him.
I need ministrator's help.

zhouyundong · Posted: Sat Nov 22, 2008 12:51 pm Post subject:

o,yours is faster than mine.
can you give time use of these:
000000010400000000020000000000050407008000300001090000300400200050100000000806000
000000010400000000020000000000050604008000300001090000300400200050100000000807000
000000012000035000000600070700000300000400800100000000000120000080000040050000600
000000012003600000000007000410020000000500300700000600280000040000300500000000000
000000012008030000000000040120500000000004700060000000507000300000620000000100000
mine is
20 ms
23 ms
11000 ms
125 ms
12000 ms
I can give the result of only one answer(I set blue led), no answer(red led) and more answers(yellow led)

Adak · Posted: Sat Nov 22, 2008 2:15 pm Post subject:

Welcome to the forum, Zhouyundong. Very Happy

You may like to try this site to host your program for free:
http://www.mediafire.com/

Be sure to get the url for your program, after you upload it, and post it here.

I ran your first two puzzles in my solver, and both were solved in "0.00 seconds". I get that because it's a Windows computer (which is running at 2.5 GHz), and the timer resolution is really not all that accurate. Also, the puzzles were solved by my programs "human" type of logic functions.

They are large, but run very fast. The puzzle grids that take it a long time to solve, are the one's where my simple "human" type of logic makes very little progress, and then a large brute force search has to be done.

My brute force search function is better than it used to be, but not really fast, yet.

I use a few files for testing:

1) Gordon's list of 17 piece Sudoku puzzles. This file has many thousands of puzzle grids, all with just one solution. I have made a sub file from that file, of the first 100 grids, and use that many times for a quick test.

Rarely, I'll run the whole file through for a longer test.

and

2) The "tough" file, (new to me), just called "Top 1465"

I look forward to seeing the rest of your solver.