Thanks for sharing! I took a few minutes and refactored it to match how I’ve been coding Zig lately. See what you think.
I did this in the branch that I’m working on because I wanted to try out and see if the new API for dealing with delimiters is more convenient.
Some notes:
- No allocation needed for this
- By wrapping the state into a struct, it becomes convenient to use namespaced functions
unreachable=>return error.Unsolvablesince it can happen in response to user input. Assertions for programmer mistakes; errors for user mistakes.
//! A sudoku solver.
const std = @import("std");
const Allocator = std.mem.Allocator;
const Sudoku = struct {
/// We are representing a sukodu puzzle as a 81 cell array.
/// 0's are going to indicate empty cells, while 1-9 cells have been filled in.
cells: [9 * 9]u8,
/// Parse a sudoku puzzle from a line of ASCII/UTF-8 text.
/// The line should contain atleast 81 numbers in the range 0-9, with 0's for empty cells.
fn parse(slice: []const u8) !Sudoku {
var result: Sudoku = undefined;
if (slice.len < result.cells.len) {
return error.TooFewBytes;
}
for (&result.cells, slice[0..result.cells.len]) |*cell, input| {
// Check that all bytes lie in the range '0' - '9'
switch (input) {
'0'...'9' => cell.* = input - '0',
else => return error.InvalidByte,
}
}
return result;
}
/// Convenience function for displaying a sudoku as a 9x9 grid of digits.
fn display(sudoku: *Sudoku, writer: *std.io.BufferedWriter) !void {
for (sudoku.cells, 0..) |cell, i| {
try writer.print("{d} ", .{cell});
if (i % 9 == 0) try writer.writeByte('\n');
}
}
/// Print the solution to stdout.
/// First we need to push all the digits into valid ASCII/UTF-8 numbers.
fn print(sudoku: *Sudoku, writer: *std.io.BufferedWriter) !void {
for (sudoku.cells) |cell| {
try writer.writeByte('0' + cell);
}
try writer.writeByte('\n');
}
/// Solves a sudoku in place via brute force.
/// Simply start at the top-left and look through the puzzle for a cell
/// where only a single digit is allowed.
/// When found, fill in the digit and start over from the top-left,
/// until there are no more cells to fill in.
fn solveBruteForce(sudoku: *Sudoku) !void {
outer: while (true) {
for (0..9) |i| {
square: for (0..9) |j| {
if (sudoku.cells[i * 9 + j] != 0) {
continue; // Already filled in this digit so skip.
}
// Compute the indicies of the cells "seen by" the current cell.
const seen = getSeenByCell(i, j);
// Compute the set of numbers that are valid in this cell.
var valid_in_slot = [_]bool{true} ** 9;
for (seen) |cell_idx| {
const val = sudoku.cells[cell_idx];
if (val > 0 and valid_in_slot[val - 1]) {
valid_in_slot[val - 1] = false;
}
}
// Compute which digit is valid.
var digit: usize = 0;
for (valid_in_slot, 0..) |is_valid, idx| {
if (is_valid) {
if (digit == 0) {
digit = idx + 1;
} else {
// More than one digit is valid, so skip this cell for now.
continue :square;
}
}
}
if (digit == 0) {
// No digit is valid in this cell, so the sudoku is unsolvable.
return error.Unsolvable;
}
// Put the valid digit into the square;
sudoku.cells[i * 9 + j] = @truncate(digit);
continue :outer; // We placed a digit, so we scan for a new square to fill again.
}
}
// When this is reached, we looped through every cell without finding a missing one,
// so the sudoku is solved.
break :outer;
}
}
/// Get's the indicies of the cells that "can be seen by" the cell at (i, j).
/// Cell A is seen by cell B if A is in the same row, column or box as B.
fn getSeenByCell(i: usize, j: usize) [9 + 9 + 9]usize {
const bi = (i / 3) * 3;
const bj = (j / 3) * 3;
return [_]usize{
// Row
i * 9 + 0,
i * 9 + 1,
i * 9 + 2,
i * 9 + 3,
i * 9 + 4,
i * 9 + 5,
i * 9 + 6,
i * 9 + 7,
i * 9 + 8,
// Column
0 * 9 + j,
1 * 9 + j,
2 * 9 + j,
3 * 9 + j,
4 * 9 + j,
5 * 9 + j,
6 * 9 + j,
7 * 9 + j,
8 * 9 + j,
// Box
(bi + 0) * 9 + bj + 0,
(bi + 0) * 9 + bj + 1,
(bi + 0) * 9 + bj + 2,
(bi + 1) * 9 + bj + 0,
(bi + 1) * 9 + bj + 1,
(bi + 1) * 9 + bj + 2,
(bi + 2) * 9 + bj + 0,
(bi + 2) * 9 + bj + 1,
(bi + 2) * 9 + bj + 2,
};
}
};
const usage =
\\Usage: zig-sudoku [path-to-puzzles]
\\Solve sudoku puzzles. Provide a path to a file containing puzzles.
\\Each puzzle should be formatted as a newline terminated line of digits 0-9.
\\0 indicates an empty cell, while any other digit is a prefilled one.
\\
;
pub fn main() !void {
var arena_allocator = std.heap.ArenaAllocator.init(std.heap.page_allocator);
defer arena_allocator.deinit();
const arena = arena_allocator.allocator();
const args = try std.process.argsAlloc(arena);
// Check that a command line argument was supplied.
if (args.len != 2) {
try std.fs.File.stderr().writeAll(usage);
std.process.exit(1);
}
// Open file to read puzzles from.
const file = try std.fs.cwd().openFile(args[1], .{});
defer file.close();
var file_reader = file.reader();
var in_buffer: [512]u8 = undefined;
var in_br = file_reader.interface().buffered(&in_buffer);
var out_buffer: [512]u8 = undefined;
var out_writer = std.fs.File.stdout().writerStreaming();
var out_bw = out_writer.interface().buffered(&out_buffer);
// Read the file line by line.
while (in_br.takeSentinel('\n')) |line| {
// Try to parse and solve the line as a sudoku puzzle.
var puzzle = try Sudoku.parse(line);
try puzzle.solveBruteForce();
try puzzle.print(&out_bw);
} else |err| switch (err) {
error.EndOfStream => {},
else => |e| return e,
}
try out_bw.flush();
}