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   

Backtracking solver by a forum newb
Goto page 1, 2  Next
 
Post new topic   Reply to topic    Sudoku Programmers Forum Index -> Programming sudoku
View previous topic :: View next topic  
Author Message
zerothbase

Joined: 02 Nov 2008
Posts: 17
:

Items
PostPosted: Sun Nov 02, 2008 11:59 pm    Post subject: Backtracking solver by a forum newb Reply with quote

Good day all,

I've been reading these forums for a few months now, but this is my first post.

I created a simple backtracking solver in C, just to see the performance compared with some of the DLX solvers out there (specifically Ignacio's fast_solv_9r2.c). I've done a little bit of optimization but I still have a lot to do, I think, to get near the "big dogs" on the forums like gsf and ignacio_ar for performance. It's about 220 lines of actual code (with comments removed).

v1 - http://tinyurl.com/5jjpl4
v2 - http://tinyurl.com/6krpwl (faster by ~25%)

Similar options to other small solvers: -q for stats only, -s2 to verify uniqueness, or -s# in general to change the max solutions to find.

It will take a puzzle file on stdin or on the command line. Also, if you modify the "#define BOX" line, it will handle 2x2, 3x3, 4x4 or 5x5 puzzles, though I've really only been focusing on 3x3's for testing.

Let me know what you think.


Last edited by zerothbase on Fri Nov 07, 2008 9:12 am; edited 1 time in total
Back to top
View user's profile Send private message
briturner

Joined: 14 Oct 2008
Posts: 75
:

Items
PostPosted: Mon Nov 03, 2008 12:59 am    Post subject: Reply with quote

It looks very good. I have also found that DLX is fast, but not the fastest (at least not on the 9x9 grids). here are the timings I got on my laptop (all compiled with Visual C 6.0, release configuration for improved optimizations), and timed with ntimer:

Stopping after first solution found:
0:00:05.000 - fast_solv_9r2.c -q < top50000.sdm
0:00:02.750 - zerodoku top50000.sdm -q
0:00:02.000 - BB_Sudoku -t0 < top50000.sdm

Verifying uniqueness
0:00:05.921 - fast_solv_9r2.c -q -s2 < top50000.sdm
0:00:03.781 - zerodoku top50000.sdm -q -s2
0:00:02.671 - BB_Sudoku -t0 -m < top50000.sdm

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

Joined: 18 Aug 2005
Posts: 411
:
Location: NJ USA

Items
PostPosted: Mon Nov 03, 2008 11:12 am    Post subject: Reply with quote

can you normalize your timing results to puzzles/second/cpu-Ghz
thanks
Back to top
View user's profile Send private message Visit poster's website
briturner

Joined: 14 Oct 2008
Posts: 75
:

Items
PostPosted: Mon Nov 03, 2008 11:45 am    Post subject: Reply with quote

Since I am on a 1.83 GHz processor, it works out to be the following:

Stopping after first solution found (Puzzles/second/cpu-Ghz) :
5464 - fast_solv_9r2.c -q < top50000.sdm
9935 - zerodoku top50000.sdm -q
13661 - BB_Sudoku -t0 < top50000.sdm

Verifying uniqueness (Puzzles/second/cpu-Ghz)
4614 - fast_solv_9r2.c -q -s2 < top50000.sdm
7226 - zerodoku top50000.sdm -q -s2
10229 - BB_Sudoku -t0 -m < top50000.sdm

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

Joined: 02 Nov 2008
Posts: 17
:

Items
PostPosted: Mon Nov 03, 2008 1:33 pm    Post subject: Reply with quote

Thanks for the quick response! Not so bad for a first try.

I'm using linux in VMPlayer so my own timings are all off.

zerodoku only uses the basic naked/hidden singles logic and backtracking. I used similar code provided by dmhayden (topic - "Find hidden singles with bits" - Thanks!) for hidden singles. It also tries to find naked and hidden zeros (none available in a square or row/col/box) for backtracking purposes. And if it can't find singles, it iterates over the possibly values in the square with the least number of values possible.

For average puzzles, it appears to only be visiting 110 nodes to solve a given puzzle (averaged across thousands of puzzles). Considering that on average, the solver has to fill in ~60 values, that's fairly efficient imo. Though on the top1465, it is more like ~450 nodes - but those are designed to put a backtrack solver in a world of hurt. I tested this by simply having a counter increment every time the backtrack() function was entered and then divide by the number of puzzles.

ToDo list includes:
1) adding more logic - box/line interactions and twins/triples/quads and seeing if they improve the speed.
2) also checking for the lowest number of places a value can be in a row/col/box for iteration as opposed to only the lowest number in a square.
Back to top
View user's profile Send private message
briturner

Joined: 14 Oct 2008
Posts: 75
:

Items
PostPosted: Mon Nov 03, 2008 2:11 pm    Post subject: Reply with quote

