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
102
103
104
|
############################################################################
#
# Name: queens.icn
#
# Title: Generate solutions to the n-queens problem
#
# Author: Stephen B. Wampler
#
# Date: June 10, 1988
#
############################################################################
#
# This program displays the solutions to the non-attacking n-
# queens problem: the ways in which n queens can be placed on an
# n-by-n chessboard so that no queen can attack another. A positive
# integer can be given as a command line argument to specify the
# number of queens. For example,
#
# iconx queens -n8
#
# displays the solutions for 8 queens on an 8-by-8 chessboard. The
# default value in the absence of an argument is 6. One solution
# for six queens is:
#
# -------------------------
# | | Q | | | | |
# -------------------------
# | | | | Q | | |
# -------------------------
# | | | | | | Q |
# -------------------------
# | Q | | | | | |
# -------------------------
# | | | Q | | | |
# -------------------------
# | | | | | Q | |
# -------------------------
#
# Comments: There are many approaches to programming solutions to
# the n-queens problem. This program is worth reading for
# its programming techniques.
#
############################################################################
#
# Links: options, post
#
############################################################################
link options, post
global n, solution
procedure main(args)
local i, opts
Init__()
opts := options(args,"n+")
n := \opts["n"] | 6
if n <= 0 then stop("-n needs a positive numeric parameter")
solution := list(n) # ... and a list of column solutions
write(n,"-Queens:")
every q(1) # start by placing queen in first column
Term__()
end
# q(c) - place a queen in column c.
#
procedure q(c)
local r
static up, down, rows
initial {
up := list(2*n-1,0)
down := list(2*n-1,0)
rows := list(n,0)
}
every 0 = rows[r := 1 to n] = up[n+r-c] = down[r+c-1] &
rows[r] <- up[n+r-c] <- down[r+c-1] <- 1 do {
solution[c] := r # record placement.
if c = n then show()
else q(c + 1) # try to place next queen.
}
end
# show the solution on a chess board.
#
procedure show()
static count, line, border
initial {
count := 0
line := repl("| ",n) || "|"
border := repl("----",n) || "-"
}
write("solution: ", count+:=1)
write(" ", border)
every line[4*(!solution - 1) + 3] <- "Q" do {
write(" ", line)
write(" ", border)
}
write()
end
|
