My older son (12 years) just came back from a sailing trip. It wasn't just an "ordinary" sailing trip ...they went with a Math teacher who invited kids that are advanced on their Math skills.
Guess what! He comes back and immediately throws a "hard to solve" Sudoku at me, telling me that he did it in 1h40 and his teacher did it in 1h20! ...he was even blunt enough to challenge me, whether I could do better than that.
Not that I needed another job or such a challenge, as I've really lost interest in burning time with these puzzles early in my life, after I solved the Rubik's cube ...only then to be thrown at all the puzzles my friends had gotten as "presents", to add peace to their life by giving them the solution.
So, what do you do when you know how to program? No, you don't program right away. You look if there's a solution already out there, that just does it (I hate reinventing wheels!).
However, all I found were incomplete, strange (to say the least) or flawed solutions. Amongst the "highlights" I found were people that are using brute force algorithms (guys, are you using a sledge hammer to open your front door?), LINQ queries to check things that a couple of simple "for" loops could do, and people that were using highly mathematical algorithms that you'd have to read a whole book on first before you knew for sure, that what you were about to do would actually have a chance for success. Oh, almost forgot another good one: someone using an algorithm that could end up in an endless loop, so a perpetual hash generator was introduced to identify such a situation ...no wonder software applications are so convoluted these days!
The Approach
Oh well, what did I do? Yep, I invented a new wheel. How did I approach it? Well, Sudokus are practically a permutation problem, which means that one typically looks out for the easy choices (e.g. squares that have only one spot for a specific value), and if you are out of those you resort to the dual options (and then the triple etc.). Also, at least for me, it is a no-brainer to use recursion to address such a problem (and also to minimize the code ...less is more :-). The whole code is less than 200 lines. As an intro, here's the method that implements the approach:
The Code
public Boolean Solve(int leftToFill)
{
if (leftToFill == 0) //if there is no more spot to fill we're done
{
Console.WriteLine(this.ToString()); //prints the solution matrix
return true; //indicates that we found the solution
}
List<RowColumnValue> valuesFound = new List<RowColumnValue>();
List<RowColumnValue> possibleValuesFound;
for (int value = 1; value <= 9; value++) //we're looping over values 1..9
{
for (int square = 1; square <= 9; square++) // ...and squares 1..9
{
if (!DoesSquareContainValue(value, square))
{
possibleValuesFound = (
List<RowColumnValue>)FindMinSquare(value, square);
if ((valuesFound.Count == 0)
|| (valuesFound.Count > possibleValuesFound.Count))
valuesFound = possibleValuesFound; //first or so far best option
}
}
}
if (valuesFound.Count == 0)
return false; //we're stuck and need to advance on a higher level
for (int i = 0; i < valuesFound.Count; i++)
{ //we're setting a single value in the array
RowColumnValue rcv = valuesFound[i];
this[rcv.Row, rcv.Column] = rcv.Value;
leftToFill--;
if (Solve(leftToFill)) //recursion call on Solve()
{ //we've found the solution
return true;
}
else
{ //we need to undo the entry in the array
this[rcv.Row, rcv.Column] = 0;
}
leftToFill++;
}
return false;
}
As you can see it is pretty straight-forward and beyond the "FindMinSquare" method, that returns the possible value with the least options in a square the solution only has a few little helper methods, e.g. that check whether a specific value already exists in a row, column or square.
The Console application
This is what the Console application looks like:
The Downloads
You can download the whole
Solution as a zip file (only 16KB), or simply get the exe for the
Console app (rar file, only 4KB).
Of course I also did a bit of testing and for that I was happy to find some good Sudokus
at this Wikipedia page (along with some entertaining info on Sudoku algorithms). None of these very hard ones took more than a couple of seconds on my MacBook Pro - come Windows Server - come Virtual machine (with less than 1 processor assigned) ...so I guess, after all, there's still nothing better for achieving performance than "keeping it simple"!
Have fun!
p.s. My son was pretty impressed that I did outperform him and his teacher by factor 150,000 and 120,000 respectively ...his Sudoku only took 0.04 seconds to solve (of course, one day he'll come to me and I won't be able to keep up with his challenge ...he is ambitious and quite a sharp cookie! :-)