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   

DLX Implementation Considerations

 
Post new topic   Reply to topic    Sudoku Programmers Forum Index -> Solving sudoku
View previous topic :: View next topic  
Author Message
veroslav

Joined: 05 Jun 2006
Posts: 7
:

Items
PostPosted: Mon Jun 05, 2006 1:17 pm    Post subject: DLX Implementation Considerations Reply with quote
Hi all,

I am trying to implement DLX algorithm and I am stuck at the point when matrix rows are removed (to remove allowed moves for givens). Now, say that I have a 2 at r3c1, then these are the rows I think should be removed:

- <3>
- <2>
- <2>, where * = {1,9}

But I am speculating about whether some columns should also be removed, like columns <d> = <2>, <d> = <2> and <d> = <2>?
In my opinion, these columns will be empty when the algorithm is ran, and therefore I canīt see it finding a solution if these columns are included.

Also, when removing rows or columns, what is the best way to do it: delete them and then insert them again for each new problem, or just "unlink" them (explanation for this will be great)?

Am I thinking in the right direction? Any tips will be helpful, as this is first time I am implementing a Sudoku solver.

Best Regards,

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

Items
PostPosted: Mon Jun 05, 2006 9:40 pm    Post subject: Reply with quote
I will try to explain how DLX works in a sudoku implementation.

Terminology

You should realize that DLX is not designed for sudoku. It is a generic algorithm to solve Exact Cover problems. In fact, many terms are used for different things in DLX and sudoku.

Column

A simple constraint in sudoku. There are 81 columns for each cell, 81 for 9 digits in 9 sudoku-rows, 81 for 9 digits in 9 sudoku-columns and 81 for 9 digits in 9 sudoku boxes. This creates a total of 324 columns.

Row

A candidate in sudoku. There are 9 candidates in 81 cells, creating 729 rows.

Node

An connection between a row to a column. Each row has 4 nodes, one for each of the 4 constraints that it links to.

Example

Take candidate R2C7D6.

It is represented by Row[(2-1)*81+(7-1)*9+(6-1)]
It has a Node for the column representing the cell: [(2-1)*9+(7-1)]
It has a Node for the column representing digit 6 in sudoku-row 2: [81+(2-1)*9+(6-1)]
It has a Node for the column representing digit 6 in sudoku-column 7: [162+(7-1)*9+(6-1)]
It has a Node for the column representing digit 6 in sudoku-box 3: [243+(3-1)*9+(6-1)]

When setting up a DLX grid, make sure you can address the nodes from the rows. I usually define a FirstNode property in the Row object.

729 Rows with 4 Nodes each creates 2916 Nodes in total.
324 Columns each have 9 Nodes attached.

Classes

If you are not familiar with object oriented programming, the following part may be difficult to understand.

Code:
class Node
{
  Node Up;
  Node Down;
  Node Left;
  Node Right;
  Header Head;
}
class Header : Node
{
  int Size;
}


Initially, a Header has no detail nodes connected to it. You should initialize a Header like this:

Code:
this.Up = this.Down = this.Head = this;
this.Size = 0;


When detail nodes are initialized, link them to their header like this:

Code:
this.Down = this.Head.Down;
this.Up = this.Head;
this.Head.Down.Up = this;
this.Head.Down = this;
this.Head.Size++;


Link-Unlink

Each column has a header node. In an object-oriented language, the Header class is inherited from the Node class. You can also implement properties like IsHeader in the Node class.

Nodes are connected to the column header using a double linked list. Each node has Up and Down properties to the adjacent nodes. The column header node is part of both lists.

All nodes belonging to the same Row are connected with Left and Right properties. Most implementations do not use Row headers. The last Node of the row links back to the first. These left-right lists are static. They will not change after the initial setup.

To unlink a node, simply connect the 2 adjacent nodes to each other with the following operation:

Code:
this.Up.Down = this.Down;
this.Down.Up = this.Up;
this.Head.Size--;


This removes a node from the list. Notice that the Header.Size property is also decremented.

The powerful thing about DLX is that this operation can easily be reversed. The node still 'knows' where it was located in the list. The following operation restores the original links:

Code:
this.Up.Down = this;
this.Down.Up = this;
this.Head.Size++;


This is only true when we can be assured that the list is in the same state it was after the node was unlinked. The recursive DLX algorithm takes care of this.

Column Headers

Header nodes use the Left and Right properties in a slightly different way. All headers are linked to each other in a doubly linked list using the Left and Right properties.

A Root will be used as the starting point for these Header lists. Initialize the Root like this:

Code:
this.Left = this.Right = this;


Additional Headers are connected to the Root like this:

Code:
this.Left = Root;
this.Right = Root.Right;
Root.Right.Left = this;
Root.Right = this;


In DLX, you will need to remove selected headers from this list. To do this, use the following operation:

Code:
this.Right.Left = this.Left;
this.Left.Right = this.Right;


Now doesn't that look familiar? We can undo this operation like this:

Code:
this.Right.Left = this;
this.Left.Right = this;


Now we have everything that we need to implement DLX.

Description of the DLX Algorithm as required for Sudoku

Initialize the grid. Use the definitions as specified. Create the Root header. Create all column headers. Save them in an array for easy access. Create all Rows, and save them in an array too. I prefer a multi dimensional array for the rows. Create the Nodes for each Row. Place the first node in the rows array, and make sure they are properly connected, sideways and to the 4 column headers.

