Extended Exercise: Checking (on) Queens

A famous problem in the game of chess concerns the placement of queens on a board. For our purposes, a chessboard is a ``square'' of, say, eight-by-eight or three-by-three tiles. The queen is a game piece that can move in a horizontal, vertical, or diagonal direction arbitrarily far. We say that a queen threatens a tile if it is on the tile or can move to it. Figure  shows an example. The solid disk represents a queen in the second column and sixth row. The solid lines radiating from the disk go through all those tiles that are threatened by the queen.

Figure: A chessboard with a single queen

The queen-placement problem is to place eight queens on a chessboard of eight-by-eight tiles such that the queens on the board don't threaten each other. In computing, we generalize the problem of course and ask whether we can place n queens on some board of arbitrary size m by m.

Even a cursory glance at the problem suggests that we need a data representation of boards and some basic functions on boards before we can even think of designing a program that solves the problem. Let's start with some basic data and function definitions.

Exercise 28.2.1

Develop a data definition for chessboards.

Hint: Use lists. Represent tiles with true and false. A value of true should indicate that a position is available for the placement of a queen; false should indicate that a position is occupied by, or threatened by, a queen. Solution

Next we need a function for creating a board and another one for checking on a specific tile. Following the examples of lists, let's define build-board and board-ref.

Exercise 28.2.2

Develop the following two functions on chessboards:

;; build-board : N (N N -> boolean) -> board
;; to create a board of size n x n,  
;; fill each position with indices i and j with (f i j) 
(define (build-board n f) ...)

;; board-ref : board N N -> boolean 
;; to access a position with indices i, j on a-board 
(define (board-ref a-board i j) ...) 

In addition to these generic functions on a chessboard representation, we also need at least one function that captures the concept of a ``threat'' as mentioned in the problem statement.

Exercise 28.2.3

Develop the function threatened?, which computes whether a queen can reach a position on the board from some given position. That is, the function consumes two positions, given as posn structures, and produces true if a queen on the first position can threaten the second position.

Hint: The exercise translate the chess problem of ``threatening queens'' into the mathematical problem of determining whether in some given grid, two positions are on the same vertical, horizontal, or diagonal line. Keep in mind that each position belongs to two diagonals and that the slope of a diagonal is either +1 or -1. Solution

Once we have data definitions and functions for the ``language of chessboards,'' we can turn our attention to the main task: the algorithm for placing a number of queens on some given board.

Exercise 28.2.4

Develop placement. The function consumes a natural number and a board and tries to place that many queens on the board. If the queens can be placed, the function produces an appropriate board. If not, it produces false. Solution