The n-queens problem asks you to place n queens on an n-by-n chessboard so that no two share a row, column, or diagonal. It is a constraint-satisfaction problem: satisfying every constraint matters, rather than optimizing an explicit objective function. section 6.3 section 1.3.2
A 7-queens tabu-search walkthrough
A 7-queens configuration begins with four collisions: Q1–Q2, Q2–Q6, Q4–Q5, and Q6–Q7. Representing the board as an ordering allows neighboring configurations to be generated by swaps. Swapping Q1 and Q7 reduces the collisions from four to two; a tabu tenure of three then forbids that recent swap for three iterations. Later swaps reduce the count to one, while aspiration criteria can permit a nearly expired tabu move. Python listings generate an initial state, count attacks, select moves, update the tabu list, and stop after repeated non-improvement. section 6.3
Key characteristics:
- Treats a board with no attacking queen pairs as a valid solution. section 6.3
- Uses collision or attack counts to compare candidate configurations during tabu search, without making that count the original CSP objective. section 6.3 section 1.3.2
- Shows that the 4-by-4 problem has two solutions, neither inherently better than the other. section 1.3.2
Figure 6.8 TS initialization for a 7-queens problem. At the left, the dotted lines show the 4 collisions between the queens. In the middle, C represents the column where a queen Q is placed. At the right, * denotes the swap that gives the best neighboring solution.
Visualizes the initial 7-queens board, its four collisions, the ordering representation, and the best neighboring swap. section 6.3