Process the clues. You can do this with existing methods. When a cell has a clue value of 1, it cannot be candidates 2 through 9. Use the unlink operation to unlink all candidates, except the clue value. You do not need to unlink all 4 nodes. Only unlink the first node (the one that you can access from the rows array). Do not forget to decrement the associated Header.Size.

Start the recursive process.

Take great care in coding this part. Everything you do must be undone in the reversed order. Sometimes switching 2 lines of code can cause error that are very difficult to detect.

Check recursion stop condition

Recursion ends when the Root has no headers attached. At this point, the algorithm has found a solution. You can save this solution at this point in the code.

Code:
if (Root.Right == Root)
{
  // save solution
  // increment solution counter
  return;
}


Find the best Column Header.

There are various ways to implement this search method. Here is the shortest version:

Code:
Header best = Root.Right;
for (Header hd = Root.Right;hd != Root;hd = hd.Right)
  if (hd.Size < best.Size) best = hd;


It this point in the process, you have found the best column header to start with. Now there are 3 options, which are all covered by the same algorithm:

1. Size = 0. You have found a dead end. The algorithm will recurse no further and start backtracking.
2. Size = 1. This will happen at least once for each clue that you have processed. When Size= 1, the process has found a single. If you want to see that the sudoku can be solved with singles only, make sure you do not allow the size of selected columns to be greater than 1.
3. Size > 1. The algorithm tries all the alternatives one by one.

How can these 3 situation be handled by a single method?

Unlink the selected Header from the header list.
Unlink the peer nodes of the nodes linked the selected Header.

Together, we call this a Cover operation. I usually implement this as a method for the Header class, and it goes like this:

Code:
this.Right.Left = this.Left;
this.Left.Right = this.Right;
for (Node child = this.Down;child != this; child = child.Down)
  for (Node peer = child.Right; peer != child; peer = peer.Right)
  {
    peer.Up.Down = peer.Down;
    peer.Down.Up = peer.Up;
    peer.Head.Size--;
  }


There is also an Uncover operation to reverse it:

Code:
for (Node child = this.Up;child != this; child = child.Up)
  for (Node peer = child.Left; peer != child; peer = peer.Left)
  {
    peer.Up.Down = peer;
    peer.Down.Up = peer;
    peer.Head.Size++;
  }
this.Right.Left = this;
this.Left.Right = this;

Please notice that even the directions Right/Left and Up/Down are reversed.

After covering a header, the code will try each of the rows linked to the selected column. In case of a size zero column, nothing happens. For other sizes, each of the rows will be selected/deselected in turn.

This is the code to navigate the rows below the column:

Code:
for (Node nd = best.Down;nd != best;nd = nd.Down)
{
  nd.Select();
  // save info
  // recurse
  nd.Unselect();
}


This is the Select method for the Node class:

Code:
for (Node peer = this.Left;peer != this; peer = peer.Left) peer.Head.Cover();


This is the Unselect method for the Node class, that reverses the Select method.

Code:
for (Node peer = this.Right;peer != this; peer = peer.Right) peer.Head.Uncover();


The final steps in the algorithm are related to the administration.

You need to save the selected rows. The generic DLX algorithm advises to use a stack, but a simple size 81 array will do fine for sudoku. Make sure you give each Node a CellIndex and a Digit property, and prepare a int[] Selected array.

You need a way to stop the algorithm when multiple solutions are found.

The modified main routine is changed to:

Code:
for (Node nd = best.Down;nd != best;nd = nd.Down)
{
  nd.Select();
  this.Selected[nd.CellIndex] = nd.Digit;
  // recurse
  nd.Unselect();
  if (this.SolutionCount > 1) break;
}


I hope this gives you a good starting point to implement DLX.

Ruud.

PS This is a long post and there are likely to be errors in the text.
_________________
Meet me at sudocue.net
Back to top
View user's profile Send private message Visit poster's website
veroslav

Joined: 05 Jun 2006
Posts: 7
:

Items
PostPosted: Tue Jun 06, 2006 12:56 pm    Post subject: Reply with quote
Hi Ruud,

thank you so much for you detailed description, it certainly helped me a lot! I implemented the algorithm yesterday, as I was eager to do it and wanted do try it on my own. Now, it is working (finds a unique solution if there is one), but because I asumed that I should also remove empty columns, it can't handle the cases where there is no solution. I will take a look in to it now, but I think I am on a good way, thanx to you reply.

Once again, thank you very much for your fast reply

Regards,
veroslav
Back to top
View user's profile Send private message
veroslav

Joined: 05 Jun 2006
Posts: 7
:

Items
PostPosted: Tue Jun 06, 2006 5:10 pm    Post subject: Reply with quote
I have got my program working and now it finds all solutions, one solution or reports if there is no solution. Now, my only problem left is, how should I do if I want to solve next puzzle using the same matrix as in first problem? I am keeping track of "removed" rows during deletion of possible moves according to givens in a puzzle. When I am done with the first puzzle, I restore those rows, but when I run my program on a new puzzle, nothing happens, and eventually it runs out of memory.

Any other things that should be restored? Perhaps some of the columns? How to know which?

I am thankful for a quick answer.

Regards
veroslav
Back to top
View user's profile Send private message
Display posts from previous:   
Post new topic   Reply to topic    Sudoku Programmers Forum Index -> Solving 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