Z80 Sudoku Challenge – Algorithm

Candidate Representation

Each candidate set represented as 9-bit mask in 16-bit register pair (lower 9 bits used).Bit 0 = digit 1, Bit 8 = digit 9.

Constraint Propagation

For each UNKN cell: compute row, column, and 3x3 box exclusions.

If only one candidate remains, fill cell and repeat sweep.

Concrete Candidate Mask Builder (Z80-Level Plan)

Routine:

BuildMask:
    ; IN:  HL = address of cell
    ; OUT: BC = 9-bit candidate mask
    ;      Z set if mask == 0 (contradiction)

    LD BC,01FFh        ; start with all digits allowed

Row scan: iterate 9 cells, clear bits for digits present (1–9 mapped to bit 0–8). Use DJNZ for loop control and ADD HL,HL for 16-bit shifts when constructing digit masks.

Column scan: same exclusion logic, stepping pointer by +9 each iteration.

Box scan: compute 3x3 base via (row/3)27 + (col/3)3, then nested 3x3 loops.

Single-candidate detection via power-of-two test on BC.

Backtracking

Select cell with minimal candidate count >1.

Push necessary state to stack.

Try each candidate in turn (depth-first).

On contradiction, pop state and try next candidate.

Rejected Alternatives

Pure brute force without propagation (inefficient).Exact cover / dancing links (too complex for Z80 constraints).