|
| View previous topic :: View next topic |
| Author |
Message |
| ThemePark
| | Joined: 22 Mar 2009 | | Posts: 17 | | : | |
Items |
|
 Posted: Tue Dec 08, 2009 8:33 pm Post subject: Optimizing Java-written DLX solver |
 |
|
I have been programming a sudoku solver in Java, that uses Dancing Links to solve a sudoku.
I compared it to a brute force solver, and found that after a few puzzles in a row, DLX becomes a lot faster than brute force. So I want to use the DLX solver in a project I'm making, but I want to optimize it as much as possible at first.
Currently, it solves 70-80 sudokus per second, which isn't very impressive, given that I've seen number of 1000 sudokus per second, using DLX. So I could use some help with optimizing my code, as shown here:
| Code: | package Puzzles:Sudoku:Solvers;
import java:util:ArrayList;
import java:util:Collections;
import Puzzles:Sudoku:Sudoku;
import Puzzles:Sudoku:Solvers:DLX:*;
public class DLXSolver {
private int sudokuSize = 9;
private byte solutions;
private Node root;
private ArrayList<Node> clues;
public DLXSolver() {
buildSparseMatrix();
}
public boolean isSudokuValid(Sudoku puzzle) {
solutions = 0;
clues = new ArrayList<Node>();
fillInClues(puzzle);
runAlgorithmX();
resetMatrix();
return (solutions == 1);
}
private void buildSparseMatrix() {
Node[][] matrix = new Node[sudokuSize * sudokuSize * sudokuSize][4 *
sudokuSize * sudokuSize];
HeaderNode[] headers = new HeaderNode[4 * sudokuSize * sudokuSize];
root = new Node();
for (int col = 0; col < 4 * sudokuSize * sudokuSize; col++) {
headers[col] = new HeaderNode();
headers[col]:setHeader(headers[col]);
headers[col]:decrementOnes();
headers[col]:IDNum = col;
}
for (byte row = 0; row < sudokuSize; row++) {
for (byte col = 0; col < sudokuSize; col++) {
for (byte number = 1; number <= sudokuSize; number++) {
matrix[row * sudokuSize * sudokuSize + col *
sudokuSize + number - 1][0 * sudokuSize * sudokuSize + row * sudokuSize + col] = new Node
();
matrix[row * sudokuSize * sudokuSize + col *
sudokuSize + number - 1][1 * sudokuSize * sudokuSize + row * sudokuSize + number - 1] = new
Node();
matrix[row * sudokuSize * sudokuSize + col *
sudokuSize + number - 1][2 * sudokuSize * sudokuSize + col * sudokuSize + number - 1] = new
Node();
matrix[row * sudokuSize * sudokuSize + col *
sudokuSize + number - 1][3 * sudokuSize * sudokuSize + ((row / (int) Math:sqrt(sudokuSize))
* (int) Math:sqrt(sudokuSize) + col / (int) Math:sqrt(sudokuSize)) * sudokuSize + number -
1] = new Node();
matrix[row * sudokuSize * sudokuSize + col *
sudokuSize + number - 1][0 * sudokuSize * sudokuSize + row * sudokuSize + col]:setHeader
(headers[0 * sudokuSize * sudokuSize + row * sudokuSize + col]);
matrix[row * sudokuSize * sudokuSize + col *
sudokuSize + number - 1][1 * sudokuSize * sudokuSize + row * sudokuSize + number -
1]:setHeader(headers[1 * sudokuSize * sudokuSize + row * sudokuSize + number - 1]);
matrix[row * sudokuSize * sudokuSize + col *
sudokuSize + number - 1][2 * sudokuSize * sudokuSize + col * sudokuSize + number -
1]:setHeader(headers[2 * sudokuSize * sudokuSize + col * sudokuSize + number - 1]);
matrix[row * sudokuSize * sudokuSize + col *
sudokuSize + number - 1][3 * sudokuSize * sudokuSize + ((row / (int) Math:sqrt(sudokuSize))
* (int) Math:sqrt(sudokuSize) + col / (int) Math:sqrt(sudokuSize)) * sudokuSize + number -
1]:setHeader(headers[3 * sudokuSize * sudokuSize + ((row / (int) Math:sqrt(sudokuSize)) *
(int) Math:sqrt(sudokuSize) + col / (int) Math:sqrt(sudokuSize)) * sudokuSize + number -
1]);
matrix[row * sudokuSize * sudokuSize + col *
sudokuSize + number - 1][0 * sudokuSize * sudokuSize + row * sudokuSize + col]:IDNum = (row
* sudokuSize * sudokuSize + col * sudokuSize + number - 1) * 1000 + 0 * sudokuSize *
sudokuSize + row * sudokuSize + col;
matrix[row * sudokuSize * sudokuSize + col *
sudokuSize + number - 1][1 * sudokuSize * sudokuSize + row * sudokuSize + number - 1]:IDNum
= (row * sudokuSize * sudokuSize + col * sudokuSize + number - 1) * 1000 + 1 * sudokuSize *
sudokuSize + row * sudokuSize + number - 1;
matrix[row * sudokuSize * sudokuSize + col *
sudokuSize + number - 1][2 * sudokuSize * sudokuSize + col * sudokuSize + number - 1]:IDNum
= (row * sudokuSize * sudokuSize + col * sudokuSize + number - 1) * 1000 + 2 * sudokuSize *
sudokuSize + col * sudokuSize + number - 1;
matrix[row * sudokuSize * sudokuSize + col *
sudokuSize + number - 1][3 * sudokuSize * sudokuSize + ((row / (int) Math:sqrt(sudokuSize))
* (int) Math:sqrt(sudokuSize) + col / (int) Math:sqrt(sudokuSize)) * sudokuSize + number -
1]:IDNum = (row * sudokuSize * sudokuSize + col * sudokuSize + number - 1) * 1000 + 3 *
sudokuSize * sudokuSize + ((row / (int) Math:sqrt(sudokuSize)) * (int) Math:sqrt
(sudokuSize) + col / (int) Math:sqrt(sudokuSize)) * sudokuSize + number - 1;
}
}
}
for (int col = 0; col < 4 * sudokuSize * sudokuSize; col++) {
for (int row = 0; row < sudokuSize * sudokuSize * sudokuSize;
row++) {
if (matrix[row][col] != null) {
for (int upRow = row - 1; upRow != row; upRow--) {
if (upRow < 0)
upRow = sudokuSize * sudokuSize *
sudokuSize - 1;
if (matrix[upRow][col] != null) {
matrix[row][col]:setUpNeighbour
(matrix[upRow][col]);
matrix[upRow]
[col]:setDownNeighbour(matrix[row][col]);
break;
}
}
for (int downRow = row + 1; downRow != row;
downRow++) {
if (downRow == sudokuSize * sudokuSize *
sudokuSize)
downRow = 0;
if (matrix[downRow][col] != null) {
matrix[row][col]:setDownNeighbour
(matrix[downRow][col]);
matrix[downRow]
[col]:setUpNeighbour(matrix[row][col]);
break;
}
}
for (int leftCol = col - 1; leftCol != col;
leftCol--) {
if (leftCol < 0)
leftCol = 4 * sudokuSize *
sudokuSize - 1;
if (matrix[row][leftCol] != null) {
matrix[row][col]:setLeftNeighbour
(matrix[row][leftCol]);
matrix[row]
[leftCol]:setRightNeighbour(matrix[row][col]);
break;
}
}
for (int rightCol = col + 1; rightCol != col;
rightCol++) {
if (rightCol == 4 * sudokuSize *
sudokuSize)
rightCol = 0;
if (matrix[row][rightCol] != null) {
matrix[row][col]:setRightNeighbour
(matrix[row][rightCol]);
matrix[row]
[rightCol]:setLeftNeighbour(matrix[row][col]);
break;
}
}
}
}
if (col > 0) {
headers[col]:setLeftNeighbour(headers[col - 1]);
headers[col - 1]:setRightNeighbour(headers[col]);
}
for (int upRow = sudokuSize * sudokuSize * sudokuSize - 1; upRow >
0; upRow--) {
if (matrix[upRow][col] != null) {
headers[col]:setUpNeighbour(matrix[upRow][col]);
matrix[upRow][col]:setDownNeighbour(headers[col]);
break;
}
}
for (int downRow = 0; downRow < sudokuSize * sudokuSize *
sudokuSize; downRow++) {
if (matrix[downRow][col] != null) {
headers[col]:setDownNeighbour(matrix[downRow]
[col]);
matrix[downRow][col]:setUpNeighbour(headers[col]);
break;
}
}
}
root:setRightNeighbour(headers[0]);
headers[0]:setLeftNeighbour(root);
root:setLeftNeighbour(headers[4 * sudokuSize * sudokuSize - 1]);
headers[4 * sudokuSize * sudokuSize - 1]:setRightNeighbour(root);
}
private void fillInClues(Sudoku sudoku) {
Node clueNode;
for (byte row = 0; row < sudokuSize; row++) {
for (byte col = 0; col < sudokuSize; col++) {
if (sudoku:getNumber(row, col) != 0) {
clueNode = root:getRightNeighbour();
while (clueNode:IDNum != row * sudokuSize + col)
clueNode = clueNode:getRightNeighbour();
while (clueNode:IDNum != (row * sudokuSize *
sudokuSize + col * sudokuSize + sudoku:getNumber(row, col) - 1) * 1000 + row * sudokuSize +
col)
clueNode = clueNode:getDownNeighbour();
clues:add(clueNode);
cover(clueNode);
for (Node rightNode = clueNode:getRightNeighbour();
rightNode != clueNode; rightNode = rightNode:getRightNeighbour())
cover(rightNode);
}
}
}
}
private void runAlgorithmX() {
if (solutions < 2) {
if (root:getRightNeighbour() != root) {
HeaderNode columnNode = chooseNextColumn();
cover(columnNode);
for (Node rowNode = columnNode:getDownNeighbour(); rowNode
!= columnNode; rowNode = rowNode:getDownNeighbour()) {
for (Node rightNode = rowNode:getRightNeighbour();
rightNode != rowNode; rightNode = rightNode:getRightNeighbour())
cover(rightNode);
runAlgorithmX();
columnNode = rowNode:getHeader();
for (Node leftNode = rowNode:getLeftNeighbour();
leftNode != rowNode; leftNode = leftNode:getLeftNeighbour())
uncover(leftNode);
}
uncover(columnNode);
}
else
solutions++;
}
}
private void resetMatrix() {
Collections:reverse(clues);
for (Node chosenNode : clues) {
for (Node leftNode = chosenNode:getLeftNeighbour(); leftNode !=
chosenNode; leftNode = leftNode:getLeftNeighbour())
uncover(leftNode);
uncover(chosenNode:getHeader());
}
}
private HeaderNode chooseNextColumn() {
HeaderNode chosenNode = (HeaderNode) root:getRightNeighbour();
HeaderNode columnNode;
for (Node node = chosenNode:getRightNeighbour(); node != root; node =
node:getRightNeighbour()) {
columnNode = (HeaderNode) node;
if (columnNode:getOnes() < chosenNode:getOnes())
chosenNode = columnNode;
}
return chosenNode;
}
private static void cover(Node dataNode) {
HeaderNode header = dataNode:getHeader();
header:getRightNeighbour():setLeftNeighbour(header:getLeftNeighbour());
header:getLeftNeighbour():setRightNeighbour(header:getRightNeighbour());
for (Node rowNode = header:getDownNeighbour(); rowNode != header; rowNode =
rowNode:getDownNeighbour()) {
for (Node rightNode = rowNode:getRightNeighbour(); rightNode !=
rowNode; rightNode = rightNode:getRightNeighbour()) {
rightNode:getUpNeighbour():setDownNeighbour
(rightNode:getDownNeighbour());
rightNode:getDownNeighbour():setUpNeighbour
(rightNode:getUpNeighbour());
}
}
}
private static void uncover(Node dataNode) {
HeaderNode header = dataNode:getHeader();
for (Node rowNode = header:getUpNeighbour(); rowNode != header; rowNode =
rowNode:getUpNeighbour()) {
for (Node leftNeighbour = rowNode:getLeftNeighbour(); leftNeighbour
!= rowNode; leftNeighbour = leftNeighbour:getLeftNeighbour()) {
leftNeighbour:getUpNeighbour():setDownNeighbour
(leftNeighbour);
leftNeighbour:getDownNeighbour():setUpNeighbour
(leftNeighbour);
}
}
header:getRightNeighbour():setLeftNeighbour(header);
header:getLeftNeighbour():setRightNeighbour(header);
}
} |
| Code: | package Puzzles:Sudoku:Solvers:DLX;
public class Node {
private Node leftNeighbour;
private Node rightNeighbour;
private Node upNeighbour;
private Node downNeighbour;
public int IDNum;
public void setLeftNeighbour(Node leftNeighbour) {
this:leftNeighbour = leftNeighbour;
}
public Node getLeftNeighbour() {
return this:leftNeighbour;
}
public void setRightNeighbour(Node rightNeighbour) {
this:rightNeighbour = rightNeighbour;
}
public Node getRightNeighbour() {
return this:rightNeighbour;
}
public void setUpNeighbour(Node upNeighbour) {
this:upNeighbour = upNeighbour;
}
public Node getUpNeighbour() {
return this:upNeighbour;
}
public void setDownNeighbour(Node downNeighbour) {
this:downNeighbour = downNeighbour;
}
public Node getDownNeighbour() {
return this:downNeighbour;
}
private HeaderNode header;
public void setHeader(HeaderNode header) {
this:header = header;
this:header:incrementOnes();
}
public HeaderNode getHeader() {
return this:header;
}
} |
| Code: | package Puzzles:Sudoku:Solvers:DLX;
public class HeaderNode extends Node {
private int ones;
public void incrementOnes() {
ones++;
}
public void decrementOnes() {
ones--;
}
public int getOnes() {
return this:ones;
}
} |
The Node and HeaderNode class are pretty standard. And I'm sure I could greatly optimize the buildSparseMatrix() method, but that's not important since I only call it once, on the creation of the solver, and just use the resetMatrix() method after that, to uncover the few clues that the sudoku contained. And when I time how long it takes to solve a puzzle, I start the timer after the matrix has been created. Also, I check for the number of solutions in runAlgorithmX() because I only want to know whether the puzzle has zero, one or many solutions, not the exact number.
runAlgorithmX() should be pretty standard as well, as I based it on some other code, and some websites explaining DLX. So the only problem I see, could be with fillInClues(), and for that I wish I could get the right Node (i.e. the one in the first of the four major columns, that tells me which number has been placed in which row and column), without having to resort to checking the IDnum of each node. But I can't imagine that is much of a bottleneck.
So is it even possible to make my program go any faster? I can't see much that can be done differently or better, so I'm inclined to believe that it's just because of Java that it's being so slow. And no, I can't change to another programming language, since this is part of a bigger project that I'm also doing in Java.
I have thought of removing the getter and setter methods and instead making the fields in Node public, and also replacing sudokuSize with the number 9, since I'm only going to run the solver on 9x9 sudokus. But I can't imagine that would give me much of a speed difference.
P. S. Because of an error with the forum software, causing the error message about 5 posts before you can post an URL, to appear I have had to replace all periods in the code with colons, to be able to post my code. If you try to run it, just replace all the colons in the code tags back to periods. |
|
| Back to top |
|
 |
