<!-- canonical: https://efficientnewlanguage.org/eml-p/projects/P040-sudoku-helper/ | updated: 2026-10-10 -->

# P040 Sudoku helper

A 4 x 4 or 9 x 9 sudoku, built in or typed in: put numbers in and take them out with a warning the moment one clashes, check the board (including when it can no longer be completed), ask for a hint that names one sure step, or let a backtracking solver finish it and say whether the solution is the only one.

EML-P project `projects/sudoku-helper` in the EML language repo: 3 module(s), entry `main.eml`, terminal UI. There, `eml project run projects/sudoku-helper` runs it and `eml project verify projects/sudoku-helper` replays every session under CPython (two hash seeds) and in the interpreter; the site build replays every session in the interpreter again and publishes a session only if its screen matches.

Built on verified corpus cases: sudoku-solver-4x4 (https://efficientnewlanguage.org/cases/124-sudoku-solver-4x4/).

## Sessions

### bad-input - interpreter: byte-equal to the golden

Input:

```text
0
x
2
4
6
1
0
5
x

1
4
5
9
12345678
1234567890
abc......
.253.4179
.3.....6.
.7.2.1.83
982.4..5.
564..78..
317825946
24.5..69.
75......8
.98......
5
2
1 1
10 1 1
1 1 0
1 2 9

3
1 1
3
1 2

6
1
4
4
11..
....
....
....
1
4
4
1...
....
....
....
6
8
```

Screen:

```text
== Sudoku helper ==
A 4 x 4 or 9 x 9 sudoku: every row, column and box holds each number once.

1) new puzzle  2) put a number  3) clear a cell  4) check  5) hint  6) solve  7) show  8) quit
choice> 0
Pick a number from 1 to 8.

1) new puzzle  2) put a number  3) clear a cell  4) check  5) hint  6) solve  7) show  8) quit
choice> x
Pick a number from 1 to 8.

1) new puzzle  2) put a number  3) clear a cell  4) check  5) hint  6) solve  7) show  8) quit
choice> 2
Choose a puzzle first.

1) new puzzle  2) put a number  3) clear a cell  4) check  5) hint  6) solve  7) show  8) quit
choice> 4
Choose a puzzle first.

1) new puzzle  2) put a number  3) clear a cell  4) check  5) hint  6) solve  7) show  8) quit
choice> 6
Choose a puzzle first.

1) new puzzle  2) put a number  3) clear a cell  4) check  5) hint  6) solve  7) show  8) quit
choice> 1
  1) 4 x 4, from the corpus case
  2) 9 x 9, easy
  3) 9 x 9, needs guessing
  4) type one in
puzzle> 0
Type a number from 1 to 4.
puzzle> 5
Type a number from 1 to 4.
puzzle> x
Type a number from 1 to 4.
puzzle> 
Cancelled.

1) new puzzle  2) put a number  3) clear a cell  4) check  5) hint  6) solve  7) show  8) quit
choice> 1
  1) 4 x 4, from the corpus case
  2) 9 x 9, easy
  3) 9 x 9, needs guessing
  4) type one in
puzzle> 4
size (4 or 9)> 5
Type 4 or 9.
size (4 or 9)> 9
Type each row as 9 digits from 1 to 9, with . for an empty cell.
row 1> 12345678
A row is 9 digits from 1 to 9 or dots, like "53..7....".
row 1> 1234567890
A row is 9 digits from 1 to 9 or dots, like "53..7....".
row 1> abc......
A row is 9 digits from 1 to 9 or dots, like "53..7....".
row 1> .253.4179
row 2> .3.....6.
row 3> .7.2.1.83
row 4> 982.4..5.
row 5> 564..78..
row 6> 317825946
row 7> 24.5..69.
row 8> 75......8
row 9> .98......
Puzzle taken.
    1 2 3   4 5 6   7 8 9
  +-------+-------+-------+
1 | . 2 5 | 3 . 4 | 1 7 9 |
2 | . 3 . | . . . | . 6 . |
3 | . 7 . | 2 . 1 | . 8 3 |
  +-------+-------+-------+
4 | 9 8 2 | . 4 . | . 5 . |
5 | 5 6 4 | . . 7 | 8 . . |
6 | 3 1 7 | 8 2 5 | 9 4 6 |
  +-------+-------+-------+
7 | 2 4 . | 5 . . | 6 9 . |
8 | 7 5 . | . . . | . . 8 |
9 | . 9 8 | . . . | . . . |
  +-------+-------+-------+
Empty cells: 38.

1) new puzzle  2) put a number  3) clear a cell  4) check  5) hint  6) solve  7) show  8) quit
choice> 5
No single sure step: every empty cell has two or more candidates, and every number two or more places. The solver can try them.

1) new puzzle  2) put a number  3) clear a cell  4) check  5) hint  6) solve  7) show  8) quit
choice> 2
cell (row column number)> 1 1
Type row column number, each from 1 to 9, like 3 4 2.
cell (row column number)> 10 1 1
Type row column number, each from 1 to 9, like 3 4 2.
cell (row column number)> 1 1 0
Type row column number, each from 1 to 9, like 3 4 2.
cell (row column number)> 1 2 9
That cell is part of the puzzle.
cell (row column number)> 
Cancelled.

1) new puzzle  2) put a number  3) clear a cell  4) check  5) hint  6) solve  7) show  8) quit
choice> 3
cell (row column)> 1 1
That cell is already empty.

1) new puzzle  2) put a number  3) clear a cell  4) check  5) hint  6) solve  7) show  8) quit
choice> 3
cell (row column)> 1 2
That cell is part of the puzzle.
cell (row column)> 
Cancelled.

1) new puzzle  2) put a number  3) clear a cell  4) check  5) hint  6) solve  7) show  8) quit
choice> 6
Solved, trying 114 numbers along the way.
    1 2 3   4 5 6   7 8 9
  +-------+-------+-------+
1 | 6 2 5 | 3 8 4 | 1 7 9 |
2 | 8 3 1 | 7 5 9 | 2 6 4 |
3 | 4 7 9 | 2 6 1 | 5 8 3 |
  +-------+-------+-------+
4 | 9 8 2 | 6 4 3 | 7 5 1 |
5 | 5 6 4 | 1 9 7 | 8 3 2 |
6 | 3 1 7 | 8 2 5 | 9 4 6 |
  +-------+-------+-------+
7 | 2 4 3 | 5 1 8 | 6 9 7 |
8 | 7 5 6 | 9 3 2 | 4 1 8 |
9 | 1 9 8 | 4 7 6 | 3 2 5 |
  +-------+-------+-------+
Empty cells: 0.
This is the only solution.

1) new puzzle  2) put a number  3) clear a cell  4) check  5) hint  6) solve  7) show  8) quit
choice> 1
  1) 4 x 4, from the corpus case
  2) 9 x 9, easy
  3) 9 x 9, needs guessing
  4) type one in
puzzle> 4
size (4 or 9)> 4
Type each row as 4 digits from 1 to 4, with . for an empty cell.
row 1> 11..
row 2> ....
row 3> ....
row 4> ....
Those numbers break the rules: Row 1 has two 1s (columns 1 and 2). The puzzle was not taken.

1) new puzzle  2) put a number  3) clear a cell  4) check  5) hint  6) solve  7) show  8) quit
choice> 1
  1) 4 x 4, from the corpus case
  2) 9 x 9, easy
  3) 9 x 9, needs guessing
  4) type one in
puzzle> 4
size (4 or 9)> 4
Type each row as 4 digits from 1 to 4, with . for an empty cell.
row 1> 1...
row 2> ....
row 3> ....
row 4> ....
Puzzle taken.
    1 2   3 4
  +-----+-----+
1 | 1 . | . . |
2 | . . | . . |
  +-----+-----+
3 | . . | . . |
4 | . . | . . |
  +-----+-----+
Empty cells: 15.

1) new puzzle  2) put a number  3) clear a cell  4) check  5) hint  6) solve  7) show  8) quit
choice> 6
Solved, trying 19 numbers along the way.
    1 2   3 4
  +-----+-----+
1 | 1 2 | 3 4 |
2 | 3 4 | 1 2 |
  +-----+-----+
3 | 2 1 | 4 3 |
4 | 4 3 | 2 1 |
  +-----+-----+
Empty cells: 0.
There is more than one solution; this is the first one found.

1) new puzzle  2) put a number  3) clear a cell  4) check  5) hint  6) solve  7) show  8) quit
choice> 8
Bye.
```

### basic - interpreter: byte-equal to the golden

Input:

```text
1
2
5
2
5 5 5
2
1 3 5
4
3
1 3
2
1,3,1
4
3
1 3
5
6
1
3
5
6
1
1
6
8
```

Screen:

```text
== Sudoku helper ==
A 4 x 4 or 9 x 9 sudoku: every row, column and box holds each number once.

1) new puzzle  2) put a number  3) clear a cell  4) check  5) hint  6) solve  7) show  8) quit
choice> 1
  1) 4 x 4, from the corpus case
  2) 9 x 9, easy
  3) 9 x 9, needs guessing
  4) type one in
puzzle> 2
Puzzle: 9 x 9, easy.
    1 2 3   4 5 6   7 8 9
  +-------+-------+-------+
1 | 5 3 . | . 7 . | . . . |
2 | 6 . . | 1 9 5 | . . . |
3 | . 9 8 | . . . | . 6 . |
  +-------+-------+-------+
4 | 8 . . | . 6 . | . . 3 |
5 | 4 . . | 8 . 3 | . . 1 |
6 | 7 . . | . 2 . | . . 6 |
  +-------+-------+-------+
7 | . 6 . | . . . | 2 8 . |
8 | . . . | 4 1 9 | . . 5 |
9 | . . . | . 8 . | . 7 9 |
  +-------+-------+-------+
Empty cells: 51.

1) new puzzle  2) put a number  3) clear a cell  4) check  5) hint  6) solve  7) show  8) quit
choice> 5
Row 5, column 5 can only be 5: its row, column and box hold every other number.

1) new puzzle  2) put a number  3) clear a cell  4) check  5) hint  6) solve  7) show  8) quit
choice> 2
cell (row column number)> 5 5 5
Row 5, column 5 is now 5.

1) new puzzle  2) put a number  3) clear a cell  4) check  5) hint  6) solve  7) show  8) quit
choice> 2
cell (row column number)> 1 3 5
Row 1, column 3 is now 5.
It clashes: Row 1 has two 5s (columns 1 and 3).
It clashes: Box 1 has two 5s (cells 1-1 and 1-3).

1) new puzzle  2) put a number  3) clear a cell  4) check  5) hint  6) solve  7) show  8) quit
choice> 4
Row 1 has two 5s (columns 1 and 3).
Box 1 has two 5s (cells 1-1 and 1-3).

1) new puzzle  2) put a number  3) clear a cell  4) check  5) hint  6) solve  7) show  8) quit
choice> 3
cell (row column)> 1 3
Row 1, column 3 is empty again.

1) new puzzle  2) put a number  3) clear a cell  4) check  5) hint  6) solve  7) show  8) quit
choice> 2
cell (row column number)> 1,3,1
Row 1, column 3 is now 1.

1) new puzzle  2) put a number  3) clear a cell  4) check  5) hint  6) solve  7) show  8) quit
choice> 4
No clashes, but the board can no longer be completed: some number put in is wrong. 49 cells are empty.

1) new puzzle  2) put a number  3) clear a cell  4) check  5) hint  6) solve  7) show  8) quit
choice> 3
cell (row column)> 1 3
Row 1, column 3 is empty again.

1) new puzzle  2) put a number  3) clear a cell  4) check  5) hint  6) solve  7) show  8) quit
choice> 5
Row 5, column 2 can only be 2: its row, column and box hold every other number.

1) new puzzle  2) put a number  3) clear a cell  4) check  5) hint  6) solve  7) show  8) quit
choice> 6
Solved, trying 50 numbers along the way.
    1 2 3   4 5 6   7 8 9
  +-------+-------+-------+
1 | 5 3 4 | 6 7 8 | 9 1 2 |
2 | 6 7 2 | 1 9 5 | 3 4 8 |
3 | 1 9 8 | 3 4 2 | 5 6 7 |
  +-------+-------+-------+
4 | 8 5 9 | 7 6 1 | 4 2 3 |
5 | 4 2 6 | 8 5 3 | 7 9 1 |
6 | 7 1 3 | 9 2 4 | 8 5 6 |
  +-------+-------+-------+
7 | 9 6 1 | 5 3 7 | 2 8 4 |
8 | 2 8 7 | 4 1 9 | 6 3 5 |
9 | 3 4 5 | 2 8 6 | 1 7 9 |
  +-------+-------+-------+
Empty cells: 0.
This is the only solution.

1) new puzzle  2) put a number  3) clear a cell  4) check  5) hint  6) solve  7) show  8) quit
choice> 1
  1) 4 x 4, from the corpus case
  2) 9 x 9, easy
  3) 9 x 9, needs guessing
  4) type one in
puzzle> 3
Puzzle: 9 x 9, needs guessing.
    1 2 3   4 5 6   7 8 9
  +-------+-------+-------+
1 | . . 5 | 3 . 4 | . 7 . |
2 | . 3 . | . . . | . . . |
3 | . . . | 2 . 1 | . 8 3 |
  +-------+-------+-------+
4 | 9 8 2 | . 4 . | . 5 . |
5 | 5 . . | . . 7 | . . . |
6 | . 1 . | 8 2 . | . 4 . |
  +-------+-------+-------+
7 | 2 . . | 5 . . | 6 9 . |
8 | 7 5 . | . . . | . . 8 |
9 | . . 8 | . . . | . . . |
  +-------+-------+-------+
Empty cells: 53.

1) new puzzle  2) put a number  3) clear a cell  4) check  5) hint  6) solve  7) show  8) quit
choice> 5
Row 7, column 2 can only be 4: its row, column and box hold every other number.

1) new puzzle  2) put a number  3) clear a cell  4) check  5) hint  6) solve  7) show  8) quit
choice> 6
Solved, trying 150 numbers along the way.
    1 2 3   4 5 6   7 8 9
  +-------+-------+-------+
1 | 6 2 5 | 3 8 4 | 1 7 9 |
2 | 8 3 1 | 7 5 9 | 2 6 4 |
3 | 4 7 9 | 2 6 1 | 5 8 3 |
  +-------+-------+-------+
4 | 9 8 2 | 6 4 3 | 7 5 1 |
5 | 5 6 4 | 1 9 7 | 8 3 2 |
6 | 3 1 7 | 8 2 5 | 9 4 6 |
  +-------+-------+-------+
7 | 2 4 3 | 5 1 8 | 6 9 7 |
8 | 7 5 6 | 9 3 2 | 4 1 8 |
9 | 1 9 8 | 4 7 6 | 3 2 5 |
  +-------+-------+-------+
Empty cells: 0.
This is the only solution.

1) new puzzle  2) put a number  3) clear a cell  4) check  5) hint  6) solve  7) show  8) quit
choice> 1
  1) 4 x 4, from the corpus case
  2) 9 x 9, easy
  3) 9 x 9, needs guessing
  4) type one in
puzzle> 1
Puzzle: 4 x 4, from the corpus case.
    1 2   3 4
  +-----+-----+
1 | 1 . | . . |
2 | . . | 3 . |
  +-----+-----+
3 | . 4 | . . |
4 | . . | . 2 |
  +-----+-----+
Empty cells: 12.

1) new puzzle  2) put a number  3) clear a cell  4) check  5) hint  6) solve  7) show  8) quit
choice> 6
Solved, trying 12 numbers along the way.
    1 2   3 4
  +-----+-----+
1 | 1 3 | 2 4 |
2 | 4 2 | 3 1 |
  +-----+-----+
3 | 2 4 | 1 3 |
4 | 3 1 | 4 2 |
  +-----+-----+
Empty cells: 0.
This is the only solution.

1) new puzzle  2) put a number  3) clear a cell  4) check  5) hint  6) solve  7) show  8) quit
choice> 8
Bye.
```

## Modules

### main.eml

```eml
# P040 sudoku helper: a 4 x 4 or 9 x 9 sudoku, built in or typed in. Put
# numbers in and take them out - the helper says at once when a number
# clashes - check the whole board, ask for a hint that names one sure step,
# or let the solver finish it and say whether the solution is the only one.
import board
import puzzles

def trim(s):
    0 => i
    len(s) => j
    while i < j and s[i] == " ":
        i + 1 => i
    while j > i and s[j - 1] == " ":
        j - 1 => j
    return s[i:j]

def words(s):
    [] => out
    "" => word
    for c in s + " ":
        if c == " " or c == ",":
            if word != "":
                out + [word] => out
            "" => word
        else:
            word + c => word
    return out

def number(s):
    if s == "" or len(s) > 2:
        return -1
    0 => n
    for c in s:
        if not (c in "0123456789"):
            return -1
        n * 10 + int(c) => n
    return n

def parsed(rows, n):
    # Rows of digits and "." (or 0) as a grid; [] if a row does not fit.
    [] => g
    for row in rows:
        [] => cells
        for ch in row:
            if ch == "." or ch == "0":
                cells + [0] => cells
            elif ch in "123456789" and int(ch) <= n:
                cells + [int(ch)] => cells
            elif ch != " ":
                return []
        if len(cells) != n:
            return []
        g + [cells] => g
    return g

def show(g):
    len(g) => n
    board.box_size(n) => b
    "    " => header
    for c in [1:n]:
        header + str(c) => header
        if c % b == 0 and c < n:
            header + "   " => header
        elif c < n:
            header + " " => header
    header ^0
    ("  +" + ("-" * (2 * b + 1) + "+") * b) => rule
    rule ^0
    for r in [0:n - 1]:
        str(r + 1) + " |" => line
        for c in [0:n - 1]:
            if g[r][c] == 0:
                line + " ." => line
            else:
                line + " " + str(g[r][c]) => line
            if c % b == b - 1:
                line + " |" => line
        line ^0
        if r % b == b - 1:
            rule ^0
    ("Empty cells: " + str(board.empty_cells(g)) + ".") ^0

def small_first(name):
    # "Row 5" as "row 5" (the names start with R, C or B).
    "RCB" => big
    "rcb" => small
    for i in [0:2]:
        if name[0] == big[i]:
            return small[i] + name[1:len(name)]
    return name

def plural(v):
    return str(v) + "s"

def clash_text(cf):
    # ["Row 3", 5, cells] as "Row 3 has two 5s (columns 2 and 7)."
    cf[0] => name
    cf[2] => cells
    ["", "", "two", "three", "four", "five", "six", "seven", "eight", "nine"] => counts
    "" => where
    if name[0:3] == "Row":
        "columns" => kind
    elif name[0:3] == "Col":
        "rows" => kind
    else:
        "cells" => kind
    for i in [0:len(cells) - 1]:
        if i > 0 and i == len(cells) - 1:
            where + " and " => where
        elif i > 0:
            where + ", " => where
        if kind == "columns":
            where + str(cells[i][1] + 1) => where
        elif kind == "rows":
            where + str(cells[i][0] + 1) => where
        else:
            where + str(cells[i][0] + 1) + "-" + str(cells[i][1] + 1) => where
    return name + " has " + counts[len(cells)] + " " + plural(cf[1]) + " (" + kind + " " + where + ")."

def new_puzzle(state):
    for i in [0:len(puzzles.puzzles) - 1]:
        ("  " + str(i + 1) + ") " + puzzles.puzzles[i][0]) ^0
    ("  " + str(len(puzzles.puzzles) + 1) + ") type one in") ^0
    while True:
        trim(input("puzzle> ")) => answer
        if answer == "":
            "Cancelled." ^0
            return state
        number(answer) => k
        if k >= 1 and k <= len(puzzles.puzzles):
            parsed(puzzles.puzzles[k - 1][1], len(puzzles.puzzles[k - 1][1])) => g
            ("Puzzle: " + puzzles.puzzles[k - 1][0] + ".") ^0
            show(g)
            return [g, given_of(g)]
        if k == len(puzzles.puzzles) + 1:
            return typed(state)
        ("Type a number from 1 to " + str(len(puzzles.puzzles) + 1) + ".") ^0

def given_of(g):
    [] => out
    for row in g:
        [] => marks
        for v in row:
            marks + [v != 0] => marks
        out + [marks] => out
    return out

def typed(state):
    0 => n
    while n == 0:
        trim(input("size (4 or 9)> ")) => answer
        if answer == "":
            "Cancelled." ^0
            return state
        if answer == "4" or answer == "9":
            int(answer) => n
        else:
            "Type 4 or 9." ^0
    ("Type each row as " + str(n) + " digits from 1 to " + str(n) + ", with . for an empty cell.") ^0
    [] => rows
    while len(rows) < n:
        trim(input("row " + str(len(rows) + 1) + "> ")) => answer
        if answer == "":
            "Cancelled." ^0
            return state
        if len(parsed([answer], n)) == 0:
            "1..4" => example
            if n == 9:
                "53..7...." => example
            ("A row is " + str(n) + " digits from 1 to " + str(n) + " or dots, like \"" + example + "\".") ^0
        else:
            rows + [answer] => rows
    parsed(rows, n) => g
    board.conflicts(g) => cf
    if len(cf) > 0:
        ("Those numbers break the rules: " + clash_text(cf[0]) + " The puzzle was not taken.") ^0
        return state
    "Puzzle taken." ^0
    show(g)
    return [g, given_of(g)]

def put(state, clearing):
    state[0] => g
    state[1] => given
    if len(g) == 0:
        "Choose a puzzle first." ^0
        return state
    len(g) => n
    "row column number" => shape
    if clearing:
        "row column" => shape
    while True:
        trim(input("cell (" + shape + ")> ")) => answer
        if answer == "":
            "Cancelled." ^0
            return state
        words(answer) => ws
        [] => xs
        for w in ws:
            xs + [number(w)] => xs
        if clearing and len(xs) == 2:
            xs + [0] => xs
        if len(xs) != 3 or xs[0] < 1 or xs[0] > n or xs[1] < 1 or xs[1] > n or xs[2] < 0 or xs[2] > n or (xs[2] == 0 and not clearing):
            "3 4 2" => example
            if clearing:
                "3 4" => example
            ("Type " + shape + ", each from 1 to " + str(n) + ", like " + example + ".") ^0
        elif given[xs[0] - 1][xs[1] - 1]:
            "That cell is part of the puzzle." ^0
        else:
            xs[0] - 1 => r
            xs[1] - 1 => c
            if clearing:
                if g[r][c] == 0:
                    "That cell is already empty." ^0
                    return state
                0 => g[r][c]
                ("Row " + str(r + 1) + ", column " + str(c + 1) + " is empty again.") ^0
                return state
            xs[2] => g[r][c]
            ("Row " + str(r + 1) + ", column " + str(c + 1) + " is now " + str(xs[2]) + ".") ^0
            for cf in board.conflicts(g):
                False => mine
                for cell in cf[2]:
                    if cell[0] == r and cell[1] == c:
                        True => mine
                if mine and cf[1] == xs[2]:
                    ("It clashes: " + clash_text(cf)) ^0
            if board.empty_cells(g) == 0 and len(board.conflicts(g)) == 0:
                "The puzzle is complete - well done!" ^0
            return state

def check(g):
    board.conflicts(g) => cf
    if len(cf) > 0:
        for x in cf:
            clash_text(x) ^0
        return 0
    if board.empty_cells(g) == 0:
        "No clashes, and every cell is filled: the puzzle is solved." ^0
        return 0
    board.solve(g) => s
    if s[0] == 0:
        ("No clashes, but the board can no longer be completed: some number put in is wrong. " + str(board.empty_cells(g)) + " cells are empty.") ^0
    else:
        ("No clashes so far; " + str(board.empty_cells(g)) + " cells to go.") ^0
    return 0

def hint(g):
    if len(board.conflicts(g)) > 0:
        "Fix the clashes first - check lists them." ^0
        return 0
    if board.empty_cells(g) == 0:
        "Every cell is filled." ^0
        return 0
    board.naked_single(g) => ns
    if len(ns) > 0 and ns[2] == 0:
        ("Row " + str(ns[0] + 1) + ", column " + str(ns[1] + 1) + " has no possible number: something put in is wrong.") ^0
        return 0
    if len(ns) > 0:
        ("Row " + str(ns[0] + 1) + ", column " + str(ns[1] + 1) + " can only be " + str(ns[2]) + ": its row, column and box hold every other number.") ^0
        return 0
    board.hidden_single(g) => hs
    if len(hs) > 0:
        ("In " + small_first(hs[0]) + ", " + str(hs[1]) + " fits only at row " + str(hs[2] + 1) + ", column " + str(hs[3] + 1) + ".") ^0
        return 0
    "No single sure step: every empty cell has two or more candidates, and every number two or more places. The solver can try them." ^0
    return 0

def solve(state):
    state[0] => g
    if len(board.conflicts(g)) > 0:
        "Fix the clashes first - check lists them." ^0
        return state
    board.solve(g) => s
    if s[0] == 0:
        ("No solution from here: some number put in is wrong (" + str(s[2]) + " numbers tried).") ^0
        return state
    ("Solved, trying " + str(s[2]) + " numbers along the way.") ^0
    show(s[1])
    if s[0] == 1:
        "This is the only solution." ^0
    else:
        "There is more than one solution; this is the first one found." ^0
    return [s[1], state[1]]

"== Sudoku helper ==" ^0
"A 4 x 4 or 9 x 9 sudoku: every row, column and box holds each number once." ^0
[[], []] => state
True => running
while running:
    "" ^0
    "1) new puzzle  2) put a number  3) clear a cell  4) check  5) hint  6) solve  7) show  8) quit" ^0
    trim(input("choice> ")) => choice
    if choice == "1":
        new_puzzle(state) => state
    elif choice == "2" or choice == "3":
        put(state, choice == "3") => state
    elif choice == "8":
        False => running
    elif choice == "4" or choice == "5" or choice == "6" or choice == "7":
        if len(state[0]) == 0:
            "Choose a puzzle first." ^0
        elif choice == "4":
            check(state[0])
        elif choice == "5":
            hint(state[0])
        elif choice == "6":
            solve(state) => state
        else:
            show(state[0])
    else:
        "Pick a number from 1 to 8." ^0
"Bye." ^0
```

Python projection of main.eml:

```python
import board
import puzzles

def trim(s):
    i = 0
    j = len(s)
    while i < j and s[i] == " ":
        i = i + 1
    while j > i and s[j - 1] == " ":
        j = j - 1
    return s[i:j]

def words(s):
    out = []
    word = ""
    for c in s + " ":
        if c == " " or c == ",":
            if word != "":
                out = out + [word]
            word = ""
        else:
            word = word + c
    return out

def number(s):
    if s == "" or len(s) > 2:
        return -1
    n = 0
    for c in s:
        if not c in "0123456789":
            return -1
        n = n * 10 + int(c)
    return n

def parsed(rows, n):
    g = []
    for row in rows:
        cells = []
        for ch in row:
            if ch == "." or ch == "0":
                cells = cells + [0]
            elif ch in "123456789" and int(ch) <= n:
                cells = cells + [int(ch)]
            elif ch != " ":
                return []
        if len(cells) != n:
            return []
        g = g + [cells]
    return g

def show(g):
    n = len(g)
    b = board.box_size(n)
    header = "    "
    for c in range(1, n+1):
        header = header + str(c)
        if c % b == 0 and c < n:
            header = header + "   "
        elif c < n:
            header = header + " "
    print(header)
    rule = "  +" + ("-" * (2 * b + 1) + "+") * b
    print(rule)
    for r in range(0, n):
        line = str(r + 1) + " |"
        for c in range(0, n):
            if g[r][c] == 0:
                line = line + " ."
            else:
                line = line + " " + str(g[r][c])
            if c % b == b - 1:
                line = line + " |"
        print(line)
        if r % b == b - 1:
            print(rule)
    print("Empty cells: " + str(board.empty_cells(g)) + ".")

def small_first(name):
    big = "RCB"
    small = "rcb"
    for i in range(0, 3):
        if name[0] == big[i]:
            return small[i] + name[1:len(name)]
    return name

def plural(v):
    return str(v) + "s"

def clash_text(cf):
    name = cf[0]
    cells = cf[2]
    counts = ["", "", "two", "three", "four", "five", "six", "seven", "eight", "nine"]
    where = ""
    if name[0:3] == "Row":
        kind = "columns"
    elif name[0:3] == "Col":
        kind = "rows"
    else:
        kind = "cells"
    for i in range(0, len(cells)):
        if i > 0 and i == len(cells) - 1:
            where = where + " and "
        elif i > 0:
            where = where + ", "
        if kind == "columns":
            where = where + str(cells[i][1] + 1)
        elif kind == "rows":
            where = where + str(cells[i][0] + 1)
        else:
            where = where + str(cells[i][0] + 1) + "-" + str(cells[i][1] + 1)
    return name + " has " + counts[len(cells)] + " " + plural(cf[1]) + " (" + kind + " " + where + ")."

def new_puzzle(state):
    for i in range(0, len(puzzles.puzzles)):
        print("  " + str(i + 1) + ") " + puzzles.puzzles[i][0])
    print("  " + str(len(puzzles.puzzles) + 1) + ") type one in")
    while True:
        answer = trim(input("puzzle> "))
        if answer == "":
            print("Cancelled.")
            return state
        k = number(answer)
        if k >= 1 and k <= len(puzzles.puzzles):
            g = parsed(puzzles.puzzles[k - 1][1], len(puzzles.puzzles[k - 1][1]))
            print("Puzzle: " + puzzles.puzzles[k - 1][0] + ".")
            show(g)
            return [g, given_of(g)]
        if k == len(puzzles.puzzles) + 1:
            return typed(state)
        print("Type a number from 1 to " + str(len(puzzles.puzzles) + 1) + ".")

def given_of(g):
    out = []
    for row in g:
        marks = []
        for v in row:
            marks = marks + [v != 0]
        out = out + [marks]
    return out

def typed(state):
    n = 0
    while n == 0:
        answer = trim(input("size (4 or 9)> "))
        if answer == "":
            print("Cancelled.")
            return state
        if answer == "4" or answer == "9":
            n = int(answer)
        else:
            print("Type 4 or 9.")
    print("Type each row as " + str(n) + " digits from 1 to " + str(n) + ", with . for an empty cell.")
    rows = []
    while len(rows) < n:
        answer = trim(input("row " + str(len(rows) + 1) + "> "))
        if answer == "":
            print("Cancelled.")
            return state
        if len(parsed([answer], n)) == 0:
            example = "1..4"
            if n == 9:
                example = "53..7...."
            print("A row is " + str(n) + " digits from 1 to " + str(n) + " or dots, like \"" + example + "\".")
        else:
            rows = rows + [answer]
    g = parsed(rows, n)
    cf = board.conflicts(g)
    if len(cf) > 0:
        print("Those numbers break the rules: " + clash_text(cf[0]) + " The puzzle was not taken.")
        return state
    print("Puzzle taken.")
    show(g)
    return [g, given_of(g)]

def put(state, clearing):
    g = state[0]
    given = state[1]
    if len(g) == 0:
        print("Choose a puzzle first.")
        return state
    n = len(g)
    shape = "row column number"
    if clearing:
        shape = "row column"
    while True:
        answer = trim(input("cell (" + shape + ")> "))
        if answer == "":
            print("Cancelled.")
            return state
        ws = words(answer)
        xs = []
        for w in ws:
            xs = xs + [number(w)]
        if clearing and len(xs) == 2:
            xs = xs + [0]
        if len(xs) != 3 or xs[0] < 1 or xs[0] > n or xs[1] < 1 or xs[1] > n or xs[2] < 0 or xs[2] > n or xs[2] == 0 and not clearing:
            example = "3 4 2"
            if clearing:
                example = "3 4"
            print("Type " + shape + ", each from 1 to " + str(n) + ", like " + example + ".")
        elif given[xs[0] - 1][xs[1] - 1]:
            print("That cell is part of the puzzle.")
        else:
            r = xs[0] - 1
            c = xs[1] - 1
            if clearing:
                if g[r][c] == 0:
                    print("That cell is already empty.")
                    return state
                g[r][c] = 0
                print("Row " + str(r + 1) + ", column " + str(c + 1) + " is empty again.")
                return state
            g[r][c] = xs[2]
            print("Row " + str(r + 1) + ", column " + str(c + 1) + " is now " + str(xs[2]) + ".")
            for cf in board.conflicts(g):
                mine = False
                for cell in cf[2]:
                    if cell[0] == r and cell[1] == c:
                        mine = True
                if mine and cf[1] == xs[2]:
                    print("It clashes: " + clash_text(cf))
            if board.empty_cells(g) == 0 and len(board.conflicts(g)) == 0:
                print("The puzzle is complete - well done!")
            return state

def check(g):
    cf = board.conflicts(g)
    if len(cf) > 0:
        for x in cf:
            print(clash_text(x))
        return 0
    if board.empty_cells(g) == 0:
        print("No clashes, and every cell is filled: the puzzle is solved.")
        return 0
    s = board.solve(g)
    if s[0] == 0:
        print("No clashes, but the board can no longer be completed: some number put in is wrong. " + str(board.empty_cells(g)) + " cells are empty.")
    else:
        print("No clashes so far; " + str(board.empty_cells(g)) + " cells to go.")
    return 0

def hint(g):
    if len(board.conflicts(g)) > 0:
        print("Fix the clashes first - check lists them.")
        return 0
    if board.empty_cells(g) == 0:
        print("Every cell is filled.")
        return 0
    ns = board.naked_single(g)
    if len(ns) > 0 and ns[2] == 0:
        print("Row " + str(ns[0] + 1) + ", column " + str(ns[1] + 1) + " has no possible number: something put in is wrong.")
        return 0
    if len(ns) > 0:
        print("Row " + str(ns[0] + 1) + ", column " + str(ns[1] + 1) + " can only be " + str(ns[2]) + ": its row, column and box hold every other number.")
        return 0
    hs = board.hidden_single(g)
    if len(hs) > 0:
        print("In " + small_first(hs[0]) + ", " + str(hs[1]) + " fits only at row " + str(hs[2] + 1) + ", column " + str(hs[3] + 1) + ".")
        return 0
    print("No single sure step: every empty cell has two or more candidates, and every number two or more places. The solver can try them.")
    return 0

def solve(state):
    g = state[0]
    if len(board.conflicts(g)) > 0:
        print("Fix the clashes first - check lists them.")
        return state
    s = board.solve(g)
    if s[0] == 0:
        print("No solution from here: some number put in is wrong (" + str(s[2]) + " numbers tried).")
        return state
    print("Solved, trying " + str(s[2]) + " numbers along the way.")
    show(s[1])
    if s[0] == 1:
        print("This is the only solution.")
    else:
        print("There is more than one solution; this is the first one found.")
    return [s[1], state[1]]

print("== Sudoku helper ==")
print("A 4 x 4 or 9 x 9 sudoku: every row, column and box holds each number once.")
state = [[], []]
running = True
while running:
    print("")
    print("1) new puzzle  2) put a number  3) clear a cell  4) check  5) hint  6) solve  7) show  8) quit")
    choice = trim(input("choice> "))
    if choice == "1":
        state = new_puzzle(state)
    elif choice == "2" or choice == "3":
        state = put(state, choice == "3")
    elif choice == "8":
        running = False
    elif choice == "4" or choice == "5" or choice == "6" or choice == "7":
        if len(state[0]) == 0:
            print("Choose a puzzle first.")
        elif choice == "4":
            check(state[0])
        elif choice == "5":
            hint(state[0])
        elif choice == "6":
            state = solve(state)
        else:
            show(state[0])
    else:
        print("Pick a number from 1 to 8.")
print("Bye.")
```

### board.eml

```eml
# P040 sudoku helper - the rules. A grid is a list of rows of numbers, 0 for
# an empty cell; it is 4 x 4 (boxes of 2 x 2) or 9 x 9 (boxes of 3 x 3).

def box_size(n):
    if n == 4:
        return 2
    return 3

def candidates(g, r, c):
    # The numbers that may go in (r, c): not yet in its row, its column or
    # its box. The box corner is the cell rounded down to a multiple of the
    # box size, as in the corpus case sudoku-solver-4x4.
    len(g) => n
    box_size(n) => b
    [False] * (n + 1) => used
    for i in [0:n - 1]:
        True => used[g[r][i]]
        True => used[g[i][c]]
    int(r / b) * b => r0
    int(c / b) * b => c0
    for i in [0:b - 1]:
        for j in [0:b - 1]:
            True => used[g[r0 + i][c0 + j]]
    [] => out
    for v in [1:n]:
        if not used[v]:
            out + [v] => out
    return out

def units(n):
    # Every row, column and box as [name, list of (row, column) cells].
    box_size(n) => b
    [] => out
    for r in [0:n - 1]:
        [] => cells
        for c in [0:n - 1]:
            cells + [[r, c]] => cells
        out + [["Row " + str(r + 1), cells]] => out
    for c in [0:n - 1]:
        [] => cells
        for r in [0:n - 1]:
            cells + [[r, c]] => cells
        out + [["Column " + str(c + 1), cells]] => out
    for k in [0:n - 1]:
        int(k / b) * b => r0
        (k % b) * b => c0
        [] => cells
        for i in [0:b - 1]:
            for j in [0:b - 1]:
                cells + [[r0 + i, c0 + j]] => cells
        out + [["Box " + str(k + 1), cells]] => out
    return out

def conflicts(g):
    # Every number that appears more than once in a row, column or box, as
    # [unit name, number, the cells holding it].
    [] => out
    for u in units(len(g)):
        for v in [1:len(g)]:
            [] => where
            for cell in u[1]:
                if g[cell[0]][cell[1]] == v:
                    where + [cell] => where
            if len(where) > 1:
                out + [[u[0], v, where]] => out
    return out

def empty_cells(g):
    0 => n
    for row in g:
        for v in row:
            if v == 0:
                n + 1 => n
    return n

def naked_single(g):
    # The first empty cell, row by row, with exactly one candidate:
    # [row, column, number]; [row, column, 0] for a cell with none; [] if
    # every empty cell has two or more.
    for r in [0:len(g) - 1]:
        for c in [0:len(g) - 1]:
            if g[r][c] == 0:
                candidates(g, r, c) => cs
                if len(cs) == 0:
                    return [r, c, 0]
                if len(cs) == 1:
                    return [r, c, cs[0]]
    return []

def hidden_single(g):
    # A number that has only one possible cell left in some row, column or
    # box: [unit name, number, row, column]; [] if there is none.
    for u in units(len(g)):
        for v in [1:len(g)]:
            False => placed
            [] => spots
            for cell in u[1]:
                g[cell[0]][cell[1]] => x
                if x == v:
                    True => placed
                elif x == 0:
                    for cand in candidates(g, cell[0], cell[1]):
                        if cand == v:
                            spots + [cell] => spots
            if not placed and len(spots) == 1:
                return [u[0], v, spots[0][0], spots[0][1]]
    return []

def search(g, found, tries):
    # Backtracking: fill the empty cell with the fewest candidates, try each
    # in turn, undo on failure. Counts solutions up to 2 (found[0]), keeps
    # the first in found[1], and counts the numbers placed in tries[0]. The
    # scan stops early at a cell with one candidate or none: nothing beats it.
    -1 => best_r
    -1 => best_c
    [] => best
    False => settled
    for r in [0:len(g) - 1]:
        for c in [0:len(g) - 1]:
            if not settled and g[r][c] == 0:
                candidates(g, r, c) => cs
                if best_r == -1 or len(cs) < len(best):
                    r => best_r
                    c => best_c
                    cs => best
                    if len(cs) <= 1:
                        True => settled
    if best_r == -1:
        found[0] + 1 => found[0]
        if found[0] == 1:
            [] => copy
            for row in g:
                copy + [row[0:len(row)]] => copy
            copy => found[1]
        return 0
    for v in best:
        if found[0] < 2:
            tries[0] + 1 => tries[0]
            v => g[best_r][best_c]
            search(g, found, tries)
            0 => g[best_r][best_c]
    return 0

def solve(g):
    # [number of solutions found (0, 1 or 2 meaning "more than one"), the
    # first solution or [], numbers placed while searching].
    [] => work
    for row in g:
        work + [row[0:len(row)]] => work
    [0, []] => found
    [0] => tries
    search(work, found, tries)
    return [found[0], found[1], tries[0]]
```

Python projection of board.eml:

```python
def box_size(n):
    if n == 4:
        return 2
    return 3

def candidates(g, r, c):
    n = len(g)
    b = box_size(n)
    used = [False] * (n + 1)
    for i in range(0, n):
        used[g[r][i]] = True
        used[g[i][c]] = True
    r0 = int(r / b) * b
    c0 = int(c / b) * b
    for i in range(0, b):
        for j in range(0, b):
            used[g[r0 + i][c0 + j]] = True
    out = []
    for v in range(1, n+1):
        if not used[v]:
            out = out + [v]
    return out

def units(n):
    b = box_size(n)
    out = []
    for r in range(0, n):
        cells = []
        for c in range(0, n):
            cells = cells + [[r, c]]
        out = out + [["Row " + str(r + 1), cells]]
    for c in range(0, n):
        cells = []
        for r in range(0, n):
            cells = cells + [[r, c]]
        out = out + [["Column " + str(c + 1), cells]]
    for k in range(0, n):
        r0 = int(k / b) * b
        c0 = k % b * b
        cells = []
        for i in range(0, b):
            for j in range(0, b):
                cells = cells + [[r0 + i, c0 + j]]
        out = out + [["Box " + str(k + 1), cells]]
    return out

def conflicts(g):
    out = []
    for u in units(len(g)):
        for v in range(1, len(g)+1):
            where = []
            for cell in u[1]:
                if g[cell[0]][cell[1]] == v:
                    where = where + [cell]
            if len(where) > 1:
                out = out + [[u[0], v, where]]
    return out

def empty_cells(g):
    n = 0
    for row in g:
        for v in row:
            if v == 0:
                n = n + 1
    return n

def naked_single(g):
    for r in range(0, len(g)):
        for c in range(0, len(g)):
            if g[r][c] == 0:
                cs = candidates(g, r, c)
                if len(cs) == 0:
                    return [r, c, 0]
                if len(cs) == 1:
                    return [r, c, cs[0]]
    return []

def hidden_single(g):
    for u in units(len(g)):
        for v in range(1, len(g)+1):
            placed = False
            spots = []
            for cell in u[1]:
                x = g[cell[0]][cell[1]]
                if x == v:
                    placed = True
                elif x == 0:
                    for cand in candidates(g, cell[0], cell[1]):
                        if cand == v:
                            spots = spots + [cell]
            if not placed and len(spots) == 1:
                return [u[0], v, spots[0][0], spots[0][1]]
    return []

def search(g, found, tries):
    best_r = -1
    best_c = -1
    best = []
    settled = False
    for r in range(0, len(g)):
        for c in range(0, len(g)):
            if not settled and g[r][c] == 0:
                cs = candidates(g, r, c)
                if best_r == -1 or len(cs) < len(best):
                    best_r = r
                    best_c = c
                    best = cs
                    if len(cs) <= 1:
                        settled = True
    if best_r == -1:
        found[0] = found[0] + 1
        if found[0] == 1:
            copy = []
            for row in g:
                copy = copy + [row[0:len(row)]]
            found[1] = copy
        return 0
    for v in best:
        if found[0] < 2:
            tries[0] = tries[0] + 1
            g[best_r][best_c] = v
            search(g, found, tries)
            g[best_r][best_c] = 0
    return 0

def solve(g):
    work = []
    for row in g:
        work = work + [row[0:len(row)]]
    found = [0, []]
    tries = [0]
    search(work, found, tries)
    return [found[0], found[1], tries[0]]
```

### puzzles.eml

```eml
# P040 sudoku helper - the built-in puzzles, one string per row, "." for an
# empty cell. The third was generated for this project: it has one solution,
# but the sure steps the hint knows run out before the end.

[
    ["4 x 4, from the corpus case", ["1...", "..3.", ".4..", "...2"]],
    ["9 x 9, easy", ["53..7....", "6..195...", ".98....6.", "8...6...3", "4..8.3..1", "7...2...6", ".6....28.", "...419..5", "....8..79"]],
    ["9 x 9, needs guessing", ["..53.4.7.", ".3.......", "...2.1.83", "982.4..5.", "5....7...", ".1.82..4.", "2..5..69.", "75......8", "..8......"]],
] => puzzles
```

Python projection of puzzles.eml:

```python
puzzles = [["4 x 4, from the corpus case", ["1...", "..3.", ".4..", "...2"]], ["9 x 9, easy", ["53..7....", "6..195...", ".98....6.", "8...6...3", "4..8.3..1", "7...2...6", ".6....28.", "...419..5", "....8..79"]], ["9 x 9, needs guessing", ["..53.4.7.", ".3.......", "...2.1.83", "982.4..5.", "5....7...", ".1.82..4.", "2..5..69.", "75......8", "..8......"]]]
```

## README

# P040 - Sudoku helper

A 4 x 4 or 9 x 9 sudoku: every row, column and box holds each number once.
Pick one of three built-in puzzles or type one in. Put numbers in and take
them out - the helper says at once when a number clashes - check the whole
board, which also tells when it can no longer be completed, ask for a hint
that names one sure step, or let the solver finish the board and say whether
its solution is the only one.

- `main.eml` - the menu, the puzzles, putting and clearing numbers with their
  checks, and the board on screen
- `board.eml` - the rules: a cell's candidates, the clashes, the two kinds of
  sure step, and the solver
- `puzzles.eml` - the built-in puzzles

How each part works:

- A cell's candidates are the numbers not yet in its row, its column or its
  box; the box corner is the cell rounded down to a multiple of the box size,
  as in the corpus case `sudoku-solver-4x4`.
- A hint looks first for an empty cell with only one candidate, then for a
  number that has only one possible cell left in some row, column or box.
  Those are the two sure steps; when there is neither, the hint says so, and
  only trying numbers can go on.
- The solver backtracks like the corpus case, with one difference: instead
  of the first empty cell it fills the one with the fewest candidates (a cell
  with one or none stops the look-around), so a forced cell is filled before
  any guess and a dead end shows at once. It does not stop at the first
  solution but looks for a second, so it can say whether the solution is the
  only one, and it counts the numbers it placed on the way.
- A number that clashes is kept but named, so that it can be seen and taken
  out. Check lists every clash; when there is none, it runs the solver to
  tell whether the board can still be completed - a wrong number need not
  clash with anything yet.
- The puzzle's own numbers cannot be changed. The third built-in puzzle was
  generated for this project: it has exactly one solution, and the sure steps
  run out after 15 of them, with 38 cells still empty.

What is checked: a puzzle number from the list; a size of 4 or 9; rows of
exactly 4 or 9 digits from 1 to the size, or dots (a typed puzzle whose
numbers clash is refused); a cell as row and column, and a number, each from
1 to the size. An empty answer cancels.

Sessions: `sessions/basic.in` opens the easy 9 x 9 puzzle, asks for a hint
(row 5, column 5 can only be 5) and puts it in; puts in a 5 that clashes in
its row and its box, checks, and clears it; puts in a 1 that clashes with
nothing but leaves the board impossible - check says so - and clears it; asks
for another hint and lets the solver finish (the only solution, without a
single guess). Then the third puzzle: a hint, and the solver places 150
numbers to finish it; then the corpus case's 4 x 4. `sessions/bad-input.in`
gives menu choices 0 and x, actions before any puzzle, puzzle numbers 0, 5
and x, size 5, rows of 8 and 10 characters and one with letters; types in
the third puzzle as it stands when the sure steps run out, so that the hint
finds none; tries a cell without a number, row 10, the number 0, a puzzle
cell to fill and to clear and an empty cell to clear; lets the solver finish
(114 numbers placed, the only solution); and types a 4 x 4 with two 1s in a
row, which is refused, and one with a single number, which has more than one
solution.

Built on the verified corpus case `sudoku-solver-4x4` (backtracking over
row, column and box rules, checked by an independent validator).