The N-queens Problem
The problem
The N Queen is the problem of placing N chess queens on an N×N chessboard so that no two queens attack each other. For example, following is a solution for N = 4.
No two queens are on the same row, column, or diagonal.
Solutions exist for all natural numbers N with the exception of N=2 and N=3.
Run
Run index.js to view an animation, created using the p5.js-library.
Hill-climbing search
The N-queens Problem is here solved by a hill-climbing search algorithm. In general, hill-climbing search algorithm is simply a loop that continually moves in the direction of increasing value - that is, uphill. It terminates when it reaches a "peak" where no neighbor has a better value. Being a local search algorithm, hill-climbing does not look ahead beyond the immediate neighbors of the current state. Each state has N queens on the NxN board, one per column. The successor of a state are all possible states generated by moving a single queen to another square in the same column. This means that each state has 8x7 = 56 successors.
Heuristic function
The heuristic cost function is the number of pairs of queens that are attacking each other, either directly or indirectly. The global minimum of this function is zero, which occurs only at perfect solutions. Under is an example of a state, showing both the placements of the queens, as well as the heuristic cost, h, for each square. For this state h = 17.
Local Maxima
Hill-climbing often gets stuck because of local maxima. A local maximum is a peak that is higher than each of its neighborig states but lower than the global maximum. Here this means that every move of a single queen makes the situation worse, hence making the algorithm getting stuck. To fix this this algorithm was extended to the random-restart hill-climbing search algorithm.
Random-restart hill-climbing
Random-restart hill-climbing conducts a series of hill-climbing searches from randomly generated initial states, until a goal is found. In this implementation I let the algorithm try to find a goal using the original state, but until a threshold is reached. If the threshold is reached and no solution is found, a new random initial state is generated and the algorithm tries again. With the random-restart feauture implemented, the algorithm becomes very effective.
Snapshots
Under are some snapshots for different N's. The highest value of N I have tried is N = 100, in which a solution was found in about 10 minutes, using maxAttempts = 1500.
| Initial State | Solution |
|---|---|
 |
 |
 |
 |
 |
 |
Tests
To check the completeness of the algorithm one can run multiple testcases (now set to 200 problems with random initial state) for the different N's. The results gets logged in the console. Eventually when N grows , one must increase the threshold for the maxAttempts in order to find a solution. As you can see, time increases exponentially when N grows, but a lot can be done to speed up this algorithm.