I have already implemented locked candidates, naked/hidden pairs/triples/quads using bitwise operations, and I have found that for raw speed, hidden and naked singles are all you need. guessing and backtracking is a very efficient method, at least for 9x9 grids.

I suspect that as grids grow in size, logical operations will become more important then guessing and backtracking, but I could be wrong. Though it could turn out that large grids are so sparse that the DLX algorithms will be the best.

I am actually working on throwing a web page up to collect efficient ways to use bitwise operations for the different solving methodologies. It is a background task, so it could take a couple day.

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

Joined: 18 Aug 2005
Posts: 411
:
Location: NJ USA

Items
PostPosted: Mon Nov 03, 2008 4:17 pm    Post subject: Reply with quote

briturner wrote:
Since I am on a 1.83 GHz processor, it works out to be the following:

Stopping after first solution found (Puzzles/second/cpu-Ghz) :
5464 - fast_solv_9r2.c -q < top50000.sdm
9935 - zerodoku top50000.sdm -q
13661 - BB_Sudoku -t0 < top50000.sdm

thanks
my stripped down ~133 line solver gets ~13600 puz/sec/ghz for the first solution
besides the bitmask representation the only optimzation is to backtrack on the most constrained nodes first

as the problem dimension increases (16x16 etc) the backtrack node count explodes
so computation at each node becomes the hot spot
and in general its a lose to increase the domain-specific computation to each node
Back to top
View user's profile Send private message Visit poster's website
briturner

Joined: 14 Oct 2008
Posts: 75
:

Items
PostPosted: Mon Nov 03, 2008 4:30 pm    Post subject: Reply with quote

Another optimization is to not re-calculate for hidden singles if nothing in the group changed.

I have not measured the increase or decrease, but I track which groups are impacted by placing a single. If a group has not had any cells that have changed, then there is no need to look for hidden singles in that group.

I will need to test to see if not doing this check increases speed (overhead in time to maintain a list of changed groups against the time saved not searching for hidden singles). By the time you add in locked candidates and subsets, it does result in a significant savings.

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

Joined: 02 Nov 2008
Posts: 17
:

Items
PostPosted: Mon Nov 03, 2008 11:44 pm    Post subject: Reply with quote

Quote:
my stripped down ~133 line solver gets ~13600 puz/sec/ghz for the first solution

gsf, when you have some time, would you mind testing my solver (zerodoku) and your 133 line solver on Gordon Royale's sudoku17 list of 47793 puzzles? I was getting some strange results using my VMPlayer when comparing sudocoo (which I assume is similar to/same as the 133 line solver you mentioned). sudocoo was taking on the order of 2 minutes whereas zerodoku and fast_solv_9r2 were closer to 2 seconds. However sudocoo could do the top50000 in 2 seconds. I couldn't figure it out.


Quote:
Another optimization is to not re-calculate for hidden singles if nothing in the group changed.

I did half-try to implement this a day or two before I first posted, but for some reason it about halved the solve speed. It definitely makes sense that this should be far faster. I'll give it another go - there was probably a bug in the code and I didn't really spend a lot of time running it down. Smile
Back to top
View user's profile Send private message
briturner

Joined: 14 Oct 2008
Posts: 75
:

Items
PostPosted: Tue Nov 04, 2008 3:05 am    Post subject: Reply with quote

I checked, without checking for changes in groups, the solver is around 15% slower.

well, here is what I have been using. It has been optimized based on Visual C 6.0 and on intel T5600, and contains some windows specific code. Nothing real pretty, but it works well for me.

brit

Code:

/****************************************************************\
**                                                              **
**  BB_Sudoku  Bit Based Sudoku Solver                          **
**                                                              **
**             Copyright (c) 2008, Brian Turner                 **
**             All rights reserved                              **
**                                                              **
\****************************************************************/

#include <windows>
#include <stdio>
#include <time>

typedef unsigned char uint8;
typedef unsigned int  uint16;





// V2B and B2V provide a quick lookup between bit positions
//   and values.  This provides an easy method to convert
//   between values and bit positions for single values.
//
// NSet looks up the number of bits set (potential values)
//   for numbers 0 to 511 (9 bits).

// Values to Bit positions lookup
uint16 V2B[17] = {0x0000, 0x0001, 0x0002, 0x0004, 0x0008,
                          0x0010, 0x0020, 0x0040, 0x0080,
                          0x0100, 0x0200, 0x0400, 0x0800,
                          0x1000, 0x2000, 0x4000, 0x8000};

// Bits to Value lookup
const int B2V[512] =
   { 0, 1, 2, 0, 3, 0, 0, 0, 4, 0, 0, 0, 0, 0, 0, 0,
     5, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
     6, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
     0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
     7, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
     0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
     0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
     0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
     8, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
     0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
     0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
     0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
     0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
     0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
     0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
     0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
     9, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
     0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
     0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
     0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
     0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
     0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
     0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
     0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
     0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
     0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
     0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
     0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
     0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
     0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
     0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
     0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 };

