<!-- canonical: https://efficientnewlanguage.org/eml-p/projects/P079-n-queens/ | updated: 2026-10-14 -->

# 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.

EML-P project `projects/n-queens` in the EML language repo: 2 module(s), entry `main.eml`, terminal UI. There, `eml project run projects/n-queens` runs it and `eml project verify projects/n-queens` 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: n-queens (https://efficientnewlanguage.org/cases/119-n-queens/).

## Sessions

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

Input:

```text
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
```

Screen:

```text
== 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.
```

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

Input:

```text
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
```

Screen:

```text
== 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.
```

## Modules

### main.eml

```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 of main.eml:

```python
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 of queens.eml:

```python
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)
```

## README

# P079 - N-queens

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 them
- `queens.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).