diff options
| -rw-r--r-- | .gitignore | 2 | ||||
| -rw-r--r-- | build.zig | 41 | ||||
| -rw-r--r-- | src/main.zig | 218 | ||||
| -rw-r--r-- | src/root.zig | 13 |
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 @@ -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); -} |