# I wrote a simple Sudoku solver

**URL:** <https://ziggit.dev/t/i-wrote-a-simple-sudoku-solver/9924>\
**Category:** Showcase\
**Created:** [May 1, 2025, 6:58pm UTC](https://ziggit.dev/t/i-wrote-a-simple-sudoku-solver/9924 "2025-05-01T18:58:48Z")\
**Posts on this page:** 13\
**Page:** 2

<div class="post-metadata">

**Author:** ![dhw9406](https://ziggit.dev/letter_avatar_proxy/v4/letter/d/90db22/32.png) [@dhw9406](https://ziggit.dev/u/dhw9406)\
**Post date:** [May 6, 2025, 4:48am UTC](https://ziggit.dev/t/i-wrote-a-simple-sudoku-solver/9924/21 "2025-05-06T04:48:37Z")

</div>

well, I didn’t get to translating to zig yet, but I fixed my old python code to search more intelligently, and the time went from an hour to 3 seconds. Algorithmics for the win!!! The new code is [here](https://github.com/hunterw01/sudoku-solvers/blob/main/solvers/hunterw01-recursive-cds.py)

---

<div class="post-metadata">

**Author:** ![herluf-ba](https://ziggit.dev/user_avatar/ziggit.dev/herluf-ba/32/5025_2.png) [@herluf-ba](https://ziggit.dev/u/herluf-ba)\
**Post date:** [May 6, 2025, 7:26pm UTC](https://ziggit.dev/t/i-wrote-a-simple-sudoku-solver/9924/22 "2025-05-06T19:26:36Z")

</div>

Neat that you tried running my solver on it. Indeed, that puzzle is beyond the solver. It can only solve puzzles where there is _at least one square with only one possible digit_ at any step during the solve. I believe that includes any sudoku with a single solution ~~(Please tell me if I am wrong 🙂 )~~ → I was wrong! For instance, in the sudoku you presented, in row 2 column 4 digits 1, 4, 6, 7, 9 are valid. _But_ because that’s the only square you can put a 1 in row 2, actually only 1 can go there.

You’ve motivated me to write a better solver to try and tackle this puzzle, thanks!

---

<div class="post-metadata">

**Author:** ![Adau](https://ziggit.dev/user_avatar/ziggit.dev/adau/32/5320_2.png) [@Adau](https://ziggit.dev/u/Adau)\
**Post date:** [May 7, 2025, 2:48pm UTC](https://ziggit.dev/t/i-wrote-a-simple-sudoku-solver/9924/23 "2025-05-07T14:48:51Z")

</div>

Good job !

My super-stupid recursive algorithm can solve it, but it takes around 2.5 s to solve.

I guess I can only reach such a speed by ditching the recursive algorithm to something more optimized.

```zig
const std = @import("std");
const builtin = @import("builtin");

const LENGTH: usize = 81;

const Sudoku = struct {
    cells: [LENGTH]u8,

    fn newFromStdIn(inr: std.io.AnyReader) !Sudoku {
        var cells: [LENGTH]u8 = undefined;
        var nbytes: usize = 0;

        while (nbytes < LENGTH) {
            const byte = inr.readByte() catch break;

            // Discard line feeds
            if (byte == 10) continue;

            // Return error if not a digit
            if (byte < 48 or byte > 57) return error.BadInput;

            cells[nbytes] = byte - '0';
            nbytes += 1;
        }

        if (nbytes != LENGTH) return error.BadLength;

        return Sudoku{ .cells = cells };
    }

    fn display(self: Sudoku, outw: std.io.AnyWriter) !void {
        for (self.cells, 1..) |c, i| {
            try outw.print("{d} ", .{c});
            if (i % 9 == 0) try outw.writeByte('\n');
        }
    }

    fn print(self: Sudoku, outw: std.io.AnyWriter) !void {
        for (self.cells) |c| {
            try outw.writeByte('0' + c);
        }
        try outw.writeByte('\n');
    }

    fn findEmpty(self: Sudoku) ?usize {
        for (self.cells, 0..) |c, i| {
            if (c == 0) return i;
        }
        return null;
    }

    fn isValid(self: Sudoku, idx: usize, num: u8) bool {
        const x = @mod(idx, 9);
        const y = @divFloor(idx, 9);

        for (0..9) |i| {
            if (self.cells[y * 9 + i] == num) return false;
        }

        for (0..9) |i| {
            if (self.cells[9 * i + x] == num) return false;
        }

        const si: usize = x - @mod(x, 3);
        const sj: usize = y - @mod(y, 3);
        for (0..3) |i| {
            for (0..3) |j| {
                if (self.cells[(si + i) + (sj + j) * 9] == num) return false;
            }
        }
        return true;
    }

    fn solve(self: *Sudoku) bool {
        const maybe_empty_idx = self.findEmpty();
        if (maybe_empty_idx == null) return true;

        const empty_idx = maybe_empty_idx.?;
        for (1..10) |n| {
            const nu8: u8 = @intCast(n);
            if (self.isValid(empty_idx, nu8)) {
                self.cells[empty_idx] = nu8;

                if (self.solve()) return true;
                self.cells[empty_idx] = 0;
            }
        }
        return false;
    }
};

pub fn main() !void {
    // --- stdout & stdin ---
    const outw = std.io.getStdOut().writer().any();
    const inr = std.io.getStdIn().reader().any();

    var s = try Sudoku.newFromStdIn(inr);
    _ = s.solve();
    try s.print(outw);
}

```

---

<div class="post-metadata">

**Author:** ![dhw9406](https://ziggit.dev/letter_avatar_proxy/v4/letter/d/90db22/32.png) [@dhw9406](https://ziggit.dev/u/dhw9406)\
**Post date:** [May 7, 2025, 5:32pm UTC](https://ziggit.dev/t/i-wrote-a-simple-sudoku-solver/9924/24 "2025-05-07T17:32:48Z")

</div>

Welcome to ziggit!

In regards to your algorithm, recursion is the way for this problem! The main optimization is to find the most constrained open cell instead of the next open cell. While you’re at it, since you’ll already be computing the possible entries for each cell (to find the one with the least number of possibilities) you can make your for loop only try those. Also you can do this in a way that doesn’t require passing a bunch of lists around if you want to be clever.

Here’s my [current solution](https://github.com/hunterw01/sudoku-solvers/blob/main/solvers/hunterw01-recursive-cds.zig). Solves the hard puzzle in less than 20ms on my machine, maybe much less. Now I have to figure out how to do profiling… does poop work on windows?

---

<div class="post-metadata">

**Author:** ![LucasSantos91](https://ziggit.dev/user_avatar/ziggit.dev/lucassantos91/32/440_2.png) [@LucasSantos91](https://ziggit.dev/u/LucasSantos91)\
**Post date:** [May 7, 2025, 7:45pm UTC](https://ziggit.dev/t/i-wrote-a-simple-sudoku-solver/9924/25 "2025-05-07T19:45:55Z")

</div>

This was a cool challenge. It motivated me to write my own solver. Here’s the [link](https://github.com/LucasSantos91/Sodusolver).

It’s not recursive. It backtracks through iteration.

It solves @ericlang’s grid in 3ms in my machine. The input for this example is in the readme.

> [@ericlang](#):
>
> ```zig
> 000000000
> 000003085
> 001020000
> 000507000
> 004000100
> 090000000
> 500000073
> 002010000
> 000040009
> 
> ```

---

<div class="post-metadata">

**Author:** ![jibal](https://ziggit.dev/user_avatar/ziggit.dev/jibal/32/3606_2.png) [@jibal](https://ziggit.dev/u/jibal)\
**Post date:** [May 8, 2025, 1:51am UTC](https://ziggit.dev/t/i-wrote-a-simple-sudoku-solver/9924/26 "2025-05-08T01:51:26Z")

</div>

From the land of Algorithmia, there’s Knuth’s “Dancing Links” algorithm for solving Sudoku as a constraint problem:

> <https://news.ycombinator.com/item?id=16036588>
>
> I found Knuth’s “Dancing Links” paper \[1\] very well written and a somewhat easy read (I had to reread certain parts a couple times). I had to write a sudoku solver for one of my classes and I read that dancing links and algorithm x was one way to do it \[2\]. I then read some things around the internet to apply dancing links to sudoku solving \[3\] \[4\]. If you read the Wikipedia entry on exact cover...

---

<div class="post-metadata">

**Author:** ![Adau](https://ziggit.dev/user_avatar/ziggit.dev/adau/32/5320_2.png) [@Adau](https://ziggit.dev/u/Adau)\
**Post date:** [May 8, 2025, 6:30am UTC](https://ziggit.dev/t/i-wrote-a-simple-sudoku-solver/9924/27 "2025-05-08T06:30:08Z")

</div>

That’s impressive ! I was really happy with my solution but you both have better one. There is a lot of room for improvement for me.

Thanks for sharing !

---

<div class="post-metadata">

**Author:** ![ericlang](https://ziggit.dev/user_avatar/ziggit.dev/ericlang/32/8515_2.png) [@ericlang](https://ziggit.dev/u/ericlang)\
**Post date:** [May 8, 2025, 8:21am UTC](https://ziggit.dev/t/i-wrote-a-simple-sudoku-solver/9924/28 "2025-05-08T08:21:45Z")

</div>

Haha yesterday I did the same:  
easy: 4.3 microseconds  
difficult: 2.5 milliseconds

```zig
const std = @import("std");
const assert = std.debug.assert;
const print = std.debug.print;

pub fn main() !void
{
    // nonsense
    solve_this_one("40350009650780030008000005a000706023000020000950304000790000060004007508830005409") catch |err| print("error: {any}\n", .{err});
    // too short
    solve_this_one("403500096507830008000005a000706023000020000950304000790000060004007508830005409") catch |err| print("error: {any}\n", .{err});
    // invalid
    solve_this_one("403500096507800300080000054000706023000020000950304000790000060004007508830005499") catch |err| print("error: {any}\n", .{err});

    // easy 4.3 microseconds
    solve_this_one("403500096507800300080000054000706023000020000950304000790000060004007508830005409") catch |err| print("error: {any}\n", .{err});
    // difficult 2.5 milliseconds
    solve_this_one("000000000000003085001020000000507000004000100090000000500000073002010000000040009") catch |err| print("error: {any}\n", .{err});
    // empty 16.1 micrsoseconds
    solve_this_one("000000000000000000000000000000000000000000000000000000000000000000000000000000000") catch |err| print("error: {any}\n", .{err});

}

pub fn solve_this_one(str: []const u8) !void
{
        var sudoku: Sudoku = try .init_from_string(str);
        print("\nproblem\n", .{});
        sudoku.show();
        var t = try std.time.Timer.start();
        const solved = sudoku.solve();
        const time = t.lap();
        if (solved)
        {
            print("solution - solve time {}\n", .{std.fmt.fmtDuration(time)});
            sudoku.show();
        }
        else
        {
            print("NOT SOLVED\n", .{});
        }
}

const Error = error { StringTooShort, InvalidString, InvalidSudoku };

pub const Sudoku = struct
{
    const empty: Sudoku = .{};

    const Options = std.bit_set.IntegerBitSet(10);
    const empty_options = Options.initEmpty();
    const full_options = Options { .mask = 0b1111111110 };

    cells: [81]Cell = @splat(Cell.empty),
    filled: u8 = 0,

    const Cell = struct
    {
        pub const empty: Cell = .{};
        value: u8 = 0,
        options: Options = empty_options,

        /// Returns the one possible option. Asserts that there is actually 1 option.
        fn only_option(self: Cell) u8
        {
            assert(self.options.count() == 1);
            return @truncate(self.options.findFirstSet().?);
        }
    };

    pub fn init_from_string(str: []const u8) Error!Sudoku
    {
        var sudoku: Sudoku = .empty;
        if (str.len < 81) return Error.StringTooShort;
        for (all_squares) |square|
        {
            const cell = &sudoku.cells[square];
            const char = str[square];
            if (char < '0' or char > '9') return Error.InvalidString;
            cell.value = char - '0';
        }
        return if (sudoku.prepare()) sudoku else Error.InvalidSudoku;
    }

    pub fn solve(self: *Sudoku) bool
    {
        if (self.filled == 81) return true;
        var is_solved: bool = false;
        self.recursive_solve(0, &is_solved);
        return is_solved;
    }

    fn recursive_solve(self: *Sudoku, depth: u8, is_solved: *bool) void
    {
        if (is_solved.*) return;
        assert(depth < 82);

        // easy: try squares with one possible option, until no more of these found.
        var next_best_square: ?u8 = null;
        while (true)
        {
            var list = self.get_sorted_traverse_squares(&next_best_square);
            if (list.len == 0) break;
            for (list.slice()) |square|
            {
                const value = self.cells[square].only_option();
                if (!self.set(square, value)) return; // dead end.
                if (self.filled == 81) { is_solved.* = true; return; }
            }
        }

        // go recursive with our next best square.
        const square = next_best_square orelse return;
        const cell = self.cells[square];
        assert (cell.value == 0 and cell.options.count() > 1);
        var iter = cell.options.iterator(.{});
        while (iter.next()) |bit|
        {
            const try_value: u8 = @truncate(bit);
            const undo: Sudoku = self.*;
            if (self.set(square, try_value)) // otherwise dead end.
            {
                self.recursive_solve(depth + 1, is_solved);
                if (is_solved.*) return;
            }
            self.* = undo;
        }
    }

    /// Returns squares with only one option. next_best is filled with the square containing the lowest amount of options > 1.
    fn get_sorted_traverse_squares(self: *const Sudoku, next_best: *?u8) std.BoundedArray(u8, 81)
    {
        var lowest: usize = 10;
        var list: std.BoundedArray(u8, 81) = .{};
        for (self.cells, all_squares) |cell, square|
        {
            if (cell.value == 0)
            {
                const option_count = cell.options.count();
                if (option_count == 1)
                {
                    list.appendAssumeCapacity(square);
                }
                else if (option_count < lowest)
                {
                    lowest = option_count;
                    next_best.* = square;
                }
            }
        }
        return list;
    }

    fn prepare(self: *Sudoku) bool
    {
        // init cells
        for (&self.cells) |*cell|
        {
            cell.options = if (cell.value != 0) empty_options else full_options;
            if (cell.value != 0) self.filled += 1;
        }

        if (!self.validate()) return false;

        // update all options
        for (&self.cells, all_squares) |*cell, square|
        {
            if (cell.value != 0)
            {
                const ok = self.on_set(square);
                if (!ok) return false;
            }
        }
        return true;
    }

    fn validate(self: *const Sudoku) bool
    {
        for (all_squares) |square|
        {
            var opts: Options = empty_options;

            for (related_squares[square], 0..) |q, index|
            {
                if (index == 9 or index == 17) opts = empty_options;
                const val = self.cells[q].value;
                if (val != 0)
                {
                    if (opts.isSet(val)) return false;
                    opts.set(val);
                }
            }
        }
        return true;
    }

    /// If set fails, we have an invalid sudoku, an insolvable one or a recursive dead end.
    fn set(self: *Sudoku, square: u8, value: u8) bool
    {
        assert(value != 0);
        const cell: *Cell = &self.cells[square];
        assert(cell.value == 0);
        cell.value = value;
        cell.options = empty_options;
        self.filled += 1;
        return self.on_set(square);
    }

    fn on_set(self: *Sudoku, square: u8) bool
    {
        const this: *Cell = &self.cells[square];
        assert(this.value != 0);
        const affected = &related_squares[square];
        for (affected) |q|
        {
            const other: *Cell = &self.cells[q];
            if (other.value == 0)
            {
                other.options.unset(this.value);
                if (other.options.mask == 0) return false;
            }
        }
        return true;
    }

    fn show(self: *const Sudoku) void
    {
        for (self.cells, 0..) |cell, square|
        {
            const x = square % 9;
            print("{u} ", .{cell.value + '0'});
            if (x == 8) print("\n", .{});
        }
    }
};

pub const all_squares: [81]u8 = blk:
{
    var out: [81]u8 = undefined;
    for (&out, 0..) |*s, q|
        s.* = @truncate(q);
    break :blk out;
};

/// index 0 = 9x horizontal
/// index 9 = 8x vertical
/// index 17 = 4x area
var related_squares: [81][21]u8 =
.{
    .{ 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 18, 27, 36, 45, 54, 63, 72, 10, 11, 19, 20 },
    .{ 0, 1, 2, 3, 4, 5, 6, 7, 8, 10, 19, 28, 37, 46, 55, 64, 73, 9, 11, 18, 20 },
    .{ 0, 1, 2, 3, 4, 5, 6, 7, 8, 11, 20, 29, 38, 47, 56, 65, 74, 9, 10, 18, 19 },
    .{ 0, 1, 2, 3, 4, 5, 6, 7, 8, 12, 21, 30, 39, 48, 57, 66, 75, 13, 14, 22, 23 },
    .{ 0, 1, 2, 3, 4, 5, 6, 7, 8, 13, 22, 31, 40, 49, 58, 67, 76, 12, 14, 21, 23 },
    .{ 0, 1, 2, 3, 4, 5, 6, 7, 8, 14, 23, 32, 41, 50, 59, 68, 77, 12, 13, 21, 22 },
    .{ 0, 1, 2, 3, 4, 5, 6, 7, 8, 15, 24, 33, 42, 51, 60, 69, 78, 16, 17, 25, 26 },
    .{ 0, 1, 2, 3, 4, 5, 6, 7, 8, 16, 25, 34, 43, 52, 61, 70, 79, 15, 17, 24, 26 },
    .{ 0, 1, 2, 3, 4, 5, 6, 7, 8, 17, 26, 35, 44, 53, 62, 71, 80, 15, 16, 24, 25 },
    .{ 9, 10, 11, 12, 13, 14, 15, 16, 17, 0, 18, 27, 36, 45, 54, 63, 72, 1, 2, 19, 20 },
    .{ 9, 10, 11, 12, 13, 14, 15, 16, 17, 1, 19, 28, 37, 46, 55, 64, 73, 0, 2, 18, 20 },
    .{ 9, 10, 11, 12, 13, 14, 15, 16, 17, 2, 20, 29, 38, 47, 56, 65, 74, 0, 1, 18, 19 },
    .{ 9, 10, 11, 12, 13, 14, 15, 16, 17, 3, 21, 30, 39, 48, 57, 66, 75, 4, 5, 22, 23 },
    .{ 9, 10, 11, 12, 13, 14, 15, 16, 17, 4, 22, 31, 40, 49, 58, 67, 76, 3, 5, 21, 23 },
    .{ 9, 10, 11, 12, 13, 14, 15, 16, 17, 5, 23, 32, 41, 50, 59, 68, 77, 3, 4, 21, 22 },
    .{ 9, 10, 11, 12, 13, 14, 15, 16, 17, 6, 24, 33, 42, 51, 60, 69, 78, 7, 8, 25, 26 },
    .{ 9, 10, 11, 12, 13, 14, 15, 16, 17, 7, 25, 34, 43, 52, 61, 70, 79, 6, 8, 24, 26 },
    .{ 9, 10, 11, 12, 13, 14, 15, 16, 17, 8, 26, 35, 44, 53, 62, 71, 80, 6, 7, 24, 25 },
    .{ 18, 19, 20, 21, 22, 23, 24, 25, 26, 0, 9, 27, 36, 45, 54, 63, 72, 1, 2, 10, 11 },
    .{ 18, 19, 20, 21, 22, 23, 24, 25, 26, 1, 10, 28, 37, 46, 55, 64, 73, 0, 2, 9, 11 },
    .{ 18, 19, 20, 21, 22, 23, 24, 25, 26, 2, 11, 29, 38, 47, 56, 65, 74, 0, 1, 9, 10 },
    .{ 18, 19, 20, 21, 22, 23, 24, 25, 26, 3, 12, 30, 39, 48, 57, 66, 75, 4, 5, 13, 14 },
    .{ 18, 19, 20, 21, 22, 23, 24, 25, 26, 4, 13, 31, 40, 49, 58, 67, 76, 3, 5, 12, 14 },
    .{ 18, 19, 20, 21, 22, 23, 24, 25, 26, 5, 14, 32, 41, 50, 59, 68, 77, 3, 4, 12, 13 },
    .{ 18, 19, 20, 21, 22, 23, 24, 25, 26, 6, 15, 33, 42, 51, 60, 69, 78, 7, 8, 16, 17 },
    .{ 18, 19, 20, 21, 22, 23, 24, 25, 26, 7, 16, 34, 43, 52, 61, 70, 79, 6, 8, 15, 17 },
    .{ 18, 19, 20, 21, 22, 23, 24, 25, 26, 8, 17, 35, 44, 53, 62, 71, 80, 6, 7, 15, 16 },
    .{ 27, 28, 29, 30, 31, 32, 33, 34, 35, 0, 9, 18, 36, 45, 54, 63, 72, 37, 38, 46, 47 },
    .{ 27, 28, 29, 30, 31, 32, 33, 34, 35, 1, 10, 19, 37, 46, 55, 64, 73, 36, 38, 45, 47 },
    .{ 27, 28, 29, 30, 31, 32, 33, 34, 35, 2, 11, 20, 38, 47, 56, 65, 74, 36, 37, 45, 46 },
    .{ 27, 28, 29, 30, 31, 32, 33, 34, 35, 3, 12, 21, 39, 48, 57, 66, 75, 40, 41, 49, 50 },
    .{ 27, 28, 29, 30, 31, 32, 33, 34, 35, 4, 13, 22, 40, 49, 58, 67, 76, 39, 41, 48, 50 },
    .{ 27, 28, 29, 30, 31, 32, 33, 34, 35, 5, 14, 23, 41, 50, 59, 68, 77, 39, 40, 48, 49 },
    .{ 27, 28, 29, 30, 31, 32, 33, 34, 35, 6, 15, 24, 42, 51, 60, 69, 78, 43, 44, 52, 53 },
    .{ 27, 28, 29, 30, 31, 32, 33, 34, 35, 7, 16, 25, 43, 52, 61, 70, 79, 42, 44, 51, 53 },
    .{ 27, 28, 29, 30, 31, 32, 33, 34, 35, 8, 17, 26, 44, 53, 62, 71, 80, 42, 43, 51, 52 },
    .{ 36, 37, 38, 39, 40, 41, 42, 43, 44, 0, 9, 18, 27, 45, 54, 63, 72, 28, 29, 46, 47 },
    .{ 36, 37, 38, 39, 40, 41, 42, 43, 44, 1, 10, 19, 28, 46, 55, 64, 73, 27, 29, 45, 47 },
    .{ 36, 37, 38, 39, 40, 41, 42, 43, 44, 2, 11, 20, 29, 47, 56, 65, 74, 27, 28, 45, 46 },
    .{ 36, 37, 38, 39, 40, 41, 42, 43, 44, 3, 12, 21, 30, 48, 57, 66, 75, 31, 32, 49, 50 },
    .{ 36, 37, 38, 39, 40, 41, 42, 43, 44, 4, 13, 22, 31, 49, 58, 67, 76, 30, 32, 48, 50 },
    .{ 36, 37, 38, 39, 40, 41, 42, 43, 44, 5, 14, 23, 32, 50, 59, 68, 77, 30, 31, 48, 49 },
    .{ 36, 37, 38, 39, 40, 41, 42, 43, 44, 6, 15, 24, 33, 51, 60, 69, 78, 34, 35, 52, 53 },
    .{ 36, 37, 38, 39, 40, 41, 42, 43, 44, 7, 16, 25, 34, 52, 61, 70, 79, 33, 35, 51, 53 },
    .{ 36, 37, 38, 39, 40, 41, 42, 43, 44, 8, 17, 26, 35, 53, 62, 71, 80, 33, 34, 51, 52 },
    .{ 45, 46, 47, 48, 49, 50, 51, 52, 53, 0, 9, 18, 27, 36, 54, 63, 72, 28, 29, 37, 38 },
    .{ 45, 46, 47, 48, 49, 50, 51, 52, 53, 1, 10, 19, 28, 37, 55, 64, 73, 27, 29, 36, 38 },
    .{ 45, 46, 47, 48, 49, 50, 51, 52, 53, 2, 11, 20, 29, 38, 56, 65, 74, 27, 28, 36, 37 },
    .{ 45, 46, 47, 48, 49, 50, 51, 52, 53, 3, 12, 21, 30, 39, 57, 66, 75, 31, 32, 40, 41 },
    .{ 45, 46, 47, 48, 49, 50, 51, 52, 53, 4, 13, 22, 31, 40, 58, 67, 76, 30, 32, 39, 41 },
    .{ 45, 46, 47, 48, 49, 50, 51, 52, 53, 5, 14, 23, 32, 41, 59, 68, 77, 30, 31, 39, 40 },
    .{ 45, 46, 47, 48, 49, 50, 51, 52, 53, 6, 15, 24, 33, 42, 60, 69, 78, 34, 35, 43, 44 },
    .{ 45, 46, 47, 48, 49, 50, 51, 52, 53, 7, 16, 25, 34, 43, 61, 70, 79, 33, 35, 42, 44 },
    .{ 45, 46, 47, 48, 49, 50, 51, 52, 53, 8, 17, 26, 35, 44, 62, 71, 80, 33, 34, 42, 43 },
    .{ 54, 55, 56, 57, 58, 59, 60, 61, 62, 0, 9, 18, 27, 36, 45, 63, 72, 64, 65, 73, 74 },
    .{ 54, 55, 56, 57, 58, 59, 60, 61, 62, 1, 10, 19, 28, 37, 46, 64, 73, 63, 65, 72, 74 },
    .{ 54, 55, 56, 57, 58, 59, 60, 61, 62, 2, 11, 20, 29, 38, 47, 65, 74, 63, 64, 72, 73 },
    .{ 54, 55, 56, 57, 58, 59, 60, 61, 62, 3, 12, 21, 30, 39, 48, 66, 75, 67, 68, 76, 77 },
    .{ 54, 55, 56, 57, 58, 59, 60, 61, 62, 4, 13, 22, 31, 40, 49, 67, 76, 66, 68, 75, 77 },
    .{ 54, 55, 56, 57, 58, 59, 60, 61, 62, 5, 14, 23, 32, 41, 50, 68, 77, 66, 67, 75, 76 },
    .{ 54, 55, 56, 57, 58, 59, 60, 61, 62, 6, 15, 24, 33, 42, 51, 69, 78, 70, 71, 79, 80 },
    .{ 54, 55, 56, 57, 58, 59, 60, 61, 62, 7, 16, 25, 34, 43, 52, 70, 79, 69, 71, 78, 80 },
    .{ 54, 55, 56, 57, 58, 59, 60, 61, 62, 8, 17, 26, 35, 44, 53, 71, 80, 69, 70, 78, 79 },
    .{ 63, 64, 65, 66, 67, 68, 69, 70, 71, 0, 9, 18, 27, 36, 45, 54, 72, 55, 56, 73, 74 },
    .{ 63, 64, 65, 66, 67, 68, 69, 70, 71, 1, 10, 19, 28, 37, 46, 55, 73, 54, 56, 72, 74 },
    .{ 63, 64, 65, 66, 67, 68, 69, 70, 71, 2, 11, 20, 29, 38, 47, 56, 74, 54, 55, 72, 73 },
    .{ 63, 64, 65, 66, 67, 68, 69, 70, 71, 3, 12, 21, 30, 39, 48, 57, 75, 58, 59, 76, 77 },
    .{ 63, 64, 65, 66, 67, 68, 69, 70, 71, 4, 13, 22, 31, 40, 49, 58, 76, 57, 59, 75, 77 },
    .{ 63, 64, 65, 66, 67, 68, 69, 70, 71, 5, 14, 23, 32, 41, 50, 59, 77, 57, 58, 75, 76 },
    .{ 63, 64, 65, 66, 67, 68, 69, 70, 71, 6, 15, 24, 33, 42, 51, 60, 78, 61, 62, 79, 80 },
    .{ 63, 64, 65, 66, 67, 68, 69, 70, 71, 7, 16, 25, 34, 43, 52, 61, 79, 60, 62, 78, 80 },
    .{ 63, 64, 65, 66, 67, 68, 69, 70, 71, 8, 17, 26, 35, 44, 53, 62, 80, 60, 61, 78, 79 },
    .{ 72, 73, 74, 75, 76, 77, 78, 79, 80, 0, 9, 18, 27, 36, 45, 54, 63, 55, 56, 64, 65 },
    .{ 72, 73, 74, 75, 76, 77, 78, 79, 80, 1, 10, 19, 28, 37, 46, 55, 64, 54, 56, 63, 65 },
    .{ 72, 73, 74, 75, 76, 77, 78, 79, 80, 2, 11, 20, 29, 38, 47, 56, 65, 54, 55, 63, 64 },
    .{ 72, 73, 74, 75, 76, 77, 78, 79, 80, 3, 12, 21, 30, 39, 48, 57, 66, 58, 59, 67, 68 },
    .{ 72, 73, 74, 75, 76, 77, 78, 79, 80, 4, 13, 22, 31, 40, 49, 58, 67, 57, 59, 66, 68 },
    .{ 72, 73, 74, 75, 76, 77, 78, 79, 80, 5, 14, 23, 32, 41, 50, 59, 68, 57, 58, 66, 67 },
    .{ 72, 73, 74, 75, 76, 77, 78, 79, 80, 6, 15, 24, 33, 42, 51, 60, 69, 61, 62, 70, 71 },
    .{ 72, 73, 74, 75, 76, 77, 78, 79, 80, 7, 16, 25, 34, 43, 52, 61, 70, 60, 62, 69, 71 },
    .{ 72, 73, 74, 75, 76, 77, 78, 79, 80, 8, 17, 26, 35, 44, 53, 62, 71, 60, 61, 69, 70 }
};

```

---

<div class="post-metadata">

**Author:** ![LucasSantos91](https://ziggit.dev/user_avatar/ziggit.dev/lucassantos91/32/440_2.png) [@LucasSantos91](https://ziggit.dev/u/LucasSantos91)\
**Post date:** [May 8, 2025, 5:06pm UTC](https://ziggit.dev/t/i-wrote-a-simple-sudoku-solver/9924/29 "2025-05-08T17:06:57Z")

</div>

With your program in my machine, I’m getting 18 ms for the hard one. I think the main difference between our implementations is that you recurse. Fans of functional programming languages downplay the cost of function calling, but iteration always does better than recursing.  
Also, I think storing both `value` and `options` in your `Cell` is slowing you down. It’s redundant information, if there’s only one option, that is the value.

---

<div class="post-metadata">

**Author:** ![ericlang](https://ziggit.dev/user_avatar/ziggit.dev/ericlang/32/8515_2.png) [@ericlang](https://ziggit.dev/u/ericlang)\
**Post date:** [May 8, 2025, 7:28pm UTC](https://ziggit.dev/t/i-wrote-a-simple-sudoku-solver/9924/30 "2025-05-08T19:28:49Z")

</div>

even in debug mode i get 12.85ms. Do I have a faster computer?  
But you are right in both cases (recursion, double data). My algo is not supposed to be the absolute fastest in the universe, but fast enough and very short code.

---

<div class="post-metadata">

**Author:** ![LucasSantos91](https://ziggit.dev/user_avatar/ziggit.dev/lucassantos91/32/440_2.png) [@LucasSantos91](https://ziggit.dev/u/LucasSantos91)\
**Post date:** [May 8, 2025, 8:01pm UTC](https://ziggit.dev/t/i-wrote-a-simple-sudoku-solver/9924/31 "2025-05-08T20:01:39Z")

</div>

> [@ericlang](#):
>
> even in debug mode i get 12.85ms. Do I have a faster computer?

I presume so. My processor is a Ryzen 3600X.

---

<div class="post-metadata">

**Author:** ![ericlang](https://ziggit.dev/user_avatar/ziggit.dev/ericlang/32/8515_2.png) [@ericlang](https://ziggit.dev/u/ericlang)\
**Post date:** [May 8, 2025, 8:22pm UTC](https://ziggit.dev/t/i-wrote-a-simple-sudoku-solver/9924/32 "2025-05-08T20:22:56Z")

</div>

I will try yours as well here. Hope it works with Zig 0.14

---

<div class="post-metadata">

**Author:** ![ericlang](https://ziggit.dev/user_avatar/ziggit.dev/ericlang/32/8515_2.png) [@ericlang](https://ziggit.dev/u/ericlang)\
**Post date:** [May 27, 2026, 7:18pm UTC](https://ziggit.dev/t/i-wrote-a-simple-sudoku-solver/9924/33 "2026-05-27T19:18:38Z")

</div>

CodeGolf style. Difficult ones take some time 🙂

```zig
const Z=@import("std");const P=Z.debug.print;const U=u64;var S:[99]U=@splat(0);var X:U=0;var Y:U=0;var f:U=0;
pub fn main()void{G("403500096507800300080000054000706023000020000950304000790000060004007508830005409");}
fn G(s:[]const u8)void{for(0..81)|i|{S[i]=s[i]-48;if(S[i]>0)f+=1;}R(0);for(0..81)|i|{P("{}",.{S[i]});}P("\n",.{});}
fn R(Q:U)void{var q=Q;while(S[q]>0)q+=1;if(f<81){for(1..10)|t|{S[q]=t;f+=1;if(V(q)<4)R(q);if(f>80)if(V(q)<4)return;S[q]=0;f-=1;}}}
fn V(Q:U)U{var g:U=0;Y=Q/9;X=Q%9;for(0..9)|i|{if(S[Y*9+i]==S[Q])g+=1;if(S[i*9+X]==S[Q])g+=1;}for(Y-Y%3..Y-Y%3+3)|y|{for(X-X%3..X-X%3+3)|x|{if(S[y*9+x]==S[Q])g+=1;}}return g;}

```

[Previous page](https://ziggit.dev/t/i-wrote-a-simple-sudoku-solver/9924.md?page=1)