THE EIGHT QUEENS PROBLEM
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."
Listing QUEENS8.BAS Download