summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
-rw-r--r--src/main.zig38
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;
}