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;
10 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.

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

I would change this to

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

It removes the magic number.

5 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
3 Likes

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:

2 Likes

I just had to think my c# sudoku solution in Code Golf.

int[]d=new int[81];var a=args[0].ToArray();int g,r,x,y,z=0,f=0;
for(x=40;x<721;x+=z%9>0?4:44)d[z++]=a[x]>47?a[x]-48:0;bool V(int q)
{void G(){if(d[r]==d[q])g++;}g=z=0;y=q/9;r=x=q%9;while(r<81){G();r+=9;}
r=y*9;while(r<y*9+9){G();r++;}r=(y-y%3)*9+x-x%3;while(z<9){G();r+=z++%3>1?7:1;}
return g<4;}void S(int q){while(q<80&d[q]>0)q++;for(int t=1;t<10&f<81;)
{d[q]=t++;f++;a[40+q/9*76+q%9*4]=(char)(t+47);if(V(q))S(q);if(f>80&V(q))
return;d[q]=0;f--;}}S(0);Console.Write(a);

Try a Zig one there! I did not dare yet.

1 Like

Oh, I was looking for something like this at one point, but didn’t manage to identify AnyWriter as the answer! Thanks, I’ll definitely be using that going forward!

1 Like

Prefer anytype instead of AnyWriter, as it generates better code. Only use AnyWriter when you actually need runtime polymorphism.

Hi, I would like to know if there’s any particular reason to use the DebugAllocator for this solution?

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.Unsolvable since 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();
}
10 Likes

I remember from about 100 years ago I also wrote a solver in Delphi.
At the time I encountered difficult sudoku’s which could not be solved with my brute force algo and I had to add some things.
Did you test it against “difficult” soduku’s? Does it solve any valid sudoku?

EDIT: after a bit of fiddling around with the code (Andrew’s one above here) I believe it does not solve this one. Please let me know if I’m wrong.

000000000
000003085
001020000
000507000
004000100
090000000
500000073
002010000
000040009

Confirmed:

000000000000003085001020000000507000004000100090000000500000073002010000000040009
// returns this original unsolved string

For example this one (more easy)

403500096507800300080000054000706023000020000950304000790000060004007508830005409
// gives
413572896567849312289631754148756923376928145952314687795483261624197538831265479

because I could not compile the code I changed the main() function to:

      var puzzle = try Sudoku.parse(...);
      try puzzle.solveBruteForce();
      try puzzle.print(); // using std.debug.print

As I saw from my antique code when the lineair algo did not solve the puzzle, the next step is:

  • take the square with the least amount of options,
  • try these all.
  • go recursive.

That hard puzzle is nasty - I dusted off my old python recursive backtracking algo code and it took an hour to solve… tomorrow I’m going to rewrite it in zig and see what happens, but wow.

edit: fixed the link

Agreed. My C solver does it in 275ms, but with lots of backtracking.

Love this API! It is an improvement over Rust version where by default reading line-by-line allocates, and even the optimized version still includes an extra memcpy. Though, I am a bit concerned that it isn’t immediately obvious just looking at the code, without intimately knowing the API, that StreamToLong is a possible error condition here. But I do love the error condition — if you are doing line-by-line processing, you should assume that your “line” is bounded in size, and its better to treat too-long-lines as outright invalid data (which they mostly likely are), rather than do a fallback allocation or something.

6 Likes

But this API is not necessarily made to read a file line by line though.

Let’s assume that:
- my file is bigger than the buffer,
- I can’t guarantee the buffer boundary cross exactly on a sentinel
- I want to parse/read the entirety of my file.

Imaging parsing a zig file, for example, and using a whitespace as a sentinel. At some point the buffer boundary is going to cross a non-whitespace character.

                   My buffer
...[...502 previous character...fn foo]...
                                   ^
                  I am here and I call `takeSentinel(' ')`
                  and I get an error, what do I do?

I fail to see how to use this API properly. The code in the branch confuses me even more because BufferedReader seems to be initialized with slices (using initFixed). Why would you need a BufferedReader on a pre-allocated slice? Why not just use the tokenize functions?

The only use on a file I could find is to parse resolve.conf and you can indeed take the reasonable assumption that it will never have a line bigger than 512 characters.

If you could let me know what I am missing. :slight_smile:

It’s a ring buffer, never mind :slight_smile:

There’s another positive interaction here with these changes. @mlugg convinced me to make the error set of the interface explicit rather than being anyerror. At first I was reluctant, but it’s become crystal clear that it was the right move.

In particular, pretty much anywhere that used readers and writers had error sets that were unwieldy. Now, they will be much smaller - containing only ReadFailed, WriteFailed, and depending on which functions are used, EndOfStream, StreamTooLong, etc., along with the error codes directly related to the surrounding code.

Stream implementations which want to report more detailed diagnostics must save that information and then return error.ReadFailed or error.WriteFailed. 30,000 lines of diff later, it has become clear this works quite well in practice.

Point being it becomes much more practical to manage error sets in the usage code, which means one will very likely notice StreamTooLong being added to an error set when a call to takeSentinel is introduced.

9 Likes