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.
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/
|
