Sudoku Programmers :: View topic - Optimizing Java-written DLX solver

FAQ

Memberlist

Usergroups

Profile

Optimizing Java-written DLX solver
Goto page Previous 1, 2

Sudoku Programmers Forum Index -> Programming sudoku

View previous topic :: View next topic

Author

Message

sudoking

Joined: 20 Oct 2009

Posts: 40

Items

Posted: Mon Dec 14, 2009 10:13 am Post subject:

ThemePark wrote:

Good, that code looks really useful, and I'm trying to translate it to Java. I'm having a few issues though, since I've never programmed C++ and don't know the language's ins and outs that well.

You have this struct:

Code:

static struct Grid_Type
{ int CellsLeft; // Cells left to solve
unsigned int Grid[81]; // Possibilities left for each cell
unsigned int Grp[27]; // Values found in each group
} G[64], *Gp;

But is Gp supposed to be an array of type Grid_Type without its dimensions initialized, or just a variable of type Grid_Type? The reason I ask is because of this code:

Code:

Gp = G;
Gp->CellsLeft = 81;

Gp is a pointer to an element in the array G. The line "Gp = G;" sets it to point to the first element in the array. This is one of the optimisations I added to the code. There were many references to G[PIdx] in the original code, but I noticed that PIdx didn't change very often, so I replaced all instances of G[PIdx] with Gp, and updated Gp whenever PIdx changed. I got an increase in performance of about 7% under 2003, but Brian only saw a 1% increase in 2008.

Java doesn't use pointers, so you could probably just replace all instances of Gp with G[PIdx], or change the way Gp is incremented. In C/C++, incrementing a pointer makes it point to the next element in the array. So if Gp points to the first array element, then Gp++ will make it point to the second element. The element Gp points to is always indexed, so changing Gp++ and Gp-- to Gp = G[PIdx] should do the trick.

Quote:

Code:

#define MarkChanged(x) { unsigned char const *ucp = C2Grp[x]; ChangedGroup[*ucp] = ChangedGroup[*(ucp+1)] = ChangedGroup[*(ucp+2)] = Changed = 1; }

ucp is supposed to be an array here, right? Because if I understand pointers and pointer arithmetic correctly, the Java equivalent would be:

Code:

void MarkChanged(x) { final byte ucp[] = C2Grp[x]; ChangedGroup[ucp[0]] = ChangedGroup[ucp[1]] = ChangedGroup[ucp[2]] = Changed = 1; }

No, it's another pointer. Any C/C++ variable declared with a * is a pointer (although pointers and arrays are often used interchangeably, they're not quite the same thing). This is another of my optimisations, which also saw a performance increase in 2003, but not much in 2008. If it make is easier, just use the original line, which is commented out below this line.

As far is implementing it in java, I wouldn't make it a function call. Function calls have overhead, and will make it slower. You could manually expand the macro in the 5 places it occurs in code. That's exactly what the C compiler does with #define macros.

Quote:

Code:

   for (v = i; v; NSet[i]++)
   { NSetX[i][NSet[i]] = v & -v;
   v = v ^ NSetX[i][NSet[i]];
   }

Why is there only a v for the conditional part of the for loop? I can't do that in Java, so what is the equivalent of this in Java?

In C, any non-zero value equates to true. So in java, this line would be

Code:

for (v = i; v != 0; NSet[i]++)

Quote:

Code:

