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

Content added Content deleted
(Added Perl)
m (syntax highlighting fixup automation)
Line 11: Line 11:
<br><br>
<br><br>
=={{header|F_Sharp|F#}}==
=={{header|F_Sharp|F#}}==
<lang fsharp>
<syntaxhighlight lang="fsharp">
// Minimum knights to attack all squares not occupied on an NxN chess board. Nigel Galloway: May 12th., 2022
// Minimum knights to attack all squares not occupied on an NxN chess board. Nigel Galloway: May 12th., 2022
type att={n:uint64; g:uint64}
type att={n:uint64; g:uint64}
Line 38: Line 38:
printfn "Solution found using %d knights in %A:" rn (System.DateTime.UtcNow-t); tc rb.att
printfn "Solution found using %d knights in %A:" rn (System.DateTime.UtcNow-t); tc rb.att
for n in 1..10 do solveK n
for n in 1..10 do solveK n
</syntaxhighlight>
</lang>
{{out}}
{{out}}
<pre>
<pre>
Line 131: Line 131:


Timing is for an Intel Core i7-8565U machine running Ubuntu 20.04.
Timing is for an Intel Core i7-8565U machine running Ubuntu 20.04.
<lang go>package main
<syntaxhighlight lang="go">package main


import (
import (
Line 336: Line 336:
elapsed := time.Now().Sub(start)
elapsed := time.Now().Sub(start)
fmt.Printf("Took %s\n", elapsed)
fmt.Printf("Took %s\n", elapsed)
}</lang>
}</syntaxhighlight>


{{out}}
{{out}}
Line 428: Line 428:
This is a crude attempt -- brute force search with some minor state space pruning. I am not patient enough to run this for boards larger than 7x7 for knights:
This is a crude attempt -- brute force search with some minor state space pruning. I am not patient enough to run this for boards larger than 7x7 for knights:


<syntaxhighlight lang="j">
<lang J>
genboard=: {{
genboard=: {{
safelen=:2*len=: {.y
safelen=:2*len=: {.y
Line 528: Line 528:
end.
end.
end.
end.
}}</lang>
}}</syntaxhighlight>


Task output:
Task output:


<lang J> task 10
<syntaxhighlight lang="j"> task 10
+--+--+--+ B: 1
+--+--+--+ B: 1
|B |Q |K | Q: 1
|B |Q |K | Q: 1
Line 608: Line 608:
|. . . . . . . . . . |. . . . . . . . . . |
|. . . . . . . . . . |. . . . . . . . . . |
+--------------------+--------------------+
+--------------------+--------------------+
</syntaxhighlight>
</lang>


=={{header|Julia}}==
=={{header|Julia}}==
Uses the Cbc optimizer (github.com/coin-or/Cbc) for its complementarity support.
Uses the Cbc optimizer (github.com/coin-or/Cbc) for its complementarity support.
<lang ruby>""" Rosetta code task N-queens_minimum_and_knights_and_bishops """
<syntaxhighlight lang="ruby">""" Rosetta code task N-queens_minimum_and_knights_and_bishops """


import Cbc
import Cbc
Line 725: Line 725:
"\nKnights:\n", examples[3])
"\nKnights:\n", examples[3])


</lang> {{out}}
</syntaxhighlight> {{out}}
<pre>
<pre>
Squares Queens Bishops Knights
Squares Queens Bishops Knights
Line 784: Line 784:
The first Q,B in the first row is only placed lmt..mid because of symmetry reasons.<br>
The first Q,B in the first row is only placed lmt..mid because of symmetry reasons.<br>
14 Queens takes 2 min @home ~2.5x faster than TIO.RUN
14 Queens takes 2 min @home ~2.5x faster than TIO.RUN
<lang pascal>program TestMinimalQueen;
<syntaxhighlight lang="pascal">program TestMinimalQueen;
{$MODE DELPHI}{$OPTIMIZATION ON,ALL}
{$MODE DELPHI}{$OPTIMIZATION ON,ALL}


Line 1,050: Line 1,050:
pG_Out(@Bsol,'_.B',max-1);
pG_Out(@Bsol,'_.B',max-1);
END.
END.
</syntaxhighlight>
</lang>
{{out|@TIO.RUN}}
{{out|@TIO.RUN}}
<pre>
<pre>
Line 1,085: Line 1,085:
Shows how the latest release of Perl can now use booleans.
Shows how the latest release of Perl can now use booleans.
{{trans|Raku}}
{{trans|Raku}}
<lang perl>use v5.36;
<syntaxhighlight lang="perl">use v5.36;
use builtin 'true', 'false';
use builtin 'true', 'false';
no warnings 'experimental::for_list', 'experimental::builtin';
no warnings 'experimental::for_list', 'experimental::builtin';
Line 1,194: Line 1,194:
}
}
}
}
}</lang>
}</syntaxhighlight>
{{out}}
{{out}}
<pre>Queens
<pre>Queens
Line 1,279: Line 1,279:
You can run this online [http://phix.x10.mx/p2js/minqbn.htm here], with cheat mode on so it should all be done in 22s (8.3 on the desktop).
You can run this online [http://phix.x10.mx/p2js/minqbn.htm here], with cheat mode on so it should all be done in 22s (8.3 on the desktop).
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.
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)-->
<!--<syntaxhighlight lang="phix">(phixonline)-->
<span style="color: #000080;font-style:italic;">--
<span style="color: #000080;font-style:italic;">--
-- demo\rosetta\minQBN.exw
-- demo\rosetta\minQBN.exw
Line 1,672: Line 1,672:
<span style="color: #000000;">main</span><span style="color: #0000FF;">()</span>
<span style="color: #000000;">main</span><span style="color: #0000FF;">()</span>
<!--</lang>-->
<!--</syntaxhighlight>-->


=={{header|Python}}==
=={{header|Python}}==
{{trans|Julia}}
{{trans|Julia}}
<lang python>""" For Rosetta Code task N-queens_minimum_and_knights_and_bishops """
<syntaxhighlight lang="python">""" For Rosetta Code task N-queens_minimum_and_knights_and_bishops """


from mip import Model, BINARY, xsum, minimize
from mip import Model, BINARY, xsum, minimize
Line 1,777: Line 1,777:
print()
print()
print()
print()
</lang>{{out}}
</syntaxhighlight>{{out}}
<pre>
<pre>
Squares Queens Bishops Knights
Squares Queens Bishops Knights
Line 1,835: Line 1,835:
Due to the time it's taking only a subset of the task are attempted.
Due to the time it's taking only a subset of the task are attempted.
{{trans|Go}}
{{trans|Go}}
<lang perl6># 20220705 Raku programming solution
<syntaxhighlight lang="raku" line># 20220705 Raku programming solution


my (@board, @diag1, @diag2, @diag1Lookup, @diag2Lookup, $n, $minCount, $layout);
my (@board, @diag1, @diag2, @diag1Lookup, @diag2Lookup, $n, $minCount, $layout);
Line 1,945: Line 1,945:
}
}
}
}
}</lang>
}</syntaxhighlight>
{{out}}
{{out}}
<pre>
<pre>
Line 2,013: Line 2,013:


