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.

queens-last

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.

queens-exp-sol

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.

queens-data-struct

Program

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.

Demonstration

You can watch the program running here.