summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorRobby Zambito <contact@robbyzambito.me>2025-05-14 08:00:50 -0400
committerRobby Zambito <contact@robbyzambito.me>2025-05-19 08:16:10 -0400
commit521a2f3c707522b575e9fdb497469f7806aefb45 (patch)
treedacc45623b5255e67481c3e2e9ecc5468e1a6499
parent05cb407e0e0a43e4d9595697051a37e8894df782 (diff)
Try saving only the minimum
still only half as fast as saving the list?
-rw-r--r--src/main.zig39
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;