/*****************************************************************************
**
** Generator.cs
**
*****************************************************************************/
using System;
using System.Diagnostics;
using System.Collections.Generic;
class Generator
{ /* -----------------------------------------------------------------------
VARIABLES
----------------------------------------------------------------------- */
private Random _rnd;
/* -----------------------------------------------------------------------
CONSTRUCTOR
----------------------------------------------------------------------- */
///
/// <summary>
/// Constructor for the Generator class
/// </summary>
///
public
Generator( )
{ _rnd = new Random( );
} /* end of Generator::Generator() */
/* -----------------------------------------------------------------------
METHODS
----------------------------------------------------------------------- */
///
/// <summary>
/// Creates a new puzzle
/// </summary>
/// <returns>TRUE if puzzle created, FALSE otherwise</returns>
///
public Grid
Create( )
{ bool bGenerating = true;
Grid grid = new Grid( );
DancingLinks dlx = new DancingLinks( );
while (bGenerating)
{ try
{ if (fillGrid( ref grid, dlx ) &&
stripGrid( ref grid, dlx ))
{ bGenerating = false;
}
}
catch (Exception)
{ /* do nothing */ }
}
return grid;
} /* end of Generator::Create() */
/* -----------------------------------------------------------------------
PRIVATE METHODS
----------------------------------------------------------------------- */
/// <summary>
/// Fills a grid by randomly placing values until a unique puzzle is found
/// </summary>
/// <returns>TRUE if filled grid found, FALSE otherwise</returns>
/// <param name="grid">Grid to create puzzle in</param>
/// <param name="dlx">DancingLinks solver used to test for uniqueness</param>
///
private bool
fillGrid( ref Grid grid, DancingLinks dlx )
{ const int kCombinations = Grid.Squares * Grid.Size;
bool bUndo;
int idx,
index,
iValue = Grid.ValueNone;
int[ ] iTries = new int[ kCombinations ];
//
// Build a list of possible combinations, then shuffle it.
//
index = 0;
for (idx = 0; idx < kCombinations; ++idx)
{ if ((iTries[ idx ] = idx) > 2)
{ int iLHS = _rnd.Next( idx ),
iRHS = _rnd.Next( idx );
//
// Swap the two array elements
//
int iTemp = iTries[ iLHS ];
iTries[ iLHS ] = iTries[ iRHS ];
iTries[ iRHS ] = iTemp;
}
}
//
// Now walk the tries and test them all
//
grid.Reset( );
for (int iTry = 0; iTry < kCombinations; ++iTry)
{ try
{ bUndo = false;
//
// Find a random candidate on a random square. If we can't
// find one, bail out.
//
index = iTries[ iTry ] % Grid.Squares;
if (!grid[ index ].IsEmpty)
continue;
iValue = (iTries[ iTry ] / Grid.Squares) + Grid.ValueMin;
if (!grid[ index ].Candidates.Test( iValue ))
continue;
//
// Set the square to the random candidate; if this results in
// an invalid puzzle, an exception will be thrown. See if we
// got a valid puzzle, but only if we have enough starting
// squares.
//
if (grid.Set( index, iValue ) &&
grid.FilledCount >= Grid.StartingValues)
{ if (dlx.Solve( grid, false ) == 1)
return true; // found a unique puzzle!
if (dlx.Solutions == 0)
bUndo = true;
}
}
catch (Exception)
{ bUndo = true;
}
//
// The last move resulted in an invalid puzzle, so back out the
// change and try again.
//
if (bUndo)
grid.SetEmpty( index );
}
return false;
} /* end of fillGrid() */
///
/// <summary>
/// Tries to reduce the number of starting squares
/// </summary>
/// <returns>TRUE if valid grid returns, FALSE otherwise</returns>
/// <param name="grid">Grid to create puzzle in</param>
/// <param name="dlx">DancingLinks solver used to test for uniqueness</param>
///
private bool
stripGrid( ref Grid grid, DancingLinks dlx )
{ int index,
iCount,
iValue;
int[ ] iTries = new int[ Grid.Squares ];
//
// Build a array of filled (non-empty) squares, and randomly shuffle
// the elements as we go. This way, we'll try to remove the filled
// squares in a quasi-random order, without repetition.
//
for (index = iCount = 0; index < Grid.Squares; ++index)
if (!grid[ index ].IsEmpty)
{ iTries[ iCount ] = index;
if (++iCount > 2)
{ int iLHS = _rnd.Next( iCount ),
iRHS = _rnd.Next( iCount );
//
// Swap the two array elements
//
int iTemp = iTries[ iLHS ];
iTries[ iLHS ] = iTries[ iRHS ];
iTries[ iRHS ] = iTemp;
}
}
for (int iStrip = 0; iStrip < iCount; ++iStrip)
{ try
{ //
// Step #1 -- find a value on the board
//
index = iTries[ iStrip ];
iValue = grid[ index ].Value;
grid.SetEmpty( index );
//
// Step #2 -- see if we still have a unique puzzle. If we
// do, then keep it.
//
if (dlx.Solve( grid, false ) == 1)
{ /*
Console.WriteLine("Dropped value in {0}.", Grid.SqName(index));
*/
if (grid.FilledCount <= Grid.StartingValues)
return true; // not going to get any smaller!
}
else // Puzzle isn't unique any more, so restore the value
grid.Set( index, iValue );
}
catch (Exception)
{ /* do nothing */ }
}
return true;
} /* end of stripGrid() */
/* -----------------------------------------------------------------------
PROPERTIES
----------------------------------------------------------------------- */
};
/*****************************************************************************
**
** End of Generator.cs
**
*****************************************************************************/