|
| View previous topic :: View next topic |
| Author |
Message |
| Aidy
| | Joined: 26 Jul 2005 | | Posts: 2 | | : | |
Items |
|
 Posted: Tue Jul 26, 2005 6:54 pm Post subject: OO approach to solving |
 |
|
(this is in c# but the principals apply to any OO language)
Most solvers I've seen so far use a multi-dimensional 9x9 array to store the grid. For the ones that don't use pure brute force this has resulted in some rules being written three times, one for rows, one for columns and one for blocks.
I took a slightly different object orientated approach to storing the grid. At the heart it still relies on a multidimensional arrays, however there is a "block" object which is a 3x3 array of "cell" objects. The "grid" object is then a 3x3 array of "block" objects.
By holding the data in such a way it has made some rule processing easier. For any rule that works on a set of nine numbers be it a row, column or block, I have it work on just a number set of 9 numbers. So to apply a rule to a row I get a number set from the row on the grid and apply the rule to that number set. If the rule is to work on a column then I create a number set from the column and apply the rule to that number set. Similarly if it is to apply to a block a get a number set from the block and apply the rule. As the rule is working on the number set and *not* a row/column/block the rule code is completely generic and the same code can be used on all three.
My Grid object calls three sub-routines to apply row/column/block specific rules;
| Code: |
ReCalculateBlocks();
ReCalculateRows();
ReCalculateColumns();
....
private void ReCalculateBlocks()
{
// Loop through each block in the 3x3 grid
for (int i = 0; i < 3; i++)
{
for (int j = 0; j < 3; j++)
{
// Create a new number set to hold the block values
NumberSet numberSet = new NumberSet();
// Add the relevant block's numbers to the number set
numberSet.AddBlock (this.blocks[i,j]);
// Tell the number set to recalculate.
// This will apply the number set specific rules to it
numberSet.ReCalculate();
}
}
}
private void ReCalculateRows()
{
// Loop for each row
for (int i = 0; i < 9; i++)
{
// Get that row as a number set
NumberSet numberSet = GetRow(i);
// Tell the number set to recalculate.
// This will apply the number set specific rules to it
numberSet.ReCalculate();
}
}
private void ReCalculateColumns()
{
// Loop for each column
for (int j = 0; j < 9; j++)
{
// Get that column as a number set
NumberSet numberSet = GetColumn(j);
// Tell the number set to recalculate.
// This will apply the number set specific rules to it
numberSet.ReCalculate();
}
}
|
This is the recalculate code. As you can see it is totally unaware if the number set it is working on is a row, column or block. This abstraction lets us write the rule only once for a set of generic 9 numbers.
| Code: |
public void ReCalculate()
{
// Pass this number set to the SolvedNumbers class
// If a number in the row is a solved number then it will be
// removed as a possibility from other cells in that number set
SolvedNumbers.CheckNumberSet (this);
// Pass this number set to the NumberPairs class
// If two cells contain the same number pair only then each
// number in the pair must be in one of those cells so remove
// those numbers from the possibilility list of other cells
// in the set
NumberPairs pairs = new NumberPairs(this);
// Pass this number set to the NumberPairs class
// If there are N numbers in N subgroups remove the possibility
// that any other number apart from ones in the group can be
// possible
UniqueSubset.CheckNumberSet(this);
}
|
To introduce a new rule we code it into a class that applies the rule to the number set then add it to the list of rules in the ReCalculate class.
Not all rules work only on a row/column/block so if it is applied to the whole grid it is invoked via the grid's ReCalculate method;
| Code: |
ReCalculateBlocks();
ReCalculateRows();
ReCalculateColumns();
XWing.CheckGrid(this);
|
So for each iteration we recalculate each row/column/block, then we apply the grid-specific rules in much the same way. Each rule has its own class and this time we pass the whole grid to the class. In my demo the only grid-wide algorithm I have implemented is the X-Wing algorithm, but if more are written they will just slot in below the Xwing one.
As I mentioned before, each block is an array of "cell" objects. Each cell is a list of possible numbers and it provides methods for adding possibilities, removing them and setting a final solution if it becomes known.
| Code: |
public class Cell
{
private ArrayList possible = new ArrayList(9);
public Cell()
{
for (int i = 1; i<10; i++)
possible.Add(i);
}
public ArrayList PossibleNumbers
{
get
{
return this.possible;
}
}
public string PossibleNumbersDisplay
{
get
{
string ret = "";
foreach (int number in this.possible)
ret = string.Concat(ret, " ", number.ToString());
return ret.Trim();
}
}
public void RemovePossible (int number)
{
possible.Remove(number);
}
public void AddPossible (int number)
{
if (!possible.Contains(number))
possible.Add(number);
}
public void MakeSolution (int number)
{
possible.Clear();
if (number > 0 && number < 10)
possible.Add (number);
}
public void RemovePossible (params int[] numbers)
{
foreach (int number in numbers)
possible.Remove(number);
}
|
As you can see from the constructor (Public Cell) upon creation it automatically sets itself has having 1-9 as possible solutions. As our algorithms find numbers that it is possible to eliminate it simply calls the RemovePossible method of the cell in question. |
|
| Back to top |
|
 |
| Michael Kennett
| | Joined: 21 Jul 2005 | | Posts: 11 | | : | | Location: Adelaide, South Australia |
Items |
|
| Posted: Fri Jul 29, 2005 7:34 am Post subject: |
|
|
Hi Aidy,
Another way of achieving what you want (generic functions for processing rows/columns/blocks) is to use function pointers in C. For example, here is a (edited) snippet of code I've written:
| Code: | #define INDEX(row,col) (9*(row)+(col))
static
int
idx_row( int el, int idx ) /* Index within a row */
{
return INDEX( el, idx );
}
static
int
idx_column( int el, int idx ) /* Index within a column */
{
return INDEX( idx, el );
}
static
int
idx_block( int el, int idx ) /* Index within a block */
{
return INDEX( 3 * ( el / 3 ) + idx / 3, 3 * ( el % 3 ) + idx % 3 );
}
/* Find all squares with a single digit allowed -- do not mutate board */
static
void
singles( int el, int (*idx_fn)( int, int ), int hintcode )
{
int i, j, idx;
count_set_digits( el, idx_fn );
for( i = 0 ; i < 9 ; ++i )
{
if( 1 == counts[ i ] )
{
/* Digit 'i+1' appears just once in the element */
for( j = 0 ; j < 9 ; ++j )
{
idx = (*idx_fn)( el, j );
if( !DISALLOWED( idx, i + 1 ) && idx_possible < 81 )
possible[ idx_possible++ ] = SET_INDEX( idx )
| SET_DIGIT( i + 1 )
| hintcode;
}
}
if( 8 == digits[ i ] )
{
/* 8 digits are masked at this position - just one remaining */
idx = (*idx_fn)( el, i );
for( j = 1 ; j <= 9 ; ++j )
if( 0 == ( STATE( idx ) & DIGIT_STATE( j ) ) && idx_possible < 81 )
possible[ idx_possible++ ] = SET_INDEX( idx )
| SET_DIGIT( j )
| hintcode;
}
}
}
/* Find, and return the number of, moves possible
*/
static
int
findmoves( void )
{
int i;
idx_possible = 0;
for( i = 0 ; i < 9 ; ++i )
{
singles( i, idx_row, HINT_ROW );
singles( i, idx_column, HINT_COLUMN );
singles( i, idx_block, HINT_BLOCK );
}
return idx_possible;
} |
Hopefully the above snippet illustrates the idea. The processing (for finding squares that can contain only one digit) is controlled by the index function.
Regards, Michael |
|
| Back to top |
|
|
| dxc31202
| | Joined: 06 Oct 2005 | | Posts: 1 | | : | | Location: London |
Items |
|
| Posted: Thu Oct 06, 2005 4:24 pm Post subject: Re: OO approach to solving |
|
|
Hi,
This looks like an excellent method, I was using a similar idea in an object approach for my next gen solver only I had a section, row and column class. I do think that this approach cuts down on a lot of issues though
I would be very interested to see how you solved the various checks with this 3x3 method for rows and columns, is there any chance of seeing the complete code ?
This is my first gen code, written in VB.Net about a year ago and very procedural. This can be made into a standalone DLL just pass in a an 8 by 8 grid and it returns a completed one (if it can) and seems to solve most puzzles I've given it and it's pretty quick too
| Code: | Imports System.Text
Namespace Soduko
Public Class Puzzle
Private Shared mWork(8, 8) As Integer ' This is our working puzzle
Private Shared Candidates(8, 8) As String ' potential entries for each cell
Public Property Grid() As Integer(,)
Get
Return mWork
End Get
Set(ByVal Value As Integer(,))
mWork = Value
End Set
End Property
Public Shared Function Solve(ByVal pGrid(,) As Integer) As Integer(,)
mWork = pGrid
Return Solve()
End Function
Public Shared Function Solve() As Integer(,)
Dim completed As Integer
Dim lastCompleted As Integer
Do
' Reset the completed flag
completed = 0
' calculate the potential values for each cell
For row As Integer = 0 To 8
For col As Integer = 0 To 8
If mWork(row, col) <> 0 Then
Candidates(row, col) = mWork(row, col).ToString
Else
Candidates(row, col) = GetCandidates(row, col)
End If
Next
Next
For row As Integer = 0 To 8
For col As Integer = 0 To 8
If mWork(row, col) = 0 Then
RemoveImpossibleCandidatesByRow(row, col)
End If
Next
Next
For row As Integer = 0 To 8
For col As Integer = 0 To 8
If mWork(row, col) = 0 Then
RemoveImpossibleCandidatesByCol(row, col)
End If
Next
Next
' Check to see if the puzzle is complete
For row As Integer = 0 To 8
For col As Integer = 0 To 8
If Len(Candidates(row, col)) = 1 Then
completed = completed + 1
If mWork(row, col) = 0 Then
mWork(row, col) = CInt(Candidates(row, col))
End If
End If
Next
Next
' Try and make each cell unique
For row As Integer = 0 To 8
For col As Integer = 0 To 8
FindUniqueValues(row, col)
Next
Next
' If the we didn't fill in any more cells then we can't complete this puzzle
If lastCompleted = completed Then
Throw New Exception("Can't solve this puzzle.")
End If
' Remember how many we completed last time
lastCompleted = completed
' If we completed 80 cells then the puzzle is complete
Loop Until completed > 80
' Return the solved puzzle
Return mWork
End Function
'
' calculate the potential values that can appear in each cell
' To do this create a scratch pad containing the numbers 1 through 9
' Then look in each direction and try to eliminate numbers
' finally return the scratch pad containing potential candidates
'
Private Shared Function GetCandidates(ByVal row As Integer, ByVal col As Integer) As String
Dim r As Integer = Segment(row)
Dim c As Integer = Segment(col)
Dim Candidates As String = ScratchArea(1, 9)
If mWork(row, col) = 0 Then
' First Check the miniblock (i.e. the 3x3 segment)
For i As Integer = 0 To 2
For j As Integer = 0 To 2
If mWork(r + i, c + j) <> 0 Then
Candidates = RemoveChar(Candidates, mWork(r + i, c + j).ToString)
End If
Next
Next
' Now look along each column for this row
For i As Integer = 0 To 8
If InStr(Candidates, mWork(row, i)) > 0 Then
If mWork(row, i) <> 0 Then
Candidates = RemoveChar(Candidates, mWork(row, i).ToString)
End If
End If
Next
' Finally look along each row for this column
For i As Integer = 0 To 8
If InStr(Candidates, mWork(i, col)) > 0 Then
If mWork(i, col) <> 0 Then
Candidates = RemoveChar(Candidates, mWork(i, col).ToString)
End If
End If
Next
Else
' We've hit lucky, so set the candidates to be the single value
Candidates = mWork(row, col).ToString
End If
Return Candidates
End Function
'
' Remove the given character (c) from a string
'
Private Shared Function RemoveChar(ByVal Text As String, ByVal c As String) As String
Dim ValueAt As Integer
ValueAt = InStr(Text, c)
If ValueAt = 0 Then
Return Text
Else
Return Text.Substring(0, ValueAt - 1) & Text.Substring(ValueAt, Text.Length - ValueAt)
End If
End Function
Private Shared Function FindUniqueValues(ByVal row As Integer, ByVal col As Integer) As Integer
CheckMiniblock(Segment(row), Segment(col))
CheckColumnsByRow(row)
CheckRowsByColumn(col)
End Function
Private Shared Sub CheckMiniblock(ByVal row As Integer, ByVal col As Integer)
Dim potential As String
Dim count As Integer
For n As Integer = 1 To 9
count = 0
For i As Integer = 0 To 2
For j As Integer = 0 To 2
If InStr(Candidates(row + i, col + j), n.ToString) > 0 _
And Candidates(row + i, col + j).Length > 1 _
Or mWork(row + i, col + j) = n Then
count = count + 1
End If
Next
Next
If count = 1 Then
For i As Integer = 0 To 2
For j As Integer = 0 To 2
If InStr(Candidates(row + i, col + j), n.ToString) > 0 _
And Candidates(row + i, col + j).Length > 1 _
Or mWork(row + i, col + j) = n Then
If mWork(row + i, col + j) = 0 Then
mWork(row + i, col + j) = n
Exit Sub
End If
End If
Next
Next
End If
Next
End Sub
Private Shared Sub CheckColumnsByRow(ByVal row As Integer)
Dim potential As String
Dim count As Integer
For n As Integer = 1 To 9
count = 0
For i As Integer = 0 To 8
If InStr(Candidates(row, i), n.ToString) > 0 _
And Candidates(row, i).Length > 1 _
Or mWork(row, i) = n Then
count = count + 1
End If
Next
If count = 1 Then
For i As Integer = 0 To 8
If InStr(Candidates(row, i), n.ToString) > 0 _
And Candidates(row, i).Length > 1 _
Or mWork(row, i) = n Then
If mWork(row, i) = 0 Then
mWork(row, i) = n
Exit Sub
End If
End If
Next
End If
Next
End Sub
Private Shared Sub CheckRowsByColumn(ByVal col As Integer)
Dim potential As String
Dim count As Integer
For n As Integer = 1 To 9
count = 0
For i As Integer = 0 To 8
If InStr(Candidates(i, col), n.ToString) > 0 _
And Candidates(i, col).Length > 1 _
Or mWork(i, col) = n Then
count = count + 1
End If
Next
If count = 1 Then
For i As Integer = 0 To 8
If InStr(Candidates(i, col), n.ToString) > 0 _
And Candidates(i, col).Length > 1 _
Or mWork(i, col) = n Then
If mWork(i, col) = 0 Then
mWork(i, col) = n
Exit Sub
End If
End If
Next
End If
Next
End Sub
' Remove impossible combinations by row
' This is where three candidate entries in a minblock row only produce three possible numbers
' in this case we can remove the numbers from the other candidates in the miniblock
Private Shared Function RemoveImpossibleCandidatesByRow(ByVal row As Integer, ByVal col As Integer) As String
Dim rowCandidates(9) As String
Dim tmp As String
Dim i As Integer
Dim j As Integer
Dim n As Integer
Dim cnt As Integer
Dim R As Integer
Dim c As Integer
Dim newCandidates As String
R = Segment(row)
c = Segment(col)
For i = 0 To 2
For j = 1 To Len(Candidates(R, c + i))
rowCandidates(CInt(Mid$(Candidates(R, c + i), j, 1))) = Mid$(Candidates(R, c + i), j, 1)
Next
Next
For i = 1 To 9
If rowCandidates(i) <> "" Then
tmp = tmp & rowCandidates(i)
End If
Next
For i = 0 To 2
If mWork(R, c + i) = 0 Then
cnt = cnt + 1
End If
Next
If cnt = Len(tmp) Then
For i = 0 To 2
If R + i <> R Then
For j = 0 To 2
newCandidates = Candidates(R + i, c + j)
For n = 1 To Len(Candidates(R + i, c + j))
If InStr(1, tmp, Mid$(Candidates(R + i, c + j), n, 1)) <> 0 Then
newCandidates = RemoveChar(newCandidates, Mid$(Candidates(R + i, c + j), n, 1))
End If
Next
Candidates(R + i, c + j) = newCandidates
Next
End If
Next
End If
End Function
' Remove impossible combinations by column
' This is where three candidate entries in a minblock column only produce three possible numbers
' in this case we can remove the numbers from the other candidates in the miniblock
Private Shared Function RemoveImpossibleCandidatesByCol(ByVal row As Integer, ByVal col As Integer) As String
Dim colCandidates(9) As String
Dim tmp As String
Dim i As Integer
Dim j As Integer
Dim n As Integer
Dim cnt As Integer
Dim R As Integer
Dim c As Integer
Dim newCandidates As String
R = Segment(row)
c = Segment(col)
For i = 0 To 2
For j = 1 To Len(Candidates(R + i, c))
colCandidates(CInt(Mid$(Candidates(R + i, c), j, 1))) = Mid$(Candidates(R + i, c), j, 1)
Next
Next
For i = 1 To 9
If colCandidates(i) <> "" Then
tmp = tmp & colCandidates(i)
End If
Next
For i = 0 To 2
If mWork(R + i, c) = 0 Then
cnt = cnt + 1
End If
Next
If cnt = Len(tmp) Then
For i = 0 To 2
If c + i <> c Then
For j = 0 To 2
newCandidates = Candidates(R + j, c + i)
For n = 1 To Len(Candidates(R + j, c + i))
If InStr(1, tmp, Mid$(Candidates(R + j, c + i), n, 1)) <> 0 Then
newCandidates = RemoveChar(newCandidates, Mid$(Candidates(R + j, c + i), n, 1))
End If
Next
Candidates(R + j, c + i) = newCandidates
Next
End If
Next
End If
End Function
'
' Convert the global coordinate to the miniblock coordinate (i.e. 0, 1 or 2 = 0, 3, 4 or 5 = 3, 6, 7 or 8 = 6)
'
Private Shared Function Segment(ByVal r As Integer) As Integer
Return (Int(r / 3) + 1) * 3 - 3
End Function
'
' Create a scratch area of consecutive numbers
'
Private Shared Function ScratchArea(ByVal numberFrom As Integer, ByVal numberTo As Integer) As String
Dim scratch As New StringBuilder
For i As Integer = numberFrom To numberTo
scratch.Append(i.ToString)
Next
Return scratch.ToString
End Function
End Class
End Namespace
|
|
|
| Back to top |
|
|
| Ruud
Site Admin
 | | Joined: 17 Sep 2005 | | Posts: 708 | | : | | Location: Netherlands |
Items |
|
| Posted: Thu Oct 06, 2005 7:03 pm Post subject: |
|
|
Looks like I found a few soul mates here 
I've written my solver completely object based. Here are some of the classes I use:
Grid (overall status, all Houses and Cells are properties)
GridValue (keeps stats per value in the grid, maintains Templates)
Template (represents a valid distribution of a single digit in the grid)
House (row, column or box, maintains bitmaps for cells & values filled or available to solver methods)
HouseValue (keeps track of candidate cells for a value in a house)
Segment (intersection of a box and row or column)
SegmentValue (handles status and effects for box-box and box-row/column interactions)
Cell (amongst the properties are 3 Houses and 9 CellValues
CellValue (takes care of elimination effects per value)
CellPainter (takes care of coloring, drawing, markup, etc.)
Alle of these objects are interlinked.
Grid.Row[4].Cell[5].Value[8] equals Grid.Cell[4,5].Value[8]
Cell, HouseValue and CellValue all implement the INode interface, so they can be used in the DLX solver without building a separate set of columns and rows.
For solving, other classes are defined:
Log, LogEntry (for solver log)
Solver (base class, keeps track of timing, repeated solving and status)
- HumanSolver (for human-style methods)
- LinkDancer (for fast solving)
- TemplateSolver (another fast variant)
- TrialAndErrorSolver (just for the sake having it...)
Each of the grid status objects also has a Backup class, to save the state for the Trial & Error solver.
BitMask (for accessing arrays when handling bitmaps)
Several other (smaller) classes that play a minor role in the program.
I do not use Collections or ArrayLists. They have nice features, but it turns out that they are much slower than strong types arrays.
Also, I never use Exceptions for error trapping in the solvers. There is an unacceptable delay on the first exception, probably because of the JIT compiler. I hope MS has fixed that in their 2005 release. |
|
| Back to top |
|
|
| Lummox JR
| | Joined: 07 Sep 2005 | | Posts: 202 | | : | |
Items |
|
| Posted: Fri Oct 07, 2005 12:26 am Post subject: |
|
|
| I've found the rows and columns from dancing links to be a great way to represent constraints and candidates. Most of the tests are quite simple to run in a loop across a set of the columns, and you can mark any rows which represent candidates to eliminate. |
|
| Back to top |
|
|
| dukuso
| | Joined: 14 Jul 2005 | | Posts: 424 | | : | | Location: germany |
Items |
|
| Posted: Fri Oct 07, 2005 1:16 am Post subject: |
|
|
I find the whole terminology and representation with the
columns and rows of the exact-cover matrix easier
and clearer than thinking with the 9*9 grid.
Maybe even all contraint programming with the
alldifferent constraints should be converted to
exact cover first !?! I found nothing about this
on the web. |
|
| Back to top |
|
|
| Lummox JR
| | Joined: 07 Sep 2005 | | Posts: 202 | | : | |
Items |
|
| Posted: Fri Oct 07, 2005 1:39 am Post subject: |
|
|
Indeed using the DLX-style constraints opens up a lot of easier avenues for understanding puzzles. Many simple tests like pointing pairs and box-line intersections, for instance, are drastically easier with this method than by trying to wrestle with a grid.
I had originally attempted a solver using bit flags for everything, but I learned very quickly that it was too much trouble to keep up with. To represent each form of constraint required multiple arrays, and modifying one array required modifying another in a different way. Keeping them in sync was an insanely difficult task. |
|
| Back to top |
|
|
| dukuso
| | Joined: 14 Jul 2005 | | Posts: 424 | | : | | Location: germany |
Items |
|
| Posted: Fri Oct 07, 2005 2:29 am Post subject: |
|
|
I don't care so much about sudoku-specific technics.
My methods should also work for similar puzzles,QWH-instances,
or larger sudokus or just other binary exact cover matrices.
Once I have the n*m matrix, I'd like to forget
where it came from |
|
| Back to top |
|
|
| Lummox JR
| | Joined: 07 Sep 2005 | | Posts: 202 | | : | |
Items |
|
| Posted: Fri Oct 07, 2005 3:56 am Post subject: |
|
|
Interesting. Most advanced sudoku techniques do work better if you remember the grid from time to time, but some will definitely work in any n*m.
The logic behind pointing pairs and box-line intersections, for example, should actually work for any pair of constraint types with a common element. That is, here it's looking for a column in one of the house-digit sections of the n*m (that is, in the latter 243 columns), where all the choices in that column also share another common column; other rows in the second column can be eliminated. You could apply this technique to any exact cover problem.
But then, these methods will only take you so far. Sudoku techniques like coloring do benefit from the DLX approach, but you still need a grid. |
|
| Back to top |
|
|
| dukuso
| | Joined: 14 Jul 2005 | | Posts: 424 | | : | | Location: germany |
Items |
|
| Posted: Fri Oct 07, 2005 6:35 am Post subject: |
|
|
-----------------------------------------------------------------------
treating all 324 constraints the same way and speaking about
the 729*324 binary exact-cover matrix instead :
for a row r let Nc[r] be the set of adjacent columns
for a column c let Nr[c] be the set of adjacent rows
for a column c let Nc[c] be the set of adjacent columns
for a row r let Nr[r] be the set of adjacent rows
for a column c let V[c]=|Nr[c]| be the size of c
a row and a column are considered adjacent, iff there is a one
in their intersection
two rows(columns) are considered adjacent, iff there is a valid
column(row) adjacent to both
|Nc[r]| is always 4 in sudoku. |Nr[c]| is at most 9 ,
|Nr[r]| is at most 29 , |Nc[c]| is at most 35
The task is to find a column c of minimum size.
Then backtrack through all its adjacent rows r,
delete all rows and columns in Nr[r] and Nc[r]
and continue until no more columns are left.
If there are several columns of minimum size
(usually size=2 in sudoku) we should refine the search, but how ?
to generalize to any n*m binary matrix :
we could also search for maximal bipartite subgraphs of
{rows} x {columns} to identify the rows,columns,blocks
I would not be surprised if what we find here with sudoku could
also have useful applications with e.g. solving QWH |
|
| 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
