Four Queens problem
Algorithm idea
The idea of the algorithm is to place the tiles successively in the columns. When it is not possible to place a tile in a column, we go back and adjust the tile in the previous column.
Solution algorithm using backspace or deep search
This algorithm uses backspace to find an array of four tiles in a 4×4 grid so that there are no two tiles in the same row, the same column, or on the diagonal.
Input: A row array of size 4
Output: true , if there is a solution or false , if there is no solution
procedure four_reines (row)
k: = 1
row (1): = 0
while k> 0 do
begin
row (k): = row (k + 1)
while row (k) <= 4 and there is conflict in column k , row row (k) do
row (k) = row (k + 1)
if row (k) <= 4 then
if k = 4 then
return (true)
else
begin
k: = k + 1
row (k): = 0
end
else
k: = k-1
end
return (false)
end four_reinas
The following Graph shows the tree generated by the previous algorithm in the search for a solution to the problem, where the solution appears at vertex 8.
This algorithm works perfectly for n queens with n> = 4 since for n = 2 or n = 3 there is no solution.
Going back or searching in depth is of particular interest in problems like that of the n queens, where all you want is a solution. Since the solution appears at a terminal vertex, moving to the terminal vertices as soon as possible generally prevents the generation of many unnecessary vertices.
