Basic solver that uses simd for simple puzzles

this assumes there is at least one cell with only one valid answer at any given step.

4 files changed, 189 insertions, 85 deletions

diff --git a/.gitignore b/.gitignore
new file mode 100644
index 0000000..d8c8979
--- /dev/null
+++ b/.gitignore
@@ -0,0 +1,2 @@
+.zig-cache
+zig-out
diff --git a/build.zig b/build.zig
index e9ba462..da5095a 100644
--- a/build.zig
+++ b/build.zig
@@ -15,19 +15,6 @@ pub fn build(b: *std.Build) void {
     // set a preferred release mode, allowing the user to decide how to optimize.
     const optimize = b.standardOptimizeOption(.{});
 
-    // This creates a "module", which represents a collection of source files alongside
-    // some compilation options, such as optimization mode and linked system libraries.
-    // Every executable or library we compile will be based on one or more modules.
-    const lib_mod = b.createModule(.{
-        // `root_source_file` is the Zig "entry point" of the module. If a module
-        // only contains e.g. external object files, you can make this `null`.
-        // In this case the main source file is merely a path, however, in more
-        // complicated build scripts, this could be a generated file.
-        .root_source_file = b.path("src/root.zig"),
-        .target = target,
-        .optimize = optimize,
-    });
-
     // We will also create a module for our other entry point, 'main.zig'.
     const exe_mod = b.createModule(.{
         // `root_source_file` is the Zig "entry point" of the module. If a module
@@ -39,25 +26,6 @@ pub fn build(b: *std.Build) void {
         .optimize = optimize,
     });
 
-    // Modules can depend on one another using the `std.Build.Module.addImport` function.
-    // This is what allows Zig source code to use `@import("foo")` where 'foo' is not a
-    // file path. In this case, we set up `exe_mod` to import `lib_mod`.
-    exe_mod.addImport("sudoku_solver_zig_lib", lib_mod);
-
-    // Now, we will create a static library based on the module we created above.
-    // This creates a `std.Build.Step.Compile`, which is the build step responsible
-    // for actually invoking the compiler.
-    const lib = b.addLibrary(.{
-        .linkage = .static,
-        .name = "sudoku_solver_zig",
-        .root_module = lib_mod,
-    });
-
-    // This declares intent for the library to be installed into the standard
-    // location when the user invokes the "install" step (the default step when
-    // running `zig build`).
-    b.installArtifact(lib);
-
     // This creates another `std.Build.Step.Compile`, but this one builds an executable
     // rather than a static library.
     const exe = b.addExecutable(.{
@@ -93,14 +61,6 @@ pub fn build(b: *std.Build) void {
     const run_step = b.step("run", "Run the app");
     run_step.dependOn(&run_cmd.step);
 
-    // Creates a step for unit testing. This only builds the test executable
-    // but does not run it.
-    const lib_unit_tests = b.addTest(.{
-        .root_module = lib_mod,
-    });
-
-    const run_lib_unit_tests = b.addRunArtifact(lib_unit_tests);
-
     const exe_unit_tests = b.addTest(.{
         .root_module = exe_mod,
     });
@@ -111,6 +71,5 @@ pub fn build(b: *std.Build) void {
     // the `zig build --help` menu, providing a way for the user to request
     // running the unit tests.
     const test_step = b.step("test", "Run unit tests");
-    test_step.dependOn(&run_lib_unit_tests.step);
     test_step.dependOn(&run_exe_unit_tests.step);
 }
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);
+}
diff --git a/src/root.zig b/src/root.zig
deleted file mode 100644
index 27d2be8..0000000
--- a/src/root.zig
+++ /dev/null
@@ -1,13 +0,0 @@
-//! By convention, root.zig is the root source file when making a library. If
-//! you are making an executable, the convention is to delete this file and
-//! start with main.zig instead.
-const std = @import("std");
-const testing = std.testing;
-
-pub export fn add(a: i32, b: i32) i32 {
-    return a + b;
-}
-
-test "basic add functionality" {
-    try testing.expect(add(3, 7) == 10);
-}