Sudoku Programmers Forum Index

 
 FAQFAQ   SearchSearch   MemberlistMemberlist   UsergroupsUsergroups   RegisterRegister   ProfileProfile   Log inLog in          Games  Calendar

Log in to check your private messagesLog in to check your private messages   

Bit Based Sudoku Solver (BB_Sudoku) V0.5
Goto page 1, 2, 3, 4, 5, 6, 7, 8, 9  Next
 
Post new topic   Reply to topic    Sudoku Programmers Forum Index -> Programming sudoku
View previous topic :: View next topic  
Author Message
briturner

Joined: 14 Oct 2008
Posts: 75
:

Items
PostPosted: Sat Nov 08, 2008 2:16 am    Post subject: Bit Based Sudoku Solver (BB_Sudoku) V0.5 Reply with quote

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


Last edited by briturner on Sat Nov 22, 2008 9:37 pm; edited 1 time in total
Back to top
View user's profile Send private message
briturner

Joined: 14 Oct 2008
Posts: 75
:

Items
PostPosted: Sat Nov 08, 2008 5:15 pm    Post subject: Reply with quote

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
Back to top
View user's profile Send private message
ChPicard

Joined: 12 Mar 2008
Posts: 82
:
Location: Montreal, Canada

Items
PostPosted: Tue Nov 11, 2008 6:11 pm    Post subject: BB_Sudoku Reply with quote

Hi

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

Thank you very much
Back to top
View user's profile Send private message
briturner

Joined: 14 Oct 2008
Posts: 75
:

Items
PostPosted: Fri Nov 14, 2008 3:46 am    Post subject: Reply with quote

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
Back to top
View user's profile Send private message
zerothbase

Joined: 02 Nov 2008
Posts: 17
:

Items
PostPosted: Fri Nov 14, 2008 3:47 am    Post subject: Reply with quote

instead of:
Code:

for (t = 1; t < 0x01FF; t = t << 1)
     if (t & t3)

try
Code:

t = t3&-t3;


slightly faster
Back to top
View user's profile Send private message
briturner

Joined: 14 Oct 2008
Posts: 75
:

Items
PostPosted: Fri Nov 14, 2008 4:17 am    Post subject: Reply with quote

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
Back to top
View user's profile Send private message
ChPicard

Joined: 12 Mar 2008
Posts: 82
:
Location: Montreal, Canada

Items
PostPosted: Sun Nov 16, 2008 1:53 am    Post subject: Congratulations Reply with quote

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
Back to top
View user's profile Send private message
JasonLion

Joined: 16 Nov 2008
Posts: 62
:
Location: Silver Spring, MD

Items
PostPosted: Sun Nov 16, 2008 3:14 am    Post subject: Reply with quote

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:
Code:
11...............................................................................
take a while even though it would be easy to spot the two 1s in row 1/block 1 as a conflict.

You could pick up a several percent in ProcessSingles if you had a list of neighbors for every cell. Then you would only need to check 20 cells instead of 27.

One other thing to keep in mind: the puzzles that a puzzle generator needs checked in the process of creating a puzzle have very different properties than the collections you have reported testing against. One of my solvers is one quarter the speed of yours on top1465, but twice as fast at the partial puzzles my generator needs double checked during the generation process.
Back to top
View user's profile Send private message
briturner

Joined: 14 Oct 2008
Posts: 75
:

Items
PostPosted: Wed Nov 19, 2008 8:21 pm    Post subject: Reply with quote

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
Back to top
View user's profile Send private message
zerothbase

Joined: 02 Nov 2008
Posts: 17
:

Items
PostPosted: Thu Nov 20, 2008 12:00 am    Post subject: Reply with quote

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.
Back to top
View user's profile Send private message
briturner

Joined: 14 Oct 2008
Posts: 75
:

Items
PostPosted: Thu Nov 20, 2008 3:56 pm    Post subject: Reply with quote

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 :
Code:
1.......2.9.4...5...6...7...5.9.3.......7.......85..4.7.....6...3...9.8...2.....1
174385962293467158586192734451923876928674315367851249719548623635219487842736591 - Solved        Time =  1070.81 usec

1.......2.9.4...5...6...7...5.964......8.........35.4.7.....6...3...9.8...2.....1
175398462298476153346251798851964327463827519927135846719582634634719285582643971 - Solved        Time =   848.71 usec

1.......2.3.4...5...6...7...5.8.4.......73......9...8.7.....6...4...8.9...2.....1
174395862238467159596182734351824976829673415467951283713549628645218397982736541 - Solved        Time =   802.06 usec


I apologize, but I do not have the source of these puzzles. If someone recognizes them, let me know and I will give them credit.

brit
Back to top
View user's profile Send private message
JasonLion

Joined: 16 Nov 2008
Posts: 62
:
Location: Silver Spring, MD

Items
PostPosted: Thu Nov 20, 2008 9:20 pm    Post subject: Reply with quote

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

#include <time.h>
#include <sys/time.h>
#ifdef __linux__
#include <sys/timeb.h>
#endif

#if defined(__FreeBSD__) || defined(__OpenBSD__) || defined(__NetBSD__) || defined(__APPLE__) || defined(sun)
#define BSD_STYLE
#endif


long
FineTime(void)               // Relative time in 1000ths of a second
{
#ifdef BSD_STYLE
   struct timeval tm;
   struct timezone z;
   static time_t base = 0;

   gettimeofday(&tm,&z);
   if (!base) base=tm.tv_sec;
   return((tm.tv_sec-base)*1000+tm.tv_usec/1000);
#else
   struct timeb tm;
   static time_t base = 0;

   ftime(&tm);
   if (!base) base=tm.time;
   return((tm.time-base)*1000+tm.millitm);
#endif
   }


On Unix like systems it would probably be better to use the user CPU time from getrusage, but I have never bothered with that.
Back to top
View user's profile Send private message
zhouyundong

Joined: 22 Nov 2008
Posts: 43
:

Items
PostPosted: Sat Nov 22, 2008 10:57 am    Post subject: very very good sodoku software Reply with quote

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.


Last edited by zhouyundong on Tue Nov 25, 2008 5:16 pm; edited 1 time in total
Back to top
View user's profile Send private message Send e-mail
zhouyundong

Joined: 22 Nov 2008
Posts: 43
:

Items
PostPosted: Sat Nov 22, 2008 12:51 pm    Post subject: Reply with quote

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)
Back to top
View user's profile Send private message Send e-mail
Adak

Joined: 27 Feb 2008
Posts: 87
:

Items
PostPosted: Sat Nov 22, 2008 2:15 pm    Post subject: Reply with quote

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.
Back to top
View user's profile Send private message
Display posts from previous:   
Post new topic   Reply to topic    Sudoku Programmers Forum Index -> Programming sudoku All times are GMT
Goto page 1, 2, 3, 4, 5, 6, 7, 8, 9  Next
Page 1 of 9

 
Jump to:  
You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot vote in polls in this forum
Sudoku Programmers topic RSS feed 


Powered by phpBB © 2001, 2005 phpBB Group

Igloo Theme Version 1.0 :: Created By: Andrew Charron