Z80 Sudoku — Backtracking Layer

This document defines the depth-first search layer that sits above the deterministic fill loop.

Design Goals

• Select unsolved cell with minimum candidate count (>1).

• Detect contradiction (zero candidates) early.

• Push guess frame to stack.

• Recurse using deterministic propagation first.

• Restore state cleanly on failure.

Stack Frame Layout

; Stack frame (per recursion level)
; +0  Cell address (low)
; +1  Cell address (high)
; +2  Candidate mask (low byte)
; +3  Candidate mask (high byte)

High-Level Flow

SOLVE:
    CALL FILL_DETERMINISTIC
    CALL FIND_MIN_CELL      ; Z = solved, C = contradiction
    JR Z, SOLVED
    JR C, FAIL

TRY_NEXT:
    CALL EXTRACT_LOWEST_BIT ; returns digit in A, mask updated
    CALL WRITE_GUESS        ; write digit to (HL) low nibble
    CALL SOLVE
    JR Z, SUCCESS

    CALL RESTORE_CELL       ; write 0 to low nibble
    CALL CLEAR_TRIED_BIT
    JR NZ, TRY_NEXT

FAIL:
    RET                     ; backtrack

SOLVED:
    XOR A                   ; Z flag set
    RET

SUCCESS:
    XOR A                   ; Z flag set
    RET

Cell Selection Strategy

FIND_MIN_CELL scans all 81 cells, computing candidate masks and counting bits. The cell with the smallest count (>1) is selected to minimise branching factor.

Integration

Board base address: $A000.

Low nibble (bits 0–3) = value (0–9).

High nibble reserved for workspace.

The solver now consists of propagation + depth-first search.