Jump to content

N-queens minimum and knights and bishops: Difference between revisions

N-queens minimum and knights and bishops (view source)

Revision as of 18:47, 13 May 2022

6,785 bytes added ,  2 years ago
m
→‎{{header|Phix}}: minor tweaks and better times
(→‎{{header|Wren}}: Incorporated latest Go improvement.)
m (→‎{{header|Phix}}: minor tweaks and better times)
Line 1,085:
{{libheader|Phix/pGUI}}
{{libheader|Phix/online}}
You can run this online [http://phix.x10.mx/p2js/minqbn.htm here], andwith explorecheat the finished (green) ones while it toils awaymode on the tougher ones, or watchso it working.should Itall examinesbe 21,801,024done positionsin before22s solving N10, plus doing things in 0(8.4s chunks on a timer probably don't help, so it ends up taking just over 3 mins to completely finish on the desktop,). though 18mins 46s in my web browser, but at least you can explore, pause, resume, or quit it at any point.
Cheat mode drops the final tricky 10N search from 8,163,658 positions to just 183,937. Without cheat mode it takes 1 min 20s to completely finish on the desktop (would be ~7mins in a browser), but it always remains fully interactive throughout.
<!--<lang Phix>(phixonline)-->
<span style="color: #000080;font-style:italic;">--
Line 1,107 ⟶ 1,108:
The window title shows additional information for the selected item.
"""</span>
<span style="color: #008080;">constant</span> <span style="color: #000000;">maxq</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">10</span><span style="color: #0000FF;">,</span> <span style="color: #000080;font-style:italic;">-- 21.8s0s (13 is 3minutes 46s58s, with maxn=1)</span>
<span style="color: #000000;">maxb</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">10</span><span style="color: #0000FF;">,</span> <span style="color: #000080;font-style:italic;">-- 1s (100 is 10s, with maxq=1 and maxn=1)</span>
<span style="color: #000000;">maxn</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">10</span><span style="color: #0000FF;">,</span> <span style="color: #000080;font-style:italic;">-- 3mins1mins 3s10s (9: 17s11.8s, 8: 78.2s1s, with maxq=1)</span>
<span style="color: #000000;">maxqbn</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">max</span><span style="color: #0000FF;">({</span><span style="color: #000000;">maxq</span><span style="color: #0000FF;">,</span><span style="color: #000000;">maxb</span><span style="color: #0000FF;">,</span><span style="color: #000000;">maxn</span><span style="color: #0000FF;">})</span>
<span style="color: #004080;">bool</span> <span style="color: #000000;">cheat</span> <span style="color: #0000FF;">=</span> <span style="color: #004600;">true</span> <span style="color: #000080;font-style:italic;">-- eg find 16N on a 10x10 w/o disproving 15N first.
-- the total time drops to 8.3s (21.9s under p2js).</span>
<span style="color: #004080;">sequence</span> <span style="color: #000000;">board</span>
Line 1,182 ⟶ 1,186:
-- or first half of diagonal (not cols)</span>
<span style="color: #7060A8;">assert</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">res</span><span style="color: #0000FF;">)=</span><span style="color: #000000;">3</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;">res</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">res</span><span style="color: #0000FF;">[</span><span style="color: #000000;">1</span><span style="color: #0000FF;">..</span><span style="color: #000000;">m</span><span style="color: #0000FF;">]&</span><span style="color: #000000;">res</span><span style="color: #0000FF;">[</span><span style="color: #000000;">n2</span><span style="color: #0000FF;">+*</span><span style="color: #000000;">1n</span><span style="color: #0000FF;">..</span><span style="color: #000000;">2</span><span style="color: #0000FF;">*</span><span style="color: #000000;">n</span><span style="color: #0000FF;">+</span><span style="color: #000000;">m</span><span style="color: #0000FF;">-</span><span style="color: #000000;">2</span><span style="color: #0000FF;">]</span>
<span style="color: #008080;">elsif</span> <span style="color: #000000;">piece</span><span style="color: #0000FF;">=</span><span style="color: #008000;">'N'</span> <span style="color: #008080;">and</span> <span style="color: #000000;">n</span><span style="color: #0000FF;">></span><span style="color: #000000;">2</span> <span style="color: #008080;">then</span>
<span style="color: #000080;font-style:italic;">-- first knight, was occupy+2, but by
Line 1,190 ⟶ 1,194:
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #000080;font-style:italic;">-- this cheeky little fella cuts more than half off the
-- last phase of 10N... (a circumstantial optimisation)</span>
<span style="color: #000000;">res</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">reverse</span><span style="color: #0000FF;">(</span><span style="color: #000000;">res</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">return</span> <span style="color: #000000;">res</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span>
Line 1,206 ⟶ 1,213:
<span style="color: #004080;">cdCanvas</span> <span style="color: #000000;">cddbuffer</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">cdcanvas</span>
<span style="color: #008080;">constant</span> <span style="color: #000000;">SQBN</span> <span style="color: #0000FF;">=</span> <span style="color: #008000;">" QBN"</span><span style="color: #0000FF;">,</span> <span style="color: #000080;font-style:italic;">-- (or " RBN")</span>
<span style="color: #000000;">QBNU</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">utf8_to_utf32</span><span style="color: #0000FF;">(</span><span style="color: #008000;">"♕♗♘"</span><span style="color: #0000FF;">)</span>
Line 1,213 ⟶ 1,220:
<span style="color: #004080;">sequence</span> <span style="color: #000000;">state</span>
<span style="color: #000080;font-style:italic;">-- eg go straight for 16N on 10x10, avoid disproving 15N (from sequence mnm = mm_baby(mm,piece,row,col,bnOEIS) -- nope!</span>▼
<span style="color: #008080;">constant</span> <span style="color: #000000;">cheats</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{{</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #000000;">3</span><span style="color: #0000FF;">,</span><span style="color: #000000;">3</span><span style="color: #0000FF;">,</span><span style="color: #000000;">4</span><span style="color: #0000FF;">,</span><span style="color: #000000;">4</span><span style="color: #0000FF;">,</span><span style="color: #000000;">5</span><span style="color: #0000FF;">,</span><span style="color: #000000;">5</span><span style="color: #0000FF;">,</span><span style="color: #000000;">5</span><span style="color: #0000FF;">,</span><span style="color: #000000;">5</span><span style="color: #0000FF;">,</span><span style="color: #000000;">7</span><span style="color: #0000FF;">,</span><span style="color: #000000;">7</span><span style="color: #0000FF;">,</span><span style="color: #000000;">8</span><span style="color: #0000FF;">,</span><span style="color: #000000;">9</span><span style="color: #0000FF;">,</span><span style="color: #000000;">9</span><span style="color: #0000FF;">,</span><span style="color: #000000;">9</span><span style="color: #0000FF;">,</span><span style="color: #000000;">10</span><span style="color: #0000FF;">,</span><span style="color: #000000;">11</span><span style="color: #0000FF;">,</span><span style="color: #000000;">11</span><span style="color: #0000FF;">,</span><span style="color: #000000;">11</span><span style="color: #0000FF;">,</span><span style="color: #000000;">12</span><span style="color: #0000FF;">,</span><span style="color: #000000;">13</span><span style="color: #0000FF;">,</span><span style="color: #000000;">13</span><span style="color: #0000FF;">,</span><span style="color: #000000;">13</span><span style="color: #0000FF;">},</span>
<span style="color: #0000FF;">{</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #000000;">2</span><span style="color: #0000FF;">,</span><span style="color: #000000;">3</span><span style="color: #0000FF;">,</span><span style="color: #000000;">4</span><span style="color: #0000FF;">,</span><span style="color: #000000;">5</span><span style="color: #0000FF;">,</span><span style="color: #000000;">6</span><span style="color: #0000FF;">,</span><span style="color: #000000;">7</span><span style="color: #0000FF;">,</span><span style="color: #000000;">8</span><span style="color: #0000FF;">,</span><span style="color: #000000;">9</span><span style="color: #0000FF;">,</span><span style="color: #000000;">10</span><span style="color: #0000FF;">,</span><span style="color: #000000;">11</span><span style="color: #0000FF;">,</span><span style="color: #000000;">12</span><span style="color: #0000FF;">,</span><span style="color: #000000;">13</span><span style="color: #0000FF;">,</span><span style="color: #000000;">14</span><span style="color: #0000FF;">,</span><span style="color: #000000;">15</span><span style="color: #0000FF;">,</span><span style="color: #000000;">16</span><span style="color: #0000FF;">,</span><span style="color: #000000;">17</span><span style="color: #0000FF;">,</span><span style="color: #000000;">18</span><span style="color: #0000FF;">,</span><span style="color: #000000;">19</span><span style="color: #0000FF;">,</span><span style="color: #000000;">20</span><span style="color: #0000FF;">,</span><span style="color: #000000;">21</span><span style="color: #0000FF;">,</span><span style="color: #000000;">22</span><span style="color: #0000FF;">},</span>
<span style="color: #0040800000FF;">sequence{</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #000000;">mnm4</span><span style="color: #0000FF;">,</span><span style="color: #000000;">4</span><span style="color: #0000FF;">,</span><span style="color: #000000;">4</span><span style="color: #0000FF;">,</span><span style="color: #000000;">mm_baby5</span><span style="color: #0000FF;">(,</span><span style="color: #000000;">mm8</span><span style="color: #0000FF;">,</span><span style="color: #000000;">piece13</span><span style="color: #0000FF;">,</span><span style="color: #000000;">col14</span><span style="color: #0000FF;">,</span><span style="color: #000000;">row14</span><span style="color: #0000FF;">,</span><span style="color: #000000;">bn16</span><span style="color: #0000FF;">),</span><span style="color: #000000;">22</span><span style="color: #0000800000FF;font-">,</span><span style="color:italic #000000;">--24</span><span yepp!style="color: (damy)#0000FF;">,</span><span style="color: #000000;">29</span><span style="color: #0000FF;">,</span><span style="color: #000000;">33</span><span style="color: #0000FF;">}}</span>▼
<span style="color: #000080;font-style:italic;">-- some more timings with cheat mode ON:
-- 11Q: 1s, 12Q: 1.2s, 13Q: 1 min 7s, 14Q: 3 min 35s
-- 11N: 1 min 42s, 12N: gave up</span>
<span style="color: #008080;">procedure</span> <span style="color: #000000;">reset</span><span style="color: #0000FF;">()</span>
Line 1,224 ⟶ 1,239:
<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: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">state</span><span style="color: #0000FF;">[</span><span style="color: #000000;">p</span><span style="color: #0000FF;">])</span> <span style="color: #008080;">do</span>
<span style="color: #004080;">atom</span> <span style="color: #000000;">scolour</span> <span style="color: #0000FF;">=</span> <span style="color: #004600;">CD_RED</span>
<span style="color: #004080000080;">integer</span> <span font-style="color: #000000italic;">m</span>-- <span style="color: #0000FF;">=</span> <span style integer m ="color: #000000;">1</span>
<span style="color: #004080;">integer</span> <span style="color: #000000;">m</span> <span style="color: #0000FF;">=</span> <span style="color: #008080;">iff</span><span style="color: #0000FF;">(</span><span style="color: #000000;">cheat</span><span style="color: #0000FF;">?</span><span style="color: #000000;">cheats</span><span style="color: #0000FF;">[</span><span style="color: #000000;">p</span><span style="color: #0000FF;">][</span><span style="color: #000000;">n</span><span style="color: #0000FF;">]:</span><span style="color: #000000;">1</span><span style="color: #0000FF;">)</span>
<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;">'0'</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: #004080;">sequence</span> <span style="color: #000000;">moves</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">get_moves</span><span style="color: #0000FF;">(</span><span style="color: #000000;">piece</span><span style="color: #0000FF;">,</span><span style="color: #000000;">n</span><span style="color: #0000FF;">,</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #000000;">1</span><span style="color: #0000FF;">)</span>
Line 1,249 ⟶ 1,265:
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">n</span><span style="color: #0000FF;">=</span><span style="color: #000000;">0</span> <span style="color: #008080;">then</span>
<span style="color: #0000FF;">?{</span><span style="color: #008000;">"solved"</span><span style="color: #0000FF;">,(</span><span style="color: #7060A8;">elapsed</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">time</span><span style="color: #0000FF;">()-</span><span style="color: #000000;">t0</span><span style="color: #0000FF;">))}</span>
<span style="color: #7060A8;">IupSetInt</span><span style="color: #0000FF;">(</span><span style="color: #000000;">timer</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"RUN"</span><span style="color: #0000FF;">,</span><span style="color: #004600;">false</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">else</span>
Line 1,372 ⟶ 1,388:
<span style="color: #7060A8;">cdCanvasFont</span><span style="color: #0000FF;">(</span><span style="color: #000000;">cddbuffer</span><span style="color: #0000FF;">,</span> <span style="color: #008000;">"Helvetica"</span><span style="color: #0000FF;">,</span> <span style="color: #004600;">CD_PLAIN</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">fontsize</span><span style="color: #0000FF;">*</span><span style="color: #000000;">2</span><span style="color: #0000FF;">)</span>
<span style="color: #7060A8;">cdCanvasSetForeground</span><span style="color: #0000FF;">(</span><span style="color: #000000;">cddbuffer</span><span style="color: #0000FF;">,</span> <span style="color: #004600;">CD_AMBER</span><span style="color: #0000FF;">)</span>
<span style="color: #004080;">sequence</span> <span style="color: #000000;">mnm</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">mm_baby</span><span style="color: #0000FF;">(</span><span style="color: #000000;">mm</span><span style="color: #0000FF;">,</span><span style="color: #000000;">piece</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;">bn</span><span style="color: #0000FF;">)</span>
▲ <span style="color: #000080;font-style:italic;">-- sequence mnm = mm_baby(mm,piece,row,col,bn) -- nope!</span>
▲ <span style="color: #004080;">sequence</span> <span style="color: #000000;">mnm</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">mm_baby</span><span style="color: #0000FF;">(</span><span style="color: #000000;">mm</span><span style="color: #0000FF;">,</span><span style="color: #000000;">piece</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;">bn</span><span style="color: #0000FF;">)</span> <span style="color: #000080;font-style:italic;">-- yepp! (damy)</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">mnm</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">do</span>
<span style="color: #004080;">integer</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">mx</span><span style="color: #0000FF;">,</span><span style="color: #000000;">my</span><span style="color: #0000FF;">}</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">mnm</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">]</span>
Line 1,401 ⟶ 1,416:
<span style="color: #008080;">function</span> <span style="color: #000000;">help</span><span style="color: #0000FF;">()</span>
<span style="color: #7060A8;">IupMessage</span><span style="color: #0000FF;">(</span><span style="color: #000000;">title</span><span style="color: #0000FF;">,</span><span style="color: #000000;">help_text</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">return</span> <span style="color: #004600;">IUP_IGNORE</span> <span style="color: #000080;font-style:italic;">-- (don't open browser help!)</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span>
Line 1,429 ⟶ 1,444:
<span style="color: #004080;">integer</span> <span style="color: #000000;">p</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">floor</span><span style="color: #0000FF;">((</span><span style="color: #000000;">x</span><span style="color: #0000FF;">+</span><span style="color: #000000;">dx</span><span style="color: #0000FF;">/</span><span style="color: #000000;">2</span><span style="color: #0000FF;">)/</span><span style="color: #000000;">dx</span><span style="color: #0000FF;">)-</span><span style="color: #000000;">36</span><span style="color: #0000FF;">,</span>
<span style="color: #000000;">n</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">floor</span><span style="color: #0000FF;">(</span><span style="color: #000000;">y</span><span style="color: #0000FF;">/</span><span style="color: #000000;">dy</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">p</span><span style="color: #0000FF;">>=</span><span style="color: #000000;">01</span> <span style="color: #008080;">and</span> <span style="color: #000000;">p</span><span style="color: #0000FF;"><</span><span style="color: #000000;">4</span> <span style="color: #008080;">and</span> <span style="color: #000000;">n3</span><span style="color: #0000FF;">></span><span style="color: #000000;">0</span> <span style="color: #008080;">then</span>
<span style="color: #008080;">and</span> <span style="color: #000000;">n</span><span style="color: #0000FF;">>=</span><span style="color: #000000;">cp1</span> <span style="color: #008080;">and</span> <span style="color: #000000;">n</span><span style="color: #0000FF;"><=</span><span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">state</span><span style="color: #0000FF;">[</span><span style="color: #000000;">p</span><span style="color: #0000FF;">])</span> <span style="color: #008080;">then</span>
<span style="color: #000000;">bn</span> <span style="color: #0000FF;">={</span> <span style="color: #7060A8000000;">mincp</span><span style="color: #0000FF;">(,</span><span style="color: #000000;">nbn</span><span style="color: #0000FF;">,}</span> <span style="color: #7060A80000FF;">length=</span> <span style="color: #0000FF;">({</span><span style="color: #000000;">statep</span><span style="color: #0000FF;">[,</span><span style="color: #000000;">cpn</span><span style="color: #0000FF;">]))}</span>
<span style="color: #7060A8;">IupUpdate</span><span style="color: #0000FF;">(</span><span style="color: #000000;">ih</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
Petelomax
7,813

edits

Retrieved from "https://rosettacode.org/wiki/Special:MobileDiff/320651"
Cookies help us deliver our services. By using our services, you agree to our use of cookies.
More information