I wrote a simple Sudoku solver

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! :slight_smile:

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;
7 Likes

Thanks for sharing! I hope you’re liking Zig so far.

You did a pretty good job following Zig best practices (error handling, cleanup, etc.), but there’s a couple little things I wanted to point out. These aren’t meant to be super critical, just to help your learning:


if (digit == 0) {
    // No digit is valid in this cell, so the sudoku is unsolvable.
    unreachable;
}

unreachable should really only be used when a point is literally unreachable, this would lead to undefined behavior if built without safety checks. I think an error would make more sense here.


var gpa: std.heap.DebugAllocator(.{}) = .init;
const allocator = gpa.allocator();

You should deinit gpa so you can get memory leak checking:

var gpa: std.heap.DebugAllocator(.{}) = .init;
defer _ = gpa.deinit();
const allocator = gpa.allocator();

sudoku[i * 9 + j] = @truncate(digit);

Since you know digit is only supposed to contain values from 1 to 9 at this point, you should use @intCast instead (so you can get the safety check). @truncate should be used to truncate, not to make a silently-failing cast. Another option would be to make digit be a u8 and do the cast when you assign a value to digit: digit = @intCast(idx + 1).


I also have some nitpicks that aren’t as important but you might want to consider:

  • parse should probably just give you a Sodoku instead of a pointer to one, so you don’t need to create and destroy it. If you don’t like large return values, you can just pass a pointer to a Sodoku and have the function populate it.
  • You might want to replace this with a normal print to stdout instead of std.debug.print: std.debug.print("{s}", .{USAGE});
  • In Zig, global constants have the same naming conventions as variables, so USAGE should just be usage.
  • You should use /// doc comments instead of // comments for all function docs, not just solveBruteForce’s (this is really easy to forget).
  • I like the strategy of getting an array of seen cells, but it may be more idiomatic to compute the values like this instead of manually writing them all out:
var row_seen: [9]usize = undefined;
for (&row_seen, 0..) |*cell_idx, k| {
    cell_idx.* = i * 9 + k;
}

var column_seen: [9]usize = undefined;
for (&column_seen, 0..) |*cell_idx, k| {
    cell_idx.* = k * 9 + j;
}

var box_seen: [9]usize = undefined;
for (&box_seen, 0..) |*cell_idx, k| {
    cell_idx.* = (bi + k / 3) * 9 + bj + k % 3;
}

return row_seen ++ column_seen ++ box_seen;

Note that the ++ concat operator, while usually used on comptime-known arrays, can be used on arrays containing runtime-known values as long as the lengths of the arrays are comptime-known.

8 Likes

I think I would add to that to use multi-dimensional arrays, which should make it possible to avoid a bunch of manual index calculations.
So using:

const Sudoku = [9][9]u8;
4 Likes

I would change this to

puzzle[i] = slice[i] - '0';

It removes the magic number.

4 Likes

Awesome, thank you! This is exactly the sort of feedback I was hoping to get. It all makes sense to me!

1 Like

Not exclusive to zig, but if you make your program read from stdin instead of a named file, you can do both:

echo "241...753" | zig_sudoku
cat puzzle.txt | zig_sudoku # same as zig_sudoku < puzzle.txt"
1 Like

Glad to see there’s more Sudoku fans out there! One piece of feedback I have for you is to use AnyReader or AnyWriter instead of anytype.

For example, your display function is a simple enough use case to get away with anytype, but you could replace it with AnyWriter. While it won’t give you a lot more type safety, it will convey your intent more precisely and help your LSP with autocomplete. To take advantage of AnyWriter, all you need to do is call any() when you get your writer:

const stdout = std.io.getStdOut().writer().any();

If you want to see a more advanced use case, here’s an example where I used AnyWriter to build up a string for a parser. For my main function, I use stdout like you do in your example above, but for my unit tests, I use ArrayList’s writer because it’s easier to test the contents of the string.

I’ve stubbed my toe on anytype vs AnyWriter. Hopefully, you can learn from my mistakes :slightly_smiling_face: