diff options
author | Robby Zambito <contact@robbyzambito.me> | 2025-05-14 08:00:50 -0400 |
---|---|---|
committer | Robby Zambito <contact@robbyzambito.me> | 2025-05-19 08:16:10 -0400 |
commit | 521a2f3c707522b575e9fdb497469f7806aefb45 (patch) | |
tree | dacc45623b5255e67481c3e2e9ecc5468e1a6499 | |
parent | 05cb407e0e0a43e4d9595697051a37e8894df782 (diff) |
Try saving only the minimum
still only half as fast as saving the list?
-rw-r--r-- | src/main.zig | 39 |
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; |