1 # http://rosettacode.org/wiki/N-queens_problem
 2 # port of the Arc solution at http://arclanguage.org/item?id=19743
 3 # run with tracing turned on:
 4 #   ./mu --trace nqueens.mu
 5 
 6 container square [
 7   rank:num
 8   file:num
 9 ]
10 
11 def nqueens n:num, queens:&:list:square -> result:num, queens:&:list:square [
12   local-scope
13   load-ingredients
14   # if 'queens' is already long enough, print it and return
15   added-so-far:num <- length queens
16   {
17   ¦ done?:bool <- greater-or-equal added-so-far, n
18   ¦ break-unless done?
19   ¦ stash queens
20   ¦ return 1
21   }
22   # still work to do
23   next-rank:num <- copy 0
24   {
25   ¦ break-unless queens
26   ¦ first:square <- first queens
27   ¦ existing-rank:num <- get first, rank:offset
28   ¦ next-rank <- add existing-rank, 1
29   }
30   result <- copy 0
31   next-file:num <- copy 0
32   {
33   ¦ done?:bool <- greater-or-equal next-file, n
34   ¦ break-if done?
35   ¦ curr:square <- merge next-rank, next-file
36   ¦ {
37   ¦ ¦ curr-conflicts?:bool <- conflict? curr, queens
38   ¦ ¦ break-if curr-conflicts?
39   ¦ ¦ queens:&:list:square <- push curr, queens
40   ¦ ¦ sub-result:num <- nqueens n, queens
41   ¦ ¦ result <- add result, sub-result
42   ¦ ¦ queens <- rest queens
43   ¦ }
44   ¦ next-file <- add next-file, 1
45   ¦ loop
46   }
47 ]
48 
49 def conflict? curr:square, queens:&:list:square -> result:bool [
50   local-scope
51   load-ingredients
52   result1:bool <- conflicting-file? curr, queens
53   return-if result1, result1
54   result2:bool <- conflicting-diagonal? curr, queens
55   return result2
56 ]
57 
58 def conflicting-file? curr:square, queens:&:list:square -> result:bool [
59   local-scope
60   load-ingredients
61   curr-file:num <- get curr, file:offset
62   {
63   ¦ break-unless queens
64   ¦ q:square <- first queens
65   ¦ qfile:num <- get q, file:offset
66   ¦ file-match?:bool <- equal curr-file, qfile
67   ¦ return-if file-match?, 1/conflict-found
68   ¦ queens <- rest queens
69   ¦ loop
70   }
71   return 0/no-conflict-found
72 ]
73 
74 def conflicting-diagonal? curr:square, queens:&:list:square -> result:bool [
75   local-scope
76   load-ingredients
77   curr-rank:num <- get curr, rank:offset
78   curr-file:num <- get curr, file:offset
79   {
80   ¦ break-unless queens
81   ¦ q:square <- first queens
82   ¦ qrank:num <- get q, rank:offset
83   ¦ qfile:num <- get q, file:offset
84   ¦ rank-delta:num <- subtract qrank, curr-rank
85   ¦ file-delta:num <- subtract qfile, curr-file
86   ¦ rank-delta <- abs rank-delta
87   ¦ file-delta <- abs file-delta
88   ¦ diagonal-match?:bool <- equal rank-delta, file-delta
89   ¦ return-if diagonal-match?, 1/conflict-found
90   ¦ queens <- rest queens
91   ¦ loop
92   }
93   return 0/no-conflict-found
94 ]
95 
96 def main [
97   nqueens 4
98   $dump-trace [app]
99 ]