N-queens minimum and knights and bishops: Difference between revisions
N-queens minimum and knights and bishops (view source)
Revision as of 10:08, 12 May 2022
, 2 years ago→{{header|F_Sharp|F#}}
(→{{header|Phix}}: updated, much faster) |
|||
Line 9:
=={{header|F_Sharp|F#}}==
<lang fsharp>
//
type att={n:uint64; g:uint64}
static member att n g=let g=g|>Seq.fold(fun n g->n ||| (1UL<<<g)) 0UL in {n=n|>Seq.fold(fun n g->n ||| (1UL<<<g)) 0UL; g=g}
static member (+) (n,g)=let x=n.g ||| g.g in {n=n.n ||| g.n; g=x}
let fN g=let fG n g
let n,g=Array.init(g*g)(fun n->att.att [n/2] (fG n g)), Array.init(g*g)(fun n->att.att (fG n g) [n/2]) in (fun g->n.[g]),(fun n->g.[n])
type cand={att:att; n:int; g:int}
type Solver={n:cand seq; i:int[]; g:(int -> att) * (int -> att); e:att; l:int[]}
member
let n=this.n|>Seq.choose(fun n->test n n.att (this.e.g^^^n.att.g) 0 0) in if Seq.isEmpty n then None else Some(n|>Seq.minBy snd)
member this.xP() ={this with n=this.n|>Seq.collect(fun n->[for g in n.n..n.g do let att=n.att+((fst this.g)(this.l.[g])) in yield {n with att=att; n=g}])}
let rec slvK (n:Solver) i g l = match n.test() with Some(r,ta)->match min l (g+ta) with t when t>2*(g+1) || l<t->slvK (n.xP()) (if t<l then Some(r,ta) else i) (g+1) (min t l) |t->Some(min t l,r)
|_->slvK (n.xP()) i (g+1) l
let tC bw s (att:att)=let n=Array2D.init s s (fun n g->if (n+g)%2=bw then (if att.n &&& pown 2UL ((n*s+g)/2) > 0UL then "X" else ".") else (if att.g &&& pown 2UL ((n*s+g)/2) > 0UL then "~" else "o"))
let solveK g=printfn "\nSolving for %dx%d board" g g
let bs,ws=[|for n in g..g+g..(g*g-1)/2 do for z in 0..g+1..(g*g-1)/2-n->((n+z)/g,(n+z)%g)|],[|for n in 0..g+g..(g*g-1)/2 do for z in 0..g+1..(g*g-1)/2-n->((n+z)/g,(n+z)%g)|]
let i,l=let n,i=[|for n in 0..g-1 do for g in 0..g-1->(n,g)|]|>Array.partition(fun(n,g)->(n+g)%2=1) in n|>Array.map(fun(n,i)->n*g+i), i|>Array.map(fun(n,i)->n*g+i)
let t,f=System.DateTime.UtcNow,fN g
let bK={l=Array.concat[bs|>Array.map(fun(n,i)->n*g+i);i]|>Array.distinct; i=l; e=att.att [0..i.Length-1] [0..l.Length-1]; n=bs|>Array.mapi(fun l (n,e)->let att=((fst f)(n*g+e)) in {att=att; n=l+1; g=i.Length-1}); g=fN g}
let wK={l=Array.concat[ws|>Array.map(fun(n,i)->n*g+i);l]|>Array.distinct; i=i; e=att.att [0..l.Length-1] [0..i.Length-1]; n=ws|>Array.mapi(fun i (n,e)->let att=((fst f)(n*g+e)) in {att=att; n=i+1; g=l.Length-1}); g=fN g}
let (rn,rb),tc=match g with 1|2->(slvK wK None 1 (g*g/2+g%2)).Value, tC 0 g
|x when x%2=0->(slvK bK None 1 (g*g/2)).Value, tC 1 g
|_->let x,y=(slvK bK None 1 (g*g/2)).Value, (slvK wK None 1 (g*g/2+1)).Value in if (fst x)<(fst y) then x,tC 1 g else y,tC 0 g
printfn "Solution found using %d knights in %A:" rn (System.DateTime.UtcNow-t); tc rb.att
for n in 1..10 do solveK n
</lang>
{{out}}
<pre>
Solving for 1x1 board
Solution found using 1 knights in 00:00:00.0331768:
X
Solving for 2x2 board
Solution found using 2 knights in 00:00:00:
Xo
oX
Solving for 3x3 board
Solution found using 4 knights in 00:00:00.0156191:
Xo.
oX~
.~.
Solving for 4x4 board
Solution found using 4 knights in 00:00:00:
~.~.
XoXo
~.~.
.~.~
Solving for 5x5 board
Solution found using 5 knights in 00:00:00:
.o.~.
~X~.~
.o.~.
~X~.~
.o.~.
Solving for 6x6 board
Solution found using 8 knights in 00:00:00:
~.~.~.
.~.~.~
oX~.oX
Xo.~Xo
~.~.~.
.~.~.~
Solving for 7x7 board
Solution found using 13 knights in 00:00:00.1426817:
X~.~.o.
oX~.~.~
X~.~.o.
~.~.~Xo
.~.~.~.
o.oX~.~
.~.o.~X
Solving for 8x8 board
Solution found using 14 knights in 00:00:00.2655969:
o.~X~.~.
X~.~.~.~
o.~.~Xo.
.~.~.o.~
~.o.~.~.
.oX~.~.o
~.~.~.~X
.~.~X~.o
Solving for 9x9 board
Solution found using 14 knights in 00:00:10.2331055:
.~.~.~.~.
~.o.~.o.~
.~Xo.oX~.
~.~.~.~.~
X~.~.~.~X
~.~.~.~.~
.~Xo.oX~.
~.o.~.o.~
.~.~.~.~.
Solving for 10x10 board
Solution found using 16 knights in 00:04:44.0573668:
~.~.~.~.~.
.~.~.~Xo.~
~Xo.~.oX~.
.oX~.~.~.~
~.~.~.~.~.
.~.~.~.~.~
~.~.~.~Xo.
.~Xo.~.oX~
~.oX~.~.~.
.~.~.~.~.~
</pre>
| |||