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
|
-- Test file for Kate's Euphoria syntax highlighting/code folding.
-- BEGIN region marker test
-- code here
-- END region marker test
-- The N Queens Problem:
-- Place N Queens on an NxN chess board
-- such that they don't threaten each other.
constant N = 8 -- try some other sizes
constant ROW = 1, COLUMN = 2
constant TRUE = 1, FALSE = 0
type square(sequence x)
-- a square on the board
return length(x) = 2
end type
type row(integer x)
-- a row on the board
return x >= 1 and x <= N
end type
function threat(square q1, square q2)
-- do two queens threaten each other?
if q1[COLUMN] = q2[COLUMN] then
return TRUE
elsif q1[ROW] - q1[COLUMN] = q2[ROW] - q2[COLUMN] then
return TRUE
elsif q1[ROW] + q1[COLUMN] = q2[ROW] + q2[COLUMN] then
return TRUE
elsif q1[ROW] = q2[ROW] then
return TRUE
else
return FALSE
end if
end function
function conflict(square q, sequence queens)
-- Would square p cause a conflict with other queens on board so far?
for i = 1 to length(queens) do
if threat(q, queens[i]) then
return TRUE
end if
end for
return FALSE
end function
integer soln
soln = 0 -- solution number
procedure print_board(sequence queens)
-- print a solution, showing the Queens on the board
integer k
position(1, 1)
printf(1, "Solution #%d\n\n ", soln)
for c = 'a' to 'a' + N - 1 do
printf(1, "%2s", c)
end for
puts(1, "\n")
for r = 1 to N do
printf(1, "%2d ", r)
for c = 1 to N do
if find({r,c}, queens) then
puts(1, "Q ")
else
puts(1, ". ")
end if
end for
puts(1, "\n")
end for
puts(1, "\nPress Enter. (q to quit) ")
while TRUE do
k = get_key()
if k = 'q' then
abort(0)
elsif k != -1 then
exit
end if
end while
end procedure
procedure place_queen(sequence queens)
-- place queens on a NxN chess board
-- (recursive procedure)
row r -- only need to consider one row for each queen
if length(queens) = N then
soln += 1
print_board(queens)
return
end if
r = length(queens)+1
for c = 1 to N do
if not conflict({r,c}, queens) then
place_queen(append(queens, {r,c}))
end if
end for
end procedure
|
