Reginae ex machina

This article shows how the 8-queens problem can be solved by using the Gray-1, a computer without microprocessor whose CPU is only made of memory chips.


The 8 queens problem

The aim is to place 8 queens on a 8 x 8 chessboard in such a way that there are no more than one queen on each row, column, and diagonal. There are 92 solutions. The figure below shows one of theses solutions.


Forward checking

To solve this problem, I implemented an algorithm called forward checking. A queen is first placed on the first row. The possible locations will be explored from left to right. Whenever a queen is placed, the locations that become prohibited on the lower rows are marked. No queen will be put on this marked locations. Next, a new queen will be place on the second line, and so on, until either the last row is reached or a whole row is blocked. At this time, the algorithm backtracks to the most recent stage with unexplored possibilities.

On the figure below, which is a photography of the display of the Gray-1, 3 queens are positioned on the 3 first rows. The green squares of the 3 first rows indicates the locations which will be tried later. The green squares on the 5 last rows indicates the locations that are not in conflict with the 3 queens of the first rows. This information are updated as the research progresses.

queens-04-wImplantation details

Data structure

The number N of placed queens is stored in a byte. The locations of the placed queens are stored in a stack of 8 bytes, where each byte is related to a row of the chessboard. The possible values are 01, 02, 04, … , 80, i.e., bytes with one bit set to 1. The bit set to 1 indicates the column where the related queen is located. The unavailable location (regarding the currently positioned queens) are represented by a matrix of 8 x 8 bytes as shown below, which corresponds to the search stage represented above.



The program is quite complex because of the low level of the used programming language, i.e., the assembly language of the Gray-1 CPU, which have only 8 instructions and does not support indirect / indexed addressing modes. By way of illustration, I give below the code of the three main procedures involved in the search for solutions.


You can watch the program running here.