diff options
| -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; |