I like to write puzzle solvers, they refreshes my thinking. You probably learned in your algorithm classes that in these cases you can resort to backtracking. While backtracking is surely a solution in many theoretical cases, it can rarely be utilized in real life applications since the performance impact is huge.
Sudoku is one of those kind of puzzles which seem trivial to solve with a backtracking but lets think about it. There are 81 positions, each position can have 9 different values, generating through the space of potential solutions and validating each and every step could take ages.
Let’s instead of backtracking, track the possible values that each cell can have. This is how humans solve it and it will bring us very far in the solution. Here are the data structures i propose.
const int unitSize = 3;
const int lineSize = unitSize * unitSize;
const int puzzleSize = lineSize * lineSize;
bool _isConflict, _isFull;
int[] _values = new int[puzzleSize];
Dictionary<int, List<int>> _possibilities;
- _values: the value in each of the 81 positions, 0 if not set, [1-9] for final values.
- _possibilities: here we keep a list of possible values for each cell
- _isConflict: we will store here when we reach an invalid state
- _isFull: will mark when every cell on the puzzle has a value
- constants: we calculate these to make our life easier when doing operations on the puzzle. The truth is i lane later to try bigger sizes of puzzles like 16×16, 25×25 and even 100×100
I’ve created two main ways we can instantiate a puzzle. Here are the constructors.
protected SudokuPuzzle()
{
_possibilities = new Dictionary<int, List<int>>();
_values = new int[puzzleSize];
}
public SudokuPuzzle(string s) : this()
{
for (int i = 0; i < puzzleSize; i++)
{
_possibilities.Add(i, new List<int>{1,2,3,4,5,6,7,8,9});
}
for (int i = 0; i < puzzleSize; i++)
{
var val = s[i] - '0';
if (val > 0)
Set(i, val);
}
}
public SudokuPuzzle(SudokuPuzzle other) : this()
{
for (int i = 0; i < puzzleSize; i++)
{
_values[i] = other._values[i];
}
foreach(var entry in other._possibilities)
{
_possibilities.Add(entry.Key, entry.Value.ToList());
}
}
The first one constructs the puzzle from a long string which makes testing easier while the other is there for cloning. I’ll explain this a bit later. So how does setting a specific position look?
public void Set(int i, int val)
{
if (!_possibilities[i].Contains(val))
_isConflict = true;
_possibilities.Remove(i);
var x = i % lineSize;
var y = i / lineSize;
_values[i] = val;
RemoveFromLine(y, val);
RemoveFromColumn(x, val);
RemoveFromSector(x, y, val);
if (_possibilities.Count == 0)
_isFull = true;
}
private void RemoveFromLine(int a, int val)
{
for (int i = 0; i < lineSize; i++)
{
RemovePossibility(a * lineSize + i, val);
}
}
private void RemoveFromColumn(int a, int val)
{
for (int i = 0; i < lineSize; i++)
{
RemovePossibility(i * lineSize + a, val);
}
}
private void RemoveFromSector(int cx, int cy, int val)
{
var x = (cx / unitSize) * unitSize;
var y = (cy / unitSize) * unitSize;
for (int i = 0; i < unitSize; i++)
{
for (int j = 0; j < unitSize; j++)
{
RemovePossibility((y + j) * lineSize + (x + i), val);
}
}
}
private void RemovePossibility(int coord, int val)
{
if (_possibilities.ContainsKey(coord))
{
_possibilities[coord].Remove(val);
}
}
So this needs a bit of explaining. Every time we decide to set a cell value, we remove the possibility of having that value again for every cell on the same line, column and sector. I think that part of the code if self explaining. To simplify execution i remove the list of possibilities for that cell too. Now here we see we can move into two different states. The first “if” from the “Set” method takes care of the possibility that we already removed that value from that line, which can only happen if the input values contained a mistake or the Set function was called outside of the solving logic. Practically there could be a user who entered something by mistake.
Now the moment that we’ve all been waiting for! The solving logic.
public int[] Solve()
{
while (!_isConflict && !_isFull)
{
var p = _possibilities
.FirstOrDefault(x => x.Value.Count == 1);
if (p.Value != null) // if not default key value pair
{
Set(p.Key, p.Value.First());
}
else
{
p = _possibilities.OrderBy(x => x.Value.Count).First();
foreach (var entry in p.Value)
{
var clone = new SudokuPuzzle(this);
clone.Set(p.Key, entry);
var result = clone.Solve();
if (result != null) return result;
}
_isConflict = true;
}
}
if (_isConflict)
return null;
return _values;
}
So the first thing we do is we fill in each cell if there is only one possibility left. Doing that we reduce the possibilities in other cells so we do this in a loop. When there is no such cell left we are either finished or this is a more complex puzzle. With there remainder we chose the cell with the least amount of possibilities that and we try to solve each sub version of the puzzle. Each sub version could either lead us to a solution or run into a conclusion. The fun part of it is that the very hardest puzzles run into this situation from the get go and this level of recursion happens multiple times. If you’ve seen Inception you know what i’m talking about already.
------------------------- -------------------------
| | | 8 1 | | 3 7 5 | 6 9 4 | 8 2 1 |
| 6 4 | | 9 | | 1 6 4 | 2 8 7 | 9 3 5 |
| | 3 | 6 | | 9 2 8 | 1 5 3 | 7 4 6 |
------------------------- -------------------------
| 3 9 | 4 | 2 | | 7 3 9 | 5 4 1 | 2 6 8 |
| 5 | 2 | | --> | 5 8 6 | 9 7 2 | 4 1 3 |
| 1 | 3 | 7 | | 4 1 2 | 8 3 6 | 5 7 9 |
------------------------- -------------------------
| | 3 6 | 2 | | 8 4 7 | 3 6 5 | 1 9 2 |
| 9 | | 5 | | 2 9 3 | 7 1 8 | 6 5 4 |
| 6 5 1 | | 7 | | 6 5 1 | 4 2 9 | 3 8 7 |
------------------------- -------------------------
Here is some nostalgia console output for you! I hope you enjoyed it, see ya!