summaryrefslogtreecommitdiff
path: root/src/main.zig
diff options
context:
space:
mode:
Diffstat (limited to 'src/main.zig')
-rw-r--r--src/main.zig218
1 files changed, 187 insertions, 31 deletions
diff --git a/src/main.zig b/src/main.zig
index 3301b7e..72be820 100644
--- a/src/main.zig
+++ b/src/main.zig
@@ -1,46 +1,202 @@
-//! By convention, main.zig is where your main function lives in the case that
-//! you are building an executable. If you are making a library, the convention
-//! is to delete this file and start with root.zig instead.
+const SudokuSolver = struct {
+ const countEql = std.simd.countElementsWithValue;
+ const join = std.simd.join;
+ // Each cell exists in memory three times.
+ // This makes it easy to compare a guess against all relevant cells simultaneously.
+ rows: [9]@Vector(9, u8),
+ cols: [9]@Vector(9, u8),
+ boxes: [9]@Vector(9, u8),
+
+ fn init(board: [9][9]u8) !SudokuSolver {
+ var res: SudokuSolver = .{
+ .rows = undefined,
+ .cols = undefined,
+ .boxes = undefined,
+ };
+ for (0..9) |row| {
+ for (0..9) |col| {
+ const cell = board[row][col];
+ if (cell > 9) return error.InvalidValue;
+ res.setCell(row, col, cell);
+ }
+ }
+
+ return res;
+ }
+
+ fn possibleMovesForCell(self: SudokuSolver, row: usize, col: usize) std.StaticBitSet(9) {
+ var cell_guesses: std.StaticBitSet(9) = .initEmpty();
+ for (1..10) |n| {
+ // A number is a possible move iff it does not already exist in the current row, col, or box.
+ if (countEql(
+ join(self.rows[row], join(self.cols[col], self.boxes[boxOf(row, col)])),
+ @intCast(n),
+ ) == 0) {
+ cell_guesses.set(n - 1);
+ }
+ }
+
+ 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) {
+ self.setCell(
+ row_i,
+ col_i,
+ @intCast(possible_moves.findFirstSet().? + 1),
+ );
+ moved_this_iteration = true;
+ }
+ }
+ }
+ }
+ if (!moved_this_iteration) return error.UnableToSolve;
+ }
+ }
+
+ fn isSolved(self: SudokuSolver) bool {
+ for (self.rows) |row| {
+ if (countEql(row, 0) > 0) return false;
+ }
+ return true;
+ }
+
+ fn setCell(self: *SudokuSolver, row: usize, col: usize, value: u8) void {
+ self.rows[row][col] = value;
+ self.cols[col][row] = value;
+ self.boxes[boxOf(row, col)][cellOfInBox(row, col)] = value;
+ }
+
+ fn boxOf(row: usize, col: usize) usize {
+ // Due to integer division, this is not the same as just adding row.
+ return (row / 3) * 3 + col / 3;
+ }
+
+ fn cellOfInBox(row: usize, col: usize) usize {
+ return (row % 3) * 3 + col % 3;
+ }
+
+ fn display(self: SudokuSolver, writer: std.io.AnyWriter) !void {
+ for (self.rows, 0..) |row, i| {
+ // Can't loop over row directly?
+ for (@as([9]u8, row), 0..) |cell, j| {
+ try writer.print("{d} ", .{cell});
+ if (j % 3 == 2 and j < 8) {
+ try writer.print("| ", .{});
+ }
+ }
+ try writer.print("\n", .{});
+ if (i % 3 == 2 and i < 8) {
+ try writer.print("{s}\n", .{"-" ** 21});
+ }
+ }
+ }
+};
pub fn main() !void {
- // Prints to stderr (it's a shortcut based on `std.io.getStdErr()`)
- std.debug.print("All your {s} are belong to us.\n", .{"codebase"});
+ var board: [9][9]u8 = undefined;
- // stdout is for the actual output of your application, for example if you
- // are implementing gzip, then only the compressed bytes should be sent to
- // stdout, not any debugging messages.
- const stdout_file = std.io.getStdOut().writer();
- var bw = std.io.bufferedWriter(stdout_file);
- const stdout = bw.writer();
+ const stdout = std.io.getStdOut().writer().any();
+ const stdin = std.io.getStdIn().reader().any();
- try stdout.print("Run `zig build test` to run the tests.\n", .{});
+ for (0..9) |row| {
+ for (0..9) |col| {
+ const byte = try stdin.readByte();
+ board[row][col] = try std.fmt.charToDigit(byte, 10);
+ }
+ }
+
+ // Unreachable because we validate while parsing.
+ var solver = SudokuSolver.init(board) catch unreachable;
+
+ solver.solveEasyBoard() catch |err| {
+ std.debug.print("Unable to solve board\n", .{});
+ return err;
+ };
- try bw.flush(); // Don't forget to flush!
+ try solver.display(stdout);
}
-test "simple test" {
- var list = std.ArrayList(i32).init(std.testing.allocator);
- defer list.deinit(); // Try commenting this out and see if zig detects the memory leak!
- try list.append(42);
- try std.testing.expectEqual(@as(i32, 42), list.pop());
+const std = @import("std");
+
+test "boxOf" {
+ const expectEql = std.testing.expectEqual;
+ try expectEql(0, SudokuSolver.boxOf(0, 0));
+ try expectEql(1, SudokuSolver.boxOf(0, 3));
+ try expectEql(2, SudokuSolver.boxOf(2, 8));
+ try expectEql(4, SudokuSolver.boxOf(4, 5));
}
-test "use other module" {
- try std.testing.expectEqual(@as(i32, 150), lib.add(100, 50));
+test "cellOfInBox" {
+ const expectEql = std.testing.expectEqual;
+ try expectEql(0, SudokuSolver.cellOfInBox(0, 0));
+ try expectEql(1, SudokuSolver.cellOfInBox(0, 1));
+ try expectEql(2, SudokuSolver.cellOfInBox(0, 2));
+ try expectEql(3, SudokuSolver.cellOfInBox(1, 0));
+
+ try expectEql(0, SudokuSolver.cellOfInBox(3, 3));
+ try expectEql(0, SudokuSolver.cellOfInBox(6, 6));
}
-test "fuzz example" {
- const Context = struct {
- fn testOne(context: @This(), input: []const u8) anyerror!void {
- _ = context;
- // Try passing `--fuzz` to `zig build test` and see if it manages to fail this test case!
- try std.testing.expect(!std.mem.eql(u8, "canyoufindme", input));
+test "get available moves for easy board" {
+ // Taken from https://ziggit.dev/t/i-wrote-a-simple-sudoku-solver/9924/14?u=zambyte
+ if (false) {
+ const board: [9][9]u8 = .{
+ .{ 4, 0, 3, 5, 0, 0, 0, 9, 6 },
+ .{ 5, 0, 7, 8, 0, 0, 3, 0, 0 },
+ .{ 0, 8, 0, 0, 0, 0, 0, 5, 4 },
+ .{ 0, 0, 0, 7, 0, 6, 0, 2, 3 },
+ .{ 0, 0, 0, 0, 2, 0, 0, 0, 0 },
+ .{ 9, 5, 0, 3, 0, 4, 0, 0, 0 },
+ .{ 7, 9, 0, 0, 0, 0, 0, 6, 0 },
+ .{ 0, 0, 4, 0, 0, 7, 5, 0, 8 },
+ .{ 8, 3, 0, 0, 0, 5, 4, 0, 9 },
+ };
+
+ const solver: SudokuSolver = SudokuSolver.init(.{ .board = board }) catch unreachable;
+
+ for (board, 0..) |row, row_i| {
+ for (row, 0..) |cell, col_i| {
+ if (cell == 0) {
+ const possible_moves = solver.possibleMovesForCell(row_i, col_i);
+ if (possible_moves.count() == 1) {
+ std.debug.print("row: {}, col: {}, value: {}\n", .{ row_i, col_i, possible_moves.findFirstSet().? });
+ }
+ }
+ }
}
- };
- try std.testing.fuzz(Context{}, Context.testOne, .{});
+ }
+ return error.SkipZigTest;
}
-const std = @import("std");
+test "Solve easy board" {
+ // Taken from https://ziggit.dev/t/i-wrote-a-simple-sudoku-solver/9924/14?u=zambyte
+ const board: [9][9]u8 = .{
+ .{ 4, 0, 3, 5, 0, 0, 0, 9, 6 },
+ .{ 5, 0, 7, 8, 0, 0, 3, 0, 0 },
+ .{ 0, 8, 0, 0, 0, 0, 0, 5, 4 },
+ .{ 0, 0, 0, 7, 0, 6, 0, 2, 3 },
+ .{ 0, 0, 0, 0, 2, 0, 0, 0, 0 },
+ .{ 9, 5, 0, 3, 0, 4, 0, 0, 0 },
+ .{ 7, 9, 0, 0, 0, 0, 0, 6, 0 },
+ .{ 0, 0, 4, 0, 0, 7, 5, 0, 8 },
+ .{ 8, 3, 0, 0, 0, 5, 4, 0, 9 },
+ };
-/// This imports the separate module containing `root.zig`. Take a look in `build.zig` for details.
-const lib = @import("sudoku_solver_zig_lib");
+ var solver: SudokuSolver = SudokuSolver.init(board) catch unreachable;
+
+ const stderr = std.io.getStdErr().writer().any();
+ std.debug.print("input:\n", .{});
+ try solver.display(stderr);
+ std.debug.print("output:\n", .{});
+
+ try solver.solveEasyBoard();
+ try solver.display(stderr);
+}
generated by cgit (git 2.34.1) at 2025-06-09 21:45:06 +0000