Project P079
N-queens
Queens on an n x n board with none attacking another: place them yourself and see which pairs attack; backtracking finds a first solution or all of them, with the squares it tried; and the solutions that are really different once the 8 turned and mirrored views count as one.
2 modules · 2 recorded sessionstext-menu UI in the terminalupdated 2026-10-14
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
n queens on an n x n board with none attacking another. You can place them yourself and see which pairs attack. Backtracking finds a first solution, or all of them, and counts the squares it tried. The program also counts how many solutions are really different once turned and mirrored boards count as one.
main.eml- the menu, reading boards, and drawing themqueens.eml- attacks, conflicts, the backtracking search, and the symmetries
How each part works:
- As in the corpus case
n-queens, a board is one column per row, so two queens can never share a row. Only columns and diagonals need checking: queens in rows r1, r2 at columns c1, c2 share a diagonal exactly when |r1 - r2| = |c1 - c2|. - Backtracking goes row by row. It tries each column in turn; a column no queen above attacks is taken, and the search goes on to the next row. When a row has none, it steps back. Every square tried is counted: 876 before the first solution for 8 queens, and 15,720 to find all 92.
- Symmetries: a quarter turn takes the queen at row r, column c to row c, column n + 1 - r, and a mirror takes column c to n + 1 - c. Four turns, each with and without the mirror, make the 8 views of a board. Taking the smallest view as its name, solutions with the same name are one solution seen another way: 92 for 8 queens, but 12 different.
- 2 and 3 queens have no solution. The search says so after trying every square it can.
What is checked: menu choices 1 to 4; a board of 4 to 12 to place by hand, 1 to 12 for a first solution, 1 to 9 for all of them; exactly n column numbers from 1 to n. An empty answer cancels.
Sessions: sessions/basic.in gives: - solutions placed by hand for 8, 4, 6 and 5 queens; - the first solution for 8 queens, none for 3, and the single queen; - all solutions for 8 (92, 12 different), 6 (4, 1 different) and 4 (2, 1 different).
sessions/bad-input.in gives: - menu choices 0 and x; - board sizes 3 and 13; boards of 3 numbers, with a 9, and of letters; - eight queens in one column: all 28 pairs attack; - sizes 0 and 13 for a first solution, and 10 for all of them, each then cancelled.
Built on the verified corpus case n-queens (one column per row, and backtracking on the column and diagonal tests).
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== N-queens ==
Queens on a board, none attacking another: by hand, and by backtracking.
1) place them yourself 2) a first solution 3) all solutions 4) quit
choice> 0
Pick a number from 1 to 4.
1) place them yourself 2) a first solution 3) all solutions 4) quit
choice> x
Pick a number from 1 to 4.
1) place them yourself 2) a first solution 3) all solutions 4) quit
choice> 1
board size (4 to 12)> 3
Type a whole number from 4 to 12.
board size (4 to 12)> 13
Type a whole number from 4 to 12.
board size (4 to 12)> 8
the column of the queen in each row, top to bottom (8 numbers from 1 to 8)> 1 2 3
Type 8 numbers from 1 to 8, separated by spaces.
the column of the queen in each row, top to bottom (8 numbers from 1 to 8)> 1 2 3 4 5 6 7 9
Type 8 numbers from 1 to 8, separated by spaces.
the column of the queen in each row, top to bottom (8 numbers from 1 to 8)> a b c d e f g h
Type 8 numbers from 1 to 8, separated by spaces.
the column of the queen in each row, top to bottom (8 numbers from 1 to 8)> 1 1 1 1 1 1 1 1
Q . . . . . . .
Q . . . . . . .
Q . . . . . . .
Q . . . . . . .
Q . . . . . . .
Q . . . . . . .
Q . . . . . . .
Q . . . . . . .
rows 1 and 2 attack along a column
rows 1 and 3 attack along a column
rows 1 and 4 attack along a column
rows 1 and 5 attack along a column
rows 1 and 6 attack along a column
rows 1 and 7 attack along a column
rows 1 and 8 attack along a column
rows 2 and 3 attack along a column
rows 2 and 4 attack along a column
rows 2 and 5 attack along a column
rows 2 and 6 attack along a column
rows 2 and 7 attack along a column
rows 2 and 8 attack along a column
rows 3 and 4 attack along a column
rows 3 and 5 attack along a column
rows 3 and 6 attack along a column
rows 3 and 7 attack along a column
rows 3 and 8 attack along a column
rows 4 and 5 attack along a column
rows 4 and 6 attack along a column
rows 4 and 7 attack along a column
rows 4 and 8 attack along a column
rows 5 and 6 attack along a column
rows 5 and 7 attack along a column
rows 5 and 8 attack along a column
rows 6 and 7 attack along a column
rows 6 and 8 attack along a column
rows 7 and 8 attack along a column
28 pairs attack.
1) place them yourself 2) a first solution 3) all solutions 4) quit
choice> 2
board size (1 to 12)> 0
Type a whole number from 1 to 12.
board size (1 to 12)> 13
Type a whole number from 1 to 12.
board size (1 to 12)>
Cancelled.
1) place them yourself 2) a first solution 3) all solutions 4) quit
choice> 3
board size (1 to 9)> 10
Type a whole number from 1 to 9.
board size (1 to 9)>
Cancelled.
1) place them yourself 2) a first solution 3) all solutions 4) quit
choice> 4
Bye.
What was typed (18 lines)
0
x
1
3
13
8
1 2 3
1 2 3 4 5 6 7 9
a b c d e f g h
1 1 1 1 1 1 1 1
2
0
13
3
10
4
basic
interpreter: byte-equal== N-queens ==
Queens on a board, none attacking another: by hand, and by backtracking.
1) place them yourself 2) a first solution 3) all solutions 4) quit
choice> 1
board size (4 to 12)> 8
the column of the queen in each row, top to bottom (8 numbers from 1 to 8)> 1 5 8 6 3 7 2 4
Q . . . . . . .
. . . . Q . . .
. . . . . . . Q
. . . . . Q . .
. . Q . . . . .
. . . . . . Q .
. Q . . . . . .
. . . Q . . . .
No two queens attack each other: a solution.
1) place them yourself 2) a first solution 3) all solutions 4) quit
choice> 1
board size (4 to 12)> 4
the column of the queen in each row, top to bottom (4 numbers from 1 to 4)> 2 4 1 3
. Q . .
. . . Q
Q . . .
. . Q .
No two queens attack each other: a solution.
1) place them yourself 2) a first solution 3) all solutions 4) quit
choice> 1
board size (4 to 12)> 6
the column of the queen in each row, top to bottom (6 numbers from 1 to 6)> 2 4 6 1 3 5
. Q . . . .
. . . Q . .
. . . . . Q
Q . . . . .
. . Q . . .
. . . . Q .
No two queens attack each other: a solution.
1) place them yourself 2) a first solution 3) all solutions 4) quit
choice> 1
board size (4 to 12)> 5
the column of the queen in each row, top to bottom (5 numbers from 1 to 5)> 1 3 5 2 4
Q . . . .
. . Q . .
. . . . Q
. Q . . .
. . . Q .
No two queens attack each other: a solution.
1) place them yourself 2) a first solution 3) all solutions 4) quit
choice> 2
board size (1 to 12)> 8
Q . . . . . . .
. . . . Q . . .
. . . . . . . Q
. . . . . Q . .
. . Q . . . . .
. . . . . . Q .
. Q . . . . . .
. . . Q . . . .
Columns 1 5 8 6 3 7 2 4 - found after trying 876 squares.
1) place them yourself 2) a first solution 3) all solutions 4) quit
choice> 2
board size (1 to 12)> 3
No way to place 3 queens: backtracking tried 18 squares and ran out.
1) place them yourself 2) a first solution 3) all solutions 4) quit
choice> 2
board size (1 to 12)> 1
Q
Columns 1 - found after trying 1 square.
1) place them yourself 2) a first solution 3) all solutions 4) quit
choice> 3
board size (1 to 9)> 8
92 solutions for 8 queens; backtracking tried 15720 squares.
Counting the 8 turned and mirrored views of a board as one, 12 are different.
1) place them yourself 2) a first solution 3) all solutions 4) quit
choice> 3
board size (1 to 9)> 6
4 solutions for 6 queens; backtracking tried 894 squares.
Counting the 8 turned and mirrored views of a board as one, there is only 1 different solution.
1) place them yourself 2) a first solution 3) all solutions 4) quit
choice> 3
board size (1 to 9)> 4
2 solutions for 4 queens; backtracking tried 60 squares.
Counting the 8 turned and mirrored views of a board as one, there is only 1 different solution.
1) place them yourself 2) a first solution 3) all solutions 4) quit
choice> 4
Bye.
What was typed (25 lines)
1
8
1 5 8 6 3 7 2 4
1
4
2 4 1 3
1
6
2 4 6 1 3 5
1
5
1 3 5 2 4
2
8
2
3
2
1
3
8
3
6
3
4
4
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# P079 N-queens: place queens yourself and see which attack each other;
# let backtracking find a first solution, or all of them, with how many
# squares it tried; and how many are really different once turned and
# mirrored boards count as one.
import queens
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 number(s):
if len(s) == 0 or len(s) > 2:
return -1
0 => n
for c in s:
if not (c >= "0" and c <= "9"):
return -1
n * 10 + int(c) => n
return n
def words(s):
[] => out
"" => w
for c in s + " ":
if c == " " or c == ",":
if w != "":
out + [w] => out
"" => w
else:
w + c => w
return out
def ask(prompt, low, high):
while True:
trim(input(prompt + " (" + str(low) + " to " + str(high) + ")> ")) => a
if a == "":
return -1
number(a) => n
if n >= low and n <= high:
return n
("Type a whole number from " + str(low) + " to " + str(high) + ".") ^0
def draw(cols):
len(cols) => n
for r in [0:n - 1]:
"" => line
for c in [1:n]:
if c == cols[r]:
line + " Q" => line
else:
line + " ." => line
line ^0
def squares(k):
if k == 1:
return "1 square"
return str(k) + " squares"
def queens_of(n):
if n == 1:
return "1 queen"
return str(n) + " queens"
def text(cols):
"" => s
for c in cols:
if s != "":
s + " " => s
s + str(c) => s
return s
def yours():
ask("board size", 4, 12) => n
if n == -1:
"Cancelled." ^0
return
while True:
trim(input("the column of the queen in each row, top to bottom (" + str(n) + " numbers from 1 to " + str(n) + ")> ")) => s
if s == "":
"Cancelled." ^0
return
words(s) => ws
True => ok
[] => cols
for w in ws:
number(w) => c
if c < 1 or c > n:
False => ok
cols + [c] => cols
if ok and len(cols) == n:
draw(cols)
queens.conflicts(cols) => bad
if len(bad) == 0:
"No two queens attack each other: a solution." ^0
else:
for b in bad:
(" rows " + str(b[0]) + " and " + str(b[1]) + " attack along a " + b[2]) ^0
if len(bad) == 1:
"1 pair attacks." ^0
else:
(str(len(bad)) + " pairs attack.") ^0
return
("Type " + str(n) + " numbers from 1 to " + str(n) + ", separated by spaces.") ^0
def first():
ask("board size", 1, 12) => n
if n == -1:
"Cancelled." ^0
return
queens.search(n, False) => r
if len(r[0]) == 0:
("No way to place " + queens_of(n) + ": backtracking tried " + squares(r[1]) + " and ran out.") ^0
return
draw(r[0][0])
("Columns " + text(r[0][0]) + " - found after trying " + squares(r[1]) + ".") ^0
def every():
ask("board size", 1, 9) => n
if n == -1:
"Cancelled." ^0
return
queens.search(n, True) => r
len(r[0]) => k
if k == 0:
("No solutions for " + queens_of(n) + "; backtracking tried " + squares(r[1]) + ".") ^0
return
queens.distinct(r[0]) => d
"solutions" => word
if k == 1:
"solution" => word
(str(k) + " " + word + " for " + queens_of(n) + "; backtracking tried " + squares(r[1]) + ".") ^0
if d == 1 and k > 1:
"Counting the 8 turned and mirrored views of a board as one, there is only 1 different solution." ^0
elif d == 1:
"Turned or mirrored, it is still the only one." ^0
else:
("Counting the 8 turned and mirrored views of a board as one, " + str(d) + " are different.") ^0
"== N-queens ==" ^0
"Queens on a board, none attacking another: by hand, and by backtracking." ^0
True => running
while running:
"" ^0
"1) place them yourself 2) a first solution 3) all solutions 4) quit" ^0
trim(input("choice> ")) => choice
if choice == "1":
yours()
elif choice == "2":
first()
elif choice == "3":
every()
elif choice == "4":
False => running
else:
"Pick a number from 1 to 4." ^0
"Bye." ^0
Python projection (main.py)
import queens
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 number(s):
if len(s) == 0 or len(s) > 2:
return -1
n = 0
for c in s:
if not (c >= "0" and c <= "9"):
return -1
n = n * 10 + int(c)
return n
def words(s):
out = []
w = ""
for c in s + " ":
if c == " " or c == ",":
if w != "":
out = out + [w]
w = ""
else:
w = w + c
return out
def ask(prompt, low, high):
while True:
a = trim(input(prompt + " (" + str(low) + " to " + str(high) + ")> "))
if a == "":
return -1
n = number(a)
if n >= low and n <= high:
return n
print("Type a whole number from " + str(low) + " to " + str(high) + ".")
def draw(cols):
n = len(cols)
for r in range(0, n):
line = ""
for c in range(1, n+1):
if c == cols[r]:
line = line + " Q"
else:
line = line + " ."
print(line)
def squares(k):
if k == 1:
return "1 square"
return str(k) + " squares"
def queens_of(n):
if n == 1:
return "1 queen"
return str(n) + " queens"
def text(cols):
s = ""
for c in cols:
if s != "":
s = s + " "
s = s + str(c)
return s
def yours():
n = ask("board size", 4, 12)
if n == -1:
print("Cancelled.")
return
while True:
s = trim(input("the column of the queen in each row, top to bottom (" + str(n) + " numbers from 1 to " + str(n) + ")> "))
if s == "":
print("Cancelled.")
return
ws = words(s)
ok = True
cols = []
for w in ws:
c = number(w)
if c < 1 or c > n:
ok = False
cols = cols + [c]
if ok and len(cols) == n:
draw(cols)
bad = queens.conflicts(cols)
if len(bad) == 0:
print("No two queens attack each other: a solution.")
else:
for b in bad:
print(" rows " + str(b[0]) + " and " + str(b[1]) + " attack along a " + b[2])
if len(bad) == 1:
print("1 pair attacks.")
else:
print(str(len(bad)) + " pairs attack.")
return
print("Type " + str(n) + " numbers from 1 to " + str(n) + ", separated by spaces.")
def first():
n = ask("board size", 1, 12)
if n == -1:
print("Cancelled.")
return
r = queens.search(n, False)
if len(r[0]) == 0:
print("No way to place " + queens_of(n) + ": backtracking tried " + squares(r[1]) + " and ran out.")
return
draw(r[0][0])
print("Columns " + text(r[0][0]) + " - found after trying " + squares(r[1]) + ".")
def every():
n = ask("board size", 1, 9)
if n == -1:
print("Cancelled.")
return
r = queens.search(n, True)
k = len(r[0])
if k == 0:
print("No solutions for " + queens_of(n) + "; backtracking tried " + squares(r[1]) + ".")
return
d = queens.distinct(r[0])
word = "solutions"
if k == 1:
word = "solution"
print(str(k) + " " + word + " for " + queens_of(n) + "; backtracking tried " + squares(r[1]) + ".")
if d == 1 and k > 1:
print("Counting the 8 turned and mirrored views of a board as one, there is only 1 different solution.")
elif d == 1:
print("Turned or mirrored, it is still the only one.")
else:
print("Counting the 8 turned and mirrored views of a board as one, " + str(d) + " are different.")
print("== N-queens ==")
print("Queens on a board, none attacking another: by hand, and by backtracking.")
running = True
while running:
print("")
print("1) place them yourself 2) a first solution 3) all solutions 4) quit")
choice = trim(input("choice> "))
if choice == "1":
yours()
elif choice == "2":
first()
elif choice == "3":
every()
elif choice == "4":
running = False
else:
print("Pick a number from 1 to 4.")
print("Bye.")
queens.eml
eml# P079 N-queens - n queens on an n x n board with none attacking another.
# As in the corpus case n-queens, a board is one column per row (columns
# numbered 1 to n), so two queens can never share a row; only columns and
# diagonals need checking: queens in rows r1, r2 at columns c1, c2 attack
# along a diagonal exactly when |r1 - r2| = |c1 - c2|.
def attacks(r1, c1, r2, c2):
# "" if they do not attack, else how: "column" or "diagonal".
if c1 == c2:
return "column"
if r1 - r2 == c1 - c2 or r1 - r2 == c2 - c1:
return "diagonal"
return ""
def conflicts(cols):
# Every attacking pair as [row, row, how], rows numbered from 1.
[] => out
for i in [0:len(cols) - 1]:
for j in [i + 1:len(cols) - 1]:
attacks(i, cols[i], j, cols[j]) => how
if how != "":
out + [[i + 1, j + 1, how]] => out
return out
def safe(cols, row, col):
for r in [0:row - 1]:
if attacks(r, cols[r], row, col) != "":
return False
return True
def search(n, want_all):
# Backtracking, row by row: try each column that no queen above
# attacks, go on to the next row, and step back when a row has none.
# Returns [solutions found (just the first unless want_all), squares
# tried]. The tries are counted in a one-element list so the recursion
# can add to it.
[0] * n => cols
[0] => tried
[] => found
place(n, 0, cols, tried, found, want_all) => found
return [found, tried[0]]
def place(n, row, cols, tried, found, want_all):
if row == n:
[0] * n => copy
for i in [0:n - 1]:
cols[i] => copy[i]
return found + [copy]
for c in [1:n]:
if want_all or len(found) == 0:
tried[0] + 1 => tried[0]
if safe(cols, row, c):
c => cols[row]
place(n, row + 1, cols, tried, found, want_all) => found
return found
def turned(cols):
# The board a quarter turn clockwise: the queen at (row r, column c)
# moves to (row c, column n + 1 - r) - rows and columns from 1.
len(cols) => n
[0] * n => out
for r in [0:n - 1]:
n - r => out[cols[r] - 1]
return out
def mirrored(cols):
len(cols) => n
[0] * n => out
for r in [0:n - 1]:
n + 1 - cols[r] => out[r]
return out
def smaller(a, b):
# Whether a comes before b, reading the columns left to right.
for i in [0:len(a) - 1]:
if a[i] != b[i]:
return a[i] < b[i]
return False
def canonical(cols):
# The smallest of the 8 boards a solution becomes when turned and
# mirrored: solutions with the same canonical form are the same
# solution seen another way.
cols => best
cols => x
for k in [1:4]:
mirrored(x) => m
if smaller(m, best):
m => best
turned(x) => x
if k < 4 and smaller(x, best):
x => best
return best
def distinct(solutions):
# How many solutions are left when the 8 symmetric views count as one.
[] => seen
for s in solutions:
canonical(s) => c
True => fresh
for t in seen:
if t == c:
False => fresh
if fresh:
seen + [c] => seen
return len(seen)
Python projection (queens.py)
def attacks(r1, c1, r2, c2):
if c1 == c2:
return "column"
if r1 - r2 == c1 - c2 or r1 - r2 == c2 - c1:
return "diagonal"
return ""
def conflicts(cols):
out = []
for i in range(0, len(cols)):
for j in range(i + 1, len(cols)):
how = attacks(i, cols[i], j, cols[j])
if how != "":
out = out + [[i + 1, j + 1, how]]
return out
def safe(cols, row, col):
for r in range(0, row):
if attacks(r, cols[r], row, col) != "":
return False
return True
def search(n, want_all):
cols = [0] * n
tried = [0]
found = []
found = place(n, 0, cols, tried, found, want_all)
return [found, tried[0]]
def place(n, row, cols, tried, found, want_all):
if row == n:
copy = [0] * n
for i in range(0, n):
copy[i] = cols[i]
return found + [copy]
for c in range(1, n+1):
if want_all or len(found) == 0:
tried[0] = tried[0] + 1
if safe(cols, row, c):
cols[row] = c
found = place(n, row + 1, cols, tried, found, want_all)
return found
def turned(cols):
n = len(cols)
out = [0] * n
for r in range(0, n):
out[cols[r] - 1] = n - r
return out
def mirrored(cols):
n = len(cols)
out = [0] * n
for r in range(0, n):
out[r] = n + 1 - cols[r]
return out
def smaller(a, b):
for i in range(0, len(a)):
if a[i] != b[i]:
return a[i] < b[i]
return False
def canonical(cols):
best = cols
x = cols
for k in range(1, 5):
m = mirrored(x)
if smaller(m, best):
best = m
x = turned(x)
if k < 4 and smaller(x, best):
best = x
return best
def distinct(solutions):
seen = []
for s in solutions:
c = canonical(s)
fresh = True
for t in seen:
if t == c:
fresh = False
if fresh:
seen = seen + [c]
return len(seen)