

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


mata
real matrix queens(real scalar n) {
	real scalar i, j, k, p, q
	real rowvector a, s, u, v
	real matrix m
 
	m = J(0, n, .)
	a = 1..n
	s = J(1, n, 0)
	u = J(1, 2*n-1, 1)
	v = J(1, 2*n-1, 1)
	i = 1
L1:	if (i > n) {
		m = m\a
		goto L4
	}
	j=i
L2:	k = a[j]
	p = i-k+n
	q = i+k-1
	if (u[p] & v[q]) {
		u[p] = v[q] = 0
		a[j] = a[i]
		a[i] = k
		s[i++] = j
		goto L1
	}
L3:	if (++j <= n) goto L2
L4:	if (--i == 0) return(m)
	j = s[i]
	k = a[i]
	a[i] = a[j]
	a[j] = k
	p = i-k+n
	q = i+k-1
	u[p] = v[q] = 1
	goto L3
}
 
a = queens(8)
e = I(8)
1:/e[a[1,.],.]
       1   2   3   4   5   6   7   8
    +---------------------------------+
  1 |  1   .   .   .   .   .   .   .  |
  2 |  .   .   .   .   1   .   .   .  |
  3 |  .   .   .   .   .   .   .   1  |
  4 |  .   .   .   .   .   1   .   .  |
  5 |  .   .   1   .   .   .   .   .  |
  6 |  .   .   .   .   .   .   1   .  |
  7 |  .   1   .   .   .   .   .   .  |
  8 |  .   .   .   1   .   .   .   .  |
    +---------------------------------+
 
 
rows(a)
  92
end