Алгоритм N королев

Question

Algorithm NQueens (k, n) //Prints all Solution to the n-queens problem 
{ 
    for i := 1 to n do 
    { 
     if Place (k, i) then 
     { 
      x[k] := i; 
      if (k = n) then write (x [1 : n] 
      else NQueens (k+1, n); 
     } 
    } 
} 

Algorithm Place (k, i) 
{ 
    for j := 1 to k-1 do 
     if ((x[ j ] = // in the same column 
      or (Abs(x [ j ] - i) =Abs (j – k))) // or in the same diagonal 
     then return false; 
     return true; 
} 

Приведенный выше код для решения задачи N ферзей с помощью backtracking.I думаю, что это может поставить первые 2 маток двух строк в соответствующих столбцах, а затем, когда дело доходит до 3-го ряда королевы она может» т. е. ни одна королева не должна атаковать, и она просто выйдет из фермы алгоритмов N ... Итак, как этот алгоритм реализует обратное отслеживание?

Answer 1

Секрет здесь - рекурсия.

Пусть каждый уровень отступа ниже указывает уровень рекурсии.

(не то, что будет на самом деле произошло, так как третья королева легко могут быть размещены, но только бы сделали совсем немного больше письменной форме и/или мыслительные, чтобы добраться до случая, который будет на самом деле отказ)

try to place first queen 
success 
    try to place second queen 
    success 
     try to place third queen 
     fail 
    try to place second queen in another position 
    success 
     try to place third queen 
     success 
     try to place fourth queen 

что-то больше в соответствии с тем, что код на самом деле делает: (до сих пор не то, что будет на самом деле произойдет)

first queen 
i = 1 
Can place? Yes. Cool, recurse. 
    second queen 
    i = 1 
    Can place? No. 
    i = 2 
    Can place? No. 
    i = 3 
    Can place? Yes. Cool, recurse. 
     third queen 
     i = 1 
     Can place? No. 
     i = 2 
     Can place? No. 
     ... (can be placed at no position) 
     fail 
     back to second queen 
    i = 4 
    Can place? Yes. Cool, recurse. 
     third queen 
     i = 1 
     Can place? No. 
     ... 

Я надеюсь, что помогает.

Answer 2

Я написал detailed, commented implementation of the N Queens problem in Python и выставил его на GitHub. Взглянуть!

Answer 3

У меня есть код для этого без использования backtracking, но приятно, что это дает временную сложность большого-о (n).

// when n is even... 
for(j=1;j<=n/2;j++) 
{ 
    x[j]=2*j; 
}; 
i=1; 
for(j=n/2 +1 ;j<=n;j++) 
{ 
    x[j] =i; 
    i=(2*i)+1; 
} 

// when n is odd.. 
i=0; 
for(j=1;j<=(n/2+1);j++) 
{ 
    x[i] = (2*i)+1; 
    i++; 
} 
i=1; 
for(j=(n/2+2);j<=n;j++) 
{ 
    x[j] = 2*i; 
    i++; 
} 

Этот код работает хорошо и дает одно решение, но теперь я ищу все возможные решения, используя этот алгоритм.