summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorRobby Zambito <contact@robbyzambito.me>2025-05-13 18:32:15 -0400
committerRobby Zambito <contact@robbyzambito.me>2025-05-19 08:16:10 -0400
commitf37041440f9fe9823f61e29834f676cd48789aae (patch)
tree984a01f20ce0d32fdf577ce40a303e03fcfa262e
parente9c293f2572a92596d54d2fec16d6aec9c8af0bf (diff)
Just storing min value
-rw-r--r--src/main.zig85
1 files changed, 63 insertions, 22 deletions
diff --git a/src/main.zig b/src/main.zig
index 72be820..88d5701 100644
--- a/src/main.zig
+++ b/src/main.zig
@@ -13,8 +13,8 @@ const SudokuSolver = struct {
.cols = undefined,
.boxes = undefined,
};
- for (0..9) |row| {
- for (0..9) |col| {
+ for (board, 0..) |r, row| {
+ for (r, 0..) |_, col| {
const cell = board[row][col];
if (cell > 9) return error.InvalidValue;
res.setCell(row, col, cell);
@@ -39,26 +39,66 @@ const SudokuSolver = struct {
return cell_guesses;
}
- fn solveEasyBoard(self: *SudokuSolver) !void {
- while (!self.isSolved()) {
- var moved_this_iteration = false;
- for (self.rows, 0..) |row, row_i| {
- for (@as([9]u8, row), 0..) |cell, col_i| {
- if (cell == 0) {
- const possible_moves = self.possibleMovesForCell(row_i, col_i);
- if (possible_moves.count() == 1) {
+ const PossibleMoves = struct {
+ row: usize,
+ col: usize,
+ moves: std.StaticBitSet(9),
+ };
+
+ fn possibleMovesLessThan(_: void, lhs: PossibleMoves, rhs: PossibleMoves) bool {
+ return lhs.moves.count() < rhs.moves.count();
+ }
+
+ fn solve(self: *SudokuSolver) bool {
+ if (self.isSolved()) return true;
+
+ var most_constrained_cell: ?PossibleMoves = null;
+ for (self.rows, 0..) |r, row| {
+ for (@as([9]u8, r), 0..) |cell, col| {
+ if (cell == 0) {
+ const current_possible_moves = self.possibleMovesForCell(row, col);
+ switch (current_possible_moves.count()) {
+ 1 => {
self.setCell(
- row_i,
- col_i,
- @intCast(possible_moves.findFirstSet().? + 1),
+ row,
+ col,
+ @intCast(current_possible_moves.findFirstSet().? + 1),
);
- moved_this_iteration = true;
- }
+ 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,
+ };
+ },
}
}
}
- if (!moved_this_iteration) return error.UnableToSolve;
}
+
+ if (most_constrained_cell == null) return false;
+
+ if (most_constrained_cell) |pm| {
+ var moves_iter = pm.moves.iterator(.{});
+
+ while (moves_iter.next()) |current_move| {
+ const backup = self.*;
+
+ self.setCell(pm.row, pm.col, @intCast(current_move + 1));
+
+ if (self.solve()) {
+ return true;
+ }
+
+ self.* = backup;
+ }
+ }
+ return false;
}
fn isSolved(self: SudokuSolver) bool {
@@ -115,13 +155,14 @@ pub fn main() !void {
// Unreachable because we validate while parsing.
var solver = SudokuSolver.init(board) catch unreachable;
+ try solver.display(stdout);
+ std.debug.print("\n", .{});
- solver.solveEasyBoard() catch |err| {
+ if (solver.solve()) {
+ try solver.display(stdout);
+ } else {
std.debug.print("Unable to solve board\n", .{});
- return err;
- };
-
- try solver.display(stdout);
+ }
}
const std = @import("std");
@@ -197,6 +238,6 @@ test "Solve easy board" {
try solver.display(stderr);
std.debug.print("output:\n", .{});
- try solver.solveEasyBoard();
+ _ = solver.solve();
try solver.display(stderr);
}