Sudoku Programmers Forum Index

 
 FAQFAQ   SearchSearch   MemberlistMemberlist   UsergroupsUsergroups   RegisterRegister   ProfileProfile   Log inLog in          Games  Calendar

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

Links to Dancing Links (DLX)

 
Post new topic   Reply to topic    Sudoku Programmers Forum Index -> Programming sudoku
View previous topic :: View next topic  
Author Message
Ruud
Site Admin
Joined: 17 Sep 2005
Posts: 708
:
Location: Netherlands

Items
PostPosted: Tue Dec 12, 2006 4:38 pm    Post subject: Links to Dancing Links (DLX) Reply with quote

People new to this forum often ask questions about Dancing Links (DLX). These pointers will help you find the material you are looking for.

Wikipedia articles

Linked Lists
Dancing Links
Algorithm X
Exact Cover

Sudopedia article

Dancing Links

Cool but not easy to digest

Knuth's papers

Source code for DLX implementations

Sudoku programs by Dukuso
D. Knuth source code (can be converted to C)
Dancing Links solver in Python
Dancing Links implementation in Java
Dancing Links generator and solver in C by Antony
Dancing Links implementation in C++
Dancing Links implementation in PHP 5 by Ruud
Solver with dlx implementation in C# by humble programmer

Interesting threads in this forum about DLX

The fastest method of creating unique puzzles
Dancing Links
Dancing Links pivoting heuristics
Dancing Links - Can it go even faster
729x324 exact cover 3D and S-DLX proposal

(thanks to JC for suggesting this post and doing the initial research)

Ruud
Back to top
View user's profile Send private message Visit poster's website
Ruud
Site Admin
Joined: 17 Sep 2005
Posts: 708
:
Location: Netherlands

Items
PostPosted: Sun Apr 15, 2007 8:50 pm    Post subject: Reply with quote

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. Smile

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
View user's profile Send private message Visit poster's website
garthd

Joined: 29 Apr 2006
Posts: 32
:

Items
PostPosted: Wed Jun 11, 2008 3:14 am    Post subject: DLX in visual basic / .net Reply with quote

A vb / .net version of DLX is available...seems to be based on Stan Chesnutt's java implementation - see
http://www.codeproject.com/KB/vb/Dancing_Links_Library.aspx
Back to top
View user's profile Send private message
ignacio_ar

Joined: 05 May 2008
Posts: 11
:

Items
PostPosted: Fri Jun 13, 2008 5:49 pm    Post subject: Reply with quote

I wrote a fast sudoku solver, just Knuth DLX with some tweaking.
Seems its now the fastest sudoku solver.

Source in C, free for use in free or comercial apps (BSD license)
Check here:

http://www.setbb.com/sudoku/viewtopic.php?t=1586&mforum=sudoku

Ignacio.
Back to top
View user's profile Send private message
Pete

Joined: 09 Jun 2008
Posts: 18
:
Location: Somerset, NJ

Items
PostPosted: Fri Aug 08, 2008 6:29 pm    Post subject: Dancing Links Sudoku is Java and open source Reply with quote

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
View user's profile Send private message AIM Address
zerothbase

Joined: 02 Nov 2008
Posts: 17
:

Items
PostPosted: Sat Nov 29, 2008 3:04 am    Post subject: Reply with quote

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
View user's profile Send private message
rukiruki

Joined: 01 Dec 2008
Posts: 1
:

Items
PostPosted: Mon Dec 01, 2008 1:33 am    Post subject: Reply with quote

*edit* I had a problem but i worked it out now, sorry for this post (delete if you want)
Back to top
View user's profile Send private message
Display posts from previous:   
Post new topic   Reply to topic    Sudoku Programmers Forum Index -> Programming sudoku All times are GMT
Page 1 of 1

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


Powered by phpBB © 2001, 2005 phpBB Group

Igloo Theme Version 1.0 :: Created By: Andrew Charron