A constraint-satisfaction problem (CSP) asks for an assignment that satisfies a specified set of constraints, without defining an explicit objective function. Feasibility is the requirement: multiple valid solutions may exist without one being objectively better. section 1.3.2
The n-queens problem
Place n queens on an n × n chessboard so that no two share a row, column, or diagonal. In the 4-queens version, two solutions satisfy the constraints; neither is inherently superior. A 7-queens instance can be represented as an ordering, evaluated by counting collisions, and improved through candidate swaps. section 1.3.2 section 6.3
Tabu search handles the 7-queens CSP by generating neighboring configurations, selecting promising moves, and recording recent moves in a tabu structure. With a tabu tenure of three iterations, recently performed swaps are temporarily forbidden; aspiration criteria can still admit a tabu move when appropriate. section 6.3
Listing 6.1 Solving the 7-queens problem
import random
import numpy as np
import matplotlib.pyplot as plt
def get_initial_state(board_size):
queens = list(range(board_size))
random.shuffle(queens)
return queens
Use the Python implementation to connect the formulation to practice: initialize a randomized state, count attacking queens, select non-tabu moves, update the tabu list, and stop after configured iterations or non-improvement. section 6.3
