Skip to: ContentEnd


My home on the Web

Describing Solutions

Having identified the first solution (or indeed any solution) to the n Queens problem for a particular size of chessboard, we need some way of briefly and consistently describing it such that anyone else could come along and reproduce it without first having to spend hours searching for it. Any method we use must of course be extensible onto any size of chessboard, however inconceiveable.

Chessboard diagram showing the first possible solution to 4x4 with Queens in squares (1,2), (2,4), (3,1) and (4,3)We will take as our example the first solution for the 4×4 chessboard, shown on the diagram. Looking at this solution, the first thing we see is that there is only one Queen on each row, a fundamental feature of the problem as Queens can attack other pieces in the same row. But this also gives us a very simple way of describing these solutions based on each Queen's co-ordinates on the chessboard. Beginning with the bottom row, we number each row from one to four. If we do the same with the columns, numbering them from one to four starting at the left-hand side, we immediately have the perfect way of describing the solution.

Let's examine it in more detail. Using our simple co-ordinate system, the Queen in Row 1 is in Column 2, so we would describe her as being at co-ordinate (1,2). The Queen in Row 2 is in Column 4, so she is therefore at co-ordinate (2,4). Similarly, the remaining two Queens are at co-ordinates (3,1) and (4,3) respectively. Notice that the Row number (the first value of each pair) always increases by one, so we can further simplify the system by omitting this Row number, resulting in the sequence 2, 4, 1, 3. The position of each number in the sequence will then represent the Row number. For instance, the third number in the sequence is 1, which tells us that the Queen on the third Row should be placed in Column 1.

Our simple co-ordinate system can be easily applied to any solution on any size of chessboard. The first solution for the standard 64-square (8×8) chessboard, for example, is 1, 5, 8, 6, 3, 7, 2, 4. Note that there are eight values in the sequence, and that each number from one to eight appears only once – this demonstrates that there is exactly one Queen on each Row and in each Column.

Why not use an existing Chess Notation system?

Because we're not playing chess! All we really need to know is the location of each Queen on the chessboard, which can be described by our very simple co-ordinate system. We don't need to distinguish between different pieces because we're only using Queens, and we don't need to keep track of all of our Queens' moves because they're not part of the final solution. In addition, many chess notation systems use letters of the alphabet to label the columns, which is perfectly adequate for a standard 8×8 chessboard, but quite useless for anything above 26×26. Pairs of letters could be used, but this is more complicated and would still only be useful up to 676×676.