Both toys are one architecture. core/tape.zig is the shared engine: a search emits an event tape — place a piece, remove a piece, one byte per event — and the display just walks a cursor over that tape, applying events forward or inverting them backward. That single idea is what makes every animation pausable and scrubbable in both directions: rewinding is not a feature bolted onto the search, it falls out of the data structure. The engine also owns the red overlay: a square where a piece was placed, found doomed, and pulled off ("empty and ever-touched" — the two are the same thing, because a square's events strictly alternate place/remove).
Each toy is then just a machine: knight.zig precomputes the knight-move
graph at compile time and runs a depth-first search for a full tour; queens.zig
runs the classic row-by-row eight-queens search with column/diagonal bitmasks. A machine
implements four things — target_count, genOne (one search
transition, one event), resetMachine, and its own "impossible right now"
overlay (the indigo squares: unreachable for the knight, attacked for the queens). The
shared wasm ABI is emitted from one list, so the toys cannot drift apart.
Everything above compiles to a freestanding WebAssembly module of a few kilobytes — no allocator, no imports, no JS framework. The browser side, board.js, is deliberately dumb: it draws the 64 move numbers and two overlay masks the wasm exposes, and forwards clicks. These are the exact sources the live modules are built from, embedded into the server binary at build time. Also on GitHub.
//! tape — the shared substrate every chess toy is built on: an EVENT TAPE
//! (place piece / remove piece, one byte per event) plus the display that
//! replays it. The tape is what makes the animations scrubbable: the search
//! MACHINE (owned by the toy — knight.zig, queens.zig) only ever appends
//! events at the tape's end; the DISPLAY walks a cursor over the tape,
//! applying events forward or inverting them backward. Events are
//! self-inverting because a remove always pulls the most recent piece.
//!
//! A toy instantiates `Substrate(@This())` and provides:
//! target_count: u32 — pieces on board that mean SOLVED
//! genOne() void — run the machine one transition, appending
//! exactly one event (or setting `exhausted`)
//! resetMachine() void — clear the machine's own state
//! computeImpossible() void — refresh the toy's "no piece can live here
//! right now" overlay (its own mask + export)
//! then emits the shared wasm ABI with `exportAbi` — the single authority
//! for the export list, so the two toys can't drift apart.
//!
//! The dead-end overlay is substrate: dead_end[sq] = a piece was placed
//! there, found doomed, and pulled off — and none has come back. Because a
//! square's events strictly alternate place/remove, that is exactly "empty
//! AND touched by any event", so it falls out of the per-square `tried`
//! counter and stays correct under scrubbing in either direction.
pub fn Substrate(comptime Toy: type) type {
return struct {
// ---------- the event tape ----------
// One byte per event: bit 7 set = place, clear = remove; low 6 bits
// = square.
pub const PLACE_BIT: u8 = 0x80;
pub const TAPE_CAP: u32 = 1 << 22;
pub var tape: [TAPE_CAP]u8 = undefined;
pub var tape_len: u32 = 0;
// ---------- the display (what the board shows) ----------
pub var cur: u32 = 0; // events [0..cur) are applied to the board
pub var board: [64]i8 = [_]i8{-1} ** 64; // move number per square, -1 = empty
pub var on_board: u32 = 0; // pieces currently shown (= next move number)
pub var tried: [64]u32 = [_]u32{0} ** 64; // events touching each square in [0..cur)
// ---------- machine-facing state (lives at the tape's end) ----------
pub var started = false;
pub var solved = false;
pub var exhausted = false; // the machine sets this when its search space is spent
var gen_pieces: u32 = 0; // pieces at the tape's END (the machine's board depth)
var best_depth: u32 = 0; // deepest the SEARCH has ever been
/// appendPlace / appendRemove are the machine's only way to speak:
/// each appends one event at the tape's end and keeps the
/// generation-side piece count (and the solved flag) true. The
/// machine's own bookkeeping — stacks, attack masks — stays in the toy.
pub fn appendPlace(sq: u8) void {
tape[tape_len] = PLACE_BIT | sq;
tape_len += 1;
gen_pieces += 1;
if (gen_pieces > best_depth) best_depth = gen_pieces;
if (gen_pieces == Toy.target_count) solved = true;
}
pub fn appendRemove(sq: u8) void {
tape[tape_len] = sq;
tape_len += 1;
gen_pieces -= 1;
}
// ---------- the shared wasm ABI (emitted by exportAbi) ----------
/// reset returns to the no-search state (the hover-the-graph warmup
/// screen).
pub fn reset() callconv(.c) void {
tape_len = 0;
cur = 0;
board = [_]i8{-1} ** 64;
tried = [_]u32{0} ** 64;
on_board = 0;
started = false;
solved = false;
exhausted = false;
gen_pieces = 0;
best_depth = 0;
Toy.resetMachine();
}
/// stepForward advances the display one event, asking the machine to
/// generate it first when the cursor is at the tape's end. Returns 1
/// if it moved.
pub fn stepForward() callconv(.c) u32 {
if (!started) return 0;
if (cur == tape_len and !solved and !exhausted and tape_len < TAPE_CAP) Toy.genOne();
if (cur == tape_len) return 0; // solved / exhausted: nothing more to show
const ev = tape[cur];
cur += 1;
const sq = ev & 63;
tried[sq] += 1;
if (ev & PLACE_BIT != 0) {
board[sq] = @intCast(on_board);
on_board += 1;
} else {
on_board -= 1;
board[sq] = -1;
}
return 1;
}
/// stepBack rewinds the display one event (inverting it). Returns 1
/// if it moved.
pub fn stepBack() callconv(.c) u32 {
if (cur == 0) return 0;
cur -= 1;
const ev = tape[cur];
const sq = ev & 63;
tried[sq] -= 1;
if (ev & PLACE_BIT != 0) {
on_board -= 1;
board[sq] = -1;
} else {
board[sq] = @intCast(on_board);
on_board += 1;
}
return 1;
}
/// boardPtr is the display board in linear memory: 64 bytes of i8,
/// the move number per square (0 = the first piece) or -1 for empty.
/// (usize = u32 on wasm32; this also compiles natively for tests.)
pub fn boardPtr() callconv(.c) usize {
return @intFromPtr(&board);
}
// dead_end[sq] = 1 when a piece was placed there, its continuations
// were explored and found barren, and it was pulled off — and no
// piece has come back since. Marked only at retraction (discovery),
// never predictively; removal cascades accumulate marks.
pub var dead_end: [64]u8 = [_]u8{0} ** 64;
/// computeOverlays refreshes both display overlays — the substrate's
/// dead_end mask and the toy's "impossible right now" mask. Both are
/// pure functions of the displayed position, so they are exactly as
/// scrubbed as the pieces are. The host calls it once per drawn frame.
pub fn computeOverlays() callconv(.c) void {
for (0..64) |sq| {
dead_end[sq] = @intFromBool(board[sq] < 0 and tried[sq] > 0);
}
Toy.computeImpossible();
}
pub fn deadEndPtr() callconv(.c) usize {
return @intFromPtr(&dead_end);
}
pub fn piecesOnBoard() callconv(.c) u32 {
return on_board;
}
pub fn targetCount() callconv(.c) u32 {
return Toy.target_count;
}
pub fn cursor() callconv(.c) u32 {
return cur;
}
pub fn tapeLen() callconv(.c) u32 {
return tape_len;
}
/// bestDepth is the deepest partial solution the SEARCH has reached
/// so far (not the display) — the "closest it's gotten" HUD stat.
pub fn bestDepth() callconv(.c) u32 {
return best_depth;
}
pub fn isStarted() callconv(.c) u32 {
return @intFromBool(started);
}
pub fn isSolved() callconv(.c) u32 {
return @intFromBool(solved);
}
pub fn isExhausted() callconv(.c) u32 {
return @intFromBool(exhausted);
}
};
}
/// exportAbi emits the shared wasm exports from an instantiated substrate.
/// Called once from a `comptime` block in each toy root, so there is exactly
/// one list of what the JS host may call.
pub fn exportAbi(comptime S: type) void {
inline for (.{
"reset", "stepForward", "stepBack", "boardPtr",
"computeOverlays", "deadEndPtr", "piecesOnBoard", "targetCount",
"cursor", "tapeLen", "bestDepth", "isStarted",
"isSolved", "isExhausted",
}) |name| {
@export(&@field(S, name), .{ .name = name });
}
}
//! knight — the Knight's Tour machine: a precomputed knight-move graph plus a
//! stepwise DFS that tries to visit all 64 squares exactly once. Built on the
//! shared tape substrate (../core/tape.zig), which owns the scrubbable event
//! tape, the display, and the dead-end overlay; this module owns only what is
//! knight-shaped — the graph, the search, and the unreachability overlay. The
//! JS host (board.js) owns the canvas and input; every decision is zig's.
//!
//! Move order is degree-ascending (a frozen Warnsdorff: try the target square
//! with the fewest onward moves first), measured empirically — naive geometric
//! order fails to finish from 54 of 64 starts within 200M events, while this
//! order completes every start within 2,520,884 events (g6, the worst; b2 is a
//! backtrack-free 64). The pinned tests below freeze those numbers.
const std = @import("std");
const tape = @import("core/tape.zig").Substrate(@This());
comptime {
@import("core/tape.zig").exportAbi(tape);
}
/// 64 knights on the board = a complete tour.
pub const target_count: u32 = 64;
// ---------- the precomputed graph ----------
const Graph = struct {
nbrs: [64][8]u8,
count: [64]u8,
};
fn buildGraph() Graph {
@setEvalBranchQuota(200_000);
const deltas = [8][2]i8{
.{ 1, 2 }, .{ 2, 1 }, .{ 2, -1 }, .{ 1, -2 },
.{ -1, -2 }, .{ -2, -1 }, .{ -2, 1 }, .{ -1, 2 },
};
var g: Graph = .{ .nbrs = undefined, .count = [_]u8{0} ** 64 };
for (0..64) |sq| {
const r: i8 = @intCast(sq / 8);
const c: i8 = @intCast(sq % 8);
for (deltas) |d| {
const nr = r + d[0];
const nc = c + d[1];
if (nr < 0 or nr > 7 or nc < 0 or nc > 7) continue;
g.nbrs[sq][g.count[sq]] = @intCast(nr * 8 + nc);
g.count[sq] += 1;
}
}
// Reorder each square's list degree-ascending (insertion sort; ties keep
// the geometric order above, which the pinned counts freeze).
for (0..64) |sq| {
var i: usize = 1;
while (i < g.count[sq]) : (i += 1) {
const v = g.nbrs[sq][i];
var j = i;
while (j > 0 and g.count[g.nbrs[sq][j - 1]] > g.count[v]) : (j -= 1) {
g.nbrs[sq][j] = g.nbrs[sq][j - 1];
}
g.nbrs[sq][j] = v;
}
}
return g;
}
const graph = buildGraph();
// ---------- the machine (generates events at the tape's end) ----------
var stack_sq: [64]u8 = undefined;
var stack_idx: [64]u8 = undefined; // next neighbor index to try at that depth
var stack_len: u32 = 0;
var visited: u64 = 0;
fn bit(sq: u8) u64 {
return @as(u64, 1) << @intCast(sq);
}
fn pushKnight(sq: u8) void {
visited |= bit(sq);
stack_sq[stack_len] = sq;
stack_idx[stack_len] = 0;
stack_len += 1;
tape.appendPlace(sq);
}
/// genOne runs the DFS machine one transition, appending exactly one event —
/// place the next reachable knight, or pull the dead-ended one off. The
/// substrate calls it only while the search is live.
pub fn genOne() void {
const top = stack_len - 1;
const sq = stack_sq[top];
var idx = stack_idx[top];
while (idx < graph.count[sq]) : (idx += 1) {
const nb = graph.nbrs[sq][idx];
if (visited & bit(nb) == 0) {
stack_idx[top] = idx + 1;
pushKnight(nb);
return;
}
}
// dead end: pull this knight off the board
visited &= ~bit(sq);
stack_len -= 1;
if (stack_len == 0) tape.exhausted = true; // no tour from this start (never on 8x8)
tape.appendRemove(sq);
}
pub fn resetMachine() void {
stack_len = 0;
visited = 0;
}
// ---------- exports (the knight-specific ABI) ----------
/// init starts a fresh tour search from `start_sq` (0..63) and applies the
/// first place event, so the clicked square shows its knight immediately.
pub export fn init(start_sq: u32) void {
tape.reset();
tape.started = true;
pushKnight(@intCast(start_sq & 63));
_ = tape.stepForward();
}
// impossible[sq] = 1 when the square is empty and PROVABLY out of reach: the
// tour, extending forward from the current head, can never enter it — no
// path of empty squares connects the head to it. Stronger and colder than a
// dead-end mark; where both hold the host paints this one.
var impossible: [64]u8 = [_]u8{0} ** 64;
/// computeImpossible floods (BFS) from the head knight through empty squares;
/// empty squares the flood never reaches are unreachable. At a literal dead
/// end (head has no empty neighbor) every empty square is, announcing the
/// imminent backtrack. Called by the substrate's computeOverlays.
pub fn computeImpossible() void {
impossible = [_]u8{0} ** 64;
if (tape.on_board == 0 or tape.on_board == 64) return;
var head: u8 = 0;
for (tape.board, 0..) |n, sq| {
if (n == @as(i8, @intCast(tape.on_board - 1))) head = @intCast(sq);
}
var reached: u64 = 0; // empty squares the tour can still enter
var queue: [64]u8 = undefined;
var q_len: usize = 0;
for (graph.nbrs[head][0..graph.count[head]]) |nb| {
if (tape.board[nb] < 0) {
reached |= bit(nb);
queue[q_len] = nb;
q_len += 1;
}
}
while (q_len > 0) {
q_len -= 1;
const sq = queue[q_len];
for (graph.nbrs[sq][0..graph.count[sq]]) |nb| {
if (tape.board[nb] < 0 and reached & bit(nb) == 0) {
reached |= bit(nb);
queue[q_len] = nb;
q_len += 1;
}
}
}
for (0..64) |sq| {
if (tape.board[sq] < 0 and reached & bit(@intCast(sq)) == 0) impossible[sq] = 1;
}
}
pub export fn impossiblePtr() usize {
return @intFromPtr(&impossible);
}
/// adjPtr / adjCountsPtr / adjStride expose the precomputed move graph as a
/// flat [64][stride]u8 plus a per-square count. The host reads them once —
/// the hover highlights ARE this graph.
pub export fn adjPtr() usize {
return @intFromPtr(&graph.nbrs);
}
pub export fn adjCountsPtr() usize {
return @intFromPtr(&graph.count);
}
pub export fn adjStride() u32 {
return 8;
}
// ---------- tests (native: ops/check_chess) ----------
test "graph shape: degrees, symmetry, 336 edges" {
var total: u32 = 0;
for (0..64) |sq| {
total += graph.count[sq];
// every edge is symmetric
for (graph.nbrs[sq][0..graph.count[sq]]) |nb| {
var back = false;
for (graph.nbrs[nb][0..graph.count[nb]]) |x| {
if (x == sq) back = true;
}
try std.testing.expect(back);
}
}
try std.testing.expectEqual(@as(u32, 336), total);
try std.testing.expectEqual(@as(u8, 2), graph.count[0]); // a1 corner
try std.testing.expectEqual(@as(u8, 8), graph.count[27]); // d4 center
}
test "every start square reaches a full tour within the tape" {
for (0..64) |sq| {
init(@intCast(sq));
while (tape.stepForward() == 1) {}
try std.testing.expectEqual(@as(u32, 1), tape.isSolved());
try std.testing.expectEqual(@as(u32, 64), tape.piecesOnBoard());
try std.testing.expect(tape.tape_len < tape.TAPE_CAP);
// a solved board is a permutation: every move number 0..63 exactly once
var seen: u64 = 0;
for (tape.board) |n| {
try std.testing.expect(n >= 0);
seen |= @as(u64, 1) << @intCast(n);
}
try std.testing.expectEqual(~@as(u64, 0), seen);
}
tape.reset();
}
test "pinned event counts freeze the move ordering" {
// b2 glides backtrack-free (64 places); g6 is the marathon. If either
// number moves, the graph ordering changed and the toy plays differently.
const pins = [_]struct { sq: u32, events: u32 }{
.{ .sq = 9, .events = 64 }, // b2
.{ .sq = 46, .events = 2_520_884 }, // g6
};
for (pins) |p| {
init(p.sq);
while (tape.stepForward() == 1) {}
try std.testing.expectEqual(p.events, tape.tape_len);
}
tape.reset();
}
test "overlays: both stay empty on a backtrack-free tour, sound when backtracking" {
// b2 glides to a tour with zero removals: no square is ever retracted
// (no dead_end), and since placements only shrink the empty subgraph, a
// square that went unreachable could never be filled — contradiction with
// completion, so impossible must stay empty too.
init(9);
while (true) {
tape.computeOverlays();
for (impossible) |d| try std.testing.expectEqual(@as(u8, 0), d);
for (tape.dead_end) |d| try std.testing.expectEqual(@as(u8, 0), d);
if (tape.stepForward() == 0) break;
}
// e4 backtracks (3876 events). At every step: an impossible square is
// empty; its empty neighbors are impossible too (a reachable neighbor
// would reach it); no empty neighbor of the head is impossible (it's
// placeable right now); and dead_end is exactly "empty and ever touched".
init(28);
var saw_impossible = false;
var saw_dead_end = false;
while (true) {
tape.computeOverlays();
var head: usize = 0;
for (tape.board, 0..) |n, sq| {
if (n == @as(i8, @intCast(tape.on_board - 1))) head = sq;
}
for (0..64) |sq| {
const expect_de: u8 = @intFromBool(tape.board[sq] < 0 and tape.tried[sq] > 0);
try std.testing.expectEqual(expect_de, tape.dead_end[sq]);
if (tape.dead_end[sq] == 1) saw_dead_end = true;
if (impossible[sq] == 0) continue;
saw_impossible = true;
try std.testing.expect(tape.board[sq] < 0);
for (graph.nbrs[sq][0..graph.count[sq]]) |nb| {
if (tape.board[nb] < 0) try std.testing.expectEqual(@as(u8, 1), impossible[nb]);
}
}
for (graph.nbrs[head][0..graph.count[head]]) |nb| {
if (tape.board[nb] < 0) try std.testing.expectEqual(@as(u8, 0), impossible[nb]);
}
if (tape.stepForward() == 0) break;
}
try std.testing.expect(saw_impossible);
try std.testing.expect(saw_dead_end);
// solved end state: board full, so both overlays are clear
tape.computeOverlays();
for (impossible) |d| try std.testing.expectEqual(@as(u8, 0), d);
for (tape.dead_end) |d| try std.testing.expectEqual(@as(u8, 0), d);
tape.reset();
}
test "dead_end marks appear at retraction, clear on re-entry, scrub cleanly" {
// e4: run to just past the FIRST removal — that square must be marked,
// and one step back (knight restored) must unmark it.
init(28);
var removed_sq: usize = 65;
while (removed_sq == 65) {
const before = tape.piecesOnBoard();
try std.testing.expectEqual(@as(u32, 1), tape.stepForward());
if (tape.piecesOnBoard() < before) {
for (0..64) |sq| {
if (tape.tried[sq] > 0 and tape.board[sq] < 0) removed_sq = sq;
}
}
}
tape.computeOverlays();
try std.testing.expectEqual(@as(u8, 1), tape.dead_end[removed_sq]);
_ = tape.stepBack();
tape.computeOverlays();
try std.testing.expectEqual(@as(u8, 0), tape.dead_end[removed_sq]);
try std.testing.expect(tape.board[removed_sq] >= 0);
// scrub all the way home: every counter zero, no marks anywhere
while (tape.stepBack() == 1) {}
tape.computeOverlays();
for (tape.tried) |t| try std.testing.expectEqual(@as(u32, 0), t);
for (tape.dead_end) |d| try std.testing.expectEqual(@as(u8, 0), d);
tape.reset();
}
test "scrubbing back and forth restores the exact board" {
init(28); // e4
for (0..1000) |_| _ = tape.stepForward();
const snap_board = tape.board;
const snap_on = tape.on_board;
for (0..500) |_| _ = tape.stepForward();
for (0..500) |_| try std.testing.expectEqual(@as(u32, 1), tape.stepBack());
try std.testing.expectEqual(snap_on, tape.on_board);
try std.testing.expectEqualSlices(i8, &snap_board, &tape.board);
// and replaying forward from a rewound cursor agrees with the tape
// (init itself applied event 0, hence 1 + 1000 + 500)
for (0..500) |_| _ = tape.stepForward();
try std.testing.expectEqual(@as(u32, 1501), tape.cursor());
tape.reset();
}
//! queens — the Eight Queens machine: place 8 queens so none attacks another.
//! Built on the same tape substrate as the Knight's Tour (core/tape.zig): the
//! search appends place/remove events, the display scrubs them, and the two
//! overlays keep their meanings — red = a queen was placed here, found doomed,
//! and retracted; indigo = no queen can live here right now (attacked).
//!
//! The click PINS the first queen: it is move 0, it is never retracted, and
//! the machine fills the OTHER seven rows top-to-bottom around it (one queen
//! per row by construction, so the search branches only on columns). The
//! classic n-queens DFS: try the next non-attacked column in this row, else
//! pull the previous row's queen and resume from its next column.
const std = @import("std");
const tape = @import("core/tape.zig").Substrate(@This());
comptime {
@import("core/tape.zig").exportAbi(tape);
}
/// 8 queens on the board = a solution.
pub const target_count: u32 = 8;
// ---------- the machine (generates events at the tape's end) ----------
var pin_sq: u8 = 0;
var rows: [7]u8 = undefined; // the rows the machine fills, in order (pin's row skipped)
var stack_col: [7]u8 = undefined; // chosen column per filled row
var stack_idx: [7]u8 = undefined; // next column to try at that row
var stack_len: u32 = 0;
// attack masks, pinned queen included. One queen per row by construction, so
// only columns and the two diagonal families can conflict.
var cols_used: u8 = 0;
var diag_sum: u15 = 0; // r+c, 0..14
var diag_diff: u15 = 0; // r-c+7, 0..14
fn setAttack(r: u8, c: u8, on: bool) void {
const cb = @as(u8, 1) << @intCast(c);
const sb = @as(u15, 1) << @intCast(r + c);
const db = @as(u15, 1) << @intCast(r + 7 - c);
if (on) {
cols_used |= cb;
diag_sum |= sb;
diag_diff |= db;
} else {
cols_used &= ~cb;
diag_sum &= ~sb;
diag_diff &= ~db;
}
}
fn attacked(r: u8, c: u8) bool {
return (cols_used & (@as(u8, 1) << @intCast(c))) != 0 or
(diag_sum & (@as(u15, 1) << @intCast(r + c))) != 0 or
(diag_diff & (@as(u15, 1) << @intCast(r + 7 - c))) != 0;
}
/// genOne runs the DFS one transition, appending exactly one event — place a
/// queen in the next open column of the current row, or (no column fits) pull
/// the previous row's queen. The substrate calls it only while the search is
/// live; solved is set by the substrate when the 8th queen lands.
pub fn genOne() void {
const r = rows[stack_len];
var c = stack_idx[stack_len];
while (c < 8) : (c += 1) {
if (!attacked(r, c)) {
stack_idx[stack_len] = c + 1;
stack_col[stack_len] = c;
setAttack(r, c, true);
stack_len += 1;
if (stack_len < rows.len) stack_idx[stack_len] = 0;
tape.appendPlace(r * 8 + c);
return;
}
}
// no column works in this row: backtrack to the previous machine row
if (stack_len == 0) {
tape.exhausted = true; // no solution with this pin
return;
}
stack_len -= 1;
const pr = rows[stack_len];
const pc = stack_col[stack_len];
setAttack(pr, pc, false);
tape.appendRemove(pr * 8 + pc);
}
pub fn resetMachine() void {
stack_len = 0;
cols_used = 0;
diag_sum = 0;
diag_diff = 0;
}
// ---------- exports (the queens-specific ABI) ----------
/// init pins the first queen at `sq` and starts the search; the pinned queen
/// shows immediately and is never retracted.
pub export fn init(sq: u32) void {
tape.reset();
tape.started = true;
pin_sq = @intCast(sq & 63);
const pr: u8 = pin_sq / 8;
setAttack(pr, pin_sq % 8, true);
var n: usize = 0;
for (0..8) |r| {
if (r != pr) {
rows[n] = @intCast(r);
n += 1;
}
}
stack_idx[0] = 0;
tape.appendPlace(pin_sq);
_ = tape.stepForward();
}
// impossible[sq] = 1 when the square is empty and ATTACKED — it shares a row,
// column, or diagonal with a queen on the display board, so no queen can live
// there right now. (The n-queens constraint ignores blocking, so whole lines
// are marked.) Same meaning as the knight's mask: provably unplaceable now.
var impossible: [64]u8 = [_]u8{0} ** 64;
/// computeImpossible recomputes the attacked mask from the DISPLAY board — a
/// pure function of the shown position, exact under scrubbing. Called by the
/// substrate's computeOverlays.
pub fn computeImpossible() void {
impossible = [_]u8{0} ** 64;
for (tape.board, 0..) |n, q| {
if (n < 0) continue;
const qr: i32 = @intCast(q / 8);
const qc: i32 = @intCast(q % 8);
for (0..64) |sq| {
if (tape.board[sq] >= 0) continue;
const r: i32 = @intCast(sq / 8);
const c: i32 = @intCast(sq % 8);
if (r == qr or c == qc or r + c == qr + qc or r - c == qr - qc) impossible[sq] = 1;
}
}
}
pub export fn impossiblePtr() usize {
return @intFromPtr(&impossible);
}
// ---------- the hover graph: every square a queen there would attack ----------
const Adj = struct {
at: [64][27]u8, // 27 = the center-square maximum (7 row + 7 col + 13 diagonal)
count: [64]u8,
};
fn buildAdj() Adj {
@setEvalBranchQuota(500_000);
var a: Adj = .{ .at = undefined, .count = [_]u8{0} ** 64 };
for (0..64) |sq| {
const r: i32 = @intCast(sq / 8);
const c: i32 = @intCast(sq % 8);
for (0..64) |other| {
if (other == sq) continue;
const or_: i32 = @intCast(other / 8);
const oc: i32 = @intCast(other % 8);
if (or_ == r or oc == c or or_ + oc == r + c or or_ - oc == r - c) {
a.at[sq][a.count[sq]] = @intCast(other);
a.count[sq] += 1;
}
}
}
return a;
}
const adj = buildAdj();
pub export fn adjPtr() usize {
return @intFromPtr(&adj.at);
}
pub export fn adjCountsPtr() usize {
return @intFromPtr(&adj.count);
}
pub export fn adjStride() u32 {
return 27;
}
// ---------- tests (native: ops/check_chess) ----------
test "attack graph shape: corner 21, center 27, symmetric" {
try std.testing.expectEqual(@as(u8, 21), adj.count[0]); // a1
try std.testing.expectEqual(@as(u8, 27), adj.count[27]); // d4
var total: u32 = 0;
for (0..64) |sq| {
total += adj.count[sq];
for (adj.at[sq][0..adj.count[sq]]) |other| {
var back = false;
for (adj.at[other][0..adj.count[other]]) |x| {
if (x == sq) back = true;
}
try std.testing.expect(back);
}
}
// 64 squares x (7 row + 7 col) + diagonal pairs x2; the frozen total
try std.testing.expectEqual(@as(u32, 1456), total);
}
test "every pin square either solves or exhausts honestly; solutions are legal" {
var solved_pins: u32 = 0;
for (0..64) |sq| {
init(@intCast(sq));
while (tape.stepForward() == 1) {}
if (tape.isSolved() == 1) {
solved_pins += 1;
try std.testing.expectEqual(@as(u32, 8), tape.piecesOnBoard());
// legality: no two queens share a row, column, or diagonal
var qs: [8]u8 = undefined;
var n: usize = 0;
for (tape.board, 0..) |v, s| {
if (v >= 0) {
qs[n] = @intCast(s);
n += 1;
}
}
try std.testing.expectEqual(@as(usize, 8), n);
for (0..8) |i| {
for (i + 1..8) |j| {
const ar: i32 = qs[i] / 8;
const ac: i32 = qs[i] % 8;
const br: i32 = qs[j] / 8;
const bc: i32 = qs[j] % 8;
try std.testing.expect(ar != br and ac != bc);
try std.testing.expect(ar + ac != br + bc and ar - ac != br - bc);
}
}
// the pin survived as move 0
try std.testing.expectEqual(@as(i8, 0), tape.board[sq]);
} else {
// honest exhaustion: the machine unwound completely, only the
// pinned queen remains at the tape's end
try std.testing.expectEqual(@as(u32, 1), tape.isExhausted());
}
}
// EVERY square of the 8x8 board is part of some 8-queens solution — the
// classic fact, rediscovered here: no pin exhausts.
try std.testing.expectEqual(@as(u32, 64), solved_pins);
tape.reset();
}
test "pinned event counts freeze the search order" {
// Frozen empirically like the knight's: if these move, row/column order
// changed and the toy animates differently. d4 nearly glides; the g8
// corner region is the marathon (306 events, the 64-pin maximum).
const pins = [_]struct { sq: u32, events: u32 }{
.{ .sq = 0, .events = 218 }, // a1
.{ .sq = 27, .events = 20 }, // d4
.{ .sq = 62, .events = 306 }, // g8, the worst pin
};
for (pins) |p| {
init(p.sq);
while (tape.stepForward() == 1) {}
try std.testing.expectEqual(@as(u32, 1), tape.isSolved());
try std.testing.expectEqual(p.events, tape.tape_len);
}
tape.reset();
}
test "overlays: attacked mask matches the constraint at every step" {
init(0); // a1's search backtracks plenty
var saw_dead_end = false;
while (true) {
tape.computeOverlays();
for (0..64) |sq| {
// recompute attacked independently
var att = false;
for (tape.board, 0..) |v, q| {
if (v < 0 or q == sq) continue;
const qr: i32 = @intCast(q / 8);
const qc: i32 = @intCast(q % 8);
const r: i32 = @intCast(sq / 8);
const c: i32 = @intCast(sq % 8);
if (r == qr or c == qc or r + c == qr + qc or r - c == qr - qc) att = true;
}
const expect_imp: u8 = @intFromBool(tape.board[sq] < 0 and att);
try std.testing.expectEqual(expect_imp, impossible[sq]);
const expect_de: u8 = @intFromBool(tape.board[sq] < 0 and tape.tried[sq] > 0);
try std.testing.expectEqual(expect_de, tape.dead_end[sq]);
if (tape.dead_end[sq] == 1) saw_dead_end = true;
}
if (tape.stepForward() == 0) break;
}
try std.testing.expect(saw_dead_end);
tape.reset();
}
test "scrubbing restores the exact board and the pin" {
init(0);
for (0..40) |_| _ = tape.stepForward();
const snap_board = tape.board;
const snap_on = tape.on_board;
for (0..30) |_| _ = tape.stepForward();
for (0..30) |_| _ = tape.stepBack();
try std.testing.expectEqual(snap_on, tape.on_board);
try std.testing.expectEqualSlices(i8, &snap_board, &tape.board);
// full rewind: even the pin unwinds from the DISPLAY (event 0), board empty
while (tape.stepBack() == 1) {}
try std.testing.expectEqual(@as(u32, 0), tape.piecesOnBoard());
tape.reset();
}
// board — the ONLY non-zig piece of the chess toys, and deliberately dumb. It
// owns no search logic: the toy's wasm (knight.wasm, queens.wasm — same ABI,
// emitted by core/tape.zig's exportAbi) holds the precomputed move graph, the
// search machine, and the scrubbable event tape; this just draws the board
// state the wasm exposes (64 bytes of move numbers + two overlay masks) and
// forwards input — click to start a search, hover to see the graph, transport
// controls to play/scrub. One host serves every toy: the page shell sets
// window.CHESS_TOY (wasm url + wording); everything numeric comes from the
// wasm itself. Plain hand-written JS (no TS, no bundler).
const TOY = window.CHESS_TOY; // set by the page shell; absent = a real bug
const SQ = 68, W = SQ * 8;
const LIGHT = '#f0d9b5', DARK = '#b58863';
async function main() {
document.body.style.cssText =
'margin:0;background:#0b0b0d;min-height:100vh;display:flex;flex-direction:column;' +
'align-items:center;justify-content:center;gap:12px;' +
'font-family:ui-monospace,Menlo,monospace;color:#cfd2d6';
const nav = document.createElement('div');
nav.innerHTML = '<a href="/chess" style="color:#8a93a0">chess toys</a>' +
'<span style="color:#4a4d55"> · </span>' +
'<a href="/chess/code" style="color:#8a93a0">under the hood</a>';
nav.style.cssText = 'font-size:12px;letter-spacing:0.4px';
document.body.appendChild(nav);
const title = document.createElement('div');
title.textContent = TOY.title;
title.style.cssText = 'font-size:20px;letter-spacing:1px;color:#e8e2d6';
document.body.appendChild(title);
const canvas = document.createElement('canvas');
canvas.width = W;
canvas.height = W;
canvas.style.cssText = 'display:block;box-shadow:0 10px 40px rgba(0,0,0,0.6);cursor:pointer';
document.body.appendChild(canvas);
const ctx = canvas.getContext('2d');
const status = document.createElement('div');
status.style.cssText = 'font-size:13px;color:#9aa0a6;min-height:18px';
document.body.appendChild(status);
// transport row: rewind ‹ step · play/pause · step › + the speed slider
const controls = document.createElement('div');
controls.style.cssText = 'display:flex;align-items:center;gap:8px';
const btnCss = 'background:#1d1f24;color:#cfd2d6;border:1px solid #33363d;border-radius:4px;' +
'padding:5px 12px;font:13px ui-monospace,Menlo,monospace;cursor:pointer';
function button(label, onclick) {
const b = document.createElement('button');
b.textContent = label;
b.style.cssText = btnCss;
b.addEventListener('click', onclick);
controls.appendChild(b);
return b;
}
const rewindBtn = button('⏪ rewind', () => setMode(mode === -1 ? 0 : -1));
button('◂ step', () => { setMode(0); wasm.stepBack(); });
const playBtn = button('▶ play', () => setMode(mode === 1 ? 0 : 1));
button('step ▸', () => { setMode(0); wasm.stepForward(); });
const speed = document.createElement('input');
speed.type = 'range';
speed.min = '0'; speed.max = '17'; speed.value = '3'; // steps/s = 2 << value
speed.style.cssText = 'width:140px;accent-color:#8a93a0';
const speedLabel = document.createElement('span');
speedLabel.style.cssText = 'font-size:12px;color:#9aa0a6;width:80px';
controls.appendChild(speed);
controls.appendChild(speedLabel);
document.body.appendChild(controls);
const hint = document.createElement('div');
hint.textContent = `hover · ${TOY.hoverHint} click · ${TOY.clickHint} SPACE play/pause · ←/→ step`;
hint.style.cssText = 'font-size:12px;color:#6d7278;letter-spacing:0.4px';
document.body.appendChild(hint);
const legend = document.createElement('div');
legend.textContent = `red · a ${TOY.noun1} was retracted here indigo · ${TOY.indigoHint}`;
legend.style.cssText = 'font-size:12px;color:#6d7278;letter-spacing:0.4px';
document.body.appendChild(legend);
const { instance } = await WebAssembly.instantiateStreaming(fetch(TOY.wasm), {});
const wasm = instance.exports;
const target = wasm.targetCount();
const board = new Int8Array(wasm.memory.buffer, wasm.boardPtr(), 64);
const deadEnd = new Uint8Array(wasm.memory.buffer, wasm.deadEndPtr(), 64);
const impossible = new Uint8Array(wasm.memory.buffer, wasm.impossiblePtr(), 64);
// the precomputed move graph, read once — the hover highlights ARE this graph
const stride = wasm.adjStride();
const adj = new Uint8Array(wasm.memory.buffer, wasm.adjPtr(), 64 * stride);
const adjCounts = new Uint8Array(wasm.memory.buffer, wasm.adjCountsPtr(), 64);
let mode = 0; // 0 paused · 1 playing · -1 rewinding
let hover = -1; // hovered square or -1
let acc = 0; // fractional steps owed to the clock
function setMode(m) {
mode = m;
acc = 0;
playBtn.textContent = mode === 1 ? '⏸ pause' : '▶ play';
rewindBtn.textContent = mode === -1 ? '⏸ pause' : '⏪ rewind';
}
function stepsPerSec() { return 2 << Number(speed.value); }
// square index <-> canvas position (rank 8 drawn at the top, a1 lower-left)
function sqX(sq) { return (sq % 8) * SQ; }
function sqY(sq) { return (7 - (sq >> 3)) * SQ; }
function sqAt(px, py) {
const c = Math.floor(px / SQ), r = 7 - Math.floor(py / SQ);
return (c < 0 || c > 7 || r < 0 || r > 7) ? -1 : r * 8 + c;
}
function draw() {
const pieces = wasm.piecesOnBoard();
// squares + coordinates (letters along rank 1, numbers up file a)
for (let sq = 0; sq < 64; sq++) {
const x = sqX(sq), y = sqY(sq);
const light = ((sq >> 3) + (sq & 7)) % 2 === 1;
ctx.fillStyle = light ? LIGHT : DARK;
ctx.fillRect(x, y, SQ, SQ);
ctx.fillStyle = light ? DARK : LIGHT;
ctx.font = '10px ui-monospace,Menlo,monospace';
if (sq >> 3 === 0) {
ctx.textAlign = 'right'; ctx.textBaseline = 'bottom';
ctx.fillText('abcdefgh'[sq & 7], x + SQ - 3, y + SQ - 2);
}
if ((sq & 7) === 0) {
ctx.textAlign = 'left'; ctx.textBaseline = 'top';
ctx.fillText(String((sq >> 3) + 1), x + 3, y + 2);
}
}
// failure overlays (see core/tape.zig + the toy's computeImpossible):
// red = a piece was placed here, found doomed, and pulled off —
// accumulating through removal cascades, cleared only when the search
// re-enters the square. Indigo = the toy's "no piece can live here right
// now" — the stronger fact, so it wins where both hold.
wasm.computeOverlays();
for (let sq = 0; sq < 64; sq++) {
if (impossible[sq]) {
ctx.fillStyle = 'rgba(80,70,190,0.45)';
ctx.fillRect(sqX(sq), sqY(sq), SQ, SQ);
} else if (deadEnd[sq]) {
ctx.fillStyle = 'rgba(190,40,40,0.5)';
ctx.fillRect(sqX(sq), sqY(sq), SQ, SQ);
}
}
// the newest piece's square glows so the search frontier is easy to track
if (pieces > 0) {
for (let sq = 0; sq < 64; sq++) {
if (board[sq] === pieces - 1) {
ctx.fillStyle = 'rgba(255,214,102,0.5)';
ctx.fillRect(sqX(sq), sqY(sq), SQ, SQ);
}
}
}
// hover: outline the square, mark its graph neighbors (dot = open, ring = occupied)
if (hover >= 0) {
ctx.strokeStyle = 'rgba(70,140,220,0.9)';
ctx.lineWidth = 3;
ctx.strokeRect(sqX(hover) + 1.5, sqY(hover) + 1.5, SQ - 3, SQ - 3);
for (let i = 0; i < adjCounts[hover]; i++) {
const nb = adj[hover * stride + i];
const cx = sqX(nb) + SQ / 2, cy = sqY(nb) + SQ / 2;
ctx.beginPath();
if (board[nb] < 0) {
ctx.fillStyle = 'rgba(60,160,90,0.9)';
ctx.arc(cx, cy, SQ * 0.13, 0, Math.PI * 2);
ctx.fill();
} else {
ctx.strokeStyle = 'rgba(200,60,60,0.85)';
ctx.lineWidth = 3;
ctx.arc(cx, cy, SQ * 0.3, 0, Math.PI * 2);
ctx.stroke();
}
}
}
// the pieces, with their move numbers
for (let sq = 0; sq < 64; sq++) {
const n = board[sq];
if (n < 0) continue;
const x = sqX(sq), y = sqY(sq);
ctx.fillStyle = n === pieces - 1 ? '#7a1f1f' : '#22232a';
ctx.font = `${Math.round(SQ * 0.72)}px serif`;
ctx.textAlign = 'center'; ctx.textBaseline = 'middle';
ctx.fillText(TOY.piece, x + SQ / 2, y + SQ / 2 + 3);
ctx.fillStyle = 'rgba(20,20,25,0.65)';
ctx.font = 'bold 11px ui-monospace,Menlo,monospace';
ctx.textAlign = 'right'; ctx.textBaseline = 'top';
ctx.fillText(String(n + 1), x + SQ - 3, y + 2);
}
drawStatus(pieces);
}
function drawStatus(pieces) {
speedLabel.textContent = stepsPerSec().toLocaleString() + '/s';
if (!wasm.isStarted()) {
status.textContent = TOY.startHint;
return;
}
const cur = wasm.cursor(), len = wasm.tapeLen();
let s = `${pieces}/${target} ${TOY.noun} · step ${cur.toLocaleString()}` +
(cur < len ? ` / ${len.toLocaleString()}` : '') +
` · deepest ${wasm.bestDepth()}`;
if (cur === len) {
if (wasm.isSolved()) s += ` — ${TOY.solvedMsg}`;
else if (wasm.isExhausted()) s += ` — ${TOY.exhaustedMsg}`;
}
status.textContent = s;
}
canvas.addEventListener('mousemove', (e) => {
const r = canvas.getBoundingClientRect();
hover = sqAt(e.clientX - r.left, e.clientY - r.top);
});
canvas.addEventListener('mouseleave', () => { hover = -1; });
canvas.addEventListener('click', (e) => {
const r = canvas.getBoundingClientRect();
const sq = sqAt(e.clientX - r.left, e.clientY - r.top);
if (sq < 0) return;
wasm.init(sq);
setMode(1);
});
window.addEventListener('keydown', (e) => {
if (e.code === 'Space') { setMode(mode === 1 ? 0 : 1); e.preventDefault(); }
else if (e.code === 'ArrowRight') { setMode(0); wasm.stepForward(); e.preventDefault(); }
else if (e.code === 'ArrowLeft') { setMode(0); wasm.stepBack(); e.preventDefault(); }
});
let lastT = performance.now();
function loop(t) {
const dt = Math.min((t - lastT) / 1000, 0.1); // clamp a slept tab's backlog
lastT = t;
if (mode !== 0) {
acc += stepsPerSec() * dt;
let n = Math.floor(acc);
acc -= n;
while (n-- > 0) {
if (!(mode === 1 ? wasm.stepForward() : wasm.stepBack())) { setMode(0); break; }
}
}
draw();
requestAnimationFrame(loop);
}
requestAnimationFrame(loop);
}
main();