Try saving only the minimum

still only half as fast as saving the list?

1 files changed, 21 insertions, 18 deletions

diff --git a/src/main.zig b/src/main.zig
index 5a8db6a..265425a 100644
--- a/src/main.zig
+++ b/src/main.zig
@@ -52,7 +52,12 @@ const SudokuSolver = struct {
     fn solve(self: *SudokuSolver) bool {
         if (self.isSolved()) return true;
 
-        var possible_moves = std.BoundedArray(PossibleMoves, 9 * 9).init(0) catch unreachable;
+        // Variables to track the most constrained cell
+        var min_row: usize = 0;
+        var min_col: usize = 0;
+        var min_moves: ?std.StaticBitSet(9) = null;
+        var min_count: usize = 10; // More than maximum possible (9)
+
         for (self.rows, 0..) |r, row| {
             for (@as([9]u8, r), 0..) |cell, col| {
                 if (cell == 0) {
@@ -67,33 +72,31 @@ const SudokuSolver = struct {
                             return self.solve();
                         },
                         0 => return false,
-                        else => possible_moves.appendAssumeCapacity(.{
-                            .row = row,
-                            .col = col,
-                            .moves = current_possible_moves,
-                        }),
+                        else => |c| if (c < min_count) {
+                            min_row = row;
+                            min_col = col;
+                            min_moves = current_possible_moves;
+                            min_count = c;
+                        },
                     }
                 }
             }
         }
 
-        if (possible_moves.len == 0) return false;
-
-        std.sort.heap(PossibleMoves, possible_moves.slice(), {}, possibleMovesLessThan);
+        if (min_moves) |pm| {
+            var moves_iter = pm.iterator(.{});
 
-        const pm = possible_moves.get(0);
-        var moves_iter = pm.moves.iterator(.{});
+            while (moves_iter.next()) |current_move| {
+                const backup = self.*;
 
-        while (moves_iter.next()) |current_move| {
-            const backup = self.*;
+                self.setCell(min_row, min_col, @intCast(current_move + 1));
 
-            self.setCell(pm.row, pm.col, @intCast(current_move + 1));
+                if (self.solve()) {
+                    return true;
+                }
 
-            if (self.solve()) {
-                return true;
+                self.* = backup;
             }
-
-            self.* = backup;
         }
 
         return false;