Abstract

A number of chessboard placement and closely related puzzles are examined and formulated as Integer Programs. These puzzles require the participant to place pieces on a board according to certain constraints and may be generalized to boards containing any number of squares, and pieces displaying properties unfamiliar in the game of chess.

1. Introduction

The literature on recreational mathematics contains many references to puzzles that require the participant to place pieces on a chessboard according to specific constraints (Dudeney, 1917;Kraitchik, 1942; Schuh, 1943). These may be generalized to boards containing any number of squares and to pieces displaying properties not permitted in the game of chess. By formulating the problem situations as Integer Programs, the solutions to puzzles of this type may be methodically deduced. A few examples of these chessboard placement problems, and the IP models to solve them, will be presented in this paper. The aim is to encourage the use of such puzzles in an educational context to improve and develop modeling skills.

The applicability of a known technique from the field of OR/MS to the seemingly unrelated context of puzzles for leisure has educational implications. If OR/MS techniques can play a role in games for fun, then, conversely, games may have a role to play in teaching OR/MS.

‘Making learning fun’ as a means of motivating students to learn is an established teaching approach, well documented in the literature on school and higher education (Gage & Berliner, 1992; Walkin, 1990; M.Rawson, 1999). The value of game playing, specifically, to encourage active rather than passive learning has also been expounded (D.Adams, 1973; Cowan, 1998).

Students of business in universities come from a range of educational backgrounds. For some, mathematics may be a subject that they have not recently studied and, of which, they have less than fond memories. Integer Programming techniques, requiring an understanding of mathematical logic and the ability to use mathematical notations, may well be anxiety provoking to such students. The usefulness of integer programming in making operational decisions is not likely to be sufficiently motivating in such cases. As teaching tools, the beauty of puzzles and games is in their capacity for mass appeal and in that they do not, on the face of it, have anything to do with the more serious and contextually dry worlds of business or mathematics. As Martin Gardner (1975) puts it:

“No student is motivated to learn advanced group theory, for example, by telling him that he will find it beautiful and stimulating, or even useful, if he becomes a particle physicist. Surely the best way to wake up a student is to present him with an intriguing mathematical game, puzzle, magic trick, paradox, limerick or any score of things that dull teachers tend to avoid because they seem frivolous.”

In Britain, the Department for Education’s Numeracy Initiative in schools seeks to echo this attitude in its guidelines for teaching mathematics in British schools. The sense of satisfaction at solving a puzzle, the buzz of discovery, the joy of ‘winning’ are all recognized as intrinsically motivating forces (DFE, 1999; Anderson et al, 1997).

The growth of international students among the UK universities means that it is increasingly important to find methods and techniques to encourage learning that have cross cultural application and appeal (Glauco de Vita, 1999). The puzzles we discuss in this paper, being based upon or closely related to the universally popular game of chess, fulfil this requirement.

2. A Pot-Pourri of Placement Puzzles

A number of chess piece placement problems are now described together with a few problems that are similar enough in structure to warrant discussion in this context.

2.1 Standard Chess Piece Placements

The Non-attacking Queens Problem
What is the maximum number of queens that can be placed on a chessboard such that no queen is attacked by another.

The Queen Domination Problem
What is the minimum number of queens that can be placed on a chessboard so that each square contains a queen or is attacked by one.

Non-dominating Queens
A puzzle referred to as ‘the non-dominating queens problem’ has been considered at some length in the literature. That is, place n queens on a board of order n in such a way as to maximise the number of squares not under attack. The formulation of this is straightforward but as n increases the solutions provide a challenge to current I.P. software. Mario Velucchi summarises the progress made and gives optimal solutions for boards up to and including order 16 and best known solutions for boards up to and including order 30.

Bishops, Rooks and Knights
The ‘Non-attacking’ and ‘Domination’ problems above have also been considered in the literature for Bishops, Knights and Rooks.

The most popular of these is perhaps the knight domination problem and is usually presented in one of two forms. That is, where occupied squares must be under attack and where occupied squares must not be under attack.

Foulds and Johnson (1984) formulate non-attacking problems for rooks, bishops, queens, knights and kings and prove that, in each case, the constraint matrix is totally unimodular.

Rook placement puzzles are less well represented in the literature as the solutions are easily achieved by casual inspection. For example, the minimum number of rooks that may be placed on the board such that every square is attacked is eight – there must be one on every rank or one on every file. The maximum number of rooks that may be placed such than none are attacked by any other is also eight - there may be one on each square of a main diagonal.

Nevertheless, the simplicity of the rook’s move will provide us with a useful starting point in our analysis and there are lessons to be learned that will be of benefit in the consideration of the less accommodating pieces.

