1 files changed, 63 insertions, 22 deletions

diff --git a/src/main.zig b/src/main.zig
index 72be820..88d5701 100644
--- a/src/main.zig
+++ b/src/main.zig
@@ -13,8 +13,8 @@ const SudokuSolver = struct {
             .cols = undefined,
             .boxes = undefined,
         };
-        for (0..9) |row| {
-            for (0..9) |col| {
+        for (board, 0..) |r, row| {
+            for (r, 0..) |_, col| {
                 const cell = board[row][col];
                 if (cell > 9) return error.InvalidValue;
                 res.setCell(row, col, cell);
@@ -39,26 +39,66 @@ const SudokuSolver = struct {
         return cell_guesses;
     }
 
-    fn solveEasyBoard(self: *SudokuSolver) !void {
-        while (!self.isSolved()) {
-            var moved_this_iteration = false;
-            for (self.rows, 0..) |row, row_i| {
-                for (@as([9]u8, row), 0..) |cell, col_i| {
-                    if (cell == 0) {
-                        const possible_moves = self.possibleMovesForCell(row_i, col_i);
-                        if (possible_moves.count() == 1) {
+    const PossibleMoves = struct {
+        row: usize,
+        col: usize,
+        moves: std.StaticBitSet(9),
+    };
+
+    fn possibleMovesLessThan(_: void, lhs: PossibleMoves, rhs: PossibleMoves) bool {
+        return lhs.moves.count() < rhs.moves.count();
+    }
+
+    fn solve(self: *SudokuSolver) bool {
+        if (self.isSolved()) return true;
+
+        var most_constrained_cell: ?PossibleMoves = null;
+        for (self.rows, 0..) |r, row| {
+            for (@as([9]u8, r), 0..) |cell, col| {
+                if (cell == 0) {
+                    const current_possible_moves = self.possibleMovesForCell(row, col);
+                    switch (current_possible_moves.count()) {
+                        1 => {
                             self.setCell(
-                                row_i,
-                                col_i,
-                                @intCast(possible_moves.findFirstSet().? + 1),
+                                row,
+                                col,
+                                @intCast(current_possible_moves.findFirstSet().? + 1),
                             );
-                            moved_this_iteration = true;
-                        }
+                            return self.solve();
+                        },
+                        0 => return false,
+                        else => if (most_constrained_cell == null or
+                            most_constrained_cell.?.moves.count() > current_possible_moves.count())
+                        {
+                            most_constrained_cell = .{
+                                .row = row,
+                                .col = col,
+                                .moves = current_possible_moves,
+                            };
+                        },
                     }
                 }
             }
-            if (!moved_this_iteration) return error.UnableToSolve;
         }
+
+        if (most_constrained_cell == null) return false;
+
+        if (most_constrained_cell) |pm| {
+            var moves_iter = pm.moves.iterator(.{});
+
+            while (moves_iter.next()) |current_move| {
+                const backup = self.*;
+
+                self.setCell(pm.row, pm.col, @intCast(current_move + 1));
+
+                if (self.solve()) {
+                    return true;
+                }
+
+                self.* = backup;
+            }
+        }
+        return false;
     }
 
     fn isSolved(self: SudokuSolver) bool {
@@ -115,13 +155,14 @@ pub fn main() !void {
 
     // Unreachable because we validate while parsing.
     var solver = SudokuSolver.init(board) catch unreachable;
+    try solver.display(stdout);
+    std.debug.print("\n", .{});
 
-    solver.solveEasyBoard() catch |err| {
+    if (solver.solve()) {
+        try solver.display(stdout);
+    } else {
         std.debug.print("Unable to solve board\n", .{});
-        return err;
-    };
-
-    try solver.display(stdout);
+    }
 }
 
 const std = @import("std");
@@ -197,6 +238,6 @@ test "Solve easy board" {
     try solver.display(stderr);
     std.debug.print("output:\n", .{});
 
-    try solver.solveEasyBoard();
+    _ = solver.solve();
     try solver.display(stderr);
 }