Although far quicker than it was originally (it now gets to 7 knights in less than a minute), it struggles after that and needs north of 21 minutes to get to 10.
Although far quicker than it was originally (it now gets to 7 knights in less than a minute), it struggles after that and needs north of 21 minutes to get to 10.
<lang ecmascript>import "./fmt" for Fmt
<syntaxhighlight lang="ecmascript">import "./fmt" for Fmt


var board
var board
Line 2,156: Line 2,156:
}
}
}
}
System.print("Took %(System.clock - start) seconds.")</lang>
System.print("Took %(System.clock - start) seconds.")</syntaxhighlight>


{{out}}
{{out}}
Line 2,253: Line 2,253:


I have borrowed one or two tricks from the Julia/Python versions in formulating the constraints.
I have borrowed one or two tricks from the Julia/Python versions in formulating the constraints.
<lang ecmascript>import "./linear" for Prob, Glp, Tran, File
<syntaxhighlight lang="ecmascript">import "./linear" for Prob, Glp, Tran, File
import "./fmt" for Fmt
import "./fmt" for Fmt


Line 2,362: Line 2,362:
}
}
File.remove(fname)
File.remove(fname)
System.print("Took %(System.clock - start) seconds.")</lang>
System.print("Took %(System.clock - start) seconds.")</syntaxhighlight>


{{out}}
{{out}}
Retrieved from "https://rosettacode.org/wiki/N-queens_minimum_and_knights_and_bishops"