// Number of bits set in the number, up to 9 bits
const int NSet[512] =
   { 0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4,
     1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
     1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
     2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
     1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
     2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
     2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
     3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
     1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
     2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
     2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
     3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
     2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
     3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
     3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
     4, 5, 5, 6, 5, 6, 6, 7, 5, 6, 6, 7, 6, 7, 7, 8,
     1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
     2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
     2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
     3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
     2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
     3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
     3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
     4, 5, 5, 6, 5, 6, 6, 7, 5, 6, 6, 7, 6, 7, 7, 8,
     2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
     3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
     3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
     4, 5, 5, 6, 5, 6, 6, 7, 5, 6, 6, 7, 6, 7, 7, 8,
     3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
     4, 5, 5, 6, 5, 6, 6, 7, 5, 6, 6, 7, 6, 7, 7, 8,
     4, 5, 5, 6, 5, 6, 6, 7, 5, 6, 6, 7, 6, 7, 7, 8,
     5, 6, 6, 7, 6, 7, 7, 8, 6, 7, 7, 8, 7, 8, 8, 9 };



// Groups and P2Group define the groups for a standard
//   3x3 grid and a look from a position (1-81) to the
//   three groups it is a part of.
// The 0 value is not used so that a zero can be used
//   as an unused marker (for things like diagonals).

// Defines the groups used in a standard 3x3 grid
const int Group[28][9] =
  {{  0,  0,  0,  0,  0,  0,  0,  0,  0 },

   {  1,  2,  3, 10, 11, 12, 19, 20, 21 },
   {  4,  5,  6, 13, 14, 15, 22, 23, 24 },
   {  7,  8,  9, 16, 17, 18, 25, 26, 27 },
   { 28, 29, 30, 37, 38, 39, 46, 47, 48 },
   { 31, 32, 33, 40, 41, 42, 49, 50, 51 },
   { 34, 35, 36, 43, 44, 45, 52, 53, 54 },
   { 55, 56, 57, 64, 65, 66, 73, 74, 75 },
   { 58, 59, 60, 67, 68, 69, 76, 77, 78 },
   { 61, 62, 63, 70, 71, 72, 79, 80, 81 },

   {  1,  2,  3,  4,  5,  6,  7,  8,  9 },
   { 10, 11, 12, 13, 14, 15, 16, 17, 18 },
   { 19, 20, 21, 22, 23, 24, 25, 26, 27 },
   { 28, 29, 30, 31, 32, 33, 34, 35, 36 },
   { 37, 38, 39, 40, 41, 42, 43, 44, 45 },
   { 46, 47, 48, 49, 50, 51, 52, 53, 54 },
   { 55, 56, 57, 58, 59, 60, 61, 62, 63 },
   { 64, 65, 66, 67, 68, 69, 70, 71, 72 },
   { 73, 74, 75, 76, 77, 78, 79, 80, 81 },

   {  1, 10, 19, 28, 37, 46, 55, 64, 73 },
   {  2, 11, 20, 29, 38, 47, 56, 65, 74 },
   {  3, 12, 21, 30, 39, 48, 57, 66, 75 },
   {  4, 13, 22, 31, 40, 49, 58, 67, 76 },
   {  5, 14, 23, 32, 41, 50, 59, 68, 77 },
   {  6, 15, 24, 33, 42, 51, 60, 69, 78 },
   {  7, 16, 25, 34, 43, 52, 61, 70, 79 },
   {  8, 17, 26, 35, 44, 53, 62, 71, 80 },
   {  9, 18, 27, 36, 45, 54, 63, 72, 81 }};

