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
1 Like
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!
3 Likes
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.
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);
}
1 Like
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. 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?
This was a cool challenge. It motivated me to write my own solver. Here’s the link.
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.
1 Like
From the land of Algorithmia, there’s Knuth’s “Dancing Links” algorithm for solving Sudoku as a constraint problem:
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 !
1 Like
Haha yesterday I did the same:
easy: 4.3 microseconds
difficult: 2.5 milliseconds
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 }
};
1 Like
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.
1 Like
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.
1 Like
I presume so. My processor is a Ryzen 3600X.
I will try yours as well here. Hope it works with Zig 0.14