N-queens problem: Difference between revisions
Content added Content deleted
m (→Python: Niklaus Wirth algorithm: Example program shortened again) |
m (→{{header|Phix}}: use pygments) |
||
Line 11,360: | Line 11,360: | ||
=={{header|Phix}}== |
=={{header|Phix}}== |
||
<!-- |
<!--(phixonline)--> |
||
<syntaxhighlight lang="phix"> |
|||
<span style="color: #008080;">with</span> <span style="color: #008080;">javascript_semantics</span> |
|||
with javascript_semantics |
|||
<span style="color: #000080;font-style:italic;">-- |
|||
-- |
|||
-- demo\rosetta\n_queens.exw |
|||
-- demo\rosetta\n_queens.exw |
|||
-- ========================= |
|||
-- ========================= |
|||
--</span> |
|||
-- |
|||
<span style="color: #004080;">sequence</span> <span style="color: #000000;">co</span><span style="color: #0000FF;">,</span> <span style="color: #000080;font-style:italic;">-- columns occupied |
|||
sequence co, -- columns occupied |
|||
-- (ro is implicit)</span> |
|||
-- (ro is implicit) |
|||
<span style="color: #000000;">fd</span><span style="color: #0000FF;">,</span> <span style="color: #000080;font-style:italic;">-- forward diagonals</span> |
|||
fd, -- forward diagonals |
|||
<span style="color: #000000;">bd</span><span style="color: #0000FF;">,</span> <span style="color: #000080;font-style:italic;">-- backward diagonals</span> |
|||
bd, -- backward diagonals |
|||
board |
|||
<span style="color: #004080;">atom</span> <span style="color: #000000;">count</span> |
|||
atom count |
|||
<span style="color: #008080;">procedure</span> <span style="color: #000000;">solve</span><span style="color: #0000FF;">(</span><span style="color: #004080;">integer</span> <span style="color: #000000;">row</span><span style="color: #0000FF;">,</span> <span style="color: #004080;">integer</span> <span style="color: #000000;">N</span><span style="color: #0000FF;">,</span> <span style="color: #004080;">integer</span> <span style="color: #000000;">show</span><span style="color: #0000FF;">)</span> |
|||
procedure solve(integer row, integer N, integer show) |
|||
<span style="color: #008080;">for</span> <span style="color: #000000;">col</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #000000;">N</span> <span style="color: #008080;">do</span> |
|||
for col=1 to N do |
|||
<span style="color: #008080;">if</span> <span style="color: #008080;">not</span> <span style="color: #000000;">co</span><span style="color: #0000FF;">[</span><span style="color: #000000;">col</span><span style="color: #0000FF;">]</span> <span style="color: #008080;">then</span> |
|||
if not co[col] then |
|||
<span style="color: #004080;">integer</span> <span style="color: #000000;">fdi</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">col</span><span style="color: #0000FF;">+</span><span style="color: #000000;">row</span><span style="color: #0000FF;">-</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span> |
|||
integer fdi = col+row-1, |
|||
<span style="color: #000000;">bdi</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">row</span><span style="color: #0000FF;">-</span><span style="color: #000000;">col</span><span style="color: #0000FF;">+</span><span style="color: #000000;">N</span> |
|||
bdi = row-col+N |
|||
<span style="color: #008080;">if</span> <span style="color: #008080;">not</span> <span style="color: #000000;">fd</span><span style="color: #0000FF;">[</span><span style="color: #000000;">fdi</span><span style="color: #0000FF;">]</span> |
|||
if not fd[fdi] |
|||
<span style="color: #008080;">and</span> <span style="color: #008080;">not</span> <span style="color: #000000;">bd</span><span style="color: #0000FF;">[</span><span style="color: #000000;">bdi</span><span style="color: #0000FF;">]</span> <span style="color: #008080;">then</span> |
|||
and not bd[bdi] then |
|||
<span style="color: #000000;">board</span><span style="color: #0000FF;">[</span><span style="color: #000000;">row</span><span style="color: #0000FF;">][</span><span style="color: #000000;">col</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #008000;">'Q'</span> |
|||
board[row][col] = 'Q' |
|||
<span style="color: #000000;">co</span><span style="color: #0000FF;">[</span><span style="color: #000000;">col</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">1</span> |
|||
co[col] = true |
|||
<span style="color: #000000;">fd</span><span style="color: #0000FF;">[</span><span style="color: #000000;">fdi</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">1</span> |
|||
fd[fdi] = true |
|||
<span style="color: #000000;">bd</span><span style="color: #0000FF;">[</span><span style="color: #000000;">bdi</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">1</span> |
|||
bd[bdi] = true |
|||
<span style="color: #008080;">if</span> <span style="color: #000000;">row</span><span style="color: #0000FF;">=</span><span style="color: #000000;">N</span> <span style="color: #008080;">then</span> |
|||
if row=N then |
|||
<span style="color: #008080;">if</span> <span style="color: #000000;">show</span> <span style="color: #008080;">then</span> |
|||
if show then |
|||
<span style="color: #7060A8;">puts</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #7060A8;">join</span><span style="color: #0000FF;">(</span><span style="color: #000000;">board</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"\n"</span><span style="color: #0000FF;">)&</span><span style="color: #008000;">"\n"</span><span style="color: #0000FF;">)</span> |
|||
puts(1,join(board,"\n")&"\n") |
|||
<span style="color: #7060A8;">puts</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #7060A8;">repeat</span><span style="color: #0000FF;">(</span><span style="color: #008000;">'='</span><span style="color: #0000FF;">,</span><span style="color: #000000;">N</span><span style="color: #0000FF;">)&</span><span style="color: #008000;">"\n"</span><span style="color: #0000FF;">)</span> |
|||
puts(1,repeat('=',N)&"\n") |
|||
end if |
|||
<span style="color: #000000;">count</span> <span style="color: #0000FF;">+=</span> <span style="color: #000000;">1</span> |
|||
count += 1 |
|||
else |
|||
<span style="color: #000000;">solve</span><span style="color: #0000FF;">(</span><span style="color: #000000;">row</span><span style="color: #0000FF;">+</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #000000;">N</span><span style="color: #0000FF;">,</span><span style="color: #000000;">show</span><span style="color: #0000FF;">)</span> |
|||
solve(row+1,N,show) |
|||
end if |
|||
<span style="color: #000000;">board</span><span style="color: #0000FF;">[</span><span style="color: #000000;">row</span><span style="color: #0000FF;">][</span><span style="color: #000000;">col</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #008000;">'.'</span> |
|||
board[row][col] = '.' |
|||
<span style="color: #000000;">co</span><span style="color: #0000FF;">[</span><span style="color: #000000;">col</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">0</span> |
|||
co[col] = false |
|||
<span style="color: #000000;">fd</span><span style="color: #0000FF;">[</span><span style="color: #000000;">fdi</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">0</span> |
|||
fd[fdi] = false |
|||
<span style="color: #000000;">bd</span><span style="color: #0000FF;">[</span><span style="color: #000000;">bdi</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">0</span> |
|||
bd[bdi] = false |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span> |
|||
end if |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span> |
|||
end if |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span> |
|||
end for |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">procedure</span> |
|||
end procedure |
|||
<span style="color: #008080;">procedure</span> <span style="color: #000000;">n_queens</span><span style="color: #0000FF;">(</span><span style="color: #004080;">integer</span> <span style="color: #000000;">N</span><span style="color: #0000FF;">=</span><span style="color: #000000;">8</span><span style="color: #0000FF;">,</span> <span style="color: #004080;">integer</span> <span style="color: #000000;">show</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span><span style="color: #0000FF;">)</span> |
|||
procedure n_queens(integer N=8, integer show=1) |
|||
<span style="color: #000000;">co</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">repeat</span><span style="color: #0000FF;">(</span><span style="color: #000000;">0</span><span style="color: #0000FF;">,</span><span style="color: #000000;">N</span><span style="color: #0000FF;">)</span> |
|||
co = repeat(false,N) |
|||
<span style="color: #000000;">fd</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">repeat</span><span style="color: #0000FF;">(</span><span style="color: #000000;">0</span><span style="color: #0000FF;">,</span><span style="color: #000000;">N</span><span style="color: #0000FF;">*</span><span style="color: #000000;">2</span><span style="color: #0000FF;">-</span><span style="color: #000000;">1</span><span style="color: #0000FF;">)</span> |
|||
fd = repeat(false,N*2-1) |
|||
<span style="color: #000000;">bd</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">repeat</span><span style="color: #0000FF;">(</span><span style="color: #000000;">0</span><span style="color: #0000FF;">,</span><span style="color: #000000;">N</span><span style="color: #0000FF;">*</span><span style="color: #000000;">2</span><span style="color: #0000FF;">-</span><span style="color: #000000;">1</span><span style="color: #0000FF;">)</span> |
|||
bd = repeat(false,N*2-1) |
|||
<span style="color: #000000;">board</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">repeat</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">repeat</span><span style="color: #0000FF;">(</span><span style="color: #008000;">'.'</span><span style="color: #0000FF;">,</span><span style="color: #000000;">N</span><span style="color: #0000FF;">),</span><span style="color: #000000;">N</span><span style="color: #0000FF;">)</span> |
|||
board = repeat(repeat('.',N),N) |
|||
<span style="color: #000000;">count</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">0</span> |
|||
count = 0 |
|||
<span style="color: #000000;">solve</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #000000;">N</span><span style="color: #0000FF;">,</span><span style="color: #000000;">show</span><span style="color: #0000FF;">)</span> |
|||
solve(1,N,show) |
|||
<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"%d queens: %d solutions\n"</span><span style="color: #0000FF;">,{</span><span style="color: #000000;">N</span><span style="color: #0000FF;">,</span><span style="color: #000000;">count</span><span style="color: #0000FF;">})</span> |
|||
printf(1,"%d queens: %d solutions\n",{N,count}) |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">procedure</span> |
|||
end procedure |
|||
<span style="color: #008080;">for</span> <span style="color: #000000;">N</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #008080;">iff</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">platform</span><span style="color: #0000FF;">()=</span><span style="color: #004600;">JS</span><span style="color: #0000FF;">?</span><span style="color: #000000;">12</span><span style="color: #0000FF;">:</span><span style="color: #000000;">14</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">do</span> |
|||
for N=1 to iff(platform()=JS?12:14) do |
|||
<span style="color: #000000;">n_queens</span><span style="color: #0000FF;">(</span><span style="color: #000000;">N</span><span style="color: #0000FF;">,</span><span style="color: #000000;">N</span><span style="color: #0000FF;"><</span><span style="color: #000000;">5</span><span style="color: #0000FF;">)</span> |
|||
n_queens(N,N<5) |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span> |
|||
end for |
|||
<!--</syntaxhighlight>--> |
|||
</syntaxhighlight> |
|||
{{out}} |
{{out}} |
||
<pre> |
<pre> |