diff options
-rw-r--r-- | src/main.zig | 85 |
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); } |