// Defines the 3 groups each position is part of
const uint8 P2Group[82][4] =
  {{ 0,  0,  0 },
   { 1, 10, 19 }, { 1, 10, 20 }, { 1, 10, 21 },
   { 2, 10, 22 }, { 2, 10, 23 }, { 2, 10, 24 },
   { 3, 10, 25 }, { 3, 10, 26 }, { 3, 10, 27 },
   { 1, 11, 19 }, { 1, 11, 20 }, { 1, 11, 21 },
   { 2, 11, 22 }, { 2, 11, 23 }, { 2, 11, 24 },
   { 3, 11, 25 }, { 3, 11, 26 }, { 3, 11, 27 },
   { 1, 12, 19 }, { 1, 12, 20 }, { 1, 12, 21 },
   { 2, 12, 22 }, { 2, 12, 23 }, { 2, 12, 24 },
   { 3, 12, 25 }, { 3, 12, 26 }, { 3, 12, 27 },
   { 4, 13, 19 }, { 4, 13, 20 }, { 4, 13, 21 },
   { 5, 13, 22 }, { 5, 13, 23 }, { 5, 13, 24 },
   { 6, 13, 25 }, { 6, 13, 26 }, { 6, 13, 27 },
   { 4, 14, 19 }, { 4, 14, 20 }, { 4, 14, 21 },
   { 5, 14, 22 }, { 5, 14, 23 }, { 5, 14, 24 },
   { 6, 14, 25 }, { 6, 14, 26 }, { 6, 14, 27 },
   { 4, 15, 19 }, { 4, 15, 20 }, { 4, 15, 21 },
   { 5, 15, 22 }, { 5, 15, 23 }, { 5, 15, 24 },
   { 6, 15, 25 }, { 6, 15, 26 }, { 6, 15, 27 },
   { 7, 16, 19 }, { 7, 16, 20 }, { 7, 16, 21 },
   { 8, 16, 22 }, { 8, 16, 23 }, { 8, 16, 24 },
   { 9, 16, 25 }, { 9, 16, 26 }, { 9, 16, 27 },
   { 7, 17, 19 }, { 7, 17, 20 }, { 7, 17, 21 },
   { 8, 17, 22 }, { 8, 17, 23 }, { 8, 17, 24 },
   { 9, 17, 25 }, { 9, 17, 26 }, { 9, 17, 27 },
   { 7, 18, 19 }, { 7, 18, 20 }, { 7, 18, 21 },
   { 8, 18, 22 }, { 8, 18, 23 }, { 8, 18, 24 },
   { 9, 18, 25 }, { 9, 18, 26 }, { 9, 18, 27 }};


// Forward function definitions
inline void InitGrid (void);
inline void ProcessSingles (void);
inline void FindHiddenSingles (void);
inline void MakeGuess (void);
void DisplaySolution (void);
void HandleArgs (int argc, char* argv[]);
void ShowValues (void);
inline void SetupTiming (void);
void DisplayTiming (void);


// Control how the solutions are displayed
char display_mode = 0;  // 0 = no output (for timing)
                        // 1 = output 1 line solution
                        // 2 = display grid solution
                        // 3 = animated solver

// Control timing modes
int timing_mode = 1;    // 0 = No timings (external timing)
                        // 1 = full program loading only
                        // 2 = puzzle timing

// Search for a single, or multiple solutions
int One_Sol = 1;        // 0 = search for all the solutions
                        // 1 = stop searching after 1 solution

// undocumented flag to diplay additional stats (-X)
int show_stats = 0;     // 0 = do not display extra stats
                        // 1 = display extra stats

// For timing, use the high preformance windows timers
LARGE_INTEGER Frequency, StartTime, EndTime, SolveTime;


// G - Grid data structure
//   Currently, the structure only contains 1 item, but when
//     Subsets are calculated, more items will be added
//   Note: 17 my be a bit small, but I never went beyond it yet
struct { uint16 Grid[82]; } G[17];

// buffer to read in the text version of puzzles (example puzzle included)
char buffer[250] = "1.......2.9.4...5...6...7...5.9.3.......7.......85..4.7.....6...3...9.8...2.....1";


// Naked Singles FIFO stack - new singles found are stored here before
char   SingleCnt = 0;
uint8  SinglePos[82];
uint16 SingleVal[82];
#define PushSingle(p, b) { SinglePos[SingleCnt] = p; SingleVal[SingleCnt] = b; SingleCnt++; Changed = 1; }

// Guess structure
char GuessPos[17];
int  GuessVal[17];

// Key global variables used throughout the solving
uint16 PuzzleCnt = 0;    // Total puzzles tested
uint16 SolvedCnt = 0;    // Total puzzles solved
int    PuzSolCnt;        // Solutions for a single puzzle
int    Changed;          // Flag to indicate Grid has changed
int    No_Sol;           // Flag to indicate there is no solution possible
int    PIdx;             // Position Index, used for guessing and backtracking
char   ChangedGroup[28]; // Marks which groups have changed


// Debug stats
long SCnt = 0, HCnt = 0, GCnt = 0;


