Figure 1: Numbering Rows, Columns and Diagonals of a Chessboard
[This page is auto-generated; please prefer to read the article’s PDF Form.]
The well-known 8-Queens Problem is to place 8 queens on an 8×8 chessboard such that no queen attacks any other queen. It is equivalent to the condition that on the row, column and the two diagonals of a queen’s square, there can be no other queen.
We can identify the 8 rows and 8 columns using integers {0,1,2,…,7} as shown in the figure below. Now onward we will use ℤ8 to denote the set of 8 integers: {0,1,2,…,7}. There are two types of diagonals: ascending and descending; the figure shows one ascending and one descending diagonal marked with -3 and 8 respectively (these identifiers are described below).
Let us denote the square on row r and column c as square (r,c). Note that on any given ascending diagonal, any square (r,c) has a fixed value of (r − c). For the 15 such diagonals, these values are distinct and range from -7 to 7. Similarly, on any given descending diagonal, any square (r,c) has a fixed value of (r + c). For the 15 such diagonals, these values are distinct and range from 0 to 14.
Thus we can uniquely identify the 15 ascending and 15 descending diagonals using integers {−7,−6,…,6,7} and {0,1,2,…,14} respectively.
Since a row cannot have more than one queen, and there are 8 rows and 8 queens, each row must have exactly one queen. Similarly, each column must have exactly one queen. So a solution placement of the 8 queens can simply be specified by mentioning for each row the column number where that row’s queen is placed. Specifically, the solution is a permutation of all the integers from ℤ8, (a0,a1,a2,…,a7), where ar is the column number for the queen on row r.
Such permutation must also reflect the constraint that two queens cannot share a diagonal. Note that for any r, values (r −ar) and (r + ar) would identify respectively the ascending and descending diagonal occupied by the queen on row r. We can in fact express the 8-Queens Problem as a simple abstract problem which deals only with integers:
Find a permutation of all the integers from ℤ8, (a0,a1,a2,…,a7), such that for all r, (r − ar) values are distinct, and (r + ar) values are distinct too.
With this abstract version, we no longer need to deal with the objects (chessboard, queens, their associated geometry) and rules of the original problem; we are left only with the necessary mathematical conditions underlying the problem.
In the rest of this discussion, we will be solving this abstract problem, the solution to which easily maps to the 8-Queens Problem. The constraint of (r − ar) and (r + ar) distinctness will be referred as constraint C.
[Next]
Copyright © 2021 Nitin Verma. All rights reserved.