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

<br><br>

=={{header|F_Sharp|F#}}==

// Minimum knights to attack all squares not occupied on an NxN chess board. Nigel Galloway: May 12th., 2022

type att={n:uint64; g:uint64}

printfn "Solution found using %d knights in %A:" rn (System.DateTime.UtcNow-t); tc rb.att

for n in 1..10 do solveK n

{{out}}

<pre>

 

Timing is for an Intel Core i7-8565U machine running Ubuntu 20.04.

 

import (

elapsed := time.Now().Sub(start)

fmt.Printf("Took %s\n", elapsed)

 

{{out}}

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:

 

genboard=: {{

safelen=:2*len=: {.y

end.

end.

 

Task output:

 

+--+--+--+ B: 1

|B |Q |K | Q: 1

|. . . . . . . . . . |. . . . . . . . . . |

+--------------------+--------------------+

 

=={{header|Julia}}==

Uses the Cbc optimizer (github.com/coin-or/Cbc) for its complementarity support.

 

import Cbc

"\nKnights:\n", examples[3])

 

<pre>

Squares Queens Bishops Knights

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

{$MODE DELPHI}{$OPTIMIZATION ON,ALL}

 

pG_Out(@Bsol,'_.B',max-1);

END.

{{out|@TIO.RUN}}

<pre>

Shows how the latest release of Perl can now use booleans.

{{trans|Raku}}

use builtin 'true', 'false';

no warnings 'experimental::for_list', 'experimental::builtin';

}

}

{{out}}

<pre>Queens

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.

<span style="color: #000080;font-style:italic;">--

-- demo\rosetta\minQBN.exw

<span style="color: #000000;">main</span><span style="color: #0000FF;">()</span>

 

=={{header|Python}}==

{{trans|Julia}}

 

from mip import Model, BINARY, xsum, minimize

print()

print()

<pre>

Squares Queens Bishops Knights

Due to the time it's taking only a subset of the task are attempted.

{{trans|Go}}

 

my (@board, @diag1, @diag2, @diag1Lookup, @diag2Lookup, $n, $minCount, $layout);

}

}

{{out}}

<pre>

 

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.

 

var board

}

}

 

{{out}}

 

I have borrowed one or two tricks from the Julia/Python versions in formulating the constraints.

import "./fmt" for Fmt

 

}

File.remove(fname)

 

{{out}}