using System;
using System.Collections.Generic;
using System.Diagnostics;
namespace Sudoku
{
/* Solves a Sudoku puzzle. The algorithm isn't genius; I wrote this to work the same way
* that I solve difficult puzzles by hand, which is to fill in each blank with all the numbers
* that could possibly go there based on the current row, block, and column constraints.
* Since difficult puzzles won't reveal any definite answers immediately, I'll need to
* guess about the value of a particular cell, and see how the additional constraint
* affects the other values. I usually have to recurse a few times, and it can get
* difficult to hold all the state in my head, or messy if I attempt to represent it on
* paper. Eventually I'll hit a state that's impossible, in which case I need to revise
* my most recent guess, or I'll complete the puzzle.
*
* In this program, the board is represented as a 9x9 grid of integers. The bits set in
* each integer determine the values that could possibly go in that cell. The low bit
* represents the first digit, 1.
*/
class Program
{
/// The value of a cell that can contain any digit.
const ushort FullCell = 0x1FF;
// a Sudoku board is NxN cells where N is K^2, and K is a positive integer
const int BlockSize=3, BoardLength=BlockSize*BlockSize, BoardSize = BoardLength*BoardLength, Digits=BoardLength;
static void Main(string[] args)
{
// ensure that there's enough space to display the board
Console.BufferWidth = Math.Max(Console.BufferWidth, BoardLength*Digits + BoardLength + 2);
Console.WindowWidth = Console.BufferWidth;
// set the initial board state
SetState(@"
-------------
| 2| 4 | 1 |
| 89| 1 | 7 |
| 1| | 8|
|---+---+---|
| | 4| 9|
|7 |281| 4|
|2 |3 | |
|---+---+---|
|9 | |3 |
| 2 | 7 |64 |
| 3 | 5 |8 |
-------------");
PushState(); // save the original data
if(Solve())
{
PrintBoard(); // display the solution
Console.WriteLine("Puzzle solved!");
}
else
{
PopState(); // display the original data
PrintBoard();
Console.WriteLine("Unable to solve this puzzle!");
}
Console.WriteLine("Press a key to exit...");
Console.ReadKey();
}
/// Gets the cell value at the given coordinates.
static ushort Get(int x, int y)
{
return state[y*BoardLength+x];
}
/// Sets the cell value at the given index, and updates affected cells.
/// Returns true if this results in a valid board.
static bool Set(int i, ushort value)
{
return Set(i%BoardLength, i/BoardLength, value);
}
/// Sets the cell value at the given coordinates, and updates affected cells.
/// Returns true if this results in a valid board.
static bool Set(int column, int row, ushort value)
{
int index = row*BoardLength+column;
// prevent infinite recursion by returning if the value already matches
if(state[index] == value) return true;
state[index] = value;
if(IsDefinite(value)) // if the new value is definite, it will affect other cells
{
for(int x=0; xTries to update a cell at the given coordinates, given a new
/// value that was inserted into a related cell.
///
static bool TryUpdateConstraint(int x, int y, ushort value)
{
ushort mask = Get(x, y);
if(mask != 0) // if the cell already has a value, update it. (the only time it won't
{ // have a value is during the initial setting of the board state)
mask &= (ushort)~value;
return mask != 0 && Set(x, y, mask); // if it becomes zero, the puzzle becomes unsolvable, so return false
}
else return true; // if the cell has no value, assume it'll be set later
}
/// Returns the number of bits set in the given cell value. This is equal to the
/// number of possible digits that could go in the cell.
///
static int BitCount(ushort value)
{
int count = 0;
while(value != 0)
{
if((value&1) != 0) count++;
value >>= 1;
}
return count;
}
/// Returns a mask corresponding to the Nth possible digit for a given cell.
/// The cell value.
/// The number of the bit to return, from 0 to BitCount(value)-1.
static ushort GetBitValue(ushort value, int bit)
{
ushort mask = 1;
Debug.Assert(bit >= 0 && BitCount(value) > bit); // make sure the bit index is within range
while(true)
{
while((value&mask) == 0) mask <<= 1;
if(bit-- == 0) break;
mask <<= 1;
}
return mask;
}
/// Gets the index of the first unsolved cell -- ie, the first cell without a
/// definite value.
///
/// True if an unsolved cell was found, and false if not.
static bool GetUnsolved(out int index)
{
for(int i=0; iSaves the current board state on a stack.
static void PushState()
{
stack.Push(state);
state = (ushort[])state.Clone();
}
/// Restores the previous board state.
static void PopState()
{
state = stack.Pop();
}
/// Attempts to solve the puzzle and returns true if it could be solved.
static bool Solve()
{
// we'll find the first unsolved cell. if there isn't one, the puzzle is
// already solved.
int index;
if(!GetUnsolved(out index)) return true;
// try each possible digit in the unsolved cell (and update surrounding cells),
// and recursively attempt to solve the resulting puzzle. if we come to an impossible
// state, we'll backtrack.
for(int b=BitCount(state[index])-1; b >= 0; b--)
{
PushState();
if(Set(index, GetBitValue(state[index], b)) && Solve()) return true;
PopState();
}
// if no digits in the unsolved cell are possible, this puzzle is unsolvable
return false;
}
/// Determines whether the given cell value is definite -- ie, it has only one bit set.
static bool IsDefinite(ushort value)
{
return (value & (value-1)) == 0 && value != 0;
}
/// Prints the board to the screen.
static void PrintBoard()
{
string separator = new string('-', BoardLength*Digits + BoardLength+1);
for(int y=0; ySets the current state based on a string description of the board.
/// A string containing board information. Spaces and digits are filled in
/// as board cells. All other characters are ignored.
///
static void SetState(string s)
{
// initialize the board to have every cell able to contain any digit
for(int i=0; iConverts a cell value to string containing the digits that could possibly exist in that cell. The string
/// will be padded with spaces to the maximum string length.
///
static string ToString(ushort cell)
{
const string chars = "123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ";
char[] buf = new char[Digits];
int j=0;
for(int i=0; i> i) & 1) != 0) buf[j++] = chars[i];
}
string digits = new string(buf, 0, j);
// return the digits, centered within a 9-character string
return new string(' ', (Digits-j)/2) + digits + new string(' ', (Digits-j+1)/2);
}
/// The current board state.
static ushort[] state = new ushort[BoardSize];
/// A stack of saved board states.
static Stack stack = new Stack();
}
} // namespace Sudoku