N-Queens Problem

What Was Given

Implement the classic N-Queens problem in Prolog using three distinct approaches that demonstrate increasing levels of sophistication in constraint satisfaction. No template code was provided.

Board Representation

A solution is a list [C1, C2, ..., CN] where Ci is the column of the queen placed in row i. Since each row gets exactly one queen by construction, the list length is always N.

% Example: [2,4,1,3] for a 4-Queens solution
% Row 1 → Column 2  → queen at (1,2)
% Row 2 → Column 4  → queen at (2,4)
% Row 3 → Column 1  → queen at (3,1)
% Row 4 → Column 3  → queen at (4,3)

    . Q . .       (row 1, col 2)
    . . . Q       (row 2, col 4)
    Q . . .       (row 3, col 1)
    . . Q .       (row 4, col 3)

This representation automatically guarantees one queen per row (the list index). The three approaches differ in how they guarantee unique columns and safe diagonals.

How to Compile & Run

# Navigate to the assignment directory
cd /Users/hansrajpatel/Dev-IITG/cs331/cs331_a3_170101025/solution

# Start SWI-Prolog and load the file
swipl assignment3_170101025.pl

# Key queries to try:
?- queens_gt(4, S).          % Approach 1: generate-and-test
?- queens_perm(4, S).        % Approach 2: permutation-based
?- queens_inc(8, S).         % Approach 3: incremental (fastest)
?- solution_count(8, N).     % Count all 8-Queens solutions
?- display_board(4).         % ASCII art for one solution per approach
?- list_all(4).              % Print all 4-Queens solutions
?- verify_approaches(4).     % Confirm all approaches agree

# Press ; after each result to get more solutions
# Press . or Enter to accept current solution
# Type halt. to exit Prolog

SWI-Prolog compiles and loads in one step. For larger boards (N ≥ 10), use queens_inc — the other approaches become noticeably slow.

Approach 1: Generate-and-Test (queens_gt/2)

What it does

Independently assigns a column from 1 to N to each row, generating a complete board candidate. Then it tests whether no two queens share a column or diagonal. This is the simplest but least efficient approach, exploring N^N candidates.

Full code

% queens_gt(+N, -Board)
queens_gt(N, Board) :-
    length(Board, N),                    % Create list of N unbound vars
    fill_cols(Board, N),                 % Assign columns 1..N to each
    no_attacks(Board).                   % Test: no queen pair conflicts

% fill_cols(+Slots, +N)
% Assign each slot a value from 1 to N.
fill_cols([], _).
fill_cols([C | T], N) :-
    between(1, N, C),                    % C = 1, then 2, ... then N
    fill_cols(T, N).

% no_attacks(+Board)
% Walk through queens; each must be safe w.r.t. queens after it.
no_attacks([]).
no_attacks([Q | Qs]) :-
    safe_against(Q, Qs, 1),             % Q vs every queen in Qs
    no_attacks(Qs).                      % Recurse on remaining pairs

% safe_against(+Col, +Rest, +RowGap)
% Queen at column Col must not conflict with any queen in Rest.
safe_against(_, [], _).
safe_against(C, [C2 | Rest], Gap) :-
    C =\= C2,                           % different column
    abs(C - C2) =\= Gap,                % different diagonal
    Gap1 is Gap + 1,
    safe_against(C, Rest, Gap1).

Line-by-line explanation

1. length(Board, N) creates a list of N unbound variables. At this point Board is something like [_1, _2, _3, _4].
2. fill_cols walks through the list and binds each variable to a value between 1 and N using between/3. Since between is non-deterministic, Prolog backtracks through all possibilities. For N=4, this means 4⁴ = 256 total candidate boards.
3. no_attacks checks every pair of queens. For each queen Q at column C, safe_against verifies against every subsequent queen that: (a) they have different columns (C =\= C2), and (b) the column distance does not equal the row distance (abs(C - C2) =\= Gap), which is the diagonal test.
4. The RowGap variable tracks distance. Since queens come from consecutive rows, the gap starts at 1 and increments for each subsequent queen.

Approach 2: Permutation-based (queens_perm/2)

What it does

Key insight: since each row has exactly one queen and no two queens can share a column, every valid board is a permutation of [1, 2, ..., N]. This eliminates column conflicts by construction and reduces the search space from N^N to N!. We then only need to check diagonals.

Full code

% queens_perm(+N, -Board)
queens_perm(N, Board) :-
    numlist(1, N, Cols),                 % Cols = [1, 2, ..., N]
    arrange(Cols, Board),                % Board = some permutation
    diags_ok(Board).                     % Test diagonal safety

% arrange(+Pool, -Permutation)
% Build a permutation by picking one element at a time.
arrange([], []).
arrange(Pool, [X | Rest]) :-
    pick(X, Pool, Remaining),            % Pick one element from Pool
    arrange(Remaining, Rest).            % Permute the rest

