<!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 [ <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? new-queens:&:list:square<span class="Special"> <- </span>push curr, queens sub-result:num<span class="Special"> <- </span>nqueens n, new-queens result<span class="Special"> <- </span>add result, sub-result <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">reply-if</span> result1, result1 result2:bool<span class="Special"> <- </span>conflicting-diagonal? curr, queens <span class="muControl">reply</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">reply-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">reply</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">reply-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">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 : -->