Navigation  without Java Scripts

The N Queens Problem

In the N Queens problem the object is to place N queens on a chessboard in such a way that no queens can capture a piece. This means that no two queens may be placed on the same row, column, or diagonal.

One way to solve the problem is to number the rows and columns of the chessboard from 1 to N. In order to number the diagonals you divide them into two types so that a diagonal is uniquely specified by a type and a value calculated from its row and column numbers:

Diagonal = N + Column - Row (Type 1)

Diagonal = Row + Column
    

When you view the chessboard with row 1 at the top and column 1 on the left side, Type 1 diagonals resemble the backslash (\) character in shape, and Type 2 diagonals resemble the shape of slash (/). Figure 15.5 shows the numbering of Type 2 diagonals on a 4x4 board.

The N Queens Chessboard

Execute the program as a CGI script by pressing the "Run" button on the form below


 for  queens

Show Source to the Nqueen-application.
Show Source to the Nqueen-application incl. cgi-support.

Problem Description

In order to solve the N Queens Problem with a Visual Prolog program, you must record which rows, columns, and diagonals are unoccupied, and also make a note of where the queens are placed.

A queen's position is described with a row number and a column number as in the domain declaration:

queen = q(integer, integer)

This declaration represents the position of one queen. You can use a list of queens to describe more positions. This is defined as:
     queens = queen*

Likewise, you need several numerical lists indicating the rows, columns, and diagonals unoccupied by queens. These lists are described by:

freelist = integer*

You will treat the chessboard as a single object with the following domain declaration:

board = board(queens, freelist, freelist, freelist, freelist)

The four freelists represent the free rows, columns, and diagonals of Type 1 and Type 2 respectively.

To see how this is going to work, let board represent a 4*4 chessboard in two situations: (1) without queens and (2) with one queen at the top left corner.

  1. board without queens
board([], [1,2,3,4], [1,2,3,4], [1,2,3,4,5,6,7], [1,2,3,4,5,6,7])
  1. board with one queen
board([q(1,1)], [2,3,4], [2,3,4], [1,2,3,5,6,7], [2,3,4,5,6,7])

You can now solve the problem by describing the relationship between an empty board and a board with N queens. You define the predicate:

placeN(integer, board, board)

with the two clauses following. Queens are placed one at a time until every row and column is occupied. You can see this in the first clause, where the two lists of freerows and freecols are empty:

placeN(_, board(D, [], [], X, Y), board(D, [], [], X, Y)) :- !.
placeN(N, Board1, Result) :-
        place_a_queen(N, Board1, Board2),
        placeN(N, Board2, Result).

In the second clause the predicate place_a_queen gives the connection between Board1 and Board2. (Board2 has one more queen than Board1). Use this predicate declaration:

place_a_queen(integer, board, board)

The core of the N Queens Problem lies in the description of how to add extra queens until they have all been successfully placed, starting with an empty board. To solve this problem, you should add the new queen to the list of those already placed:

[q(R, C)|Queens]

Among the remaining free rows, Rows, you need to find a row R where you can place the next queen. At the same time you must remove R from the list of free rows, resulting in a new list of free rows, NewR. This is formulated as:

findandremove(R, Rows, NewR)

Correspondingly, you must find and remove a vacant column C. From R and C you can calculate the numbers of the occupied diagonals. Then you can determine if D1 and D2 are among the vacant diagonals.

This is the place_a_queen clause:

place_a_queen(N, board(Queens, Rows, Columns, Diag1, Diag2),
                board([q(R,C)|Queens], NewR, NewS, NewD1, NewD2)) :-
        findandremove(R, Rows, NewR),
        findandremove(C, Columns, NewC),
        D1=N+S-R,
        findandremove(D1, Diag1, NewD1),
        D2=R+S-1,
        findandremove(D2, Diag2, NewD2).

NQUEEN.PRO is the complete program. It contains a number of smaller additions to defining nqueens so you only need to give a goal like:

nqueens(5)

to obtain a possible solution (in this case for placing five queens on a 5*5 board).