The Eight Queens Problem. A movie


Note that the speed is being manipulated as it plays, so that much of it runs at Greenfoot's fastest normal speed.

The first part of this movie show the documentation provided for the basic classes, such as UrRobot and KarelWorld. Then we populate the world and begin the simulation. At the end, when the robot turns off, we move the robot to see the last queen that was correctly placed.

When a queen is initially placed on a street, the robot checks to see if there is another queen (beeper) on the same avenue, and on the two diagonals. If there is, the position can be attacked, so the robot moves the beeper and checks again. When it finds no successful attacks it moves to the next row (street). However, if it tries every corner on that row unsuccessfully, it must back up (recursive backtracking) to the previous row and keep trying there. The program eventually finds a solution.