

Solve the eight queens puzzle.



You can extend the problem to solve the puzzle with a board of size   NxN.

For the number of solutions for small values of   N,   see   OEIS: A000170.



Related tasks

 A* search algorithm
 Solve a Hidato puzzle
 Solve a Holy Knight's tour
 Knight's tour
 Peaceful chess queen armies
 Solve a Hopido puzzle
 Solve a Numbrix puzzle
 Solve the no connection puzzle


/* translation of Fortran 77, return solutions as permutations */
 
queens(n) := block([a, i, j, m, p, q, r, s, u, v, w, y, z],
a: makelist(i, i, 1, n), s: a*0, u: makelist(0, i, 1, 4*n - 2),
m: 0, i: 1, r: 2*n - 1, w: [ ], go(L40), L30, s[i]: j, u[p]: 1,
u[q + r]: 1, i: i + 1, L40, if i > n then go(L80), j: i, L50,
z: a[i], y: a[j], p: i - y + n, q: i + y - 1, a[i]: y, a[j]: z,
if u[p] = 0 and u[q + r] = 0 then go(L30), L60, j: j + 1,
if j <= n then go(L50), L70, j: j - 1, if j = i then go(L90),
z: a[i], a[i]: a[j], a[j]: z, go(L70), L80, m: m + 1,
w: endcons(copylist(a), w), L90, i: i - 1, if i = 0 then go(L100),
p: i - a[i] + n, q: i + a[i] - 1, j: s[i], u[p]: 0, u[q + r]: 0,
go(L60), L100, w)$
 
queens(8); /* [[1, 5, 8, 6, 3, 7, 2, 4],
               [1, 6, 8, 3, 7, 4, 2, 5],
               ...]] */
length(%); /* 92 */