diff options
| -rw-r--r-- | src/main.zig | 38 |
1 files changed, 18 insertions, 20 deletions
diff --git a/src/main.zig b/src/main.zig index 88d5701..5a8db6a 100644 --- a/src/main.zig +++ b/src/main.zig @@ -52,7 +52,7 @@ const SudokuSolver = struct { fn solve(self: *SudokuSolver) bool { if (self.isSolved()) return true; - var most_constrained_cell: ?PossibleMoves = null; + var possible_moves = std.BoundedArray(PossibleMoves, 9 * 9).init(0) catch unreachable; for (self.rows, 0..) |r, row| { for (@as([9]u8, r), 0..) |cell, col| { if (cell == 0) { @@ -67,37 +67,35 @@ const SudokuSolver = struct { 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, - }; - }, + else => possible_moves.appendAssumeCapacity(.{ + .row = row, + .col = col, + .moves = current_possible_moves, + }), } } } } - if (most_constrained_cell == null) return false; + if (possible_moves.len == 0) return false; - if (most_constrained_cell) |pm| { - var moves_iter = pm.moves.iterator(.{}); + std.sort.heap(PossibleMoves, possible_moves.slice(), {}, possibleMovesLessThan); - while (moves_iter.next()) |current_move| { - const backup = self.*; + const pm = possible_moves.get(0); + var moves_iter = pm.moves.iterator(.{}); - self.setCell(pm.row, pm.col, @intCast(current_move + 1)); + while (moves_iter.next()) |current_move| { + const backup = self.*; - if (self.solve()) { - return true; - } + self.setCell(pm.row, pm.col, @intCast(current_move + 1)); - self.* = backup; + if (self.solve()) { + return true; } + + self.* = backup; } + return false; } |