Sudoku Solver in C#

Posted on 1/8/2007 @ 8:19 AM in #Vanilla .NET by | Feedback | 14410 views

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.

Sound off but keep it civil:

Older comments..


On 1/7/2007 6:50:55 PM Ahmad said ..
Where is the PopulateGrid() implementation?


On 1/7/2007 7:39:50 PM Bill said ..
Well, I don't know WTF Soduku is but this looks pretty kick a55. Nice job man.


On 1/7/2007 8:26:08 PM Sahil Malik said ..
Ahmad - PopulateGrid simply sets values for the grid before you ask to solve. I wrote only the engine - you could write a UI on top of this, which will take place of PopulateGrid.

Thanks Bill - you've gotta try Sudoku @least once.


On 1/7/2007 9:59:48 PM Steven Smith said ..
Oh, here's the fix to Solve(), which uses recursion in this case:


public bool 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


return Solve();


}


}


}


return true;


}


On 1/8/2007 12:44:54 AM Laurent said ..
This is damn cool :)


I do not like Sudoku because soon after having started a grid, I get frustrated thinking about computers bruteforce algorithms that would solve it better and quicker than me.


That piece of code has free my mind : thanks a lot !


On 1/8/2007 2:21:20 AM pranot said ..
excellent. now i can show this to my wife


we have always had arguments on whether this could be done, and if yes, how ethical it is


On 1/8/2007 12:33:24 PM Sahil Malik said ..
Pranot -

Is it ethical? Who cares, all I know is that - it works !!

Laurent -

My theory is, Humans are good at abstract thought, and Computers are good at computational thought. But a good enough complicated enough program in computational thought can mimic abstract thought. I don't think we are far away from the day when we will have computer rights in addition to human right. Frankly, we should have those today.

Steven -

Can you explain that a bit?

SM


On 1/24/2007 12:02:44 PM Steven Smith said ..
SM - I left a previous comment with more info, but apparently it didn't take. Basically your version of Solve() has an off-by-one error such that if the upper left (1,1) square in the grid is empty, it will never be solved. The reason is that you set row=1;column=1; but then the ++ iterator will still apply to one of them resulting in it going back to 2 before it re-enters the loop (so 1 is never checked). Changing loop control variables in the middle of a loop is BAD, so my replacement method accomplishes the same task using recursion. Might be a little more memory intensive (deeper call stack) but it works.


On 2/19/2007 8:41:46 AM Chris said ..
I had some problems with this solutions. For example for

0 0 0 0 0 6 3 0 0


7 0 0 0 8 0 4 2 0


0 0 0 2 0 0 5 0 0


0 0 0 0 5 0 0 4 0


2 8 0 0 0 0 0 6 7


0 3 0 0 1 0 0 0 0


0 0 1 0 0 3 0 0 0


0 2 4 0 7 0 0 0 9


0 0 7 5 0 0 0 0 0

.. which was the first example i found on websoduku.com

it does not work ??? why ??? are there any assumptions made to the start matrix???

I guess the part

if (possibleValuesFound.Count == 1)

is not correct for all examples. Very often there are more than 1 solutions found which then end up in incompleete solutions. maybee one need to "traverse" all possible solutions???


On 2/2/2008 11:42:53 AM e-quan said ..
tried this out but guess the algorithm of just checking 3 things


1) vertically


2) horizontally


3) in a square


will only solve easy sudokus


wouldn't work for websudoku's medium level and above


On 5/19/2008 9:10:45 AM tim said ..
hello i like your program but does it work without writing the populategrid() method...


you haven't and in the example it works but i can't get it working.. i just get a grid of zero's and when i enter it just closes down..


i tried the debugmode on htis program and i found out that the method TrySolving() never returns true.

greetz tim


On 8/19/2008 11:21:25 AM Kate said ..
I found this site very helpful when I was learning how to <a href="http://www.monkeysee.com/play/5134-how-to-play-sudoku">play sudoku</a>. I'm not sure if you're interested in watching how to videos, but these are great for beginners!


On 3/6/2009 10:58:28 AM jon said ..
Hey, I have a simple question to the author. How do I implement this code. I am confused because when i create a simple console application and copy the source code there are 7 mistakes. Could you help me on this matter because I am really a newbie in c#.

thnx, ud be a life saver.


jon


On 3/8/2009 7:25:46 PM Galletly said ..
Dear Jon!

Don't forget to implement the Main function!

;)


On 6/14/2009 3:59:23 AM James said ..
The reason this doesn't work on hard is you don't check for unique values in rows, columns, blocks. If a square can have 3 values, but only 1 is valid for the entire row/column/block, then only that 1 will fit and you can ignore the other possiblities.

I modified the code fairly quickly by duplicating the "Does*" functions to find unique instances of values in the row instead if finding all valid. e.g.

private int UniqueRowValue(int value, int row)


{


int foundIndex = -1;


for (int columnIndex = 1; columnIndex <= 9; columnIndex++)


{


int index = FindIndex(row, columnIndex);

if (vals[index].value == value)


return -1; // existing value found, no need to check more

if (vals[index].possibleValues.Contains(value))


{


if (foundIndex > -1)


return -1; // more than 1 value found


foundIndex = index;


}


}


return foundIndex;


}

I also had to store the possibleValues around (you didn't preserve them between squares), by adding them to the vars array (which now has value & an List<int> of possible values).

I'll probably play around with a bit more to clean stuff up, but it was a nice start for me to play with.

Here's a hard that it solved:

|0|6|0|0|0|0|0|0|7|


|0|0|4|8|0|0|0|1|0|


|0|0|2|5|0|7|0|0|0|


|1|0|0|0|2|0|0|0|5|


|4|0|0|0|9|0|0|0|6|


|3|0|0|0|7|0|0|0|8|


|0|0|0|7|0|4|8|0|0|


|0|5|0|0|0|3|2|0|0|


|7|0|0|0|0|0|0|9|0|


Hit enter to begin

|5|6|3|2|1|9|4|8|7|


|9|7|4|8|3|6|5|1|2|


|8|1|2|5|4|7|3|6|9|


|1|9|6|4|2|8|7|3|5|


|4|8|7|3|9|5|1|2|6|


|3|2|5|6|7|1|9|4|8|


|2|3|9|7|6|4|8|5|1|


|6|5|1|9|8|3|2|7|4|


|7|4|8|1|5|2|6|9|3|

Done!


On 3/8/2010 11:21:48 PM CoolCoder said ..
For Populate Grid try this


change in the main function


grid.PopulateGrid();

in the SudokuGrid class Add the PopulateGrid method


public void PopulateGrid()


{


string str = "003020600900305001001806400008102900700000008006708200002609500800203009005010300";


for (int i = 0; i < 81; i++)


{


string s = str[i].ToString();


vals[i] = Int32.Parse(s);


}

}

// Notice i changed row to column


// this aligns the grid correctly


private int FindIndex(int row, int column)


{

return (((row - 1) * 9) + column - 1);

}


On 6/8/2010 1:12:43 PM e-screams said ..
Hii very good job.


This is my Sudoku game.


http://sourceforge.net/projects/sudokucs/


On 9/21/2010 5:53:04 PM tigress said ..
HI,

I've got an important project


with sudoku,so...


how this code must look with all of it,


with :


private int UniqueRowValue(int value, int row)


and :


the PopulateGrid method

Could you help me on this


because I'm a middle class in c#.