% pick(?Elem, +List, -ListWithout)
% Non-deterministically select an element, return the rest.
pick(X, [X | Xs], Xs).                  % Pick the head
pick(X, [Y | Ys], [Y | Zs]) :-          % Or skip it and pick deeper
    pick(X, Ys, Zs).

% diags_ok(+Board)
% Since columns are already unique, only check diagonals.
diags_ok([]).
diags_ok([C | Cs]) :-
    diag_clear(C, Cs, 1),               % C vs all queens after it
    diags_ok(Cs).

% diag_clear(+Col, +Others, +Dist)
diag_clear(_, [], _).
diag_clear(C, [C2 | Cs], D) :-
    abs(C - C2) =\= D,                  % column distance != row distance
    D1 is D + 1,
    diag_clear(C, Cs, D1).

Line-by-line explanation

1. numlist(1, N, Cols) builds the list [1, 2, ..., N]. This is the pool of available columns.
2. arrange/2 generates permutations by repeatedly calling pick/3. Each call picks one element from the pool and recurses on the remaining elements.
3. pick/3 is the heart of permutation generation. It has two clauses: pick the head of the list (clause 1), or skip the head and pick from the tail (clause 2). Via backtracking, this non-deterministically selects every element.
4. diags_ok/1 and diag_clear/3 only check diagonal conflicts since column uniqueness is guaranteed by the permutation. The logic is the same as safe_against in Approach 1 but without the column check.

Approach 3: Incremental (queens_inc/2) — The Key Approach

What it does

This is the most important approach for the viva. Instead of building a complete board and then testing, it places queens one row at a time and immediately prunes any placement that conflicts with already-placed queens. It maintains three sets that track which columns, rising diagonals, and falling diagonals are occupied.

Full code

% queens_inc(+N, -Board)
queens_inc(N, Board) :-
    numlist(1, N, Rows),                 % Rows = [1, 2, ..., N]
    place(Rows, N, [], [], [], RevBoard),% Start with empty sets
    reverse(RevBoard, Board).            % Reverse accumulator

% place(+Rows, +N, +UsedCols, +UsedUps, +UsedDowns, -Acc)
place([], _, _, _, _, []).               % No rows left → done
place([R | Rs], N, Cols, Ups, Downs, [C | More]) :-
    between(1, N, C),                    % Try column C = 1..N
    \+ member(C, Cols),                  % Column C not yet taken
    Up is R + C,                         % Rising diagonal ID
    \+ member(Up, Ups),                  % Rising diagonal free
    Down is R - C,                       % Falling diagonal ID
    \+ member(Down, Downs),              % Falling diagonal free
    place(Rs, N, [C|Cols], [Up|Ups], [Down|Downs], More).

The three tracking sets

Why R+C and R-C identify diagonals

Consider a 4x4 board. All cells on the same rising diagonal (/) share the same value of R+C, and all cells on the same falling diagonal (\) share the same value of R-C:

% Rising diagonals (R+C):         Falling diagonals (R-C):
%
%   Col:  1   2   3   4           Col:  1   2   3   4
% Row 1:  2   3   4   5         Row 1:  0  -1  -2  -3
% Row 2:  3   4   5   6         Row 2:  1   0  -1  -2
% Row 3:  4   5   6   7         Row 3:  2   1   0  -1
% Row 4:  5   6   7   8         Row 4:  3   2   1   0
%
% Cells (1,3) and (2,4) share R+C = 4 and 6 ... wait:
%   (1,3): R+C=4    (2,4): R+C=6  → different / diagonal   OK
%   (1,3): R+C=4    (3,1): R+C=4  → SAME / diagonal       BLOCKED
%
% Cells (1,2) and (3,4) share R-C = -1 and -1 → same \ diagonal

How early pruning works

Suppose we are placing the queen for row 3 on a 4-Queens board, and rows 1 and 2 already have queens at columns 1 and 3:

% State after placing rows 1 and 2:
%   Cols  = [3, 1]       → columns 1 and 3 taken
%   Ups   = [5, 2]       → diagonals R+C=5 (row2,col3) and R+C=2 (row1,col1)
%   Downs = [-1, 0]      → diagonals R-C=-1 (row2,col3) and R-C=0 (row1,col1)
%
% Now placing row 3, try C=1:
%   \+ member(1, [3,1])  → FAILS! Column 1 is taken. Skip immediately.
%
% Try C=2:
%   \+ member(2, [3,1])  → passes (column free)
%   Up = 3+2 = 5
%   \+ member(5, [5,2])  → FAILS! Rising diagonal 5 is taken. Skip.
%
% Try C=3:
%   \+ member(3, [3,1])  → FAILS! Column 3 is taken. Skip.
%
% Try C=4:
%   \+ member(4, [3,1])  → passes
%   Up = 3+4 = 7
%   \+ member(7, [5,2])  → passes
%   Down = 3-4 = -1
%   \+ member(-1, [-1,0]) → FAILS! Falling diagonal -1 is taken. Skip.
%
% All columns fail for row 3 → backtrack to row 2 and try next column.

