Performing Miracles with C#

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

Simple rules, stunning solutions

There are many types of Sudoku, but almost all forms of sudoku follow the same process;

1) Define a play space. Usually a 9×9 grid of cells, often made up of 9 groups of 3×3 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.

VALIDATORS

Cell Contains Number

Does this cell already contain a number? If so, it’s invalid for any value.

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 (3×3 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.

public class WouldInvalidateAnotherGroup : ValidationStep {
public override void Validate(Vector2Int cell, int value, Model model) {
Vector2Int groupID = Model.GroupIDFromCell(cell);
return;
}

if (model.TryGetKnownValue(cell, out int cellValue)) {
return;
}

List<ValidationStep> validators = new List<ValidationStep>();

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.

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