One-liner solution to the N-queens puzzle


#1

Here it is:

((fix f(n:int):stream_vt(list0(int))=>if(n > 0)then((f(n-1)*intrange(0,N)).
filter()(lam(xsy)=>let val(xs,y)=xsy in $effmask_all(xs.iforall()(lam(i,x
)=>(x != y && abs(x-y) != i+1)))end)).map()(lam(xs_y)=>let val (xs, y)=xs_y
in cons0(y,xs) end)else(sing(nil0())))(N)).foreach()(lam(xs)=>((xs).rforeach
()(lam(x)=>((N).foreach()(lam(i)=>print_string(ifval(i=x," Q"," .")));
println!()));println!()))

I wrote it mainly for testing the support for overloading in ATS.

Here is the source file:


#2

I modified the one-liner solution a bit as follows.

The output of calling qsolve(1000000) can be seen at

http://myflask-tutoriats.rhcloud.com/QueenPuzzle

//
macdef sing = stream_make_sing
macdef intrange = list0_make_intrange
//
fun qsolve(nsol: Nat): void =
(((fix qsolve(n: int): stream(list0(int)) => if(n > 0)then((qsolve(n-1)*
intrange(0,N)).map(TYPE{list0(int)})(lam($tup(xs,x))=>cons0(x,xs))).filter
()(lam(xs)=>let val-cons0(x0,xs) = xs in xs.iforall()(lam(i, x)=>((x0)!=x
)&&(abs(x0-x)!=i+1)) end)else(sing(nil0())))(N)).takeLte(nsol)).iforeach()(
lam(i,xs)=>(gprintln!(“Solution#”, i+1, “:”); xs.rforeach()(lam(x) => ((N).
foreach()(lam(i)=>(gprint_string(ifval(i=x," Q", “.”))));gprintln!()));
gprintln!()))
//On Sunday, July 3, 2016 at 3:30:18 AM UTC-4, gmhwxi wrote:

Here it is:

((fix f(n:int):stream_vt(list0(int))=>if(n > 0)then((f(n-1)*intrange(0,N
)).filter()(lam(xsy)=>let val(xs,y)=xsy in $effmask_all(xs.iforall()(lam(i
,x)=>(x != y && abs(x-y) != i+1)))end)).map()(lam(xs_y)=>let val (xs, y)=xs_y
in cons0(y,xs) end)else(sing(nil0())))(N)).foreach()(lam(xs)=>((xs).
rforeach()(lam(x)=>((N).foreach()(lam(i)=>print_string(ifval(i=x," Q"," ."
)));println!()));println!()))

I wrote it mainly for testing the support for overloading in ATS.

Here is the source file:

https://github.com/githwxi/ATS-Postiats/blob/master/doc/EXAMPLE/MISC/queens_comb.dats


#3

I added this “showcase” example to the ats-lang homepage:

http://www.ats-lang.org/

You can easily find and try it at the lower right corner of the page.On Tuesday, July 26, 2016 at 11:01:37 PM UTC-4, gmhwxi wrote:

I modified the one-liner solution a bit as follows.

The output of calling qsolve(1000000) can be seen at

http://myflask-tutoriats.rhcloud.com/QueenPuzzle

//
macdef sing = stream_make_sing
macdef intrange = list0_make_intrange
//
fun qsolve(nsol: Nat): void =
(((fix qsolve(n: int): stream(list0(int)) => if(n > 0)then((qsolve(n-1)*
intrange(0,N)).map(TYPE{list0(int)})(lam($tup(xs,x))=>cons0(x,xs))).filter
()(lam(xs)=>let val-cons0(x0,xs) = xs in xs.iforall()(lam(i, x)=>((x0)!=x
)&&(abs(x0-x)!=i+1)) end)else(sing(nil0())))(N)).takeLte(nsol)).iforeach
()(lam(i,xs)=>(gprintln!(“Solution#”, i+1, “:”); xs.rforeach()(lam(x) =>
((N).foreach()(lam(i)=>(gprint_string(ifval(i=x," Q", “.”))));gprintln
!()));gprintln!()))
//

On Sunday, July 3, 2016 at 3:30:18 AM UTC-4, gmhwxi wrote:

Here it is:

((fix f(n:int):stream_vt(list0(int))=>if(n > 0)then((f(n-1)*intrange(0,N
)).filter()(lam(xsy)=>let val(xs,y)=xsy in $effmask_all(xs.iforall()(lam(
i,x)=>(x != y && abs(x-y) != i+1)))end)).map()(lam(xs_y)=>let val (xs, y
)=xs_y in cons0(y,xs) end)else(sing(nil0())))(N)).foreach()(lam(xs)=>((xs
).rforeach()(lam(x)=>((N).foreach()(lam(i)=>print_string(ifval(i=x," Q","
.")));println!()));println!()))

I wrote it mainly for testing the support for overloading in ATS.

Here is the source file:

https://github.com/githwxi/ATS-Postiats/blob/master/doc/EXAMPLE/MISC/queens_comb.dats