about summary refs log tree commit diff stats
path: root/html/nqueens.mu.html
blob: b05a8618369f9a11e91d932b5fafa75b9193673d (plain) (blame)
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
<!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; }
.muRecipe { color: #ff8700; }
.muData { color: #ffff00; }
.Delimiter { color: #800080; }
.Comment { color: #9090ff; }
.Constant { color: #00a0a0; }
.Special { color: #c00000; }
.muControl { color: #c0a020; }
-->
</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:&amp;:list:square<span class="muRecipe"> -&gt; </span>result:num [
  <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"> &lt;- </span>length queens
  <span class="Delimiter">{</span>
    done?:boolean<span class="Special"> &lt;- </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"> &lt;- </span>copy <span class="Constant">0</span>
  <span class="Delimiter">{</span>
    <span class="muControl">break-unless</span> queens
    first:square<span class="Special"> &lt;- </span>first queens
    existing-rank:num<span class="Special"> &lt;- </span>get first, <span class="Constant">rank:offset</span>
    next-rank<span class="Special"> &lt;- </span>add existing-rank, <span class="Constant">1</span>
  <span class="Delimiter">}</span>
  result<span class="Special"> &lt;- </span>copy <span class="Constant">0</span>
  next-file:num<span class="Special"> &lt;- </span>copy <span class="Constant">0</span>
  <span class="Delimiter">{</span>
    done?:boolean<span class="Special"> &lt;- </span>greater-or-equal next-file, n
    <span class="muControl">break-if</span> done?
    curr:square<span class="Special"> &lt;- </span>merge next-rank, next-file
    <span class="Delimiter">{</span>
      curr-conflicts?:boolean<span class="Special"> &lt;- </span>conflict? curr, queens
      <span class="muControl">break-if</span> curr-conflicts?
      new-queens:&amp;:list:square<span class="Special"> &lt;- </span>push curr, queens
      sub-result:num<span class="Special"> &lt;- </span>nqueens n, new-queens
      result<span class="Special"> &lt;- </span>add result, sub-result
    <span class="Delimiter">}</span>
    next-file<span class="Special"> &lt;- </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:&amp;:list:square<span class="muRecipe"> -&gt; </span>result:boolean [
  <span class="Constant">local-scope</span>
  <span class="Constant">load-ingredients</span>
  result1:boolean<span class="Special"> &lt;- </span>conflicting-file? curr, queens
  <span class="muControl">reply-if</span> result1, result1
  result2:boolean<span class="Special"> &lt;- </span>conflicting-diagonal? curr, queens
  <span class="muControl">reply</span> result2
]

<span class="muRecipe">def</span> conflicting-file? curr:square, queens:&amp;:list:square<span class="muRecipe"> -&gt; </span>result:boolean [
  <span class="Constant">local-scope</span>
  <span class="Constant">load-ingredients</span>
  curr-file:num<span class="Special"> &lt;- </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"> &lt;- </span>first queens
    qfile:num<span class="Special"> &lt;- </span>get q, <span class="Constant">file:offset</span>
    file-match?:boolean<span class="Special"> &lt;- </span>equal curr-file, qfile
    <span class="muControl">reply-if</span> file-match?, <span class="Constant">1/conflict-found</span>
    queens<span class="Special"> &lt;- </span>rest queens
    <span class="muControl">loop</span>
  <span class="Delimiter">}</span>
  <span class="muControl">reply</span> <span class="Constant">0/no-conflict-found</span>
]

<span class="muRecipe">def</span> conflicting-diagonal? curr:square, queens:&amp;:list:square<span class="muRecipe"> -&gt; </span>result:boolean [
  <span class="Constant">local-scope</span>
  <span class="Constant">load-ingredients</span>
  curr-rank:num<span class="Special"> &lt;- </span>get curr, <span class="Constant">rank:offset</span>
  curr-file:num<span class="Special"> &lt;- </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"> &lt;- </span>first queens
    qrank:num<span class="Special"> &lt;- </span>get q, <span class="Constant">rank:offset</span>
    qfile:num<span class="Special"> &lt;- </span>get q, <span class="Constant">file:offset</span>
    rank-delta:num<span class="Special"> &lt;- </span>subtract qrank, curr-rank
    file-delta:num<span class="Special"> &lt;- </span>subtract qfile, curr-file
    rank-delta<span class="Special"> &lt;- </span>abs rank-delta
    file-delta<span class="Special"> &lt;- </span>abs file-delta
    diagonal-match?:boolean<span class="Special"> &lt;- </span>equal rank-delta, file-delta
    <span class="muControl">reply-if</span> diagonal-match?, <span class="Constant">1/conflict-found</span>
    queens<span class="Special"> &lt;- </span>rest queens
    <span class="muControl">loop</span>
  <span class="Delimiter">}</span>
  <span class="muControl">reply</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 : -->