int bb_solver(unsigned *puzzle)
{ register unsigned i;

I assume that puzzle is supposed to be an array, correct? But of what type? If I recall correctly, int is standard in C++, so if there is no data type it's automatically int, correct?

In C, "unsigned" is equivalent to "unsigned int". The variable puzzle is a pointer to the first element in an array of unsigned integers

Quote:

Code:

if (Gp.Grp[*(ucp++)] & b) {

I'm a bit confused as to what this means. Doesn't it mean that you take the current index of the ucp array, add one, and then use that index for Gp.Grp? In that case, I would need an index variable to keep track of where I am at in the array in Java.

This is a complicated one. It takes the value stored at the address ucp points at, and uses that value as the index of Grp[]. It also increments ucp, to point to the next element in the array C2Grp[t][].

Use this instead:

Code:

// ucp = C2Grp[t]; // THIS LINE WILL NO LONGER BE NEEDED
for (g = 0; g <3>Grp[C2Grp[t][g]] & b) {
No_Sol = 1; SingleCnt = Changed = 0;
return;
}

Quote:

Code:

   if (!No_Sol)
   { // Check if any Singles to be propogated
   if (SingleCnt)
   {

Here I'm not sure how to rewrite this to Java, since Java doesn't allow converting ints to booleans. But as far as I know, false equals 0 and true equals everything else, right? So it would be == 0 and != 0.

Like this:

Code:

   if (No_Sol == 0)
   { // Check if any Singles to be propogated
   if (SingleCnt != 0)
   {

That's one of the things I dislike about Java, the fact that is doesn't automatically convert non-zero values to true, and zero values to false, like C/C++.

Quote:

Finally, there's the register keyword which seems to be for optimizing, but is there a similar thing in Java?

Just remove it. It's supposed to suggest to the compiler that the variable should be stored in a processor register, if possible. Be it is virtually redundant with modern compilers.

Hope this helps. Smile

ThemePark

Joined: 22 Mar 2009

Posts: 17

Items

Posted: Tue Dec 15, 2009 1:49 pm Post subject:

Thanks, sudoking, that was very helpful. I have one question left though, then I can compile my code, and see if it works against the top 50000 sudokus.

Code:

(Gp - 1).Grid[gpp] ^= GuessVal[PIdx];

This would just be G[PIdx - 1] in Java, right?

Another question.

Code:

#define PushSingle(p, b) { SinglePos[SingleCnt] = p; SingleVal[SingleCnt] = b; SingleCnt++; Changed = 1; }

...

for (i = 0; i <SingleCnt>Grid[t] == 0) continue; // Check if we already processed this position
if (!(Gp->Grid[t] & b)) // Check for error conditions
{ No_Sol = 1; SingleCnt = Changed = 0; return; }
SolGrid[t] = b; // Store the single in the solution grid
Gp->CellsLeft--; // mark one less empty space
Gp->Grid[t] = 0; // mark this position processed

for (g = 0; g <3>Grp[C2Grp[t][g]] |= b; // mark the value as found in the group
for (g = 0; g <20>Grid[t2] & b) // check if removing a possibility
{ Gp->Grid[t2] = Gp->Grid[t2] ^ b; // remove possibility
if (Gp->Grid[t2] == 0) // check for error (no possibility)
{ No_Sol = 1; SingleCnt = 0; Changed = 0; return; }
if (B2V[Gp->Grid[t2]]) // Check if a naked single is found
PushSingle(t2, Gp->Grid[t2]);
MarkChanged(t2); // Mark groups as changed
}
}
}
SingleCnt = 0; // Clear the single count

Since SingleCnt is a global variable, every time PushSingle is called, SingleCnt is incremented, which in turn lets the for loop last longer. I don't see how the for loop ever stops in the C++ version, and in my Java version, I get an ArrayOutOfBoundsIndexException, because SingleCnt gets to 127, is incremented and then because of it being signed, becomes -128. But the SinglePos and SingleVal arrays only have 128 indexes anyway, from 0 to 127, so it shouldn't be necessary to use an int instead of a byte. So how does the loop stop in the C++ version, without running infinitely or getting an error?

sudoking

Joined: 20 Oct 2009

Posts: 40

Items

Posted: Tue Dec 15, 2009 2:40 pm Post subject:

Well, at least it compiles now, that's a start. Smile

ThemePark wrote:

Thanks, sudoking, that was very helpful. I have one question left though, then I can compile my code, and see if it works against the top 50000 sudokus.

Code:

(Gp - 1).Grid[gpp] ^= GuessVal[PIdx];

This would just be G[PIdx - 1] in Java, right?

Yes. (Gp - 1) is a pointer to the element in the array immediately before the element that Gp points to. (Gp + 1) would be pointer to the element in the array immediately after the element that Gp points to.

Quote:

Make sure you've converted the code correctly. The call to PushSingle should be OUTSIDE the for (i = 0; i < SingleCnt; i++) loop. It looks like you've placed a } in the wrong place.

As with MarkChanged, you should probably expand the PushSingle macro to remove the overhead of a function call. That should make it run faster, however, your java compiler MAY do this automatically, in which case manual expansion would be a waste of time. Perhaps get it working as a function call first, then expand it later.

ThemePark

Joined: 22 Mar 2009

Posts: 17

Items

Posted: Tue Dec 15, 2009 3:03 pm Post subject:

Well, you are right, I must've done something wrong because I got the code to compile and run now. The first test gave me a time of 8.39 seconds, which isn't too bad, considering that I thought it would be much slower. To make sure it worked properly, I also had a variable keep track of how many sudokus in the top 50000 had only one solution, and fortunately the program decided they all only had one, just like the original program does, so it seems to work perfectly. Now I'll try to replace the calls to the #defines with the actual code instead, and see if that speeds things up a bit.

sudoking

Joined: 20 Oct 2009

Posts: 40

Items

Posted: Tue Dec 15, 2009 3:58 pm Post subject:

ThemePark wrote:

Yeah, my first goal is to get this to actually work, and then time it. If it's too slow, I'll work on optimizing it then.

If it's too slow, it'll probably be the JVM. When you look at the assemble this C++ compiles into, it's pretty slick.

Quote:

But are you sure that the call has to be outside the for loop? Because it isn't in your C++ code:

My Bad, I was looking at the wrong routine. In ProcessSingles, PushSingle isn't called for every iteration of the for (i = 0; i < SingleCnt; i++) loop, so it doesn't cause an endless loop.

I tried the routine on the following puzzle, (the first puzzle in the top50k), and the first few times ProcessSingles is called, it didn't call PushSingle from within this loop at all.

081600090000000000004037600600400500030000070007002004005210300000000000070004810

I'm not sure why you're seeing that out of bounds error, but there must be something that's not been converted correctly, and it might not necessarily be in this routine, it could be almost anywhere. Perhaps the best way to solve this issue would be to compile the original code in a C compiler, compile your code in java, and step through both sets of code side by side, both attempting to solve the same puzzle. if your code is right, then you should see the same values in each at any give time. It would be a little slow going though.

sudoking

Joined: 20 Oct 2009

Posts: 40

Items

Posted: Tue Dec 15, 2009 4:09 pm Post subject:

ThemePark wrote:

Well, you are right, I must've done something wrong because I got the code to compile and run now. The first test gave me a time of 8.39 seconds, which isn't too bad, considering that I thought it would be much slower.

To make sure it worked properly, I also had a variable keep track of how many sudokus in the top 50000 had only one solution, and fortunately the program decided they all only had one, just like the original program does, so it seems to work perfectly.

Now I'll try to replace the calls to the #defines with the actual code instead, and see if that speeds things up a bit.

Excellent. Smile

You should also test it with a list of sudokus that have more than one solution, and some that have no solution at all. You could make these lists by adding or removing a few key values to a single solution sudoku.

ThemePark

Joined: 22 Mar 2009

Posts: 17

Items

Posted: Tue Dec 15, 2009 4:25 pm Post subject:

Yeah, I don't know what my error was, but I solved it by starting from the beginning and going through the code from top to bottom, changing one line at a time with your suggestions. I've now tried running the program using both #defines as private methods, running it with one removed and with both removed. I ran each version 10 times to get an average, and I ended up with 8.2108, 8.3221 and 8.3063 seconds respectively. So it seems not to change anything whether I use those two private methods or not. I've been running the program while I've also been running another Java program that takes a few hours to complete. So I will try to reboot my computer, and not run any other Java programs than the Sudoku Solver to see if it that speeds it up a bit. But I can live with 8 seconds of time, considering that we're still talking about 50,000 sudokus here. I will try to supply puzzles with no and many solutions and see how that works out later on. And I will post my complete Java implementation here, but because it's a lot of code, I will post it as a seperate post. So sorry in advance for the double posting. Update: I tried running it with the top 50000 sudokus, replacing a random number for each of them, running it with a puzzle grid I know has more than 1 solution, and running it with an empty grid. No matter what, the solver never returns more than 1 as the number of solutions. Even for the empty grid, it still returns 1. I'm not quite sure what went wrong in my code, I can't seem to pinpoint the error. Last edited by ThemePark on Tue Dec 15, 2009 5:20 pm; edited 1 time in total

ThemePark

Joined: 22 Mar 2009

Posts: 17

Items

Posted: Tue Dec 15, 2009 4:26 pm Post subject:

Code:

package Puzzles.Sudoku.Solvers.BB;

import java.io.BufferedReader;
import java.io.File;
import java.io.FileReader;
import java.io.IOException;

public class BB_Sudoku_Solver {
private static int solutions;

public static void main(String[] args) throws IOException {
   BufferedReader input = new BufferedReader(new FileReader(new File("top50000.sdm")));
   String sudoku;
   int[][] puzzles = new int[50000][81];

   for (byte i = 0; i < 64; i++) {
      G[i] = new Grid_Type();
   }
   bb_init();

   int index = 0;
   while ((sudoku = input.readLine()) != null) {
      for (byte i = 0; i < 81; i++) {
         puzzles[index][i] = Character.digit(sudoku.charAt(i), 10);
      }
      index++;
   }
   input.close();

   long startTime = System.currentTimeMillis();
   for (int i = 0; i < 50000; i++) {
      bb_solver(puzzles[i]);
   }
   long endTime = System.currentTimeMillis();
   System.out.println(endTime - startTime);
   System.out.println(solutions);
}

/****************************************************************\
** BB_Sudoku Bit Based Sudoku Solver **
\****************************************************************/

/****************************************************************\
** (c) Copyright Brian Turner, 2008-2009. This file may be **
** freely used, modified, and copied for personal, **
** educational, or non-commercial purposes provided this **
** notice remains attached. **
\****************************************************************/

/****************************************************************\
** The solver source code has now been broken into 3 files: **
** - bb_sudoku.cpp : Driver code which handles things **
** like decoding arguments, **
** loading puzzles, timings, **
** and outputs. **
** - bb_sudoku_solver.cpp : The actual solver code **
** - bb_sudoku_tables.h : Various tables used for solving **
** - random.h : Various Random Number Generators **
** **
** I do use a nonstandard method for including the solver code, **
** but it makes compiling from the command line easier and **
** does not need a makefile or anything. **
** **
** **
** Compiling: **
** **
** This code has been compiled with both Visual C (Windows), **
** and gcc (Linux). The following shows options used: **
** **
** Visual C (tested under Windows XP) **
** Build under a Win32 Console Application, turn off the **
** precomiled headers, and use the Release configuration **
** for full optimizations. **
** NOTE: Under XP, there is a Windows bug when using the **
** timer with AMDs that can cause negative times. **
** **
** GCC (tested under Ubuntu 8.10) **
** Use the following command line to compile the code: **
** **
** gcc -O3 -lrt -xc -obb_sudoku.out bb_sudoku.cpp **
** **
** -O3 = preform full optimizations **
** -lrt = needed for linking of timing routines **
** -xc = compile as a C program **
** -oBB_Sudoku.out = name of the output file **
** BB_Sudoku.cpp = name of file to compile **
** **
\****************************************************************/

// V2B and B2V stand for "Binary to Value" and "Value to
// Binary", and 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). NSetX provides a lookup
// to the xth bit in the value

// Values to Bit positions lookup
static final int V2B[] = {0x00000000, 0x00000001, 0x00000002, 0x00000004, 0x00000008,
                                    0x00000010, 0x00000020, 0x00000040, 0x00000080,
                                    0x00000100, 0x00000200, 0x00000400, 0x00000800,
                                    0x00001000, 0x00002000, 0x00004000, 0x00008000,
                                    0x00010000, 0x00020000, 0x00040000, 0x00080000,
                                    0x00100000, 0x00200000, 0x00400000, 0x00800000,
                                    0x01000000, 0x02000000, 0x04000000, 0x08000000,
                                    0x10000000, 0x20000000, 0x40000000, 0x80000000};

// Bits to Value lookup
static int B2V[] = new int[512];

// Number of bits set in the number, up to 9 bits, along with
// a lookup for getting the xth bit of the value
static int NSet[] = new int[512], NSetX[][] = new int[512][10];

// Groups and P2Group define the groups for a standard
// 3x3 grid and a look from a position (0-80) to the
// three groups it is a part of.

// In_Groups defines all the cells included in all the groups associated with
// with the index cell. It includes 8 for the 8, 8 for the column, and 4 for
// the remaining cells in the box that are not in the row or column.
static final byte In_Groups[][] =
   {{ 1, 2, 3, 4, 5, 6, 7, 8, 9, 18, 27, 36, 45, 54, 63, 72, 10, 11, 19, 20 },
   { 0, 2, 3, 4, 5, 6, 7, 8, 10, 19, 28, 37, 46, 55, 64, 73, 9, 11, 18, 20 },
   { 0, 1, 3, 4, 5, 6, 7, 8, 11, 20, 29, 38, 47, 56, 65, 74, 9, 10, 18, 19 },
   { 0, 1, 2, 4, 5, 6, 7, 8, 12, 21, 30, 39, 48, 57, 66, 75, 13, 14, 22, 23 },
   { 0, 1, 2, 3, 5, 6, 7, 8, 13, 22, 31, 40, 49, 58, 67, 76, 12, 14, 21, 23 },
   { 0, 1, 2, 3, 4, 6, 7, 8, 14, 23, 32, 41, 50, 59, 68, 77, 12, 13, 21, 22 },
   { 0, 1, 2, 3, 4, 5, 7, 8, 15, 24, 33, 42, 51, 60, 69, 78, 16, 17, 25, 26 },
   { 0, 1, 2, 3, 4, 5, 6, 8, 16, 25, 34, 43, 52, 61, 70, 79, 15, 17, 24, 26 },
   { 0, 1, 2, 3, 4, 5, 6, 7, 17, 26, 35, 44, 53, 62, 71, 80, 15, 16, 24, 25 },
   { 10, 11, 12, 13, 14, 15, 16, 17, 0, 18, 27, 36, 45, 54, 63, 72, 1, 2, 19, 20 },
   { 9, 11, 12, 13, 14, 15, 16, 17, 1, 19, 28, 37, 46, 55, 64, 73, 0, 2, 18, 20 },
   { 9, 10, 12, 13, 14, 15, 16, 17, 2, 20, 29, 38, 47, 56, 65, 74, 0, 1, 18, 19 },
   { 9, 10, 11, 13, 14, 15, 16, 17, 3, 21, 30, 39, 48, 57, 66, 75, 4, 5, 22, 23 },
   { 9, 10, 11, 12, 14, 15, 16, 17, 4, 22, 31, 40, 49, 58, 67, 76, 3, 5, 21, 23 },
   { 9, 10, 11, 12, 13, 15, 16, 17, 5, 23, 32, 41, 50, 59, 68, 77, 3, 4, 21, 22 },
   { 9, 10, 11, 12, 13, 14, 16, 17, 6, 24, 33, 42, 51, 60, 69, 78, 7, 8, 25, 26 },
   { 9, 10, 11, 12, 13, 14, 15, 17, 7, 25, 34, 43, 52, 61, 70, 79, 6, 8, 24, 26 },
   { 9, 10, 11, 12, 13, 14, 15, 16, 8, 26, 35, 44, 53, 62, 71, 80, 6, 7, 24, 25 },
   { 19, 20, 21, 22, 23, 24, 25, 26, 0, 9, 27, 36, 45, 54, 63, 72, 1, 2, 10, 11 },
   { 18, 20, 21, 22, 23, 24, 25, 26, 1, 10, 28, 37, 46, 55, 64, 73, 0, 2, 9, 11 },
   { 18, 19, 21, 22, 23, 24, 25, 26, 2, 11, 29, 38, 47, 56, 65, 74, 0, 1, 9, 10 },
   { 18, 19, 20, 22, 23, 24, 25, 26, 3, 12, 30, 39, 48, 57, 66, 75, 4, 5, 13, 14 },
   { 18, 19, 20, 21, 23, 24, 25, 26, 4, 13, 31, 40, 49, 58, 67, 76, 3, 5, 12, 14 },
   { 18, 19, 20, 21, 22, 24, 25, 26, 5, 14, 32, 41, 50, 59, 68, 77, 3, 4, 12, 13 },
   { 18, 19, 20, 21, 22, 23, 25, 26, 6, 15, 33, 42, 51, 60, 69, 78, 7, 8, 16, 17 },
   { 18, 19, 20, 21, 22, 23, 24, 26, 7, 16, 34, 43, 52, 61, 70, 79, 6, 8, 15, 17 },
   { 18, 19, 20, 21, 22, 23, 24, 25, 8, 17, 35, 44, 53, 62, 71, 80, 6, 7, 15, 16 },
   { 28, 29, 30, 31, 32, 33, 34, 35, 0, 9, 18, 36, 45, 54, 63, 72, 37, 38, 46, 47 },
   { 27, 29, 30, 31, 32, 33, 34, 35, 1, 10, 19, 37, 46, 55, 64, 73, 36, 38, 45, 47 },
   { 27, 28, 30, 31, 32, 33, 34, 35, 2, 11, 20, 38, 47, 56, 65, 74, 36, 37, 45, 46 },
   { 27, 28, 29, 31, 32, 33, 34, 35, 3, 12, 21, 39, 48, 57, 66, 75, 40, 41, 49, 50 },
   { 27, 28, 29, 30, 32, 33, 34, 35, 4, 13, 22, 40, 49, 58, 67, 76, 39, 41, 48, 50 },
   { 27, 28, 29, 30, 31, 33, 34, 35, 5, 14, 23, 41, 50, 59, 68, 77, 39, 40, 48, 49 },
   { 27, 28, 29, 30, 31, 32, 34, 35, 6, 15, 24, 42, 51, 60, 69, 78, 43, 44, 52, 53 },
   { 27, 28, 29, 30, 31, 32, 33, 35, 7, 16, 25, 43, 52, 61, 70, 79, 42, 44, 51, 53 },
   { 27, 28, 29, 30, 31, 32, 33, 34, 8, 17, 26, 44, 53, 62, 71, 80, 42, 43, 51, 52 },
   { 37, 38, 39, 40, 41, 42, 43, 44, 0, 9, 18, 27, 45, 54, 63, 72, 28, 29, 46, 47 },
   { 36, 38, 39, 40, 41, 42, 43, 44, 1, 10, 19, 28, 46, 55, 64, 73, 27, 29, 45, 47 },
   { 36, 37, 39, 40, 41, 42, 43, 44, 2, 11, 20, 29, 47, 56, 65, 74, 27, 28, 45, 46 },
   { 36, 37, 38, 40, 41, 42, 43, 44, 3, 12, 21, 30, 48, 57, 66, 75, 31, 32, 49, 50 },
   { 36, 37, 38, 39, 41, 42, 43, 44, 4, 13, 22, 31, 49, 58, 67, 76, 30, 32, 48, 50 },
   { 36, 37, 38, 39, 40, 42, 43, 44, 5, 14, 23, 32, 50, 59, 68, 77, 30, 31, 48, 49 },
   { 36, 37, 38, 39, 40, 41, 43, 44, 6, 15, 24, 33, 51, 60, 69, 78, 34, 35, 52, 53 },
   { 36, 37, 38, 39, 40, 41, 42, 44, 7, 16, 25, 34, 52, 61, 70, 79, 33, 35, 51, 53 },
   { 36, 37, 38, 39, 40, 41, 42, 43, 8, 17, 26, 35, 53, 62, 71, 80, 33, 34, 51, 52 },
   { 46, 47, 48, 49, 50, 51, 52, 53, 0, 9, 18, 27, 36, 54, 63, 72, 28, 29, 37, 38 },
   { 45, 47, 48, 49, 50, 51, 52, 53, 1, 10, 19, 28, 37, 55, 64, 73, 27, 29, 36, 38 },
   { 45, 46, 48, 49, 50, 51, 52, 53, 2, 11, 20, 29, 38, 56, 65, 74, 27, 28, 36, 37 },
   { 45, 46, 47, 49, 50, 51, 52, 53, 3, 12, 21, 30, 39, 57, 66, 75, 31, 32, 40, 41 },
   { 45, 46, 47, 48, 50, 51, 52, 53, 4, 13, 22, 31, 40, 58, 67, 76, 30, 32, 39, 41 },
   { 45, 46, 47, 48, 49, 51, 52, 53, 5, 14, 23, 32, 41, 59, 68, 77, 30, 31, 39, 40 },
   { 45, 46, 47, 48, 49, 50, 52, 53, 6, 15, 24, 33, 42, 60, 69, 78, 34, 35, 43, 44 },
   { 45, 46, 47, 48, 49, 50, 51, 53, 7, 16, 25, 34, 43, 61, 70, 79, 33, 35, 42, 44 },
   { 45, 46, 47, 48, 49, 50, 51, 52, 8, 17, 26, 35, 44, 62, 71, 80, 33, 34, 42, 43 },
   { 55, 56, 57, 58, 59, 60, 61, 62, 0, 9, 18, 27, 36, 45, 63, 72, 64, 65, 73, 74 },
   { 54, 56, 57, 58, 59, 60, 61, 62, 1, 10, 19, 28, 37, 46, 64, 73, 63, 65, 72, 74 },
   { 54, 55, 57, 58, 59, 60, 61, 62, 2, 11, 20, 29, 38, 47, 65, 74, 63, 64, 72, 73 },
   { 54, 55, 56, 58, 59, 60, 61, 62, 3, 12, 21, 30, 39, 48, 66, 75, 67, 68, 76, 77 },
   { 54, 55, 56, 57, 59, 60, 61, 62, 4, 13, 22, 31, 40, 49, 67, 76, 66, 68, 75, 77 },
   { 54, 55, 56, 57, 58, 60, 61, 62, 5, 14, 23, 32, 41, 50, 68, 77, 66, 67, 75, 76 },
   { 54, 55, 56, 57, 58, 59, 61, 62, 6, 15, 24, 33, 42, 51, 69, 78, 70, 71, 79, 80 },
   { 54, 55, 56, 57, 58, 59, 60, 62, 7, 16, 25, 34, 43, 52, 70, 79, 69, 71, 78, 80 },
   { 54, 55, 56, 57, 58, 59, 60, 61, 8, 17, 26, 35, 44, 53, 71, 80, 69, 70, 78, 79 },
   { 64, 65, 66, 67, 68, 69, 70, 71, 0, 9, 18, 27, 36, 45, 54, 72, 55, 56, 73, 74 },
   { 63, 65, 66, 67, 68, 69, 70, 71, 1, 10, 19, 28, 37, 46, 55, 73, 54, 56, 72, 74 },
   { 63, 64, 66, 67, 68, 69, 70, 71, 2, 11, 20, 29, 38, 47, 56, 74, 54, 55, 72, 73 },
   { 63, 64, 65, 67, 68, 69, 70, 71, 3, 12, 21, 30, 39, 48, 57, 75, 58, 59, 76, 77 },
   { 63, 64, 65, 66, 68, 69, 70, 71, 4, 13, 22, 31, 40, 49, 58, 76, 57, 59, 75, 77 },
   { 63, 64, 65, 66, 67, 69, 70, 71, 5, 14, 23, 32, 41, 50, 59, 77, 57, 58, 75, 76 },
   { 63, 64, 65, 66, 67, 68, 70, 71, 6, 15, 24, 33, 42, 51, 60, 78, 61, 62, 79, 80 },
   { 63, 64, 65, 66, 67, 68, 69, 71, 7, 16, 25, 34, 43, 52, 61, 79, 60, 62, 78, 80 },
   { 63, 64, 65, 66, 67, 68, 69, 70, 8, 17, 26, 35, 44, 53, 62, 80, 60, 61, 78, 79 },
   { 73, 74, 75, 76, 77, 78, 79, 80, 0, 9, 18, 27, 36, 45, 54, 63, 55, 56, 64, 65 },
   { 72, 74, 75, 76, 77, 78, 79, 80, 1, 10, 19, 28, 37, 46, 55, 64, 54, 56, 63, 65 },
   { 72, 73, 75, 76, 77, 78, 79, 80, 2, 11, 20, 29, 38, 47, 56, 65, 54, 55, 63, 64 },
   { 72, 73, 74, 76, 77, 78, 79, 80, 3, 12, 21, 30, 39, 48, 57, 66, 58, 59, 67, 68 },
   { 72, 73, 74, 75, 77, 78, 79, 80, 4, 13, 22, 31, 40, 49, 58, 67, 57, 59, 66, 68 },
   { 72, 73, 74, 75, 76, 78, 79, 80, 5, 14, 23, 32, 41, 50, 59, 68, 57, 58, 66, 67 },
   { 72, 73, 74, 75, 76, 77, 79, 80, 6, 15, 24, 33, 42, 51, 60, 69, 61, 62, 70, 71 },
   { 72, 73, 74, 75, 76, 77, 78, 80, 7, 16, 25, 34, 43, 52, 61, 70, 60, 62, 69, 71 },
   { 72, 73, 74, 75, 76, 77, 78, 79, 8, 17, 26, 35, 44, 53, 62, 71, 60, 61, 69, 70 }};

// Defines the groups used in a standard 3x3 grid
static final byte Group[][] =
   {{ 0, 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 },

   { 0, 9, 18, 27, 36, 45, 54, 63, 72 }, { 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 },

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

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

// Defines the interaction of segments used for Lock Candidate searches
static final byte LC_Segment[][] =
   {{1, 2, 3, 6}, {0, 2, 4, 7}, {0, 1, 5, 8}, {4, 5, 0, 6}, {3, 5, 1, 7}, {3, 4, 2, 8}, {7, 8, 0, 3}, {6, 8, 1, 4}, {6, 7, 2, 5}};

static class Grid_Type {
   int CellsLeft; // Cells left to solve
   int Grid[] = new int[81]; // Possibilities left for each cell
   int Grp[] = new int[27]; // Values found in each group
}
static Grid_Type G[] = new Grid_Type[64];

static Grid_Type Gp;

// Solution Grid, which will contain the answer after the puzzle is solved
static int SolGrid[] = new int[81];

// Naked Singles FIFO stack - new singles found are stored here before
static byte SingleCnt = 0;
static byte SinglePos[] = new byte[128];
static int SingleVal[] = new int[128];
static void PushSingle(byte p, int b) { SinglePos[SingleCnt] = p; SingleVal[SingleCnt] = b; SingleCnt++; Changed = 1; }

// Changed Flags
static int Changed; // Flag to indicate Grid has changed
static byte ChangedGroup[] = new byte[27]; // Marks which groups have changed
static byte ChangedLC[] = new byte[27];
static int SingleGroup[] = new int[27];

static void MarkChanged(int x) { ChangedGroup[C2Grp[x][0]] = ChangedGroup[C2Grp[x][1]] = ChangedGroup[C2Grp[x][2]] = (byte) (Changed = 1); }

// Guess structure
static byte GuessPos[] = new byte[128];
static int GuessVal[] = new int[128];
static int OneStepP[] = new int[81], OneStepI;

// Key global variables used throughout the solving
static int PuzSolCnt; // Solutions for a single puzzle
static int No_Sol; // Flag to indicate there is no solution possible
static int PIdx; // Position Index, used for guessing and backtracking

// Debug stats
static int SCnt = 0, HCnt = 0, GCnt = 0, LCCnt = 0, SSCnt = 0, FCnt = 0, OneCnt = 0, TwoCnt = 0;
static long TSCnt = 0, THCnt = 0, TGCnt = 0, TLCCnt = 0, TSSCnt = 0, TFCnt = 0, TOneCnt = 0, TTwoCnt = 0;
static int MaxDepth = 0, Givens = 0;

/****************\
** InitTables *************************************************\
** **
** populates the B2V and NSet tables. They can **
** be initialized when defined, but if the grid sizes are **
** increased, the size of these tables will also increase **
** exponentially (9x9=512 items, 25x25=33,554,432 items). **
** **
\****************************************************************/
static void bb_init() {
   int i, v;

   for (i = 0; i < 512; i++) {
      B2V[i] = NSet[i] = 0;
      for (v = i; v != 0; NSet[i]++) {
         NSetX[i][NSet[i]] = v & -v;
         v = v ^ NSetX[i][NSet[i]];
      }
   }
   for (i = 1; i <= 9; i++)
      B2V[1 << (i - 1)] = i;
}

/************\
** Solver *****************************************************\
** **
** Solver runs the sudoku solver. Input puzzle is in the **
** buffer array, and somewhat controlled by a number of **
** globals (see the globals at the top of the main program **
** for globals and meanings). **
** **
\****************************************************************/
static int bb_solver(int puzzle[]) {
   int i;

   PuzSolCnt = 0;

   InitGrid();

   for (i = 0; i < 81; i++)
      if (puzzle[i] != 0)
         PushSingle((byte) i, V2B[puzzle[i]]);

   // Loop through the puzzle solving routines until finished
   while (Changed != 0) {
      // If No Solution possible, jump straight to the backtrack routine
      if (No_Sol == 0) {
         // Check if any Singles to be propogated
         if (SingleCnt != 0) {
            SCnt++;
            if (SingleCnt > 2) // If multiple singles
               ProcessInitSingles(); // process them all at once
            if (SingleCnt != 0) // otherwise
               ProcessSingles(); // process them one at a time
            if (Gp.CellsLeft == 0) {
               if (No_Sol == 0) {
                  PuzSolCnt++;
                  if (PuzSolCnt > 1)
                     break;
               }
               No_Sol = Changed = 1;
               continue;
            }
         }

         // If nothing has changed, apply the next solver
         if (Changed != 0) {
            HCnt++;
            FindHiddenSingles();
            if (SingleCnt != 0)
               continue;
            LCCnt++;
            FindLockedCandidates();
            if (Changed != 0)
               continue;
         }
      }

      //If nothing new found, just make a guess
      GCnt++;
      MakeGuess();
      if (No_Sol != 0)
         break;
   }

   TSCnt += SCnt; // Update Stats
   THCnt += HCnt;
   TGCnt += GCnt;
   TLCCnt += LCCnt;
   TSSCnt += SSCnt;
   TFCnt += FCnt;
   TOneCnt += OneCnt;
   TTwoCnt += TwoCnt;

   if (PuzSolCnt == 1)
      solutions++;
   return PuzSolCnt;
}

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

   // Initialize some key variables
   PIdx = 0;
   Gp = G[PIdx];
   Gp.CellsLeft = 81;
   SingleCnt = 0;
   Changed = 1;
   No_Sol = 0;
   OneStepI = 0;
   Givens = 0;
   SCnt = HCnt = GCnt = LCCnt = SSCnt = FCnt = OneCnt = TwoCnt = 0;

   // Loop through the buffer and set the singles to be set
   for (i = 0; i < 81; i++) {
      Gp.Grid[i] = 0x1FF;
      SolGrid[i] = OneStepP[i] = 0;
   }

   // Clear the Groups Found values
   for (i = 0; i < 27; i++)
      Gp.Grp[i] = ChangedGroup[i] = ChangedLC[i] = (byte) (SingleGroup[i] = 0);
}

/************************\
** ProcessInitSingles *****************************************\
** **
** ProcessInitSingles 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. **
** **
** This routines marks all the groups first, then marks the **
** cells for each changed groups. **
** **
\****************************************************************/
static void ProcessInitSingles () {
   int i, t, g, t2, j;
   int b;

   while (SingleCnt > 2) {
      for (i = 0; i < SingleCnt; i++) {
         t = SinglePos[i]; // Get local copy of position
         b = SingleVal[i]; // Get local copy of the value

         if (Gp.Grid[t] == 0) // Check if we already processed this position
            continue;
         if ((Gp.Grid[t] & b) == 0) { // Check for error conditions
            No_Sol = 1; SingleCnt = (byte) (Changed = 0); return;
         }
         SolGrid[t] = b; // Store the single in the solution grid
         Gp.CellsLeft--; // mark one less empty space
         Gp.Grid[t] = 0; // mark this position processed
         for (g = 0; g < 3; g++) { // loop through all 3 groups
            if ((Gp.Grp[C2Grp[t][g]] & b) != 0) {
               No_Sol = 1; SingleCnt = (byte) (Changed = 0);
               return;
            }
            Gp.Grp[C2Grp[t][g]] |= b; // mark the value as found in the group
            SingleGroup[C2Grp[t][g]] = 1;
         }
      }

      SingleCnt = 0;
      for (i = 0; i < 27; i++)
         if (SingleGroup[i] != 0) {
            SingleGroup[i] = 0;
            for (j = 0; j < 9; j++) {
               t2 = Group[i][j]; // get temp copy of position
               b = Gp.Grp[i];
               if ((Gp.Grid[t2] & b) != 0) { // check if removing a possibility
                  Gp.Grid[t2] = Gp.Grid[t2] & ~b; // remove possibility
                  if (Gp.Grid[t2] == 0) { // check for error (no possibility)
                     No_Sol = 1; SingleCnt = 0; Changed = 0;
                     return;
                  }
                  if (B2V[Gp.Grid[t2]] != 0) // Check if a naked single is found
                     PushSingle((byte) t2, Gp.Grid[t2]);
                  MarkChanged(t2); // Mark groups as changed
               }
            }
         }
   }
}

/********************\
** 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. **
** **
** This routines marks cells changed as each single is **
** processed. **
** **
\****************************************************************/
static void ProcessSingles () {
   int i, t, g, t2;
   int 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 (Gp.Grid[t] == 0) // Check if we already processed this position
         continue;
      if ((Gp.Grid[t] & b) == 0) { // Check for error conditions
         No_Sol = 1; SingleCnt = (byte) (Changed = 0);
         return;
      }
      SolGrid[t] = b; // Store the single in the solution grid
      Gp.CellsLeft--; // mark one less empty space
      Gp.Grid[t] = 0; // mark this position processed

      for (g = 0; g < 3; g++) // loop through all 3 groups
         Gp.Grp[C2Grp[t][g]] |= b; // mark the value as found in the group
      for (g = 0; g < 20; g++) { // loop through each cell in the groups
         t2 = (int) In_Groups[t][g]; // get temp copy of position
         if ((Gp.Grid[t2] & b) != 0) { // check if removing a possibility
            Gp.Grid[t2] = Gp.Grid[t2] ^ b; // remove possibility
            if (Gp.Grid[t2] == 0) { // check for error (no possibility)
               No_Sol = 1; SingleCnt = 0; Changed = 0;
               return;
            }
            if (B2V[Gp.Grid[t2]] != 0) // Check if a naked single is found
               PushSingle((byte) t2, Gp.Grid[t2]);
            MarkChanged(t2); // Mark groups as changed
         }
      }
   }
   SingleCnt = 0; // Clear the single count
}

/***********************\
** 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. **
** **
\****************************************************************/
static void FindHiddenSingles () {
   int t1, t2, t3, b, t;
   int i, j;
   byte g;

   for (i = 0; i < 27; i++)
      if (ChangedGroup[i] != 0) {
         ChangedLC[i] = 1;
         t1 = t2 = t3 = 0;
         for (j = 0; j < 9; j++) {
            b = Gp.Grid[Group[i][j]];
            t2 = t2 | (t1 & b);
            t1 = t1 | b;
         }
         if ((t1 | Gp.Grp[i]) != 0x01FF) {
            No_Sol = 1; SingleCnt = 0; Changed = 0;
            return;
         }
         t3 = t2 ^ t1;
         if (t3 != 0) {
            for (j = 0; j < 9; j++) {
               g = Group[i][j];
               if ((t3 & Gp.Grid[g]) != 0) {
                  t = t3 & Gp.Grid[g];
                  if (B2V[t] == 0) {
                     No_Sol = 1; SingleCnt = 0; Changed = 0;
                     return;
                  }
                  PushSingle((byte) g, t);
                  if (t3 == t)
                     return;
                  t3 = t3 ^ t;
               }
            }
         }
         ChangedGroup[i] = 0;
      }
   Changed = 0;
}

/**************************\
** FindLockedCandidates ***************************************\
** **
** FindLockedCandidates will scan through the grid to find **
** any locked candidates. **
** **
\****************************************************************/
static void FindLockedCandidates () {
   int Seg[] = new int[9], b;
   int i, j, k, x;
   int s, s1, s2, gp;

   for (i = 0; i < 18; i += 3)
      if (ChangedLC[i] != 0 || ChangedLC[i + 1] != 0 || ChangedLC[i + 2] != 0) {
         int gpg[] = Gp.Grid;
         ChangedLC[i] = ChangedLC[i + 1] = ChangedLC[i + 2] = 0;
         Seg[0] = gpg[Group[i ][0]] | gpg[Group[i ][1]] | gpg[Group[i ][2]];
         Seg[1] = gpg[Group[i ][3]] | gpg[Group[i ][4]] | gpg[Group[i ][5]];
         Seg[2] = gpg[Group[i ][6]] | gpg[Group[i ][7]] | gpg[Group[i ][8]];
         Seg[3] = gpg[Group[i + 1][0]] | gpg[Group[i + 1][1]] | gpg[Group[i + 1][2]];
         Seg[4] = gpg[Group[i + 1][3]] | gpg[Group[i + 1][4]] | gpg[Group[i + 1][5]];
         Seg[5] = gpg[Group[i + 1][6]] | gpg[Group[i + 1][7]] | gpg[Group[i + 1][8]];
         Seg[6] = gpg[Group[i + 2][0]] | gpg[Group[i + 2][1]] | gpg[Group[i + 2][2]];
         Seg[7] = gpg[Group[i + 2][3]] | gpg[Group[i + 2][4]] | gpg[Group[i + 2][5]];
         Seg[8] = gpg[Group[i + 2][6]] | gpg[Group[i + 2][7]] | gpg[Group[i + 2][8]];
         for (j = 0; j < 9; j++) {
            b = Seg[j] & ((Seg[LC_Segment[j][0]] | Seg[LC_Segment[j][1]]) ^ (Seg[LC_Segment[j][2]] | Seg[LC_Segment[j][3]]));
            if (b != 0) {
               for (k = 0; k < 4; k++) {
                  s = LC_Segment[j][k];
                  s1 = i + s / 3;
                  s2 = (s % 3) * 3;
                  for (x = 0; x < 3; x++) {
                     gp = Group[s1][s2 + x];
                     if ((Gp.Grid[gp] & b) != 0) {
                        Gp.Grid[gp] = Gp.Grid[gp] & ~b;
                        MarkChanged(gp);
                        if (Gp.Grid[gp] == 0) {
                           No_Sol = 1; SingleCnt = 0; Changed = 0;
                           return;
                        }
                        if (B2V[Gp.Grid[gp]] != 0)
                           PushSingle((byte) gp, Gp.Grid[gp]);
                     }
                  }
               }
               return;
            }
         }
      }
}

/***************\
** MakeGuess **************************************************\
** **
** MakeGuess handles the guessing and backtracking used **
** when solving puzzles. **
** **
\****************************************************************/
static void MakeGuess () {
   byte gpp = GuessPos[PIdx];
   int ns;
   int LastPos = 0;
   int i;
   int v;
   int Found = 0;
   byte mt;

   Changed = 1;
   SingleCnt = 0;

   // Check to see where the next guess should be
   if (No_Sol != 0) {
      while (No_Sol != 0) {
         if (PIdx == 0)
            return;
         G[PIdx - 1].Grid[gpp] ^= GuessVal[PIdx];
         if (G[PIdx - 1].Grid[gpp] != 0) {
            if (B2V[G[PIdx - 1].Grid[gpp]] != 0)
               PushSingle(gpp, G[PIdx - 1].Grid[gpp]);
            No_Sol = 0;
            MarkChanged(gpp);
            PIdx--;
            Gp = G[PIdx];
            return;
         }
      }
   }

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

   // Find next spot to check
   if (Found == 0) {
      mt = 99;
      i = LastPos;
      do {
         ns = NSet[Gp.Grid[i]];
         if ((ns < mt) && (ns > 1)) {
            GuessPos[PIdx] = (byte) i;
            mt = (byte) ns;
            if (mt == 2) // if 2, then its the best it can get
               break;
         }
         if (++i >= 81)
            i = 0;
      } while (i != LastPos);
      LastPos = i;
   }

   // Mark the next guess in the position
   No_Sol = 1;
   v = Gp.Grid[GuessPos[PIdx]];
   if (v != 0) {
      v = v & -v;
      GuessVal[PIdx] = v;
      PushSingle(GuessPos[PIdx], v);
      Changed = 1;
      No_Sol = 0;
   }
}
}

sudoking

Joined: 20 Oct 2009

Posts: 40

Items

Posted: Tue Dec 15, 2009 6:38 pm Post subject:

Hmmm... The only difference I can see with a quick scan, is that there are no unsigned ints in your code (why they left those out of java, I'll never know). But I just converted all the unsigned ints and chars to signed in my code, and it made no difference. Is it possible for you to run a side by side test, to see where the discrepancy is?

ThemePark

Joined: 22 Mar 2009

Posts: 17

Items

Posted: Wed Dec 16, 2009 1:48 am Post subject:

So when you compile your code, it correctly returns 2 if a puzzle has many solutions? And maybe I can, but I've been having trouble compiling files in Visual Studio. I will try stepping through my code though after it has found the first solution and see what happens.

sudoking

Joined: 20 Oct 2009

Posts: 40

Items

Posted: Wed Dec 16, 2009 1:30 pm Post subject:

ThemePark wrote:

So when you compile your code, it correctly returns 2 if a puzzle has many solutions?

Yes, it returns a 2 for puzzles without a solution. Perhaps you could post a puzzle that you expect to return a 2, and I'll test it on mine.

Quote:

And maybe I can, but I've been having trouble compiling files in Visual Studio. I will try stepping through my code though after it has found the first solution and see what happens.

Here's a copy of the main.cpp file I compile with it to test it. You should be able to drop both of these files into a console project in VS, and compile it. Again, much of this code was written by Brian Turner, I just modified it to suit my needs.

Code:

/****************************************************************\
** (c) Copyright Brian Turner, 2008-2009. This file may be **
** freely used, modified, and copied for personal, **
** educational, or non-commercial purposes provided this **
** notice remains attached. **
\****************************************************************/

#ifdef WIN32
#include <windows.h> // Allow high preformance timing routines
#else
#include <time.h> // Allow high preformance timing routines
#include <stdlib.h> // For exit()
#endif
#include <stdio.h> // For IO (fgets, stdin, printf)

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

// filename used when an input file is declared
char fname[250] = {0}; // start fname as a 0 length string
static FILE *infile = stdin; // input file handle, default to stdin
static FILE *outfile = stdout; // output file handle, default to stdout

static long PuzzleCnt = 0; // Total puzzles tested
static long SolvedCnt = 0; // Total puzzles solved
static long UnsolvedCnt = 0; // Total puzzles solved
static int PuzSolCnt; // Solutions for a single puzzle

// buffer to read in the text version of puzzles (example puzzle included)
char buffer[250];

// Forward function definitions
extern void __stdcall bb_init(void);
extern int __stdcall bb_solver(unsigned *puzzle);

static void SetupTiming (void);
static void DisplayTiming (void);

// For timing, use the high preformance windows timers
#ifdef WIN32
static LARGE_INTEGER Frequency, StartTime, EndTime, SolveTime;
#define GETTIME(x) QueryPerformanceCounter (&x)
#else
struct timespec StartTime, EndTime, DiffTime;
#define GETTIME(x) (void) clock_gettime(CLOCK_REALTIME, &x)
#endif

/**********\
** main *******************************************************\
** **
** main routine sets up the timers and handles loading the **
** puzzles and calling the solver. **
** **
\****************************************************************/
int main(int argc, char* argv[])
{
unsigned puzzle[81], i, split = 0;
bb_init(); // Initialize a couple bitbased tables

SetupTiming(); // Prepare for timing the solver
GETTIME (StartTime); // Get the current timer for program timing

if (argc > 1)
   if ((infile = fopen(argv[1], "r")) == NULL) {
      fprintf(stderr, "Error opening file %s.\n", argv[1]);
      exit(1);
   }

// Read the puzzles from the stardard input, looping through all the puzzles
while (fgets(buffer, 240, infile))
{
PuzzleCnt++; // increment the puzzle count
   for (i = 0; i < 81; i++)
      puzzle[i] = buffer[i] == '.' ? 0 : buffer[i] - '0';

   PuzSolCnt = bb_solver(puzzle);

   switch (PuzSolCnt) {
      case 1:
         SolvedCnt++;
         break;
      default:
         UnsolvedCnt++;
         break;
   }
}

GETTIME (EndTime); // Get ending timer
DisplayTiming(); // Display the final timing and counts

fcloseall();
return 0;
}

/****************\
** 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). **
** **
** Note: under Windows, doing this really does make the **
** timings more consistant. Under Linux, there does **
** not appear to be anything I can do to improve **
** the consistancy of the timings. The timings **
** appear to change by 10% or more between runs. **
** **
\****************************************************************/
static void SetupTiming (void)
{
// Only do this for Windows, it does not seem to help under Linux
#ifdef WIN32
// 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)
{
GETTIME (StartTime);
do { GETTIME (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);
}
#endif
}

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

fprintf (outfile, " %5ld Puzzles, %5ld Solved, %5ld Unsolved\n", PuzzleCnt, SolvedCnt, UnsolvedCnt);
if (timing_mode == 1)
{
fulltime = (float)(EndTime.QuadPart - StartTime.QuadPart) / (float)Frequency.QuadPart;

if (fulltime > 0.95)
fprintf (outfile, " Time = %3.3f sec ", fulltime);
else if (fulltime > 0.00095)
fprintf (outfile, " Time = %3.3f msec ", fulltime * 1000);
else
fprintf (outfile, " Time = %3.3f usec ", fulltime * 1000000);
fprintf (outfile, "(%3.3f usec / puzzle)\n\n", fulltime * 1000000 / PuzzleCnt);
}
fprintf (outfile, "\n");
}

ThemePark

Joined: 22 Mar 2009

Posts: 17

Items

Posted: Thu Dec 17, 2009 4:36 pm Post subject:

Thanks, but I can't quite get it to work. I get a couple of deprecation messages in VS 2005, which I have been able to fix, and then I get these two errors:

Code:

Linking...
main.obj : error LNK2001: unresolved external symbol "int __stdcall bb_solver(unsigned int *)" (?bb_solver@@YGHPAI@Z)
main.obj : error LNK2001: unresolved external symbol "void __stdcall bb_init(void)" (?bb_init@@YGXXZ)

If I rightclick each file and choose compile, with main being last, every file compiles, but I still can't run it for some reason.

I have found out something interesting with my Java code though, although I don't understand why it happens. I run my program with an empty grid and when it has found the first solution, it then goes on to make a guess for placing a number. It then goes on to find hidden singles and locked candidates, and at that time No_Sol has become 1, causing the loop to break, and the solver to only return 1 solution.

lkSudoku

Joined: 16 May 2009

Posts: 60

Items

Posted: Thu Dec 17, 2009 7:29 pm Post subject:

ThemePark wrote:

Code:

If I rightclick each file and choose compile, with main being last, every file compiles, but I still can't run it for some reason.

Perhaps you need to declare these functions type in main source, or in a header included by main

Another thing I would check is C/C++ declerations, are main and the bb code both in C++ files

sudoking

Joined: 20 Oct 2009

Posts: 40

Items

Posted: Fri Dec 18, 2009 2:51 pm Post subject:

ThemePark wrote:

Thanks, but I can't quite get it to work. I get a couple of deprecation messages in VS 2005, which I have been able to fix, and then I get these two errors:

Code:

Sorry, My bad. __stdcall is a Microsoft calling convention modifier. It tells the compilers what calling convention to use when calling functions. When I posted the original routine, I removed it, to allow you to compile it in any compiler you like. However, when I posted the main source file, I forgot to remove it. So the linker is looking for routines with a different calling convention.

The fix is simple. Either remove the __stdcall from the main.cpp file, or replace it in the other source file. (replace "void bb_init(void)" with "void __stdcall bb_init(void)" and "int bb_solver(unsigned *puzzle)" with "int __stdcall bb_solver(unsigned *puzzle)" in the function definitions and prototypes. The prototypes are immediately below the comments at the start of the file).

ThemePark

Joined: 22 Mar 2009

Posts: 17

Items

Posted: Sat Dec 19, 2009 2:29 pm Post subject:

Thanks sudoking, I got your program to work now, and I found out that there's inconsistency somewhere in my code. I can't pinpoint it exactly though, but sometimes it doesn't find any solutions to the first sudoku and sometimes it does. On the times it does, PIdx is always different, where it should always be 7. So I'm thinking my issue is in these lines from MakeGuess:

Code:

            PIdx--;
            Gp = G[PIdx];
            return;
         }
      }
   }

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

I am not sure it's the equivalent of your C++ code, since PIdx changes all the time.

Edit:
I think I found my error. I now changed the code to this:

Code:

            PIdx--;
            Gp = G[PIdx - 1];
            return;
         }
      }
   }

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

Now PIdx seems to be consistent, although it's always 0 now. And now all the sudokus seem to have 0 solutions.

Display posts from previous:

	Sudoku Programmers Forum Index -> Programming sudoku	All times are GMT Goto page Previous 1, 2
Page 2 of 2

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