/*****************************************************************************
**
** dlx.cs
**
*****************************************************************************/
using System;
using System.Diagnostics;
class DancingLinks
{/* -----------------------------------------------------------------------
DECLARATIONS
----------------------------------------------------------------------- */
#region "DECLARATIONS"
private const int M = 4 * Grid.Squares; // 324 for classic Sudoku
private const int N = Grid.Size * Grid.Squares; // 729 for classic Sudoku
#endregion
/* -----------------------------------------------------------------------
VARIABLES
----------------------------------------------------------------------- */
#region "VARIABLES"
private static bool _bInitialized = false;
private static int[] _iCols = null;
private static int[] _iRows = null;
private static int[ , ] _col = null;
private static int[ , ] _row = null;
private int _iSolutions;
private bool[] _bColFlags;
private int[] _iRowFlags;
#endregion
/* -----------------------------------------------------------------------
STATIC METHODS
----------------------------------------------------------------------- */
#region "STATIC METHODS"
///
/// <summary>
/// Generates the shared (constant) exact-cover matrix.
/// </summary>
///
private static void
initializeStaticArrays()
{ int idx, iC, iR;
_bInitialized = true;
_col = new int[ N + 1, 4 ];
_iCols = new int[ N + 1 ];
_row = new int[ M + 1, Grid.Size + 1 ];
_iRows = new int[ M + 1 ];
idx = 0;
for (iR = 0; iR < Grid.Size; ++iR)
for (iC = 0; iC < Grid.Size; ++iC)
for (int z = 1; z <= Grid.Size; ++z)
{ idx++;
_iCols[ idx ] = 4;
_col[ idx, 0 ] = (iR * Grid.Size) + iC + 1;
_col[ idx, 1 ] = ((Grid.BoxSize * (iR / Grid.BoxSize)) + (iC / Grid.BoxSize)) * Grid.Size + Grid.Squares + z;
_col[ idx, 2 ] = (iR * Grid.Columns) + (2 * Grid.Squares) + z;
_col[ idx, 3 ] = (iC * Grid.Rows) + (3 * Grid.Squares) + z;
}
for (iC = 1; iC <= M; ++iC)
_iRows[ iC ] = 0;
for (iR = 1; iR <= N; ++iR)
for (iC = 0; iC < _iCols[ iR ]; ++iC)
{ idx = _col[ iR, iC ];
_iRows[ idx ]++;
_row[ idx, _iRows[ idx ] ] = iR;
}
} /* end of initializeStaticArrays() */
#endregion
/* -----------------------------------------------------------------------
CONSTRUCTOR
----------------------------------------------------------------------- */
#region "CONSTRUCTOR"
///
/// <summary>
/// Constructor for the "dancing links" class
/// </summary>
///
public
DancingLinks()
{ _iSolutions = 0;
if (!_bInitialized)
initializeStaticArrays();
} /* end of DancingLinks::DancingLinks() */
#endregion
/* -----------------------------------------------------------------------
PUBLIC METHODS
----------------------------------------------------------------------- */
#region "PUBLIC METHODS"
///
/// <summary>
/// Solves an input string
/// </summary>
/// <param name="strIn">Input string</param>
/// <param name="bFindAll">TRUE to find all solutions, FALSE to stop after second</param>
/// <returns>Number of solutions found</returns>
///
public int
Solve( String strIn, bool bFindAll )
{ int idx,
index,
iEmpty,
iState,
iValue;
_iSolutions = 0;
if (strIn == null || strIn.Length < Grid.Squares)
return 0;
_bColFlags = new bool[ M + 1 ];
for (idx = 0; idx <= M; ++idx)
_bColFlags[ idx ] = false;
_iRowFlags = new int[ N + 1 ];
for (idx = 0; idx <= N; ++idx)
_iRowFlags[ idx ] = 0;
index = iEmpty = 0;
for (int iR = 0; iR < Grid.Rows; ++iR)
for (int iC = 0; iC < Grid.Columns; ++iC)
{ if (Int32.TryParse( strIn.Substring( index++, 1 ), out iValue ) &&
Grid.IsValidValue( iValue ))
{ iState = iValue + (iR * Grid.Squares) + (iC * Grid.Size);
for (int j = 0; j < _iCols[ iState ]; ++j)
{ idx = _col[ iState, j ];
if (_bColFlags[ idx ])
return 0;
_bColFlags[ idx ] = true;
for (int k = 1; k <= _iRows[ idx ]; ++k)
_iRowFlags[ _row[ idx, k ] ]++;
}
}
else
iEmpty++;
}
solve( iEmpty, !bFindAll );
return _iSolutions;
}
///
/// <summary>
/// Attempts to solve the puzzle
/// </summary>
/// <param name="grid">Grid to solve</param>
/// <param name="bFindAll">TRUE to find all solutions, FALSE to stop after second</param>
/// <returns>Number of solutions found</returns>
///
public int
Solve( Grid grid, bool bFindAll )
{ int index,
iState;
int j, k, idx;
_iSolutions = 0;
if (grid == null)
return 0;
_bColFlags = new bool[ M + 1 ];
for (idx = 0; idx <= M; ++idx)
_bColFlags[ idx ] = false;
_iRowFlags = new int[ N + 1 ];
for (idx = 0; idx <= N; ++idx)
_iRowFlags[ idx ] = 0;
for (index = 0; index < Grid.Squares; ++index)
if (!grid[index].IsEmpty)
{ iState = grid[ index ].Value +
(Grid.GetRow(index) * Grid.Squares) +
(Grid.GetColumn(index) * Grid.Size);
for (j = 0; j < _iCols[ iState ]; ++j)
{ idx = _col[ iState, j ];
if (_bColFlags[ idx ])
return 0;
_bColFlags[ idx ] = true;
for (k = 1; k <= _iRows[ idx ]; ++k)
_iRowFlags[ _row[ idx, k ] ]++;
}
}
solve( grid.EmptyCount, !bFindAll );
return _iSolutions;
}
///
/// <summary>
/// Recursive search portion of the dancing links algorithm
/// </summary>
/// <param name="iEmpty"></param>
/// <param name="bQuick">TRUE to stop after second solution</param>
///
private void
solve(int iEmpty, bool bQuick)
{ int iBest,
iSolved,
iState;
int j, k, iR, iC, idx;
int[] C = new int[ Grid.Squares ];
int[] I = new int[ Grid.Squares + 1 ];
if (iEmpty > (Grid.Squares - Grid.StartingValues))
return;
iSolved = iState = 0;
for (;;)
{ switch (iState)
{ //
// Compute the next entry by finding the column C[iSolved] with
// fewest matching rows.
//
case 0:
I[ ++iSolved ] = 0;
iBest = N + 1;
for (iC = 1; iC <= M; ++iC)
if (!_bColFlags[ iC ])
{ int iMatch = 0;
for (iR = 1; iR <= _iRows[ iC ]; ++iR)
if (_iRowFlags[ _row[ iC, iR ] ] == 0)
iMatch++;
if (iMatch < iBest)
{ iBest = iMatch;
C[ iSolved ] = iC;
}
}
iState = (iBest > 0 && iBest <= N) ? 1 : 2;
break;
//
// Walk through all unmarked rows iR matching column C[iSolved]
//
case 1:
iC = C[ iSolved ];
I[ iSolved ]++;
if (I[ iSolved ] > _iRows[ iC ])
{ iState = 2;
continue;
}
iR = _row[ iC, I[ iSolved ] ];
if (_iRowFlags[ iR ] != 0)
{ iState = 1;
continue;
}
if (iSolved == iEmpty)
{ _iSolutions++;
if (bQuick && _iSolutions > 1)
{ //
// j = (iR - 1) / Grid.Squares;
// k = ((iR - 1) % Grid.Squares) / Grid.Size;
// sq[j, k] = ((iR - 1) % Grid.Size) + 1;
//
return;
}
}
//
// Delete all columns which match row iR and all rows which
// match any of these columns.
//
for (j = 0; j < _iCols[ iR ]; ++j)
{ idx = _col[ iR, j ];
_bColFlags[ idx ] = true;
for (k = 1; k <= _iRows[ idx ]; ++k)
_iRowFlags[ _row[ idx, k ] ]++;
}
// Entry was made, matrix was updated, goto the next level
iState = 0;
break;
//
// Backtrack: goto previous level, take back the last move,
// and restore the data as they were before that move and make
// the next available move at that level.
//
case 2:
iC = C[ --iSolved ];
iR = _row[ iC, I[ iSolved ] ];
for (j = 0; j < _iCols[ iR ]; ++j)
{ idx = _col[ iR, j ];
_bColFlags[ idx ] = false;
for (k = 1; k <= _iRows[ idx ]; ++k)
_iRowFlags[ _row[ idx, k ] ]--;
}
iState = (iSolved > 0) ? 1 : -1;
break;
default:
return;
}
}
} /* end of DancingLinks::solve() */
#endregion
/* -----------------------------------------------------------------------
PROPERTIES
----------------------------------------------------------------------- */
#region "PROPERTIES"
public int
Solutions
{ get
{ return _iSolutions;
}
}
}
#endregion
/*****************************************************************************
**
** End of dlx.cs
**
*****************************************************************************/