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
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
|
<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01//EN" "http://www.w3.org/TR/html4/strict.dtd">
<html>
<head>
<meta http-equiv="content-type" content="text/html; charset=UTF-8">
<title>Mu - nqueens.mu</title>
<meta name="Generator" content="Vim/7.4">
<meta name="plugin-version" content="vim7.4_v2">
<meta name="syntax" content="none">
<meta name="settings" content="use_css,pre_wrap,no_foldcolumn,expand_tabs,prevent_copy=">
<meta name="colorscheme" content="minimal">
<style type="text/css">
<!--
pre { white-space: pre-wrap; font-family: monospace; color: #eeeeee; background-color: #080808; }
body { font-size: 12pt; font-family: monospace; color: #eeeeee; background-color: #080808; }
* { font-size: 12pt; font-size: 1em; }
.muData { color: #ffff00; }
.muControl { color: #c0a020; }
.Delimiter { color: #800080; }
.Comment { color: #9090ff; }
.Constant { color: #00a0a0; }
.Special { color: #c00000; }
.muRecipe { color: #ff8700; }
-->
</style>
<script type='text/javascript'>
<!--
-->
</script>
</head>
<body>
<pre id='vimCodeElement'>
<span class="Comment"># <a href="http://rosettacode.org/wiki/N-queens_problem">http://rosettacode.org/wiki/N-queens_problem</a></span>
<span class="Comment"># port of the Arc solution at <a href="http://arclanguage.org/item?id=19743">http://arclanguage.org/item?id=19743</a></span>
<span class="Comment"># run with tracing turned on:</span>
<span class="Comment"># ./mu --trace nqueens.mu</span>
<span class="muData">container</span> square [
rank:num
file:num
]
<span class="muRecipe">def</span> nqueens n:num, queens:&:list:square<span class="muRecipe"> -> </span>result:num, queens:&:list:square [
<span class="Constant">local-scope</span>
<span class="Constant">load-ingredients</span>
<span class="Comment"># if 'queens' is already long enough, print it and return</span>
added-so-far:num <span class="Special"><-</span> length queens
<span class="Delimiter">{</span>
done?:bool <span class="Special"><-</span> greater-or-equal added-so-far, n
<span class="muControl">break-unless</span> done?
stash queens
<span class="muControl">return</span><span class="Constant"> 1</span>
<span class="Delimiter">}</span>
<span class="Comment"># still work to do</span>
next-rank:num <span class="Special"><-</span> copy<span class="Constant"> 0</span>
<span class="Delimiter">{</span>
<span class="muControl">break-unless</span> queens
first:square <span class="Special"><-</span> first queens
existing-rank:num <span class="Special"><-</span> get first, <span class="Constant">rank:offset</span>
next-rank <span class="Special"><-</span> add existing-rank,<span class="Constant"> 1</span>
<span class="Delimiter">}</span>
result <span class="Special"><-</span> copy<span class="Constant"> 0</span>
next-file:num <span class="Special"><-</span> copy<span class="Constant"> 0</span>
<span class="Delimiter">{</span>
done?:bool <span class="Special"><-</span> greater-or-equal next-file, n
<span class="muControl">break-if</span> done?
curr:square <span class="Special"><-</span> merge next-rank, next-file
<span class="Delimiter">{</span>
curr-conflicts?:bool <span class="Special"><-</span> conflict? curr, queens
<span class="muControl">break-if</span> curr-conflicts?
queens:&:list:square <span class="Special"><-</span> push curr, queens
sub-result:num <span class="Special"><-</span> nqueens n, queens
result <span class="Special"><-</span> add result, sub-result
queens <span class="Special"><-</span> rest queens
<span class="Delimiter">}</span>
next-file <span class="Special"><-</span> add next-file,<span class="Constant"> 1</span>
<span class="muControl">loop</span>
<span class="Delimiter">}</span>
]
<span class="muRecipe">def</span> conflict? curr:square, queens:&:list:square<span class="muRecipe"> -> </span>result:bool [
<span class="Constant">local-scope</span>
<span class="Constant">load-ingredients</span>
result1:bool <span class="Special"><-</span> conflicting-file? curr, queens
<span class="muControl">return-if</span> result1, result1
result2:bool <span class="Special"><-</span> conflicting-diagonal? curr, queens
<span class="muControl">return</span> result2
]
<span class="muRecipe">def</span> conflicting-file? curr:square, queens:&:list:square<span class="muRecipe"> -> </span>result:bool [
<span class="Constant">local-scope</span>
<span class="Constant">load-ingredients</span>
curr-file:num <span class="Special"><-</span> get curr, <span class="Constant">file:offset</span>
<span class="Delimiter">{</span>
<span class="muControl">break-unless</span> queens
q:square <span class="Special"><-</span> first queens
qfile:num <span class="Special"><-</span> get q, <span class="Constant">file:offset</span>
file-match?:bool <span class="Special"><-</span> equal curr-file, qfile
<span class="muControl">return-if</span> file-match?, <span class="Constant">1/conflict-found</span>
queens <span class="Special"><-</span> rest queens
<span class="muControl">loop</span>
<span class="Delimiter">}</span>
<span class="muControl">return</span> <span class="Constant">0/no-conflict-found</span>
]
<span class="muRecipe">def</span> conflicting-diagonal? curr:square, queens:&:list:square<span class="muRecipe"> -> </span>result:bool [
<span class="Constant">local-scope</span>
<span class="Constant">load-ingredients</span>
curr-rank:num <span class="Special"><-</span> get curr, <span class="Constant">rank:offset</span>
curr-file:num <span class="Special"><-</span> get curr, <span class="Constant">file:offset</span>
<span class="Delimiter">{</span>
<span class="muControl">break-unless</span> queens
q:square <span class="Special"><-</span> first queens
qrank:num <span class="Special"><-</span> get q, <span class="Constant">rank:offset</span>
qfile:num <span class="Special"><-</span> get q, <span class="Constant">file:offset</span>
rank-delta:num <span class="Special"><-</span> subtract qrank, curr-rank
file-delta:num <span class="Special"><-</span> subtract qfile, curr-file
rank-delta <span class="Special"><-</span> abs rank-delta
file-delta <span class="Special"><-</span> abs file-delta
diagonal-match?:bool <span class="Special"><-</span> equal rank-delta, file-delta
<span class="muControl">return-if</span> diagonal-match?, <span class="Constant">1/conflict-found</span>
queens <span class="Special"><-</span> rest queens
<span class="muControl">loop</span>
<span class="Delimiter">}</span>
<span class="muControl">return</span> <span class="Constant">0/no-conflict-found</span>
]
<span class="muRecipe">def</span> main [
nqueens<span class="Constant"> 4</span>
$dump-trace <span class="Constant">[app]</span>
]
</pre>
</body>
</html>
<!-- vim: set foldmethod=manual : -->
|