/**********\
**  main  *******************************************************\
**                                                              **
**    main routine sets up the timers and handles loading the   **
**    puzzles and calling the solver.                           **
**                                                              **
\****************************************************************/
int main(int argc, char* argv[])
{
  HandleArgs (argc, argv);               // Process command line arguments
  SetupTiming();                         // Prepare for timing the solver
  QueryPerformanceCounter (&StartTime);  // Get the current timer for program timing

  // Read the puzzles from the stardard input, looping through all the puzzles
  while (fgets(buffer, 240, stdin))
  {
    if (buffer[0] == '#') continue;      // ignore comments in the intputs
    PuzzleCnt++;                         // increment the puzzle count
    PuzSolCnt = 0;                       // reset the solutions for this puzzle
    if (timing_mode == 2)
      QueryPerformanceCounter (&StartTime); // Get the current timer for puzzle timing
    InitGrid();                          // Load the Grid from the buffer

    // Loop through the puzzle solving routines until finished 
    while (Changed)
    { // If No Solution possible, jump straight to the backtrack routine
      if (!No_Sol)
      { // Check if any Singles to be propogated
        if (SingleCnt)
        {
          ProcessSingles();
          SCnt++;
          if (display_mode == 3) ShowValues();
          if (!G[PIdx].Grid[0])
          { if (!No_Sol)
            { PuzSolCnt++;
              if (display_mode)
                ShowValues();     
            }
            if (One_Sol) break;
            No_Sol = Changed = 1;
            continue;
          }
        }

        // If anything has changed, look for hidden singles
        if (Changed)       
        {
          FindHiddenSingles();
          HCnt++;
          if (display_mode == 3) ShowValues();
          if (SingleCnt) continue;
        }
      }

      //If nothing new found, just make a guess
      MakeGuess();   
      GCnt++;
      if (No_Sol) break;
      if (PIdx > 17) { printf ("Max Depth exceeded, recompile for more depth.\n\n"); exit(0); }
    }

    SolvedCnt += PuzSolCnt;    // Update solved count
    DisplaySolution();         // Display the solution and timing
  }

  QueryPerformanceCounter (&EndTime);  // Get ending timer
  DisplayTiming();                     // Display the final timing and counts
  return 0;
}




/*******************\
**  DisplayTiming  **********************************************\
**                                                              **
**    DisplayTiming displays timing of the entire program, and  **
**    puzzle counts (puzzles and solutions).                    **
**                                                              **
\****************************************************************/
void DisplayTiming (void)
{
  float  fulltime;         

  printf ("%5d Puzzles,  %5d Solved ", PuzzleCnt, SolvedCnt);
  if (timing_mode == 1)
  {
    fulltime = (float)(EndTime.QuadPart - StartTime.QuadPart) / (float)Frequency.QuadPart;
    if (fulltime > 0.95)
      printf ("  Time = %2.3f sec  ( %I64d counts )       \n\n", fulltime,  EndTime.QuadPart - StartTime.QuadPart);
    else if (fulltime > 0.00095)
      printf ("  Time = %2.3f msec  ( %I64d counts )      \n\n", fulltime*1000,  EndTime.QuadPart - StartTime.QuadPart);
    else
      printf ("  Time = %2.3f usec  ( %I64d counts )      \n\n", fulltime*1000000,  EndTime.QuadPart - StartTime.QuadPart);
  }
  if (show_stats)
    printf ("  %ld Singles,   %ld Hiddens,   %ld Guesses\n\n", SCnt, HCnt, GCnt);
}




/*********************\
**  DisplaySolution  ********************************************\
**                                                              **
**    DisplaySolution handles the final display task for each   **
**    puzzle, and displays the timings.  This is controled by   **
**    by the state of the display_mode and timing_mode.         **
**                                                              **
\****************************************************************/
inline void DisplaySolution (void)
{
  // Display answer if displays are used
  if (display_mode)
  {
    if (timing_mode == 2)
      QueryPerformanceCounter (&EndTime);

    if (display_mode == 1)
    {
      if (PuzSolCnt == 0) ShowValues();
      if (!One_Sol) printf ("\n");
    }

    if (display_mode > 1)
    { 
      if (PuzSolCnt == 0)
      {
        ShowValues();
        printf ("No Solutions found ");
      }
      else if (One_Sol)
        printf ("Solved             ");
      else
        printf ("%2d Solutions found ", PuzSolCnt);
       
      if (timing_mode == 2)
        printf ("  Time = %2.2f usec  ( %I64d counts )      ",
                (float)(EndTime.QuadPart - StartTime.QuadPart) * 1000000.0 / (float)Frequency.QuadPart,
                EndTime.QuadPart - StartTime.QuadPart);
      printf ("\n\n");
    }
  }
}




/****************\
**  SetupTiming  *************************************************\
**                                                              **
**    SetupTiming increases the waits for 1 second for other    **
**    tasks to finish, and increases the priority of the        **
**    solver.  Since we are using a high preformace timers,     **
**    these steps help make the timing more accurate and        **
**    repeatable (there is still some variation from run to     **
**    run, but much less than if we don't do this).             **
**                                                              **
\****************************************************************/
void SetupTiming (void)
{
  // Get the frequency of the timer (for my system, it was a 0.279 usec a tick)
  QueryPerformanceFrequency (&Frequency);

  // If puzzle timing, wait 1 second before running the puzzle to allow
  //   other background threads to finish up.  This provides better timings
  if (timing_mode)
  {
    QueryPerformanceCounter (&StartTime);
    do { QueryPerformanceCounter (&EndTime); }
    while ((EndTime.QuadPart - StartTime.QuadPart) < Frequency.QuadPart);
  }

  // To make the timing more accurate, raise the priority of the program.
  //   This helps prevent other things from inturrupting the solving.
  SetPriorityClass(GetCurrentProcess(), HIGH_PRIORITY_CLASS);
  SetThreadPriority(GetCurrentThread(), THREAD_PRIORITY_ABOVE_NORMAL);
}




