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("Complete with {0} iterations", numIterations);
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)
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)
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;
sb.Append("\r\n");
if (lct++ == 3)
lct = 1;
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();
/// 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
public bool IsLegal(int x, int y, int value)
//if it is a fixed value, return false
//any other setting to zero is valid..
if (value == 0) return true;
//check columns...
if (Math.Abs(board[x, i]) == value) return false;
//check rows
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;