55 lines
1.4 KiB
Plaintext
55 lines
1.4 KiB
Plaintext
--
|
|
-- demo\rosetta\n_queens.exw
|
|
-- =========================
|
|
--
|
|
sequence co, -- columns occupied
|
|
-- (ro is implicit)
|
|
fd, -- forward diagonals
|
|
bd, -- backward diagonals
|
|
board
|
|
|
|
atom count
|
|
|
|
procedure solve(integer row, integer N, integer show)
|
|
for col=1 to N do
|
|
if not co[col] then
|
|
integer fdi = col+row-1,
|
|
bdi = row-col+N
|
|
if not fd[fdi]
|
|
and not bd[bdi] then
|
|
board[row][col] = 'Q'
|
|
co[col] = 1
|
|
fd[fdi] = 1
|
|
bd[bdi] = 1
|
|
if row=N then
|
|
if show then
|
|
puts(1,join(board,"\n")&"\n")
|
|
puts(1,repeat('=',N)&"\n")
|
|
end if
|
|
count += 1
|
|
else
|
|
solve(row+1,N,show)
|
|
end if
|
|
board[row][col] = '.'
|
|
co[col] = 0
|
|
fd[fdi] = 0
|
|
bd[bdi] = 0
|
|
end if
|
|
end if
|
|
end for
|
|
end procedure
|
|
|
|
procedure n_queens(integer N=8, integer show=1)
|
|
co = repeat(0,N)
|
|
fd = repeat(0,N*2-1)
|
|
bd = repeat(0,N*2-1)
|
|
board = repeat(repeat('.',N),N)
|
|
count = 0
|
|
solve(1,N,show)
|
|
printf(1,"%d queens: %d solutions\n",{N,count})
|
|
end procedure
|
|
|
|
for N=1 to 14 do
|
|
n_queens(N,N<5)
|
|
end for
|