2.2 The Crowded Board
“You are given a chessboard together with 8 queens, 8 rooks, 14 bishops, and 21 knights. The puzzle is to arrange the 51 pieces on the chessboard so that no queen shall attack another queen, no rook attack another rook, no bishop attack another bishop, and no knight attack another knight. No notice is to be taken of the intervention of pieces of another type from that under consideration - that is, two queens will be considered to attack one another although there may be, say, a rook, a bishop, and a knight between them. It is not difficult to dispose of each type of piece seperately; the difficulty comes in when you have to find room for all the arrangements on the board simultaneously.” (Dudeney, 1917)

2.3 Detective Chess
This type of puzzle was originated by Jaime Poniachek and explored by Martin Gardner in Isaac Asimov’s Science Fiction Magazine, reprinted in Gardner’s Puzzles from other Worlds.

A number of chessboard squares are marked and these squares are to be occupied by a given set of pieces (pawns are not included). The objective is to deduce which pieces must occupy each of the marked squares. Clues are given in the form of numbered squares and these represent the number of attacks on the respective square. A sample puzzle is given below.

Figure 1: Detective Chess
 

The puzzle has been programmed by Gerry Quinn (http://indigo.ie/~gerryq/Det/Det.htm). His implementation has the facility to generate random puzzles on a range of board sizes and with a variety of pieces for placement including several borrowed from ‘Fairy’ chess. Each puzzle generated has a unique solution.

2.4 The Gentle Art of Stamp Licking
“If you have a card divided into sixteen spaces (4 x 4), and are provided with plenty of stamps of the values 1d., 2d., 3d., 4d., and 5d., what is the greatest value that you can stick on the card if the Chancellor of the Exchequer forbids that you place any stamp in a straight line (that is, horizontally, vertically, or diagonally) with another stamp of similar value? Of course, only one stamp can be affixed in a space.” (Dudeney, 1917)

2.5 5-by-5 (http://www.chlond.demon.co.uk/Five.html)
Each of the squares in a 5-by-5 grid can be in one of two states, lit or unlit. If the player clicks on a square then that square and each orthogonal neighbor will toggle between the two states. Each mouse click constitutes one move and the objective of the puzzle is to light all 25 squares in the least number of moves. The starting configuration has all 25 squares unlit.

2.6 Lights on (http://www.chlond.demon.co.uk/Lights.html)
This is a puzzle similar to 5-by-5 but is played on a 4-by-4 grid. The squares affected by a mouse click are the current square and all those squares within a single rook’s move. Again the objective is to light up all squares. The starting configuration is generated with a random selection of squares already lit.

2.7 Equal Vision
A watchman looks in all directions (horizontal, vertical and diagonal). On the board below, each watchman has five vacant cells under his gaze. A watchman can see beyond another watchman. What is the maximum number of watchmen that can be placed so that each sees six empty cells? What if each watchman must see seven empty cells? (Poniachek, 1998)

Figure 2: Equal Vision
 

2.8 The Abbott’s Window
Dudeney’s description of the Abbott’s Window is quaint though unnecessarily convoluted. The puzzle in effect consists of an 8-by-8 grid where individual squares must be covered in such a way that all horizontal, vertical and diagonal lines contain an even number of uncovered squares. An added condition is that each corner square must not be covered.

3. Tools of the Trade

If a stamp of value k is placed on square {i,j} then it is not in line with any stamp of the same value:

4.7 5-by-5
Consider a placement puzzle involving a hypothetical piece which may make rook-like moves but with a maximum of one square per move. Each occupied square must be attacked by an odd number of pieces and each unoccupied square must be attacked by an even number of pieces. This is analogous to the five-by-five puzzle. A mechanism to achieve these conditions is:

Where d_i,,j is a dummy integer variable for each square.

The objective is to minimize the number of placements.

4.8 Lights on
This is essentially a rook placement problem.

where d_i,,j is defined as for the five-by-five puzzle and r_i,,j = 1 if square {i,j} is unlit in the initial configuration, 0 otherwise.

4.9 Equal Vision
A moment’s reflection reveals the ‘watchmen’ problem to be the inverse of a queen placement problem on a four-by-four board. If we imagine a queen on each empty square and an empty square where each watchman is currently placed then each empty square is attacked by five queens. The problem is then to maximize the number of queens placed such that six and then seven queens attack each empty square. The empty squares in the solution to the revised puzzle will be the squares where the watchmen are to be placed in the original puzzle.

To solve the problem directly the binary decision variables, x_i,,j, are defined for each square, {i,j}, such that if square {i,j} is occupied by a watchman then x_i,,j = 0, otherwise x_i,,j = 1.

In order to maximize the number of occupied squares, the objective function will be minimized as follows:

The constraints necessary to ensure compliance with the conditions of the puzzle are:

where V = number of vacant cells visible to watchmen, i.e. either six or seven.

4.10 The Abbott’s Window
Constraints may be generated for each square using modifications of the bishop and rook moves. This renders the formulation exercise trivial but produces an unwieldy model involving many redundant constraints. A more efficient approach is to consider the grid on a line by line basis rather than by individual squares, similar to the approach taken for “The Crowded Board”.

5. Conclusion