Heuristic Repair
At initial state, in which every variable is assigned a value and the successor function choose a new value for a variable, the most obvious heuristic is select the value that should bring a minimum number of conflicts with other variable . This is called min conflicts heuristic.
Example
Q | 2 | Q | 3 | Q | |||||||||||||||||||||
Q | 2 | Q | 3 | Q | |||||||||||||||||||||
Q | 1 | Q | Q | Q | |||||||||||||||||||||
Q | 2 | Q | 2 | Q | |||||||||||||||||||||
Q | 3 | Q | 3 | Q | |||||||||||||||||||||
Q | 1 | 2 | Q | Q | |||||||||||||||||||||
Q | 2 | Q | 3 | Q | |||||||||||||||||||||
Q | 0 | Q | |||||||||||||||||||||||
Stage 1 | Stage 2 | Stage 3 | |||||||||||||||||||||||
From the above Table, 8 queen problem we will start with the 8 queens, one per column in a permutation of the 8 rows, .by having2 queens. which swaps rows.
If the placement of Queens in board in 1st stage is not counted, then the runtime of min conflicts is independent of problem size.
So by using min conflicts algorithm, even we can solve million queens problem in an average of 50 steps.
n queens is easy for local search because solutions are distributed through out the state space (i.e.,) chess board.
Algorithm MIN-CONFLICTS
function MIN_CONFLICTS (CSP, max steps) returns a solution or failure
Inputs: CSP, a constraint satisfaction problem' max steps, the number of steps allowed before giving up.
current ← an initial complete assignment for CSP for i = 1 to max steps do
if current is a solution for CSP then return current
var ← a randomly chosen, conflicted variable from VARIABLES [CSP]
value ← the value v for var that minimizes conflicts (VAR, v, current, CSP)
set var = value in current.
return failure.
