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 ]