1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
|
############################################################################
#
# File: genqueen.icn
#
# Subject: Program to solve arbitrary-size n-queens problem
#
# Author: Peter A. Bigot
#
# Date: October 25, 1990
#
############################################################################
#
# This file is in the public domain.
#
############################################################################
#
# This program solve the non-attacking n-queens problem for (square) boards
# of arbitrary size. The problem consists of placing chess queens on an
# n-by-n grid such that no queen is in the same row, column, or diagonal as
# any other queen. The output is each of the solution boards; rotations
# not considered equal. An example of the output for n:
#
# -----------------
# |Q| | | | | | | |
# -----------------
# | | | | | | |Q| |
# -----------------
# | | | | |Q| | | |
# -----------------
# | | | | | | | |Q|
# -----------------
# | |Q| | | | | | |
# -----------------
# | | | |Q| | | | |
# -----------------
# | | | | | |Q| | |
# -----------------
# | | |Q| | | | | |
# -----------------
#
# Usage: genqueen n
# where n is the number of rows / columns in the board. The default for n
# is 6.
#
############################################################################
global
n, # Number of rows/columns
rw, # List of queens in each row
dd, # List of queens in each down diagonal
ud # List of queens in each up diagonal
procedure main (args) # Program arguments
n := integer (args [1]) | 6
rw := list (n)
dd := list (2*n-1)
ud := list (2*n-1)
solvequeen (1)
return
end # procedure main
# placequeen(c) -- Place a queen in every permissible position in column c.
# Suspend with each result.
procedure placequeen (c) # Column at which to place queen
local r # Possible placement row
every r := 1 to n do
suspend (/rw [r] <- /dd [r+c-1] <- /ud [n+r-c] <- c)
fail
end # procedure placequeen
# solvequeen(c) -- Place the c'th and following column queens on the board.
# Write board if have completed it. Suspends all viable results
procedure solvequeen (c) # Column for next queen placement
if (c > n) then {
# Have placed all required queens. Write the board, and resume search.
writeboard ()
fail
}
suspend placequeen (c) & solvequeen (c+1)
fail
end # procedure solvequeen
# writeboard() -- Write an image of the board with the queen positions
# represented by Qs.
procedure writeboard ()
local
r, # Index over rows during print
c, # Column of queen in row r
row # Depiction of row as its created
write (repl ("--", n), "-")
every r := 1 to n do {
c := rw [r]
row := repl ("| ", n) || "|"
row [2*c] := "Q"
write (row)
write (repl ("--", n), "-")
}
write ()
end # procedure writeboard
|
