|
| View previous topic :: View next topic |
| Author |
Message |
| Ruud
Site Admin
 | | Joined: 17 Sep 2005 | | Posts: 708 | | : | | Location: Netherlands |
Items |
|
|
| Back to top |
|
 |
| Ruud
Site Admin
| | Joined: 17 Sep 2005 | | Posts: 708 | | : | | Location: Netherlands |
Items |
|
 Posted: Sun Apr 15, 2007 8:50 pm Post subject: |
 |
|
Here is a new DLX solver in C++
It accepts the name of an input file and solves all puzzles in this file.
Change the precompiler directives BOX_WIDTH and BOX_HEIGHT if you want to adapt it for different puzzle formats.
You can also use the objects in a generator.
On my P4 2.4MHz it solves:
sudoku17 collection by GF Royle: 4730 puzzles / second.
top50000: 3770 puzzles / second.
top1465: 967 puzzles / second.
Thanks to Havard for the original version. 
| Code: | #include <iostream>
#include <time.h>
#define MAX_SUDOKU_IN_FILE 50000
#define SOLUTION_LIMIT 100000
#define BOX_WIDTH 3
#define BOX_HEIGHT 3
#define UNIT_SIZE (BOX_WIDTH * BOX_HEIGHT)
#define GRID_SIZE (UNIT_SIZE * UNIT_SIZE)
//#define COLNAMES
char sudokus[MAX_SUDOKU_IN_FILE][GRID_SIZE];
///////////////////////
// Forward declarations
///////////////////////
class CHead;
class CCandidate;
class CCell;
////////////////////
// Class definitions
////////////////////
// Node class definition
// Besides the constructors, there are no methods. Node data is only manipulated by other objects.
class CNode
{
protected:
CNode(bool head);
public:
~CNode();
CNode(CHead *head, CCandidate *candidate);
CNode *up;
CNode *down;
bool IsHead;
// The properties below are only used in detail nodes. They will not be set for header nodes.
CNode *Peer1;
CNode *Peer2;
CNode *Peer3;
CHead *Head;
CCandidate *Candidate;
};
// Header class definition
class CHead : public CNode
{
public:
CHead();
#ifdef COLNAMES
CHead(CHead *root, const char *fmt, int d1, int d2);
char Name[40];
#else
CHead(CHead *root);
#endif
~CHead();
CHead *left;
CHead *right;
bool IsRoot;
void Cover();
void Uncover();
int size;
};
// Candidate class definition
// This class links 4 nodes to a cell.
class CCandidate
{
public:
CCandidate(CCell *cell, int digit);
~CCandidate();
CCell *Cell;
int Digit;
CNode *CelNode;
CNode *RowNode;
CNode *ColNode;
CNode *BoxNode;
void Disable();
void Enable();
bool Disabled;
};
// Cell class definition
// Keeps track of the cell solving status and provides access to the candidates.
class CCell
{
public:
CCell(int index);
~CCell();
int Index;
int RowOffset;
int ColOffset;
int BoxOffset;
int Given; // Nonzero for a cell with a given digit
int Selected; // Currently selected digit in the DLX algorithm
int Solution; // Digit recorded in the (first) solution
CCandidate **Candidates;
void SetGiven(char digit);
void ClearGiven();
};
// Solver class
class CSolver
{
private:
CHead *Root;
CHead *celHdr[GRID_SIZE];
CHead *rowHdr[GRID_SIZE];
CHead *colHdr[GRID_SIZE];
CHead *boxHdr[GRID_SIZE];
int solution_count;
int SolutionLimit;
bool Abort;
void Recurse();
public:
CSolver();
~CSolver();
int Solve(bool all);
CCell *Cells[GRID_SIZE];
};
////////////////////////
// Class implementations
////////////////////////
// Protected CNode constructor for CHead
CNode::CNode(bool head)
{
IsHead = head;
}
CNode::~CNode()
{
}
// Public constructor for detail nodes
// Each node links a candidate to a column header
CNode::CNode(CHead *head, CCandidate *cand)
{
IsHead = false;
Head = head;
up = Head->up;
down = Head;
up->down = this;
down->up = this;
Head->size++;
Candidate = cand;
}
// Constructor for the root header
// Only one root header is created by the solver
CHead::CHead() : CNode(true)
{
#ifdef COLNAMES
Name[0] = '\0';
strcat_s(Name,"Root");
#endif
IsRoot = true;
IsHead = true;
size = 99;
up = down = left = right = this;
}
CHead::~CHead()
{
}
// Constructor for a column header
// Each constraint (cell, row+digit, column+digit, box+digit) has a column header
#ifdef COLNAMES
CHead::CHead(CHead *root, const char *fmt, int d1, int d2) : CNode(true)
#else
CHead::CHead(CHead *root) : CNode(true)
#endif
{
#ifdef COLNAMES
sprintf_s(Name,fmt,d1,d2);
#endif
IsRoot = false;
IsHead = true;
size = 0;
left = root->left;
right = root;
up = down = left->right = right->left = this;
}
// Cover method.
// Removes the header from the linked list that connects it to the root node.
// Removes the peers of all detail nodes below this header.
void CHead::Cover()
{
left->right = right;
right->left = left;
for (CNode *b = down; !b->IsHead ; b = b->down)
{
b->Peer1->down->up = b->Peer1->up;
b->Peer1->up->down = b->Peer1->down;
b->Peer1->Head->size--;
b->Peer2->down->up = b->Peer2->up;
b->Peer2->up->down = b->Peer2->down;
b->Peer2->Head->size--;
b->Peer3->down->up = b->Peer3->up;
b->Peer3->up->down = b->Peer3->down;
b->Peer3->Head->size--;
}
}
// Uncover method.
// Restores the peers of all detail nodes below this header.
// Reinserts the header in the linked list that connects it to the root node.
void CHead::Uncover()
{
for (CNode *b = up; !b->IsHead; b = b->up)
{
b->Peer3->down->up = b->Peer3->up->down = b->Peer3;
b->Peer3->Head->size++;
b->Peer2->down->up = b->Peer2->up->down = b->Peer2;
b->Peer2->Head->size++;
b->Peer1->down->up = b->Peer1->up->down = b->Peer1;
b->Peer1->Head->size++;
}
left->right = right->left = this;
}
// Candidate Constructor. Cell and digit are given.
CCandidate::CCandidate(CCell *cell, int dx)
{
this->Cell = cell;
Digit = dx+1;
Disabled = false;
}
CCandidate::~CCandidate()
{
delete CelNode;
delete RowNode;
delete ColNode;
delete BoxNode;
}
// Disable candidate
// This happens when the associated cell is set to another digit.
// All detail nodes are disconnected from their respective column chains.
void CCandidate::Disable()
{
if (!Disabled)
{
Disabled = true;
CelNode->up->down = CelNode->down;
CelNode->down->up = CelNode->up;
CelNode->up = CelNode->down = CelNode;
CelNode->Head->size--;
RowNode->up->down = RowNode->down;
RowNode->down->up = RowNode->up;
RowNode->up = RowNode->down = RowNode;
RowNode->Head->size--;
ColNode->up->down = ColNode->down;
ColNode->down->up = ColNode->up;
ColNode->up = ColNode->down = ColNode;
ColNode->Head->size--;
BoxNode->up->down = BoxNode->down;
BoxNode->down->up = BoxNode->up;
BoxNode->up = BoxNode->down = BoxNode;
BoxNode->Head->size--;
}
}
// Enable candidate
// This happens when the associated cell is cleared after the solver is finished.
// All detail nodes are reconnected to their respective column chains.
void CCandidate::Enable()
{
if (Disabled)
{
BoxNode->up = BoxNode->Head->up;
BoxNode->down = BoxNode->Head;
BoxNode->up->down = BoxNode->down->up = BoxNode;
BoxNode->Head->size++;
ColNode->up = ColNode->Head->up;
ColNode->down = ColNode->Head;
ColNode->up->down = ColNode->down->up = ColNode;
ColNode->Head->size++;
RowNode->up = RowNode->Head->up;
RowNode->down = RowNode->Head;
RowNode->up->down = RowNode->down->up = RowNode;
RowNode->Head->size++;
CelNode->up = CelNode->Head->up;
CelNode->down = CelNode->Head;
CelNode->up->down = CelNode->down->up = CelNode;
CelNode->Head->size++;
Disabled = false;
}
}
// Cell constructor
CCell::CCell(int index)
{
Index = index;
int rx = index / UNIT_SIZE;
int cx = index % UNIT_SIZE;
RowOffset = rx * UNIT_SIZE;
ColOffset = cx * UNIT_SIZE;
BoxOffset = (BOX_HEIGHT * (rx / BOX_HEIGHT) + cx / BOX_WIDTH) * UNIT_SIZE;
Given = 0;
Selected = 0;
Solution = 0;
Candidates = new CCandidate*[UNIT_SIZE];
}
CCell::~CCell()
{
delete[] Candidates;
}
// Set the given digit for a cell. All other candidates are disabled as a result.
void CCell::SetGiven(char digit)
{
Given = digit;
for (int dx = 0; dx < UNIT_SIZE; dx++)
{
if (dx != (Given-1)) Candidates[dx]->Disable();
}
}
// Clear the given digit. All other candidates are enabled.
void CCell::ClearGiven()
{
for (int dx = UNIT_SIZE-1; dx >= 0; dx--)
{
if (dx != (Given-1)) Candidates[dx]->Enable();
}
Given = 0;
}
// Solver constructor.
// Initializes the root header, the cells, all column headers, the candidates and their detail nodes
CSolver::CSolver()
{
Root = new CHead();
// Initialize the column headers.
for(int n = 0; n < GRID_SIZE; ++n)
{
Cells[n] = new CCell(n);
#ifdef COLNAMES
int un = (n/UNIT_SIZE)+1;
int dg = (n%UNIT_SIZE)+1;
celHdr[n] = new CHead(Root,"CCell r%dc%d",un,dg);
rowHdr[n] = new CHead(Root,"Row %d digit %d",un,dg);
colHdr[n] = new CHead(Root,"Col %d digit %d",un,dg);
boxHdr[n] = new CHead(Root,"Box %d digit %d",un,dg);
#else
celHdr[n] = new CHead(Root);
rowHdr[n] = new CHead(Root);
colHdr[n] = new CHead(Root);
boxHdr[n] = new CHead(Root);
#endif
}
for (int cx = 0; cx < GRID_SIZE; cx++)
{
for (int dx = 0; dx < UNIT_SIZE; dx++)
{
Cells[cx]->Candidates[dx] = new CCandidate(Cells[cx],dx);
Cells[cx]->Candidates[dx]->CelNode = new CNode(celHdr[cx],Cells[cx]->Candidates[dx]);
Cells[cx]->Candidates[dx]->RowNode = new CNode(rowHdr[Cells[cx]->RowOffset+dx],Cells[cx]->Candidates[dx]);
Cells[cx]->Candidates[dx]->ColNode = new CNode(colHdr[Cells[cx]->ColOffset+dx],Cells[cx]->Candidates[dx]);
Cells[cx]->Candidates[dx]->BoxNode = new CNode(boxHdr[Cells[cx]->BoxOffset+dx],Cells[cx]->Candidates[dx]);
Cells[cx]->Candidates[dx]->CelNode->Peer1 = Cells[cx]->Candidates[dx]->RowNode;
Cells[cx]->Candidates[dx]->CelNode->Peer2 = Cells[cx]->Candidates[dx]->ColNode;
Cells[cx]->Candidates[dx]->CelNode->Peer3 = Cells[cx]->Candidates[dx]->BoxNode;
Cells[cx]->Candidates[dx]->RowNode->Peer1 = Cells[cx]->Candidates[dx]->CelNode;
Cells[cx]->Candidates[dx]->RowNode->Peer2 = Cells[cx]->Candidates[dx]->ColNode;
Cells[cx]->Candidates[dx]->RowNode->Peer3 = Cells[cx]->Candidates[dx]->BoxNode;
Cells[cx]->Candidates[dx]->ColNode->Peer1 = Cells[cx]->Candidates[dx]->CelNode;
Cells[cx]->Candidates[dx]->ColNode->Peer2 = Cells[cx]->Candidates[dx]->RowNode;
Cells[cx]->Candidates[dx]->ColNode->Peer3 = Cells[cx]->Candidates[dx]->BoxNode;
Cells[cx]->Candidates[dx]->BoxNode->Peer1 = Cells[cx]->Candidates[dx]->CelNode;
Cells[cx]->Candidates[dx]->BoxNode->Peer2 = Cells[cx]->Candidates[dx]->RowNode;
Cells[cx]->Candidates[dx]->BoxNode->Peer3 = Cells[cx]->Candidates[dx]->ColNode;
}
}
}
CSolver::~CSolver()
{
}
// Solve method.
// For an exhaustive search, use all=true, otherwise the solver aborts after 2 solutions found.
// Even with an exhaustive search, the predefined solution limit prevents the solver from hanging.
int CSolver::Solve(bool all)
{
if (all) SolutionLimit = SOLUTION_LIMIT; else SolutionLimit = 2;
Abort = false;
solution_count = 0;
Recurse();
return solution_count;
}
// Internal recursive DLX method.
void CSolver::Recurse()
{
// Increment solution count when all Heads are covered.
if (Root->right->IsRoot)
{
solution_count++;
if (solution_count>1)
Abort = (solution_count >= SolutionLimit);
else
for (int cx = 0; cx < GRID_SIZE; cx++) Cells[cx]->Solution = Cells[cx]->Selected;
return;
}
// Find the smallest size with CHeads attached
CHead *col = Root->right;
if (col->size > 1)
{
for (CHead *c = col->right; !c->IsRoot; c = c->right)
{
if (c->size < col->size)
{
col = c;
if (col->size <= 1) break;
}
}
}
// Skip processing rows for a size 0 column.
if (col->size == 0) return;
// Cover the selected column once, so it does not need to be covered for each row.
col->Cover();
// Process each row below this column.
for (CNode *rn = col->down; !rn->IsHead; rn = rn->down)
{
// Cover the columns for the 3 peer nodes.
rn->Candidate->Cell->Selected = rn->Candidate->Digit;
rn->Peer1->Head->Cover();
rn->Peer2->Head->Cover();
rn->Peer3->Head->Cover();
// Next recursion level.
Recurse();
// Uncover the columns for the 3 peer nodes.
rn->Peer3->Head->Uncover();
rn->Peer2->Head->Uncover();
rn->Peer1->Head->Uncover();
// Abort further processing when multiple solutions were found.
if (Abort) break;
} // Next row node
// Uncover the selected column header.
col->Uncover();
}
// Read sudokus from a text file into the internal arrays.
int ReadSudokus(const char *filename)
{
FILE *input;
// Open file explicitly in binary mode, otherwise the CRLF characters are converted to LF
// and the file length is returned incorrectly.
if (fopen_s(&input, filename, "rb") != 0) return 0;
fseek(input, 0L, SEEK_END); // Position to end of file
long lFileLen = ftell(input); // Get file length
rewind(input); // Back to start of file
char *cFile = (char *) calloc(lFileLen + 1, sizeof(char));
if(cFile == NULL) return 0; // Not enough memory
fread(cFile, lFileLen, 1, input); // Read the file into a character buffer
fclose(input);
int puzzleIndex = 0;
int cellIndex = 0;
bool comment = false;
char *cRead = cFile;
while (*cRead)
{
switch (*cRead)
{
case 10: // LF character
case 13: // CR character
if (cellIndex == GRID_SIZE) puzzleIndex++;
cellIndex = 0;
comment = false;
break;
case 26: // DOS EOF character. Not used often, but renders remainder of file invalid.
if (cellIndex == GRID_SIZE) puzzleIndex++;
return puzzleIndex;
case '#': // Comment character. Ignore remainder of this line.
comment = true;
break;
default:
if (!comment && (cellIndex < GRID_SIZE))
{
if ((*cRead > 48) && (*cRead < 58)) // Digits 1-9
sudokus[puzzleIndex][cellIndex++] = *cRead - 48;
else if (*cRead == '0' || *cRead == '.')
sudokus[puzzleIndex][cellIndex++] = 0;
}
}
cRead++;
}
return puzzleIndex;
}
int main(int argc, char *argv[])
{
char *filename = "testfile.sdm";
if (argc>=2) filename = argv[1];
int rounds = ReadSudokus(filename);
CSolver solver;
clock_t start, finish;
start = clock();
for(int j = 0; j < rounds; j++) {
for (int i = 0; i < GRID_SIZE; i++) if (sudokus[j][i]) solver.Cells[i]->SetGiven(sudokus[j][i]);
// Change this call to Solve(true) if you really want to know the number of solutions.
// Solve(false) returns 2 for all problems with multiple solutions, but it is a lot faster.
int DLX_sol = solver.Solve(false);
for (int i = GRID_SIZE-1; i >= 0; i--) if (sudokus[j][i]) solver.Cells[i]->ClearGiven();
}
finish = clock();
printf("time: %2.3f sec\n",(double)(finish - start)/CLOCKS_PER_SEC);
printf("%d problems processed!\n", rounds);
return(0);
}
|
|
|
| Back to top |
|
|
| garthd
| | Joined: 29 Apr 2006 | | Posts: 32 | | : | |
Items |
|
|
| Back to top |
|
|
| ignacio_ar
| | Joined: 05 May 2008 | | Posts: 11 | | : | |
Items |
|
|
| Back to top |
|
|
| Pete
 | | Joined: 09 Jun 2008 | | Posts: 18 | | : | | Location: Somerset, NJ |
