Solve.
Or don't, as the case may be.
I was recently recommended a video on YouTube, of a man solving a Miracle Sudoku. I have never shown interest in these kinds of puzzles before, yet I found myself drawn to the elegant beauty of such a simple set of rules resulting in a long and winding chain of logic, eventually reaching a single possible answer.
"I could do that", my monkey brain said, so off I went.
The YouTuber solved the puzzle in less than 20 minutes. It took me an hour and a half.
"Okay, well, I bet I could write some code to solve this in less than that time".
For the second (though not the last) time that day, my monkey brain was wrong.
Sudoku
Simple rules, stunning solution.
There are many types of Sudoku, but almost all forms of sudoku follow the same process;
1) Define a play space. Usually a 9x9 grid of cells, often made up of 9 groups of3x3 cells.
2) Define a set of rules which players can apply to the space in order to resolve cell values, until all cells have been filled and a "solution" is found.
In puzzles with only a single solution, it is common to progress by applying the rules and noting which cells have been invalidated (or made possible) by their application.
Usually, when all rules are applied, a cell value will reveal itself, which allows rules to be applied in a new way, revealing another cell, and so on.
Writing the solver
Thoughts
Approaching this problem, a few important concepts came to mind.
1) Each rule should be a distinct "block" of code, which could be tested in isolation, removed or changed. A unit, if you will.
2) The solution should not be overly constrained to this specific type of Sudoku, but should allow a modular approach where other rules could be added or removed. Where possible, allow the model to define it's own limits (Groups, Cell count, Adjacency etc).
3) Since "virtual" cell values were likely to be needed (Like drawing a number in pencil, checking its right, then erasing if it's not),the "model" (A representation of the puzzles state) should be something that can be copied and changed easily.
01
For every potential cell value. 1 - 9
02
For every cell in the model. (x, y)
03
For every validator in puzzle type.
04
Validate & Check for solutions.
05
Loop until complete (Or failed).
Validators
Cell Contains Number
Does this cell already contain a number? If so, it's invalid for any value.
Adjacent Consecutive
Does the cell above, right, left, or below contain a number exactly 1 higher, or 1 lower than value? If so, invalidate.
Sudoku
Look at all cells in this row or column. If any contain a known value matching "value", this cell is invalid.
Group Contains Match
Look at all cells in this group (3x3 on a standard sudoku). If any known values match "value", this cell is invalid.
Kings Move
Loop around this cell. If any cells known value matches "value", this cell is invalid.
Knights Move
Elegantly (Or in my case, brute forcefully) check the 8 knight moves around this cell. If any known value matches "value", this cell is invalid.
We use C# objects, and pass the full validation context (In this case, the Model) to each validator sequentially.
By passing in a model, rather than accessing one statically, we will be able to make a "Copy" of a Model, and validate against the copy, without modifying the "true" puzzle model. Validators do not know whether the Model they are passed is the "real" model, or a copier temporary one.
public class CellContainsNumber : ValidationStep {
public override void Validate(Vector2Int cell, int value, Model model) {
if (!model.TryGetKnownValue(cell, out int cellValue)) return;
if (cellValue != value) {
model.RegisterInvalidValue(value, cell);
}
}
}
public class AdjacentConsecutive : ValidationStep {
public override void Validate(Vector2Int cell, int value, Model model) {
bool IsConsective(int a, int b) {
if (a == b - 1 || a == b + 1) return true;
return false;
}
if (model.TryGetKnownValue(cell + Solver.Up, out int testCellValue)) {
if (IsConsective(value, testCellValue)) {
model.RegisterInvalidValue(value, cell);
return;
}
}
if (model.TryGetKnownValue(cell + Solver.Right, out testCellValue)) {
if (IsConsective(value, testCellValue)) {
model.RegisterInvalidValue(value, cell);
return;
}
}
if (model.TryGetKnownValue(cell + Solver.Down, out testCellValue)) {
if (IsConsective(value, testCellValue)) {
model.RegisterInvalidValue(value, cell);
return;
}
}
if (model.TryGetKnownValue(cell + Solver.Left, out testCellValue)) {
if (IsConsective(value, testCellValue)) {
model.RegisterInvalidValue(value, cell);
}
}
}
}
public class SudokuMatches : ValidationStep {
public override void Validate(Vector2Int cell, int value, Model model) {
int testCellValue = 0;
for (int x = 0; x < Model.Width; x++) {
if (model.TryGetKnownValue(new Vector2Int(x, cell.y), out testCellValue)) {
if (testCellValue == value) {
model.RegisterInvalidValue(value, cell);
return;
}
}
}
for (int y = 0; y < Model.Height; y++) {
if (model.TryGetKnownValue(new Vector2Int(cell.x, y), out testCellValue)) {
if (testCellValue == value) {
model.RegisterInvalidValue(value, cell);
return;
}
}
}
}
}The Clever Ones
Only cell in row or column
Look at all the potential cells in your row. If all of them are in this group, then all other cells in this group are invalid. Do the same for columns.
Would Invalidate Another Group
By applying all our rules to the space, we can invalidate lots of cells. That's great, and gets us closer to the solution.
The hard bit appears when the following case arises: In order to invalidate a cell, we need to "pretend" to put a value in that cell, then check whether we have invalidated any other values.
For this validator, we make a perfect copy of the Model. We then register a known value in the cell that's being tested. Finally, we look through all values 1-9 and check all their potential cells to see if they're still valid.
If any group and value is fully invalidated, then we know that this cell cannot contain the simulated value.
1) Define a play space. Usually a 9x9 grid of cells, often made up of 9 groups of3x3 cells.
2) Define a set of rules which players can apply to the space in order to resolve cell values, until all cells have been filled and a "solution" is found.
In puzzles with only a single solution, it is common to progress by applying the rules and noting which cells have been invalidated (or made possible) by their application.
Usually, when all rules are applied, a cell value will reveal itself, which allows rules to be applied in a new way, revealing another cell, and so on.
public class WouldInvalidateAnotherGroup : ValidationStep {
public override void Validate(Vector2Int cell, int value, Model model) {
Vector2Int groupID = Model.GroupIDFromCell(cell);
if (model.GroupHasKnownValue(groupID, value)) {
return;
}
if (model.TryGetKnownValue(cell, out int cellValue)) {
return;
}
List<ValidationStep> validators = new List<ValidationStep>();
validators.Add(new SudokuMatches());
validators.Add(new KingsMoveMatches());
validators.Add(new KnightsMoveMatches());
validators.Add(new AdjacentConsecutive());
validators.Add(new CellContainsNumber());
Model tempModel = Model.CopyTemp(model);
tempModel.RegisterKnownCell(cell, value);
Solver.ActiveModel = tempModel;
for (int j = -1; j <= 1; j++) {
int index = value + j;
if (index < 1 || index > 9) continue;
Solver.ActiveIndex = index;
// Get all the cells that need checking again.
HashSet<Vector2Int> potentialCells = tempModel.GetPotentialCells(index);
foreach (Vector2Int potentialCell in potentialCells) {
Solver.ActiveCell = potentialCell;
// Validate that the cell can still contain their potential value.
foreach (ValidationStep validator in validators) {
validator.Validate(potentialCell, index, tempModel);
}
}
if (tempModel.HasFullyInvalidatedGroup(out Vector2Int invalidatedGroupID, out int invalidatedGroupValue)) {
model.RegisterInvalidValue(value, cell);
return;
}
}
}
}What's Next?
What else can we solve?
A few things are now possible.
01
Since the core of the solver (Checking against validators, checking against simulated values, finding guarenteed cell values) is fairly general, the same code could be used to solve other types of Sudoku puzzle.
02
Since this solving approach only works for puzzles with a single solution, by running the solver on random input patterns of a few numbers, then seeing if a valid solution can be found, we can generate brand new miracle sudoku's to be solved.
03
If the rules were to be extracted into a user friendly tool, it would be possible to release a solver which could be tweaked by users to solve puzzles which we've never even seen before!
Bonus
Puzzles to solve.
By testing different input puzzles on the solver, I was able to find a few new puzzles which keen players can have a go at! I can tell from the way the solver ran (things like the iteration count, but no spoilers here!) that the three here increase in difficulty (6,5) - (1,2) - (7,8).
Conclusion
Thanks for reading.
If you've made it this far, then thank you. I hope no puzzlers take offence at the idea of a computer solving the puzzle. The joy you feel when solving your craft is the same joy I feel when designing and implementing mine.
Happy puzzling!