| sudoking
| | Joined: 20 Oct 2009 | | Posts: 40 | | : | |
Items |
|
| Posted: Tue Dec 08, 2009 9:44 pm Post subject: |
|
|
if it's speed you want, then I'd give java and dlx a miss, and look at the bb_sudoku algorithm written in C. I know you said that the project is in java, however, would it be possible to call C code from your java project? I'm not sure of the best way to achieve this. Perhaps calling a stand alone C app that did the solving and wrote its output to a text file, which your java app could read.
If C is right out of the question, then perhaps you could look at re-writing the bb_sudoku algorithm in java, unless it's already been done. |
|
| Back to top |
|
|
| ThemePark
| | Joined: 22 Mar 2009 | | Posts: 17 | | : | |
Items |
|
| Posted: Wed Dec 09, 2009 9:35 am Post subject: |
|
|
Well, you make a good point. I actually can call a C program from Java using JNI. However I suspect that it will be much slower than my current implementation.
I couldn't get the original bb_sudoku to compile, so for now I'm gonna try to implement the DLX code into Java, and see how fast that runs.
Edit:
Okay, I've implemented the DLX code in Java, and it's still very fast. It solves about 70-80 sudokus in 32 milliseconds, where my own DLX implementation takes 700-800 milliseconds. And solving one million sudokus takes about 3 minutes. I don't know if this is fast though, or if it could be improved.
So now I wonder, how it can be so fast? I see that he unlike me doesn't seem to use classes for the matrix, but just primitives, but is that really what causes it to be so fast? Or is there something else to it? |
|
| Back to top |
|
|
| strmckr
 | | Joined: 24 Apr 2009 | | Posts: 52 | | : | |
