Hi there!
To learn Zig, I wrote a simple brute force sudoku solver. It works as a CLI app, so you pass it the path to a file containing puzzles and it will in turn spew out solutions on stdout
.
Each puzzle is formatted as a single line of digits, with 0 indicating an empty cell. So I might make a file like so:
> echo "001700509573024106800501002700295018009400305652800007465080071000159004908007053" > puzzle.txt
And then solve it like so:
> zig_sudoku ./puzzle.txt
241768539573924186896531742734295618189476325652813497465382971327159864918647253
I’d be thrilled if anyone wants to comment on the code. Any and all feedback is welcome!
You can find the code, and a large list of puzzles here: https://codeberg.org/herluf-ba/zig-sudoku.
Here’s a copy-paste of the entire solver:
//! A sudoku solver.
// 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.
const Sudoku = [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(allocator: Allocator, slice: []const u8) !*Sudoku {
if (slice.len < 9 * 9) {
return error.TooFewBytes;
}
// Allocate a new Sudoku and copy the bytes from slice into it.
var puzzle = try allocator.create(Sudoku);
errdefer allocator.destroy(puzzle);
for (0..9 * 9) |i| {
// Check that all bytes lie in the range '0' - '9'
if (slice[i] < '0' or slice[i] > '9') {
return error.InvalidByte;
}
// ASCII/UTF-8 '0' is 48, '1' is 49, '2' is 50 and so on.
// By subtracting 48 here we offset the digits to their int values.
puzzle[i] = slice[i] - 48;
}
return puzzle;
}
// Convenience function for displaying a sudoku as a 9x9 grid of digits.
fn display(sudoku: *Sudoku, writer: anytype) !void {
for (0..9) |i| {
for (0..9) |j| {
try writer.print("{d} ", .{sudoku[i * 9 + j]});
}
try writer.print("\n", .{});
}
}
// 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,
};
}
/// 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[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[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.
unreachable;
}
// Put the valid digit into the square;
sudoku[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;
}
}
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 {
const stdout = std.io.getStdOut().writer();
var gpa: std.heap.DebugAllocator(.{}) = .init;
const allocator = gpa.allocator();
const args = try std.process.argsAlloc(allocator);
defer std.process.argsFree(allocator, args);
// Check that a command line argument was supplied.
if (args.len != 2) {
std.debug.print("{s}", .{USAGE});
return;
}
// Open file to read puzzles from.
const file = try std.fs.cwd().openFile(args[1], .{});
defer file.close();
var buf_reader = std.io.bufferedReader(file.reader());
const reader = buf_reader.reader();
// Allocate a buffer we can read a line into.
var line = std.ArrayList(u8).init(allocator);
defer line.deinit();
const writer = line.writer();
// Read the file line by line.
while (reader.streamUntilDelimiter(writer, '\n', null)) {
defer line.clearRetainingCapacity();
// Try to parse and solve the line as a sudoku puzzle.
const puzzle = try parse(allocator, line.items);
defer allocator.destroy(puzzle);
try solveBruteForce(puzzle);
// Print the solution to stdout.
// First we need to push all the digits into valid ASCII/UTF-8 numbers.
for (puzzle) |*cell| {
cell.* += 48;
}
try stdout.print("{s}\n", .{puzzle});
} else |err| switch (err) {
error.EndOfStream => {},
else => return err,
}
}
const std = @import("std");
const Allocator = std.mem.Allocator;