# My code for solving n queens problem Compile Failed

I want to make my code for solving n-queens problem faster, but it seems that MapIndexed can't be compiled. Mathematica return

CompiledFunction::cfse: Compiled expression If[Abs[1-CompileGetElement[{2},1]]==1,Throw[False]] should be a machine-size real number. >>

Clear["*"];
safe[col_, queens_] :=
FreeQ[queens, col] &&
Catch[MapIndexed[
If[Abs[col - #] == Length@queens - First@#2 + 1, Throw@False] &,
queens];
True];

safeCompiled =
Compile[{{col, _Integer}, {queens, _Integer, 1}},
FreeQ[queens, col] &&
Catch[MapIndexed[
If[Abs[col - #] == Length@queens - First@#2 + 1, Throw@False] &,
queens];
True]
];

8 /. size_ :>
Nest[Table[sol~Append~i,
{i, size}, {sol, Select[#, safeCompiled[i, #] &]}]~Flatten~1 &,
{{}}, size] // Length // AbsoluteTiming


Updated

A bit faster version:

safe = Compile[{{col, _Integer}, {queens, _Integer, 1}},
If[MemberQ[queens, col], Return@0];
Catch[Do[If[Abs[col - queens[[i]] ] == Length@queens - i + 1, Throw@0],
{i, Length@queens}]; 1],
RuntimeAttributes -> Listable];

size = 11;
iter = Table[Append[sol, i], {i, size}, {sol, Pick[#, safe[i, #], 1]}]~ Flatten~1 &;
Nest[iter, List /@ Range@size, size - 1] // Length // AbsoluteTiming


{1.083062, 2680}

The problem is with the return value of

If[Abs[col - #] == Length@queens - First@#2 + 1, Throw@False] &


which needs to be of a type handled by Compile. The If statement returns Null when the test is not True, and Compile does not support Null.

One fix is to make the value of the function be 0 (or whatever, since this value is not used).

safeCompiled =
Compile[{{col, _Integer}, {queens, _Integer, 1}},
FreeQ[queens, col] &&
Catch[MapIndexed[(If[Abs[col - #] == Length@queens - First@#2 + 1,
Throw@False]; 0) &, queens];
True]]


A slightly more efficient approach is to use Do, since the list created by MapThread is immaterial.

safeCompiled =
Compile[{{col, _Integer}, {queens, _Integer, 1}},
FreeQ[queens, col] &&
Catch[Do[
If[Abs[col - queens[[i]]] == Length@queens - i + 1, Throw@False],
{i, Length @ queens}];
True]]

8 /. size_ :>
Nest[Table[sol ~Append~ i,
{i, size}, {sol, Select[#, safeCompiled[i, #] &]}] ~Flatten~ 1 &,
{{}}, size] // Length // AbsoluteTiming
(* {0.023975, 92} *)


MapIndexed is not a compilable function until Mathematica 9. See more information in this question.

• Try CompileCompilerFunctions[]~MemberQ~MapIndexed`. Nov 8, 2013 at 15:45