The N-queens puzzle¶

A classic of logic programming: place N queens on an N×N chessboard so that no two attack each other. The Prolog program describes what a solution is; the solver searches for solutions by backtracking, and enumerates them lazily.

In [1]:

from tuprolog.solve.prolog import prolog_solver
from tuprolog.theory.parsing import parse_theory

queens = parse_theory("""
    queens(N, Qs) :- numlist(1, N, Ns), permutation(Ns, Qs), safe(Qs).

    numlist(N, N, [N]) :- !.
    numlist(L, H, [L | T]) :- L < H, L1 is L + 1, numlist(L1, H, T).

    permutation([], []).
    permutation(L, [X | P]) :- select(X, L, R), permutation(R, P).

    select(X, [X | T], T).
    select(X, [H | T], [H | R]) :- select(X, T, R).

    safe([]).
    safe([Q | Qs]) :- no_attack(Q, Qs, 1), safe(Qs).

    no_attack(_, [], _).
    no_attack(Q, [Q1 | Qs], D) :-
        Q =\\= Q1 + D, Q =\\= Q1 - D, D1 is D + 1, no_attack(Q, Qs, D1).
""")
solver = prolog_solver(static_kb=queens)

from tuprolog.solve.prolog import prolog_solver from tuprolog.theory.parsing import parse_theory queens = parse_theory(""" queens(N, Qs) :- numlist(1, N, Ns), permutation(Ns, Qs), safe(Qs). numlist(N, N, [N]) :- !. numlist(L, H, [L | T]) :- L < H, L1 is L + 1, numlist(L1, H, T). permutation([], []). permutation(L, [X | P]) :- select(X, L, R), permutation(R, P). select(X, [X | T], T). select(X, [H | T], [H | R]) :- select(X, T, R). safe([]). safe([Q | Qs]) :- no_attack(Q, Qs, 1), safe(Qs). no_attack(_, [], _). no_attack(Q, [Q1 | Qs], D) :- Q =\\= Q1 + D, Q =\\= Q1 - D, D1 is D + 1, no_attack(Q, Qs, D1). """) solver = prolog_solver(static_kb=queens)

Qs[i] is the row of the queen in column i. The first solution for 8 queens:

In [2]:

first = solver.solve_once("queens(8, Qs)").to_dict()["Qs"]
first

first = solver.solve_once("queens(8, Qs)").to_dict()["Qs"] first

Out[2]:

[1, 5, 8, 6, 3, 7, 2, 4]

In [3]:

def board(rows):
    n = len(rows)
    return "\n".join(
        " ".join("Q" if rows[c] == r else "." for c in range(n)) for r in range(1, n + 1)
    )


print(board(first))

def board(rows): n = len(rows) return "\n".join( " ".join("Q" if rows[c] == r else "." for c in range(n)) for r in range(1, n + 1) ) print(board(first))

Q . . . . . . .
. . . . . . Q .
. . . . Q . . .
. . . . . . . Q
. Q . . . . . .
. . . Q . . . .
. . . . . Q . .
. . Q . . . . .

Counting every solution for 6 queens:

In [4]:

len(list(solver.query("queens(6, Qs)")))

len(list(solver.query("queens(6, Qs)")))

Out[4]:

4