Project 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.
3 modules · 2 recorded sessionstext-menu UI in the terminalupdated 2026-10-10
Every screen below was recorded under CPython. When this page was built, the EML interpreter replayed each session from the same input and printed the same bytes.
About
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 screenboard.eml- the rules: a cell's candidates, the clashes, the two kinds of sure step, and the solverpuzzles.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).
Recorded sessions
What the screen shows while someone uses the program. Each typed line appears after its prompt, the way a terminal shows it.
bad-input
interpreter: byte-equal== 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.
What was typed (55 lines)
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
basic
interpreter: byte-equal== 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.
What was typed (25 lines)
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
Modules
The program as written, entry module first. Each module transpiles to its own Python file, which is what eml project run executes.
main.eml(entry)
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 (main.py)
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 (board.py)
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 (puzzles.py)
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......"]]]