/****************\
**  HandleArgs  *************************************************\
**                                                              **
**    HandleArgs decodes the command line arguments and sets    **
**    the appropriate flags.                                    **
**                                                              **
\****************************************************************/
void HandleArgs (int argc, char* argv[])
{
  int    i;

  // Print Title
  printf ("Bit Based Sudoku Solver, by Brian Turner\n\n");

  // Check the arguments passed into the program
  for (i = 1; i <argc>= '0') && (argv[i][2] <= '2'))
        timing_mode = argv[i][2] - '0';
    if ((argv[i][1] == 'd') || (argv[i][1] == 'D'))
      if ((argv[i][2] >= '0') && (argv[i][2] <= '3'))
        display_mode = argv[i][2] - '0';
    if ((argv[i][1] == 'u') || (argv[i][1] == 'U')) One_Sol = 1;
    if ((argv[i][1] == 'm') || (argv[i][1] == 'M')) One_Sol = 0;
    if ((argv[i][1] == 'x') || (argv[i][1] == 'X')) show_stats = 1;
  }

  // Clear the screen for animated displays
  if (display_mode == 3)
  { 
    system ("cls");
    printf ("Bit Based Sudoku Solver, by Brian Turner\n\n");
  }
}




/**************\
**  InitGrid  ***************************************************\
**                                                              **
**    InitGrid takes the text string stored in the buffer and   **
**    populates the solution grid.  It assumes the text is      **
**    properly formatted.                                       **
**                                                              **
\****************************************************************/
inline void InitGrid (void)
{ char i;

  // Initialize some key variables
  G[0].Grid[0] = 81;
  PIdx = 0;
  SingleCnt = 0;
  Changed = 1;
  No_Sol = 0;

  // Loop through the buffer and set teh singles to be set
  for (i = 0; i <81> '0') && (buffer[i] <= '9'))
      PushSingle((char)(i+1), V2B[buffer[i] - '0']);
  }
}




/********************\
**  ProcessSingles  *********************************************\
**                                                              **
**    ProcessSingles takes a naked single and marks each cell   **
**    in the 3 associated groups as not allowing that number.   **
**    It also marks the groups as changed so we know to check   **
**    for hidden singles in that group.                         **
**                                                              **
\****************************************************************/
inline void ProcessSingles (void)
{ int i, gp, t, g, t2;
  uint16 b;

  for (i = 0; i < SingleCnt; i++)
  { t = SinglePos[i];                    // Get local copy of position
    b = SingleVal[i];                    // Get local copy of the value
    if (G[PIdx].Grid[t] == 0) continue;  // Check if we already processed this position
    G[PIdx].Grid[0]--;                   // mark one less empty space
    G[PIdx].Grid[t] = 0;                 // mark this position processed
    for (gp = 0; gp < 3; gp++)           // loop through all 3 groups
      for (g = 0; g < 9; g++)            // loop through each cell in the group
      { t2 = (int)Group[P2Group[t][gp]][g];   // get temp copy of position
        if (G[PIdx].Grid[t2] & b)        // check if removing a possibility
        { G[PIdx].Grid[t2] = G[PIdx].Grid[t2] & ~b;
          if (G[PIdx].Grid[t2] == 0)
             { No_Sol = 1; SingleCnt = 0; Changed = 0; return; }
          if (B2V[G[PIdx].Grid[t2]])
            PushSingle(t2, G[PIdx].Grid[t2]);
          ChangedGroup[P2Group[t2][0]] = ChangedGroup[P2Group[t2][1]] = ChangedGroup[P2Group[t2][2]] = 1;
          Changed = 1;
        }
      }             
  }
  for (i = 0; i < SingleCnt; i++)
    G[PIdx].Grid[SinglePos[i]] = SingleVal[i];
  SingleCnt = 0;
}