The critical advantage: when a column or diagonal is occupied, we skip it instantly without building the rest of the board. In Approach 1, we would fill all N rows, then discover the conflict. Here, we prune as soon as the conflict is detected.

Comparison of Approaches

Utility Functions

solution_count/2

% Count all distinct solutions for an NxN board.
solution_count(N, Count) :-
    aggregate_all(count, queens_inc(N, _), Count).

aggregate_all(count, Goal, Count) is a SWI-Prolog built-in that counts all solutions to Goal. The _ means we don't care about the actual board, just the count.

list_all/1

% Print every solution for NxN.
list_all(N) :-
    queens_inc(N, S),
    format("~w~n", [S]),
    fail ; true.

The fail forces backtracking after printing each solution, so all solutions are printed. The ; true catches the final failure so the predicate succeeds overall. This is the classic failure-driven loop pattern in Prolog.

display_board/1

% Show one solution from each approach with ASCII art.
display_board(N) :-
    format("~n--- Generate-and-Test (~w-Queens) ---~n", [N]),
    ( queens_gt(N, S1) ->
        show(N, S1)
    ; format("No solution.~n") ), !,

    format("~n--- Permutation (~w-Queens) ---~n", [N]),
    ( queens_perm(N, S2) ->
        show(N, S2)
    ; format("No solution.~n") ), !,

    format("~n--- Incremental (~w-Queens) ---~n", [N]),
    ( queens_inc(N, S3) ->
        show(N, S3)
    ; format("No solution.~n") ), !.

% show(+N, +Board) - print the board and draw ASCII art
show(N, Board) :-
    format("  ~w~n", [Board]),
    draw(Board, N).

draw([], _).
draw([Col | Rest], N) :-
    draw_row(1, N, Col), nl,
    draw(Rest, N).

draw_row(I, N, _) :- I > N, !.
draw_row(I, N, Col) :-
    ( I =:= Col -> write(' Q') ; write(' .') ),
    I1 is I + 1,
    draw_row(I1, N, Col).

Uses ( Cond -> Then ; Else ) (Prolog's if-then-else) to attempt each approach and print "No solution." as a fallback. The cuts after each block prevent backtracking across approach boundaries.

verify_approaches/1

% Confirm all three approaches find the same number of solutions.
verify_approaches(N) :-
    format("Verifying ~w-Queens across all approaches:~n", [N]),
    aggregate_all(count, queens_gt(N, _), A),
    aggregate_all(count, queens_perm(N, _), B),
    aggregate_all(count, queens_inc(N, _), C),
    format("  Generate-and-Test : ~w~n", [A]),
    format("  Permutation       : ~w~n", [B]),
    format("  Incremental       : ~w~n", [C]),
    ( A =:= B, B =:= C ->
        format("  All match - correct.~n")
    ; format("  MISMATCH - something is wrong!~n") ).

A correctness check: all three approaches must produce the same count. If they don't, there's a bug.

Full Expected Output

4-Queens solutions

?- queens_inc(4, S).
S = [2, 4, 1, 3] ;
S = [3, 1, 4, 2] ;
false.

?- queens_gt(4, S).
S = [2, 4, 1, 3] ;
S = [3, 1, 4, 2] ;
false.

?- queens_perm(4, S).
S = [2, 4, 1, 3] ;
S = [3, 1, 4, 2] ;
false.

8-Queens (first solution)

?- queens_inc(8, S).
S = [1, 5, 8, 6, 3, 7, 2, 4] ;
...

Solution counts

?- solution_count(4, N).
N = 2.

?- solution_count(8, N).
N = 92.

Board display

?- display_board(4).

--- Generate-and-Test (4-Queens) ---
  [2,4,1,3]
 . Q . .
 . . . Q
 Q . . .
 . . Q .

--- Permutation (4-Queens) ---
  [2,4,1,3]
 . Q . .
 . . . Q
 Q . . .
 . . Q .

--- Incremental (4-Queens) ---
  [2,4,1,3]
 . Q . .
 . . . Q
 Q . . .
 . . Q .

Verify approaches

?- verify_approaches(4).
Verifying 4-Queens across all approaches:
  Generate-and-Test : 2
  Permutation       : 2
  Incremental       : 2
  All match - correct.

List all 4-Queens solutions

?- list_all(4).
[2,4,1,3]
[3,1,4,2]
true.

Key Concepts for Viva