summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorRobby Zambito <contact@robbyzambito.me>2025-05-13 17:38:28 -0400
committerRobby Zambito <contact@robbyzambito.me>2025-05-19 08:16:10 -0400
commite9c293f2572a92596d54d2fec16d6aec9c8af0bf (patch)
tree2c9b0d9c4ef0f146e77dc92aa5871c5f20352038
parent753c9a9970e5426a66133504b9232f5472c55c2e (diff)
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.
-rw-r--r--.gitignore2
-rw-r--r--build.zig41
-rw-r--r--src/main.zig218
-rw-r--r--src/root.zig13
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);
-}