/***********************\
**  FindHiddenSingles  ******************************************\
**                                                              **
**    FindHiddenSingles checks each grouping that has changed   **
**    to see if they contain any hidden singles.  If one is     **
**    found, the routine adds it to the queue and exits.        **
**                                                              **
\****************************************************************/
inline void FindHiddenSingles (void)
{ uint16 t1, t2, t3, b, t;
  int i, j;
 
  for (i = 1; i <= 27; i++)
    if (ChangedGroup[i])
    { t1 = t2 = t3 = 0;
      for (j = 0; j < 9; j++)
      { b  = G[PIdx].Grid[Group[i][j]];
        t2 = t2 | (t1 & b);
        t1 = t1 | b;
        if (B2V[b]) t3 = t3 | b;
      }
      if (t1 != 0x01FF)
        { No_Sol = 1; SingleCnt = 0; Changed = 0; goto DoneHidden; }
      t3 = ~(t2 | t3) & 0x01FF;
      if (t3)
      { for (t = 1; t < 0x01FF; t = t << 1)
          if (t & t3)
            for (j = 0; j < 9; j++)
              if (t & G[PIdx].Grid[Group[i][j]])
              {
                PushSingle((char)Group[i][j], t);
                goto DoneHidden;
              }
      }
      ChangedGroup[i] = 0;
    }
  Changed = 0;
  DoneHidden: ;
}




/***************\
**  MakeGuess  **************************************************\
**                                                              **
**    MakeGuess handles the guessing and backtracking used      **
**    when solving puzzles.                                     **
**                                                              **
\****************************************************************/
inline void MakeGuess (void)
{
  int i, t;
  uint16 v;
  int Found = 0;
  char mt;

  memset (ChangedGroup, 0, sizeof(ChangedGroup));
  Changed = 1;
  SingleCnt = 0;

  // Check to see where the next guess should be
  if (No_Sol)
    while (No_Sol)
    { if (PIdx == 0) goto DoneGuess;
      G[PIdx-1].Grid[GuessPos[PIdx]] &= ~V2B[GuessVal[PIdx]];
      if (G[PIdx-1].Grid[GuessPos[PIdx]]) { No_Sol = 0; Found = 1; }
      PIdx--;
    }     

  // Populate the grid for the next guess
  G[PIdx+1] = G[PIdx];
  PIdx++;

  // Find next spot to check
  if (!Found)
  {
    mt = 99;
    for (i = 1; i <= 81; i++)
      if ((NSet[G[PIdx].Grid[i]] <mt> 1))
      { GuessPos[PIdx] = i;
        mt = NSet[G[PIdx].Grid[i]];
        if (mt == 2) break;
      }
  }

  // Mark the next guess in the position
  v = G[PIdx].Grid[GuessPos[PIdx]];
  for (t = 1; t <= 9; t++)
    if (v & V2B[t])
    { GuessVal[PIdx] = t;
      PushSingle(GuessPos[PIdx], V2B[t]);
      Changed = 1;
      break;
    }       
  DoneGuess: ;
}




/****************\
**  ShowValues  *************************************************\
**                                                              **
**    ShowValues display the current state of the puzzle.       **
**                                                              **
**    display_mode determines how it is displayed:              **
**      0 : Nothing is displayed (this routine is not called)   **
**      1 : Displays the puzzle on a single line (81 char)      **
**      2 : Displays the puzzle on a grid with ASCII char       **
**      3 : Same as 2, but is used to animate the process       **
**                                                              **
\****************************************************************/
char c1[12] = "  °°±±²²ÛÛÛ";
char c2[4]  = "³º³";
void ShowValues (void)
{ int i, t;

  if (display_mode == 1)
  {
    for (i = 1; i <= 81; i++)
      printf ("%c", '0' + B2V[G[PIdx].Grid[i]]);
    if (No_Sol)
      printf (" - No Solution\n");
    else
      printf (" - Solved\n");   
  }
  else
  {
    if (display_mode == 3)
    {
      COORD scrn;   
      HANDLE hOuput = GetStdHandle(STD_OUTPUT_HANDLE);
      scrn.X = 0; scrn.Y = 2;
      SetConsoleCursorPosition(hOuput, scrn);
    }
    printf ("ÉÍÍÑÍÍÑÍÍËÍÍÑÍÍÑÍÍËÍÍÑÍÍÑÍÍ»\n");
    for (i = 1; i <= 81; i++)
    {
      printf ("%c", c2[i % 3]);
      t = NSet[G[PIdx].Grid[i]];
      if (t == 1)
        printf (" %c", B2V[G[PIdx].Grid[i]]+'0');
      else
        printf ("%c%c", c1[t], c1[t+1]);
      if (i == 81) printf ("º\nÈÍÍÏÍÍÏÍÍÊÍÍÏÍÍÏÍÍÊÍÍÏÍÍÏÍͼ\n");
      else if ((i % 27) == 0) printf ("º\nÌÍÍØÍÍØÍÍÎÍÍØÍÍØÍÍÎÍÍØÍÍØÍ͹\n");
      else if ((i %  9) == 0) printf ("º\nÇÄÄÅÄÄÅÄÄ×ÄÄÅÄÄÅÄÄ×ÄÄÅÄÄÅÄĶ\n");
    }
  }
}

Back to top
View user's profile Send private message
gsf

Joined: 18 Aug 2005
Posts: 411
:
Location: NJ USA

