Sudoku solver in C#
using System;
using System.Collections.Generic;
using System.Text;
using System.IO;
namespace SudokuSample
{
class Driver
{
public static string Usage = "sudoku <filename> \r\n where <filename> is a text file containg the initial board state as a 9x9 matix of integers, zero for blanks";
static void Main(string[] args)
{
//checking args
if (args.Length > 1)
{
Console.WriteLine(Usage);
return;
}
//if we have a file, use it...
string init;
if (args.Length == 1)
{
init = File.ReadAllText(args[0]);
}
//otherwise, use a baked in test..
else
{
init =
@"9 0 6 5 0 7 0 2 0
8 0 0 0 0 0 3 7 0
0 0 0 3 0 2 0 0 0
0 6 0 0 0 0 0 0 2
0 9 0 0 7 0 0 4 0
2 0 0 0 0 0 0 9 0
0 0 0 4 0 3 0 0 0
0 1 3 0 0 0 0 0 4
0 4 0 1 0 5 2 0 7";
}
Board b = new Board(init);
Console.WriteLine(b.ToString());
Random rand = new Random((int)DateTime.Now.Ticks);
int numIterations = 0;
//We will keep looping until we have a complete solution
while (!b.IsComplete)
{
numIterations++;
for (int i = 0; i < 9; i++)
{
for (int j = 0; j < 9; j++)
{
//ok, so this is a bit of a hack, I try 10 times to find a move that will work
//for this spot... if I can great, otherwise, punt
for (int k = 1; k < 10; k++)
{
if (b.Move(i, j, rand.Next(1, 10))) break;
}
}
}
//if I didn't complete, it is likely because we are stuck,
//so I zero out (or undo) a couple of moves..
if (!b.IsComplete)
{
//zero 2
Console.WriteLine("zeroing 2");
for (int i = 0; i < 2; i++)
{
b.Move(rand.Next(0, 9), rand.Next(0, 9), 0);
}
Console.WriteLine("Board State at iteration {0}", numIterations);
Console.WriteLine(b.ToString());
}
}
Console.WriteLine("Complete with {0} iterations", numIterations);
Console.WriteLine(b.ToString());
Console.ReadLine();
}
}
//Contains the Sudoku
public class Board
{
int[,] board;
//an empty board, used just for testing...
public Board()
{
board = new int[9, 9];
}
//init a board from a string...
public Board(string value)
{
board = new int[9, 9];
int i = 0;
int j = 0;
foreach (char c in value)
{
if (char.IsDigit(c))
{
board[j, i] = Convert.ToInt32(c.ToString());
//make it negative to indicate it is a fixed value that can't be changed
//notice, zeros can be changed, how cute ;-)
board[j, i] = board[j, i] * -1;
i++;
if (i >= 9) { i = 0; j++; };
}
}
}
//utility function to find out if a value is in the board...
bool In(int value)
{
for (int i = 0; i < 9; i++)
{
for (int j = 0; j < 9; j++)
{
if (board[i, j] == value) return true;
}
}
return false;
}
//are we done? Assuming all moves are legal, we are done when
//there are no blanks (zeros).
public bool IsComplete
{
get
{
return !In(0);
}
}
//Fanzy tostring to help with debugging...
public override string ToString()
{
System.Text.StringBuilder sb = new StringBuilder();
int lct = 0;
int wct = 1;
for (int i = 0; i < 9; i++)
{
sb.Append("\r\n");
if (lct++ == 3)
{
sb.Append("\r\n");
lct = 1;
}
for (int j = 0; j < 9; j++)
{
sb.AppendFormat("{0} ", Math.Abs(board[i, j]));
if (wct++ == 3)
{
sb.Append(" ");
wct = 1;
}
}
}
return sb.ToString();
}
/// <summary>
/// Tries to perform a move, returns true if i can, false otherwise.
/// </summary>
public bool Move(int x, int y, int value)
{
if (board[x, y] < 0) return false;
if (!IsLegal(x, y, value)) return false;
board[x, y] = value;
return true;
}
// figure out what box a given cooridate is in
public void GetBox(int x, int y, out int boxX, out int boxY)
{
if (x < 3) boxX = 0; else if (x < 6) boxX = 3; else if (x < 9) boxX = 6; else throw new Exception();
if (y < 3) boxY = 0; else if (y < 6) boxY = 3; else if (y < 9) boxY = 6; else throw new Exception();
}
/// <summary>
/// Deterimes is a given move is legal... There are several reasons it may not be legal.
/// (1) move at a fixed spot (a negative value)
/// (2) this value is already in the row
/// (2) this value is already in the column
/// (3) this value is already in the 3x3 box
/// </summary>
public bool IsLegal(int x, int y, int value)
{
//if it is a fixed value, return false
if (board[x, y] < 0) return false;
//any other setting to zero is valid..
if (value == 0) return true;
//check columns...
for (int i = 0; i < 9; i++)
{
if (Math.Abs(board[x, i]) == value) return false;
}
//check rows
for (int i = 0; i < 9; i++)
{
if (Math.Abs(board[i, y]) == value) return false;
}
//check boxes of three
int boxX, boxY;
GetBox(x, y, out boxX, out boxY);
for (int i = boxX; i < boxX + 3; i++)
{
for (int j = boxY; j < boxY + 3; j++)
{
if (Math.Abs(board[i, j]) == value) return false;
}
}
return true;
}
}
}
Comments
- Anonymous
September 26, 2005
It is NOT "solver" (may be "blind trier" :) )
It is NOT programm.
shame on you. - Anonymous
September 28, 2005
Thanks a lot. My son came home yesterday and asked me about these puzzles. He asked me to write a program that would build these. Now I can just pass on the code. :) - Anonymous
October 11, 2005
Abusing CPU cycles?
A backtracking algorithm seems to be more elegant for this.
ME