This 8 Queens visualization shows an implementation of an iterative repair algorithm, a greedy algorithm and a simulated annealing algorithm.
Explanations
In the N Queens puzzle you have an N by N chess board. On it you must place N queens so that no queen is threatening any other queen. Queens threaten any queen in the same row, column or diagonal.
There are many possible aglorithms for finding a valid placement of the N queens. The ones implemented here are:
- Random Permutations: The queens are initially placed in random rows and columns such that each queen is in a different row and a different column. During each turn, two queens are selected at random and their columns are swapped. Eventually this algorithm will find a valid placement, though it can be very slow.
- Iterative Repair: The queens are initially placed in random rows and columns such that each queen is in a different row and a different column. During each turn the next queen that is being threatened by any other queen is moved within its row to the location in which there are the least threatening queens. If there are several such spots, one is chosen at random.
- Simulated Annealing: The queens are initially placed in random rows and columns such that each queen is in a different row and a different column. During each turn, an attacked queen is chosen and a random column is picked for that queen. If moving the queen to the new column will reduce the number of attacked queens on the board, the move is taken. Otherwise, the move is taken only with a certain probability, which decreases over time. Hence early on the algorithm will tend to take moves even if they don't improve the situation. Later on, the algorithm will only make moves which improve the situation on the board. The temperature function used is: T(n) = 100 / n where n is the round number. The probability function used to decide if a move with a negative impact on the score is allowed is: P(dE)=exp(dE/T) where dE is the difference in "energy" (the difference in the number of attacked queens) and T is the temperature for the round.
- Greedy: The queens are initially placed in random rows and columns such that each queen is in a different row and a different column. During each turn, A move is chosen that reduces the number of attacked queens on the board by the largest amount. If there are several such moves, one is chosen at random, preferring moves that don't involve the same queen that was moved in the previous round.