Items
PostPosted: Tue Nov 04, 2008 2:56 pm    Post subject: Reply with quote

zerothbase wrote:
Quote:
my stripped down ~133 line solver gets ~13600 puz/sec/ghz for the first solution

gsf, when you have some time, would you mind testing my solver (zerodoku) and your 133 line solver on Gordon Royale's sudoku17 list of 47793 puzzles? I was getting some strange results using my VMPlayer when comparing sudocoo (which I assume is similar to/same as the 133 line solver you mentioned). sudocoo was taking on the order of 2 minutes whereas zerodoku and fast_solv_9r2 were closer to 2 seconds. However sudocoo could do the top50000 in 2 seconds. I couldn't figure it out.

I did use a stripped down sudocoo (no runtime options)
its performance degrades with smaller #givens
so the 17s are its worst case input
zerodoku does well for both top50000 and sudoku17
with just a bit more complexity in the code
its also bit better than my sudocoup (which I think does singles checks comparable to zerodoku)

I'll do some more comparisons in the next few weeks and get back
Back to top
View user's profile Send private message Visit poster's website
Lunatic

Joined: 11 Mar 2007
Posts: 166
:
Location: Ghent - Belgium

Items
PostPosted: Tue Nov 04, 2008 7:55 pm    Post subject: Reply with quote

Idea Why don't anyone uses 'in line assembly' ? I would, if Visual Basic 6 had that option.
_________________
Marc
~~~<><~~~<><~~~<><~~~<><~~~
Back to top
View user's profile Send private message Send e-mail Visit poster's website
briturner

Joined: 14 Oct 2008
Posts: 75
:

Items
PostPosted: Tue Nov 04, 2008 8:39 pm    Post subject: Reply with quote

I have debated using inline assembly, and I have in the past (not for Sudoku).

Think about it, using the 128 bit SSE instructions to process 8 columns at a time, or the AMD POPCNT to check the number of bits set in 2 clock cycles.

But, then you have code that only runs on certain machines and is difficult to port or maintain.

I always believe that converting to assembly is that last thing you want to do when optimizing. I am not saying it should not be done, but it really should be the last step. Algorithms and Data Structures should always be optimized before before writing anything in assembly. Once you go to assembly, it becomes more difficult to modify and maintain.

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

Joined: 02 Nov 2008
Posts: 17
:

Items
PostPosted: Tue Nov 04, 2008 11:58 pm    Post subject: Reply with quote

I fully agree brit.

My compilers professor back in college always used to say: with how advanced modern optimizing compilers are, you'd be hard pressed to get more than 10% speed improvement from hand coded assembly over well optimized C code. But you can get large improvements going from badly coded C to well coded C (I'm paraphrasing from his thick Indian accent - but you get the idea).

I'm much more interested in elegant algorithms than I am in translating to another language to make the compiler's life easier. Much the same as I would be more interested in writing elegant poetry in my native tongue, rather than the laborious job of translating it into another language to make my reader's life easier (not to mention that the poetry loses everything that made it elegant).

Also, if you are dissatisfied with well coded C vs assembly, then you can always wait a month or two for the next CPU to be released and it will probably be 10% faster (this has been true for many years at least). Whereas if your algorithm/datastructure is horrible - it won't matter which language you use - it could take the age of the universe to solve the problem. Recursive Fibonacci is generally the classic problem in CS101 to demonstrate this.

From my testing, I've even seen the newer Java JVMs perform only about 10% to 20% slower than C (assuming you use identical algorithms and data structures). So the same might apply here to - though YMMV.

Just my thoughts.
Back to top
View user's profile Send private message
Lunatic

Joined: 11 Mar 2007
Posts: 166
:
Location: Ghent - Belgium

Items
PostPosted: Wed Nov 05, 2008 12:19 am    Post subject: Reply with quote

I was thinking... backtracking occurs when an empty cell is encountered... an empty cell is the smallest subset short of one candidate... so there could be larger subsets short of one candidate allready present before an empty cell occurs... finding those subsets would prevent unneeded guesses and could speed up the solve speed....

Did some experiments... unfortunately, looking for those subsets took longer than the time i won by preventing those unneeded guesses.

This is how i did it:

For each house
----count unsolved cells
----if more than 1 unsolved cell
--------for any possible subset (starting with pair, then triple, and so on...)
------------count common candidates
------------if candidate count < subset then backtrack

So, i must find a better way to spot those subsets short of 1 candidate. Does anyone have any suggestion ?
_________________
Marc
~~~<><~~~<><~~~<><~~~<><~~~
Back to top
View user's profile Send private message Send e-mail Visit poster's website
Display posts from previous:   
Post new topic   Reply to topic    Sudoku Programmers Forum Index -> Programming sudoku All times are GMT
Goto page 1, 2  Next
Page 1 of 2

 
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