How do we solve N-Rooks variation using primes?

Another possibility, at least for relatively small matrices, is to take the determinant (strictly speaking it is the permanent that is required, I suppose).

For example, for an $11 \times 11$ matrix (o=5), I find there are 7 solutions.

primePositions5 = 
  Position[With[{o = 5}, 
    Table[If[PrimeQ[n], 1, 0], {m, 0, Prime[o]^2 - Prime[o], 
      Prime[o]}, {n, m + 1, m + Prime[o]}]], 1];

mylist = List @@ (Det@
     SparseArray[## -> Subscript[a, ##] & /@ 
       primePositions5] /. {-x_ -> x})

gives the following:

enter image description here

Matrix plots of all seven solutions:

MatrixPlot[
   Normal@SparseArray[(List @@ #) /. 
      Subscript[a, {x_, y_}] -> {x, y} -> 1], Mesh -> All, 
   ImageSize -> 200] & /@ mylist

I'll give then as a grid:

enter image description here

I reckon it needs to be emphasized that the Mathematica's Det command is slow.

With o=7 which gives a $17 \times 17$ matrix, I obtain 2144 solutions. For 0 =8 ($19 \times 19$), the figure is 2641. I could not go beyond this with the computer I am using (with Mathematica 7, as it so happens).

For o=4 ($7 \times 7$), I get two solutions:

7x 7 matrix

Update for Mathematica 11

In Mma 11, we can use the Permanent function

myListAlt = List @@ (SparseArray[## -> Subscript[a, ##] & /@  primePositions5] // 
 Permanent // Expand)

The behaviour of Det seems to have changed somewhat since this question was posted.
I now need to Expand the result of the Det function:

mylist = List @@ (Expand@
 Det@SparseArray[## -> Subscript[a, ##] & /@ 
    primePositions5] /. {-x_ -> x})

and

mylist == myListAlt

True


A very simple one, not very elegant :

f[o_] := Module[{mat, sol, vars, const, output}, 
  mat = Table[If[PrimeQ[n], Unique["p"], 0], {m, 0, Prime[o]^2 - Prime[o], 
    Prime[o]}, {n, m + 1, m + Prime[o]}];
  vars = Cases[Flatten[mat], _?(Not[NumericQ[#]] &)] ;
  const = Join[{Last[First[mat]] == 1}, Total[#] == 1 & /@ mat, 
    Total[#] == 1 & /@ Transpose[mat], 
    Thread[GreaterEqual[vars, 0]]];
  sol = FindInstance[const, vars, Integers];
  output = (mat /. First[sol])
]

f[8]/.{0 -> "."} //MatrixForm

prime


This is neither elegant nor smart nor memory efficient. It is a brute force method to get all solutions of a given size

isGood[m_] := Sort@m === reye@Length@m;
i : reye[l_] := i = Reverse@IdentityMatrix@l;

getAllSolutions[n_?PrimeQ] := With[{id = IdentityMatrix@n},
     Pick[id, #, 1] & /@ Boole@PrimeQ@Partition[Range[n^2], n] // 
     Tuples]~Select~isGood;

So

Row[MatrixForm /@ #] & /@ 
  Composition[getAllSolutions, Prime]~Array~4 // 
 Column@Riffle[#, "New prime"] &

Gives

Mathematica graphics

EDIT

I imagined that a solution along the lines of @bgatessucks 's great answer, but with booleans, would be more efficient and appropriate. However, while this is true for sizes below 13 (an order of magnitude faster in my tests), for some reason it suddenly becomes terribly slow afterwards.

v2[n_?PrimeQ, nsols_Integer: 1] := Module[{mat, vars},
  {mat, {vars}} = 
   Reap[PrimeQ@Partition[Range[n^2], n] /. True :> Sow@Unique["p"]];
  SatisfiabilityInstances[
    And @@ BooleanCountingFunction[{1}, n] @@@ 
      Join[mat, Transpose@mat], vars, nsols] /. 
   res_ :> (mat /. (Thread[vars -> #] & /@ res) /. {False -> ".", 
       True -> "P"})
  ]

Now

MatrixForm /@ v2[Prime@6, 3]

Gives

Mathematica graphics