Items |
|
| Posted: Fri Aug 08, 2008 6:29 pm Post subject: Dancing Links Sudoku is Java and open source |
|
|
I've just released my implementation of Knuth's Algorithm X (Dancing Links) under the name Dancing Links Sudoku.
It's a sudoku generator and solver. It also uses the same code to solve pentomino puzzles. (Only the node generation is specific to each kind of puzzle).
I'm calling it a beta release. It's in Java, so it's platform independent. It's been tested under Windows XP, Vista, and Linux. You can run the sudoku generator and solver on the Web at http://www.jfasttrack.com/demos/sudoku/
You can also download it and run sudoku and pentominoes as applications. To do this, you will also need the Java Runtime Environment (available at http://java.sun.com/javase/downloads/index.jsp).
It can be downloaded from SourceForge: http://sourceforge.net/projects/dancinglinks/ It's all available under the GPL.
This is a first (beta) release, so I have just the basic features:
. Basic GUI
. Dancing Links sudoku generator
. Dancing Links solvers for sudoku and pentominoes
. Sudoku solvers:
. . Naked single
. . Hidden single
. . Intersections
. . Naked pairs
. Hints for each solver
. Undo and redo |
|
| Back to top |
|
|
| zerothbase
| | Joined: 02 Nov 2008 | | Posts: 17 | | : | |
Items |
|
| Posted: Sat Nov 29, 2008 3:04 am Post subject: |
|
|
I thought I'd contribute to this post:
From a learning perspective, a lot of the DLX solvers I see posted are either too generic (solve other problems besides sudoku) or are too optimized to really read well, imho.
I set out to write one as a direct copy from Knuth's paper (as much as I could), and be as readable as possible. I didn't comment it as well as I should, but Knuth gives a fairly good explanation of each function in his paper.
In C++ - zerodlx.cpp
And Java - Zerodlx.java
The only optimizations are a cut-off after a max number of solutions has been reached, and Knuth's minimum size column search. It is certainly not the fastest DLX code out there, but it does well enough just due to the elegance of Knuth's algorithm. It will solve any regular sized sudoku (2x2,3x3,4x4,5x5...), and I've tested on as high as m_b_metcalf's 144x144 (aka 12x12).
The interface to both classes is simple: contruct the object and call solve() repeatedly for as many puzzles as you like. Solve() returns the number of solutions found and fills in the puzzle parameter with the solution.
I thought it might contribute to those programmers that don't want to dig through Knuth's paper, or ones that just want a quick, portable answer to DLX sudoku solving. Or for new programmers that are trying to learn DLX but don't know quite where to start.
Anyone is free to use this code for any purpose you like.
Please feel free to send me comments, if you think the code could be clarified in specific ways.
--Zerothbase |
|
| Back to top |
|
|
| rukiruki
| | Joined: 01 Dec 2008 | | Posts: 1 | | : | |
Items |
|
| Posted: Mon Dec 01, 2008 1:33 am Post subject: |
|
|
| *edit* I had a problem but i worked it out now, sorry for this post (delete if you want) |
|
| 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