Items |
|
| Posted: Wed Dec 09, 2009 10:49 am Post subject: |
|
|
bb_sudoku reduces search time in dlx by applying singles/blr/ subsets
first before triggering its variation of dlx.
{and possibly uses the same above during the execution to quickly cut the search tree down} |
|
| Back to top |
|
|
| sudoking
| | Joined: 20 Oct 2009 | | Posts: 40 | | : | |
Items |
|
| Posted: Wed Dec 09, 2009 11:47 am Post subject: |
|
|
| ThemePark wrote: | | Well, you make a good point. I actually can call a C program from Java using JNI. However I suspect that it will be much slower than my current implementation. |
Possibly. Can you call a C shared library from java? Of course, that would limit portability.
| Quote: | | I couldn't get the original bb_sudoku to compile, so for now I'm gonna try to implement the DLX code into Java, and see how fast that runs. |
Read the comments. bb_sudoku includes one source file within another, which ironically is designed to make it easier to compile. To compile it, only compile bb_sudoku.cpp, while will #include bb_sudoku_solver.cpp.
| Quote: | Edit:
Okay, I've implemented the DLX code in Java, and it's still very fast. It solves about 70-80 sudokus in 32 milliseconds, where my own DLX implementation takes 700-800 milliseconds. And solving one million sudokus takes about 3 minutes. I don't know if this is fast though, or if it could be improved. |
That's still pretty slow. Of course, it depends on your processor speed, but my 1.6GHz will do the top 50k puzzles in less than 2 seconds. That's an average of about 40us per puzzle.
| Quote: | | So now I wonder, how it can be so fast? I see that he unlike me doesn't seem to use classes for the matrix, but just primitives, but is that really what causes it to be so fast? Or is there something else to it? |
Hard to tell without the code.  |
|
| Back to top |
|
|
| ThemePark
| | Joined: 22 Mar 2009 | | Posts: 17 | | : | |
Items |
|
| Posted: Wed Dec 09, 2009 3:14 pm Post subject: |
|
|
Well, this is ironic. When I wanted to find the source code, I googled for bb_sudoku and found it...I thought. The title reads Bits & Bytes, but the program itself is called SOO. I thought it had just changed its name, but now that you talk about C++, I realize that I've been using the wrong program, since that one is written in C#. But that was hard to know.
So anyway, how can I get a copy of the source code and the program? I tried using the links from its thread on this forum, but all the links are dead. So do you or anyone else for that matter have it? |
|
| Back to top |
|
|
| lkSudoku
| | Joined: 16 May 2009 | | Posts: 60 | | : | |
Items |
|
| Posted: Wed Dec 09, 2009 8:40 pm Post subject: |
|
|
I think that in your case, it would be better to implement an algorithm that combines logic with backtracking, such a combination, when implemented carefully can yield fast solution time, you do not have to use the bb sudoku code, and there is no reason why it cannot be implemented in java, if you do use the bb sudoku source code, do not forget to maintain the license agreement
Combinations of logic and backtracking that are not with the same algorithm as in bb sudoku may yield slower solving time, but it will still be faster than a millisecond per puzzle on most computers |
|
| Back to top |
|
|
| strmckr
| | Joined: 24 Apr 2009 | | Posts: 52 | | : | |
Items |
|
|
| Back to top |
|
|
| sudoking
| | Joined: 20 Oct 2009 | | Posts: 40 | | : | |
Items |
|
| Posted: Thu Dec 10, 2009 12:22 pm Post subject: |
|
|
Here's a cut down version I've been using.
Call the bb_init() routine first (once), then call bb_solver(), passing it an array of unsigned ints. Returns 0 (no solution), 1 (single solution), or 2 (many solutions).
Hope this helps.
| Code: |
/****************************************************************\
** 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 **
** **
\****************************************************************/
#define CALC_STATSx
int bb_solver (unsigned *puzzle);
void bb_init(void);
/*
// masks for methodologies to use
#define USE_GUESSES 0x01 // use backtracking and guesses
#define USE_LOCK_CAND 0x02 // use locked candidates
#define USE_SUBSETS 0x04 // use subset searching
#define USE_FISHIES 0x08 // use fishies (x-wing, swordfish, jellyfish)
#define USE_1_STEP 0x10 // use one step commonalitytest
#define USE_2_STEP 0x20 // use two step commonality test
// masks for variations
#define GT_LT_PUZZLE 0x100 // Greater Than and Less Than puzzle
#define KILLER_PUZZLE 0x200 // Killer Sudoku puzzle
*/
// 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 const unsigned int V2B[33] = {0x0000, 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[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[512], NSetX[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 const unsigned char In_Groups[81][20] =
{{ 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 const unsigned char Group[27][9] =
{{ 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 const unsigned char C2Grp[81][3] =
{{ 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 const unsigned char LC_Segment[9][4] =
{{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 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;
//register struct Grid_Type *Gx;
// Solution Grid, which will contain the answer after the puzzle is solved
static unsigned int SolGrid[81];
// Naked Singles FIFO stack - new singles found are stored here before
static char SingleCnt = 0;
static char SinglePos[128];
static unsigned int SingleVal[128];
#define PushSingle(p, b) { SinglePos[SingleCnt] = p; SingleVal[SingleCnt] = b; SingleCnt++; Changed = 1; }
// Changed Flags
static int Changed; // Flag to indicate Grid has changed
static char ChangedGroup[27]; // Marks which groups have changed
static char ChangedLC[27];
static int SingleGroup[27];
#define MarkChanged(x) { unsigned char const *ucp = C2Grp[x]; ChangedGroup[*ucp] = ChangedGroup[*(ucp+1)] = ChangedGroup[*(ucp+2)] = Changed = 1; }
// original
//#define MarkChanged(x) { ChangedGroup[C2Grp[x][0]] = ChangedGroup[C2Grp[x][1]] = ChangedGroup[C2Grp[x][2]] = Changed = 1; }
// Seems to work as well. But not for everyone
//#define MarkChanged(x) ChangedGroup[C2Grp[x][0]] = Changed = 1;
// Guess structure
static char GuessPos[128];
static int GuessVal[128];
static int OneStepP[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
#ifdef CALC_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;
#endif
static int MaxDepth = 0, Givens = 0;
// forward procedure declarations
static void InitGrid ();
static void ProcessInitSingles (void);
static void ProcessSingles (void);
static void FindHiddenSingles (void);
static void FindLockedCandidates (void);
static void MakeGuess (void);
/****************\
** 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). **
** **
\****************************************************************/
void bb_init(void)
{ int i, v;
// RND_Init();
for (i = 0; i < 512; i++)
{ B2V[i] = NSet[i] = 0;
for (v = i; v; 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). **
** **
\****************************************************************/
int bb_solver(unsigned *puzzle)
{ register unsigned i;
PuzSolCnt = 0;
InitGrid();
for (i = 0; i < 81; i++)
if (puzzle[i])
PushSingle((char)(i), V2B[puzzle[i]]);
// 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)
{
#ifdef CALC_STATS
SCnt++;
#endif
if (SingleCnt > 2) // If multiple singles
ProcessInitSingles(); // process them all at once
if (SingleCnt) // otherwise
ProcessSingles(); // process them one at a time
if (!Gp->CellsLeft)
{ if (!No_Sol)
{ PuzSolCnt++;
if (PuzSolCnt > 1) break;
}
No_Sol = Changed = 1;
continue;
}
}
// If nothing has changed, apply the next solver
if (Changed)
{
#ifdef CALC_STATS
HCnt++;
#endif
FindHiddenSingles(); if (SingleCnt) continue;
// if (use_methods & USE_LOCK_CAND)
{
#ifdef CALC_STATS
LCCnt++;
#endif
FindLockedCandidates(); if (Changed) continue; }
}
}
//If nothing new found, just make a guess
#ifdef CALC_STATS
GCnt++;
#endif
MakeGuess();
if (No_Sol) break;
// if (!initp && (MaxDepth < PIdx)) MaxDepth = PIdx;
// if (PIdx > 62) { printf ("Max Depth exceeded, recompile for more depth.\n\n"); exit(0); }
}
#ifdef CALC_STATS
TSCnt += SCnt; // Update Stats
THCnt += HCnt;
TGCnt += GCnt;
TLCCnt += LCCnt;
TSSCnt += SSCnt;
TFCnt += FCnt;
TOneCnt += OneCnt;
TTwoCnt += TwoCnt;
#endif
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 (void)
{ register char i;
// Initialize some key variables
Gp = G;
Gp->CellsLeft = 81;
PIdx = 0;
SingleCnt = 0;
Changed = 1;
No_Sol = 0;
OneStepI = 0;
Givens = 0;
#ifdef CALC_STATS
SCnt = HCnt = GCnt = LCCnt = SSCnt = FCnt = OneCnt = TwoCnt = 0;
#endif
// 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] = 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 (void)
{ register unsigned char const *ucp;
register int i, t, g, t2, j;
unsigned 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) 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
ucp = C2Grp[t];
for (g = 0; g < 3; g++) { // loop through all 3 groups
if (Gp->Grp[*(ucp++)] & b) {
No_Sol = 1; SingleCnt = 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]) {
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) { // 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
}
}
}
}
}
/********************\
** 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 (void)
{ int i, t, g, t2;
register unsigned 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) 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; 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) // 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
}
/***********************\
** 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 (void)
{ unsigned int t1, t2, t3, b, t;
int i, j;
unsigned char g;
for (i = 0; i < 27; i++)
if (ChangedGroup[i])
{ 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)
{ for (j = 0; j < 9; j++)
{ g = Group[i][j];
if (t3 & Gp->Grid[g])
{ t = t3 & Gp->Grid[g];
if (!B2V[t]) { No_Sol = 1; SingleCnt = 0; Changed = 0; return; }
PushSingle((char)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 (void)
{ unsigned int Seg[9], b;
int i, j, k, x;
int s, s1, s2, gp;
for (i = 0; i < 18; i += 3)
if (ChangedLC[i] || ChangedLC[i+1] || ChangedLC[i+2])
{ register unsigned *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)
{
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)
{ Gp->Grid[gp] = Gp->Grid[gp] & ~b;
MarkChanged(gp);
if (!(Gp->Grid[gp]))
{ No_Sol = 1; SingleCnt = 0; Changed = 0; return; }
if (B2V[Gp->Grid[gp]])
PushSingle(gp, Gp->Grid[gp]);
}
}
}
return;
}
}
}
}
/***************\
** MakeGuess **************************************************\
** **
** MakeGuess handles the guessing and backtracking used **
** when solving puzzles. **
** **
\****************************************************************/
static void MakeGuess (void)
{
register char gpp = GuessPos[PIdx];
register int ns;
static int LastPos = 0;
int i;
//unsigned
int v;
int Found = 0;
char mt;
Changed = 1;
SingleCnt = 0;
// Check to see where the next guess should be
/*
if (No_Sol)
while (No_Sol)
{ if (PIdx == 0) return;
//Gp2 = Gp - 1;
(Gp - 1)->Grid[GuessPos[PIdx]] ^= GuessVal[PIdx];
if ((Gp - 1)->Grid[GuessPos[PIdx]])
{ if (B2V[(Gp - 1)->Grid[GuessPos[PIdx]]])
PushSingle(GuessPos[PIdx], (Gp - 1)->Grid[GuessPos[PIdx]]);
No_Sol = 0;
MarkChanged(GuessPos[PIdx]);
PIdx--; Gp--;
return;
}
}
*/
if (No_Sol) {
// register char gpp = GuessPos[PIdx];
while (No_Sol)
{ if (PIdx == 0) return;
//Gp2 = Gp - 1;
(Gp - 1)->Grid[gpp] ^= GuessVal[PIdx];
if ((Gp - 1)->Grid[gpp])
{ if (B2V[(Gp - 1)->Grid[gpp]])
PushSingle(gpp, (Gp - 1)->Grid[gpp]);
No_Sol = 0;
MarkChanged(gpp);
PIdx--; Gp--;
return;
}
}
}
// Populate the grid for the next guess
G[PIdx+1] = G[PIdx];
PIdx++; Gp++;
// Find next spot to check
if (!Found)
{ mt = 99;
i = LastPos;
do
{ ns = NSet[Gp->Grid[i]];
if ((ns < mt) && (ns > 1))
{ GuessPos[PIdx] = i;
mt = ns;
if (mt == 2) break; // if 2, then its the best it can get
}
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)
{
v = v & -v;
GuessVal[PIdx] = v;
PushSingle(GuessPos[PIdx], v);
Changed = 1;
No_Sol = 0;
}
}
|
Last edited by sudoking on Fri Dec 11, 2009 9:32 am; edited 2 times in total |
|
| Back to top |
|
|
| ThemePark
| | Joined: 22 Mar 2009 | | Posts: 17 | | : | |
Items |
|
| Posted: Fri Dec 11, 2009 4:28 am Post subject: |
|
|
Thanks sudoking, that looks like it's perfect. But I don't think you've pasted all of the code. I get lots of errors, and there are weird for loops like this one:
for (i = 0; i <81> 2) // If multiple singles
I've been getting a lot of errors when compiling the original code. I'm guessing this is because I use VS 2005, but he seem to have used 2008. I can't get the installation for VS 2008 to work though, but I'll have to keep trying. |
|
| Back to top |
|
|
| sudoking
| | Joined: 20 Oct 2009 | | Posts: 40 | | : | |
Items |
|
| Posted: Fri Dec 11, 2009 9:37 am Post subject: |
|
|
OMG, the forum took out huge sections of code. I thought the purpose of enclosing code in code tags was to prevent that. There's more than 10 lines of code missing from between the 81 and the >. I think it's the semicolon. It seems to work if you disable HTML. I've edited the above post, and it should compile now.
It should compile with 2005, as I compiled it with 2003.
Hope this helps. If it does, remember to thank Bri Turner, it's his code. I just added some optimisations to it, which did give some improvement in performance when compiled under 2003, but didn't really make much difference when compiled on 2008. I also cut out a lot of code that I wasn't using, or was legacy code for features that Brian had removed. The original routine that imported the puzzle was quite complex. It read the puzzle from text and allowed for comments, and special formatting characters, which I wasn't using. By removing these features, the routine is simpler, and more modular.
I shouldn't imagine this code would be too hard to convert to java. However, I wouldn't expect to get the same performance as you'll get from C. |
|
| Back to top |
|
|
| strmckr
| | Joined: 24 Apr 2009 | | Posts: 52 | | : | |
Items |
|
| Posted: Fri Dec 11, 2009 11:09 am Post subject: |
|
|
yeah it will do that if u do not disable html box (make sure its checked off!)
edit: see you figured it out on your own.. |
|
| Back to top |
|
|
| ThemePark
| | Joined: 22 Mar 2009 | | Posts: 17 | | : | |
Items |
|
| Posted: Sun Dec 13, 2009 2:06 am Post subject: |
|
|
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; |
To assign G to Gp, Gp has to be an array. But then it's not possible to access Gp.CellsLeft in Java, unless I specify an index.
| 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; } |
| 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?
| 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?
| 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.
| 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.
Finally, there's the register keyword which seems to be for optimizing, but is there a similar thing in Java? |
|
| Back to top |
|
|
| Adak
| | Joined: 27 Feb 2008 | | Posts: 87 | | : | |
Items |
|
| Posted: Sun Dec 13, 2009 8:08 am Post subject: |
|
|
Gp is a pointer to G - as the name implies.
| Quote: |
To assign G to Gp, Gp has to be an array. But then it's not possible to access Gp.CellsLeft in Java, unless I specify an index.
|
No, Gp has been assigned to G, and now holds the address of G. it is not an array. You can access G's struct members, with it.
*ucp is a pointer to an unsigned char, but it is also const - so it's memory address can't be changed.
Many times coders in C/C++ will put a p either as the first or last letter of a variable to remind themselves (and others), that the variable is indeed a pointer.
Yes, false equals 0, and true equals everything else. You don't need to have boolean data types. Early C compilers didn't even have a boolean data type. Just use 0 and 1/any number except 0, and you're good to go. |
|
| Back to top |
|
|
| JasonLion
| | Joined: 16 Nov 2008 | | Posts: 61 | | : | | Location: Silver Spring, MD |
Items |
|
| Posted: Sun Dec 13, 2009 1:29 pm Post subject: |
|
|
| One good way to think about Gp is as an index into the G array. Saying Gp is kind of like a short hand for saying G[<index>]. Assigning G to Gp is like setting the index to zero. |
|
| Back to top |
|
|
|
|
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
|
Powered by phpBB © 2001, 2005 phpBB Group
Igloo Theme Version 1.0 :: Created By: Andrew Charron |
FAQ
Search
Memberlist
Usergroups
Register
Profile
Log in
Log in to check your private messages
