.. because Solving Sudoku the fair way wouldn't be any fun.
Reposting: Apparently, when I redid my site recently, I ignored putting this back. Since then I've got repeated requests to put this back online, so here it is again. Thank god for backups.
Ya know what !!!
I got pretty sick n tired of sucking at Sudoku. Seriously!! I have this friend, who keeps beating the crap out of me in Sudoku puzzles. (What is Sudoku?) (Play Sudoku here). It is indeed a pretty addictive game. But I take 30 minutes to solve, when the world average seems to be around 6 minutes - THATS LIKE YUK!!
So, I wrote a small C# program to solve Sudoku. LOL. :-)
Here is the code in action (with an intentional 200 ms delay between each number so you can see what is going on) -
And here is the actual code usage -
private
static SudokuGrid grid = new SudokuGrid();
static void Main(string[] args)
{
PopulateGrid();
Console.WriteLine(grid.ToString());
Console.WriteLine("Hit Enter to Begin Solving!!") ;
Console.Read() ;
// Start Solving.
grid.Solve();
Console.WriteLine("Done !!!");
Console.ReadLine() ;
}
Of course, the fun part is in the "SudokuGrid" class itself. (Sorry the code is a bit lengthy) -
public class SudokuGrid
{
private int[] vals = new int[81];
public int this[int row, int column]
{
get { return vals[FindIndex(row, column)]; }
set
{
vals[FindIndex(row, column)] = value;
}
}
private int FindIndex(int row, int column)
{
return (((column - 1) * 9) + row - 1);
}
public override string ToString()
{
System.Text.StringBuilder sb = new System.Text.StringBuilder();
sb.AppendLine();
for (int row = 1; row <= 9; row++)
{
for (int column = 1; column <= 9; column++)
{
sb.Append(this[row, column] + " ");
}
sb.AppendLine();
}
return sb.ToString();
}
public void Solve()
{
for (int column = 1; column <= 9; column++)
{
for (int row = 1; row <= 9; row++)
{
if (TrySolving(row, column))
{
Console.Clear();
Console.WriteLine(this.ToString());
System.Threading.Thread.Sleep(200);
// restart
row = 1;
column = 1;
}
}
}
}
private bool TrySolving(int row, int column)
{
List<RowColumnValue> possibleValuesFound = new List<RowColumnValue>();
if (this[row, column] == 0)
{
for (int possiblevalues = 1; possiblevalues <= 9; possiblevalues++)
{
if (!DoesRowContainValue(possiblevalues, row, column))
{
if (!DoesColumnContainValue(possiblevalues, row, column))
{
if (!DoesSquareContainValue(possiblevalues, row, column))
{
possibleValuesFound.Add(new RowColumnValue(row, column, possiblevalues));
}
}
}
}
if (possibleValuesFound.Count == 1)
{
this[possibleValuesFound[0].Row, possibleValuesFound[0].Column] = possibleValuesFound[0].Value;
return true;
}
}
return false;
}
private bool DoesRowContainValue(int value, int row, int column)
{
for (int columnindex = 1; columnindex <= 9; columnindex++)
{
if ((this[row, columnindex] == value) & column != columnindex)
{
return true;
}
}
return false;
}
private bool DoesColumnContainValue(int value, int row, int column)
{
for (int rowindex = 1; rowindex <= 9; rowindex++)
{
if ((this[rowindex, column] == value) & row != rowindex)
{
return true;
}
}
return false;
}
private bool DoesSquareContainValue(int value, int row, int column)
{
//identify square
int rowStart = ((row - 1) / 3) + 1;
int columnStart = ((column - 1) / 3) + 1;
int rowIndexEnd = rowStart * 3;
if (rowIndexEnd == 0) rowIndexEnd = 3;
int rowIndexStart = rowIndexEnd - 2;
int columnIndexEnd = columnStart * 3;
if (columnIndexEnd == 0) columnIndexEnd = 3;
int columnIndexStart = columnIndexEnd - 2;
for (int rowIndex = rowIndexStart; rowIndex <= rowIndexEnd; rowIndex++)
{
for (int columnIndex = columnIndexStart; columnIndex <= columnIndexEnd; columnIndex++)
{
if ((this[rowIndex, columnIndex] == value) & (columnIndex != column) & (rowIndex != row))
{
return true;
}
}
}
return false;
}
}
The RowColumnValue holder class is as below -
internal class RowColumnValue
{
private int row;
internal int Row
{
get { return row; }
}
private int column;
internal int Column
{
get { return column; }
}
private int value;
internal int Value
{
get { return value; }
}
internal RowColumnValue(int r, int c, int v)
{
row = r;
column = c;
value = v;
}
}
Wow this was fun !! :-)
This took me about 45 minutes to write. I am sure there are better ways of solving Sudoku, but hey this works, and now I won't be beaten 24X7.
