ANTIC VOL. 3, NO. 12 / APRIL 1985

# THE EIGHT QUEENS PROBLEM

by ANGELO GIAMBRA

The brute force of computer power is used to solve a complicated chess problem in this BASIC program.  Works on all Atari computers with 24K memory for cassette, or 32K for disk.

Antic challenges you to solve the well-known Eight Queens Chess Problem: You must arrange eight queens on a chessboard so that none of them threatens another!
(In case you are unfamiliar with chess, the queen is the most powerful piece on the board. It can attack at any distance along a horizontal, vertical, or diagonal line.)
Done yet? No? You didn't find all 92 solutions? It shouldn't have taken more than a few hours to find at least three solutions.
But maybe you said to yourself, "I'd be stupid to beat my brains out on this. My Atari should be able to figure it out." You were right. This is exactly the kind of problem suitable for solution by computer.

BRUTE COMPUTING
The Eight Queens Problem demonstrates your computer's impressive brute number-crunching trial and error capability. It systematically tries every possible combination until it arrives at a solution.
To access this brute force, type in listing 1, check it with TYPO II, and SAVE it to disk or cassette.
When you RUN the program, it will first ask you to enter a starting position. Key in any number from one to eight. The computer will draw a chessboard on your screen and place a queen in the square in the top row corresponding to the position you entered. It will then proceed to place queens in other squares in an attempt to solve the problem.

WATCH IT WORK
You'll be able to watch as the computer tries combinations, then backs out of the moves that do not work.
Finally, when it finds one of the solutions, the screen will flash and the program will display the message PRESS ANY KEY Press any key and the computer will begin searching for the next solution.
Your computer may seem to be randomly trying squares, but it is actually proceeding in an orderly fashion and will not come up with the same solution twice.
Though this application may seem trivial, computers are often used in just this fashion to solve real-life problems.
For example, some trucking firms employ software to find the most efficient route between several cities. Using the the same brute force method, these programs calculate the mileage of all possible routes, determine the number of stops needed for each alternative, and then choose the best route.

MORE UNIQUE
Incidentally, only 12 of the 92 solutions are unique. Some solutions duplicate others if you rotate the chessboard. This program doesn't attempt to isolate the unique solutions.
For a real challenge, you might want to try modifying the program so that only unique solutions are found. Now there's a real challenge.

Angelo Giambra is a technical analyst from Buffalo, New York who normally deals with mainframes in COBOL and ALGOL. He describes himself as "an avid Atari hobbyist."