Take the 2-minute tour ×
Mathematica Stack Exchange is a question and answer site for users of Mathematica. It's 100% free, no registration required.

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-Compile`GetElement[{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}

share|improve this question
1  
Just in case lauschkeconsulting.net/nqueens.html –  belisarius Nov 8 '13 at 15:59

2 Answers 2

up vote 3 down vote accepted

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} *)
share|improve this answer

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

share|improve this answer
    
Try Compile`CompilerFunctions[]~MemberQ~MapIndexed. –  expression Nov 8 '13 at 15:45

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.