/* 

  Lights out puzzle in Picat.

  See:
  - https://en.wikipedia.org/wiki/Lights_Out_%28game%29
  - http://www.logicgamesonline.com/lightsout/tutorial.html
    """
    LightsOut is a puzzle where you are given a grid of cells, or lights, with some dark and 
    others light. You must turn them all off by clicking on the cells. Each click toggles that cell 
    and each of its immediate neighbors.
    """
  - http://mathworld.wolfram.com/LightsOutPuzzle.html


  This Picat model was created by Hakan Kjellerstrand, hakank@gmail.com
  See also my Picat page: http://www.hakank.org/picat/

*/

% import sat.
import mip.
% import cp.


main => go.


go ?=>
  nolog,
  % problem(1,R),
  % problem(2,R), % hard for MIP solver, both sat and cp are fast on this
  % problem('2b',R), % ibid. See below for details.
  % problem(3,R),
  problem(4,R),
  % problem(5,R),

  print_matrix(R,"R"),

  lights_out(R, D,X,Moves),

  println(moves=Moves),
  print_matrix(X,"X"),
  print_matrix(D,"D"),

  print_solution(R,X),
  nl,
  nl.

go => true.

%
% Random instance.2
%
% The mip solver tends to be fast on large instances, 
% e.g. > N=30 and NumMoves=N*2.
% Strange that it's so slow in instance #2 (9x9). Perhaps
% #2 is constructed so it should be hard...
%
% It's also a matter of how many moves that's requred.
% 
%
go2 =>
  garbage_collect(200_000_000),
  nolog,
  N = 50,
  NumMoves = N*3,
  [R,Moves1] = random_instance(N,NumMoves),
  print_matrix(R,"R"),
  MovesEst = Moves1.sort_remove_dups(),
  println(estimated_moves=MovesEst),
  println(len=MovesEst.len),

  lights_out(R, D,X,Moves),

  println(moves=Moves),
  print_matrix(X,"X"),
  print_matrix(D,"D"),

  print_solution(R,X),

  println(estim_moves=MovesEst),
  println(num_estim_moves=MovesEst.len),

  nl.


%
% Find all optimal solutions for a random generated instance.
% Note: the MIP solver don't handle this well.
%
go3 ?=>
  if member(mip, loaded_modules()) then
    println("Don't run this with the mip solver!"),
    nl,
    halt
  end,
  nolog,
  N = 16,
  NumMoves = 50,
  [R,_Moves1] = random_instance(N,NumMoves),

  print_matrix(R,"R"),

  Map = get_global_map(),
  Map.put(count,0),
  println("Get the optimal number of moves."),
  lights_out(R, _D,_X,Moves),

  println(moves=Moves),
  println("\nGet all optimal solutions:"),
  lights_out(R, D2,X2,Moves),
  Map.put(count,Map.get(count)+1),
  print_matrix(X2,"X"),
  print_matrix(D2,"D"),
  % print_solution(R,X),
  nl,
  fail,

  nl.

go3 => 
  println(count=get_global_map().get(count)),
  nl.

%
% Number of solvable grids for N = 1..5.
%
% N       #grids
% --------------------------
% 1            2
% 2           16
% 3          512  2^9
% 4       65 536  2^16
% 5   33 554 432  2^25   (counted in 3:06minutes)
%
% Distribution of number of grids per Moves length
%
% N = 1
%   0 = 1
%   1 = 1
%
% N = 2
% -----
%   0 = 1
%   1 = 4
%   2 = 6
%   3 = 4
%   4 = 1
% 
% N = 3
% -----
%   0 = 1
%   1 = 9
%   2 = 36
%   3 = 84
%   4 = 126
%   5 = 126
%   6 = 84
%   7 = 36
%   8 = 9
%   9 = 1
% 
% N = 4
% -----
%   0 = 1
%   1 = 16
%   2 = 120
%   3 = 560
%   4 = 1820
%   5 = 4368
%   6 = 8008
%   7 = 11440
%   8 = 12870
%   9 = 11440
%  10 = 8008
%  11 = 4368
%  12 = 1820
%  13 = 560
%  14 = 120
%  15 = 16
%  16 = 1
% 
% N = 5
% -----
%   0 = 1
%   1 = 25
%   2 = 300
%   3 = 2300
%   4 = 12650
%   5 = 53130
%   6 = 177100
%   7 = 480700
%   8 = 1081575
%   9 = 2042975
%  10 = 3268760
%  11 = 4457400
%  12 = 5200300
%  13 = 5200300
%  14 = 4457400
%  15 = 3268760
%  16 = 2042975
%  17 = 1081575
%  18 = 480700
%  19 = 177100
%  20 = 53130
%  21 = 12650
%  22 = 2300
%  23 = 300
%  24 = 25
%  25 = 1
%
% 1,25,300,2300,12650,53130,177100,480700,1081575,2042975,3268760,4457400,5200300
% 
% Ah, this is binomial(N*N,0..N*N)
% For N = 5: http://oeis.org/A010941
%
go4 ?=>
  if member(mip, loaded_modules()) then
    println("Don't run this with the mip solver!"),
    nl,
    halt
  end,

  nolog,
  N = 4,

  Map = get_global_map(),
  Map.put(count,0),

  R = new_array(N,N),
  R :: 0..1,

  member(Moves,0..N*N),
  println(moves=Moves),

  lights_out(R, D,X,Moves),
  print_matrix(R,"R"),
  println(moves=Moves),
  print_matrix(X,"X"),
  print_matrix(D,"D"),
  print_solution(R,X),

  Map.put(count,Map.get(count)+1),
  Map.put(Moves,Map.get(Moves,0)+1),
  % nl,
  fail,

  nl.

go4 => 
  Map = get_global_map(),
  % println(count=Map.get(count)),
  foreach(I in sort(keys(Map)))
    println(I=Map.get(I))
  end,
  nl.



% print a matrix
print_matrix(M,Name) =>
  printf("%s: \n", Name),
  foreach(Row in M)
     println(Row.to_list())
  end,
  nl.

%
% generate a random instance
%
random_instance(N,NumMoves) = [T,Moves] =>
  T = new_array(N,N),
  bind_vars(T,0),
  _ = random2(),
  
  Moves = [],
  foreach(_M in 1..NumMoves)
     T2 = copy_term(T),  
     I = 1+random() mod N,
     J = 1+random() mod N,
     foreach([A,B] in [[A,B] : A in [-1,0,1], B in [-1,0,1],
                           member(I+A, 1..N), member(J+B,1..N),
                          (abs(A) + abs(B) = 1 ;  A = 0, B = 0)])
         T2[I+A,J+B] := cond(T[I+A,J+B]==1,0,1)
     end,
     Moves := Moves ++ [[I,J]],
     T := T2
  end.


%
% The main solver.
%
lights_out(R, D,X,Moves) =>
  N = R.len,

  % solution matrix
  X = new_array(N,N),
  X :: 0..1,

  % aux. matrix
  D = new_array(N,N),
  D :: 0..N,

  Moves :: 0..N*N,
  Moves #= sum(X.vars()),

  foreach(I in 1..N, J in 1..N)
     % count all the neighboring cells, including this cell
     2*D[I,J] + R[I,J]  #= sum([X[I+A,J+B] : A in [-1,0,1], B in [-1,0,1],
                           member(I+A, 1..N), member(J+B,1..N),
                           (abs(A) + abs(B) = 1 ;  A= 0, B = 0)
                           ]) 
  end,

  % Alternative formulation from 
  % Martin Chlond: "Puzzle—Shedding Light on Higher Dimensions"
  % INFORMS Transactions on Education, Volume 15 (2015), Issue 2
  % http://pubsonline.informs.org/doi/abs/10.1287/ited.2014.0135
  % foreach(I in 1..N, J in 1..N)
  %    % note: Chlond's original was: "(2*D[I,J]+(1-R[I,J]))" (i.e. (1-R[I,J])
  %    % but this will solve for all lights _on_, not off (out).
  %    sum([X[I,K] : K in J-1..J+1, K >= 1, K <= N, K != J]) +
  %    sum([X[K,J] : K in I-1..I+1, K >= 1, K <= N]) #= 2*D[I,J]+(R[I,J])
  % end,
  

  Vars = X.vars() ++ D.vars(),
  % Vars = D.vars() ++ X.vars(),
  println(solve),
  % solve($[report(printf("Moves: %d\n", Moves))],Vars).
  if var(Moves) then
    % find optimal value
    solve($[split,min(Moves),report(printf("Moves: %d\n", Moves))],Vars)
  else 
    % find a solution with a given number of Moves
    solve($[ff,split,report(printf("Moves: %d\n", Moves))],Vars)
  end.



%
% Print the solution
%
print_solution(R,M) =>
  println("Grid\n"),
  N = R.len,
  T = copy_term(R),
  print_matrix(T,"T (orig)"),
  Moves = [],
  foreach(I in 1..N, J in 1..N)
     if M[I,J] == 1 then
       printf("Cell %w:\n",[I,J]),
       T2 = copy_term(T),
       foreach([A,B] in [[A,B] : A in [-1,0,1], B in [-1,0,1],
                              member(I+A, 1..N), member(J+B,1..N),
                              (abs(A) + abs(B) = 1 ;  A = 0, B = 0)])
          
          T2[I+A,J+B] := cond(T[I+A,J+B]==1,0,1)
       end,
       T := T2,
       print_matrix(T,"T"),
       Moves := Moves ++ [[I,J]]
     end
  end,
  println(numMoves=Moves.len),
  println(found_moves=Moves),
  nl.


%
% (random) problem from http://www.logicgamesonline.com/lightsout/
%
% numMoves = 8
% found_moves = [[1,3],[1,5],[2,2],[2,3],[3,2],[3,4],[4,4],[5,4]]
% 
problem(1,R) =>
  R = 
  {
% {0,0,0,0,0},
{0,0,0,0,1},
{1,1,1,0,1},
{1,0,1,0,1},
{0,1,1,1,1},
{0,0,1,0,1}
   }.

%
% (random) problem from http://www.logicgamesonline.com/lightsout/
%
% 27 moves
%
% SAT: 0.476s
% MIP: 17.4s
% CP : 0.076s
%
% numMoves = 27
% found_moves = [[1,2],[1,3],[1,7],[1,9],[2,7],[2,9],[3,1],[3,3],[3,5],[3,6],[3,7],[4,4],[4,7],[5,3],[5,4],[5,7],[5,8],[6,8],[7,4],[7,9],[8,1],[8,3],[8,7],[8,9],[9,1],[9,3],[9,7]]
% 
problem(2,R) =>
  R = 
  {
% {0,0,0,0,0,0,0,0,0},

{1,0,0,1,0,1,0,0,0},
{1,1,0,0,1,0,1,0,0},
{1,0,1,1,0,1,0,1,1},
{1,0,1,0,0,0,1,0,0},
{0,1,0,1,1,1,1,1,1},
{0,0,1,0,0,0,0,0,0},
{1,0,0,1,1,0,1,0,0},
{0,0,0,0,0,1,0,0,0},
{0,0,0,1,0,1,0,1,1}
}.

%
% another sample from http://www.logicgamesonline.com/lightsout/
% 25 moves
% SAT: 0.366s
% MIP: 5.4s!
% CP : 0.048s
% numMoves = 25
% found_moves = [[1,5],[1,7],[1,9],[2,4],[2,7],[2,9],[3,3],[3,7],[3,9],[4,3],[4,5],[5,1],[6,1],[6,5],[7,1],[7,2],[7,4],[7,6],[7,7],[8,2],[8,3],[8,6],[9,2],[9,4],[9,6]]
%
problem('2b',R) =>
  R = 
  {
% {0,0,0,0,0,0,0,0,0},
{0,0,0,0,1,0,0,0,0},
{0,0,0,1,0,1,1,0,1},
{0,1,0,0,1,1,0,0,0},
{1,1,0,0,1,1,1,0,1},
{0,1,1,0,0,0,0,0,0},
{1,0,0,0,1,0,1,0,0},
{1,1,1,1,1,1,0,1,0},
{0,0,0,1,1,1,0,0,0},
{1,0,1,1,0,0,1,0,0}
}.


%
% random generated: 20x20
% 34 moves
%
% SAT: 
% MIP: 0.096s
% CP : 0.65s
%
% numMoves = 34
% found_moves = [[2,1],[2,8],[2,16],[2,18],[3,10],[3,12],[3,19],[4,15],[5,18],[6,2],[6,7],[6,9],[6,19],[10,4],[10,17],[12,4],[12,6],[12,9],[12,12],[12,20],[13,12],[13,20],[15,14],[15,20],[16,14],[16,16],[16,17],[17,8],[17,9],[18,17],[18,19],[20,13],[20,18],[20,20]]
%
problem(3,R) => 
 R =
{
{1,0,0,0,0,0,0,1,0,0,0,0,0,0,0,1,0,1,0,0},
{1,1,0,0,0,0,1,1,1,1,0,1,0,0,1,1,0,1,0,0},
{1,0,0,0,0,0,0,1,1,1,0,1,1,0,1,1,0,0,1,1},
{0,0,0,0,0,0,0,0,0,1,0,1,0,1,1,1,0,1,1,0},
{0,1,0,0,0,0,1,0,1,0,0,0,0,0,1,0,1,1,0,0},
{1,1,1,0,0,1,1,0,1,1,0,0,0,0,0,0,0,0,1,1},
{0,1,0,0,0,0,1,0,1,0,0,0,0,0,0,0,0,0,1,0},
{0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},
{0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0},
{0,0,1,1,1,0,0,0,0,0,0,0,0,0,0,1,1,1,0,0},
{0,0,0,0,0,1,0,0,1,0,0,1,0,0,0,0,1,0,0,1},
{0,0,1,1,0,1,1,1,1,1,1,0,1,0,0,0,0,0,1,0},
{0,0,0,1,0,1,0,0,1,0,1,0,1,0,0,0,0,0,1,0},
{0,0,0,0,0,0,0,0,0,0,0,1,0,1,0,0,0,0,0,0},
{0,0,0,0,0,0,0,0,0,0,0,0,1,0,1,1,1,0,1,1},
{0,0,0,0,0,0,0,1,1,0,0,0,1,0,0,0,0,1,0,1},
{0,0,0,0,0,0,1,0,0,1,0,0,0,1,0,1,0,0,1,0},
{0,0,0,0,0,0,0,1,1,0,0,0,0,0,0,1,1,0,1,1},
{0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,1,1,1,1},
{0,0,0,0,0,0,0,0,0,0,0,1,1,1,0,0,1,1,0,1}
}.


%
% random generated 50x50
% 92 moves
%
% SAT: 
% MIP: 0.49s
% CP : finds optimal value in ~1s but then continue to search "forever"
%
% numMoves = 92
% found_moves = [[2,31],[3,7],[4,2],[4,20],[5,50],[6,26],[7,24],[7,34],[9,16],[9,46],[10,28],[10,37],[12,19],[12,43],[13,21],[13,24],[13,28],[14,8],[15,18],[15,29],[16,21],[16,40],[18,2],[18,7],[18,30],[18,36],[18,43],[19,29],[19,46],[20,18],[20,25],[21,19],[22,6],[22,20],[23,9],[23,37],[25,15],[25,22],[25,46],[26,8],[27,19],[27,29],[27,37],[29,22],[29,30],[30,3],[30,24],[30,38],[30,39],[32,18],[32,26],[33,2],[33,11],[33,30],[33,31],[33,46],[34,37],[35,28],[35,29],[35,38],[36,44],[37,6],[37,16],[37,42],[37,43],[38,7],[38,9],[38,29],[39,35],[40,13],[41,10],[41,27],[41,30],[41,50],[42,1],[42,31],[44,7],[44,12],[44,36],[44,42],[45,20],[45,40],[46,21],[47,2],[47,24],[47,30],[47,32],[48,3],[48,4],[48,22],[49,25],[50,22]]
%
problem(4,R) => 
R = 
{
{0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},
{0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},
{0,1,0,0,0,1,1,1,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},
{1,1,1,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,1,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1},
{0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1},
{0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,1,1,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1},
{0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,1,1,0,0,0,0,0,0,1,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},
{0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0},
{0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,1,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,1,1,1,0,0,0},
{0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,1,1,1,0,0,0,0,0,0,1,1,1,0,0,0,0,0,0,0,1,0,0,0,0},
{0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,1,0,0,0,0,0,1,0,0,0,0,0,0,0},
{0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,1,1,0,0,1,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,1,0,0,0,0,0,0},
{0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,1,1,1,1,1,1,1,0,1,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0},
{0,0,0,0,0,0,1,1,1,0,0,0,0,0,0,0,0,1,0,0,1,0,0,1,0,0,0,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},
{0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,1,1,1,0,1,0,0,0,0,0,0,1,1,1,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0},
{0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,1,1,1,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,1,1,1,0,0,0,0,0,0,0,0,0},
{0,1,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,1,0,0,0,0,0,1,0,0,0,1,0,0,1,0,0,0,0,0,0,0},
{1,1,1,0,0,1,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,0,0,0,1,1,1,0,0,0,0,1,1,1,0,1,0,0,0,0},
{0,1,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,1,0,0,1,1,0,0,0,0,0,0,1,0,0,0,0,0,0,1,0,1,1,1,0,0,0},
{0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,0,0,0,0,0,1,1,1,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0},
{0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},
{0,0,0,0,1,1,1,0,1,0,0,0,0,0,0,0,0,0,0,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0},
{0,0,0,0,0,1,0,1,1,1,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,1,0,0,0,0,0,0,0,0,0,0,0,0},
{0,0,0,0,0,0,0,0,1,0,0,0,0,0,1,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,1,0,0,0,0},
{0,0,0,0,0,0,0,1,0,0,0,0,0,1,1,1,0,0,0,0,1,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,1,0,0,0},
{0,0,0,0,0,0,1,1,1,0,0,0,0,0,1,0,0,0,1,0,0,1,0,0,0,0,0,0,1,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,1,0,0,0,0},
{0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,1,1,1,0,0,0,0,0,0,0,1,1,1,0,0,0,0,0,1,1,1,0,0,0,0,0,0,0,0,0,0,0,0},
{0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,1,0,0,0,0,0,0,1,1,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0},
{0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,1,1,0,0,0,0,1,1,1,0,0,0,0,0,0,1,1,0,0,0,0,0,0,0,0,0,0,0},
{0,1,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,1,1,0,0,0,0,1,0,0,0,0,0,0,1,0,0,1,0,0,0,0,0,0,0,0,0,0},
{0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,1,0,1,0,0,0,0,0,0,0,0,0,0,0,1,1,0,0,0,0,0,0,0,0,0,0,0},
{0,1,0,0,0,0,0,0,0,0,1,0,0,0,0,0,1,1,1,0,0,0,0,0,1,1,1,0,0,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0},
{1,1,1,0,0,0,0,0,0,1,1,1,0,0,0,0,0,1,0,0,0,0,0,0,0,1,0,0,1,0,0,1,0,0,0,0,1,0,0,0,0,0,0,0,1,1,1,0,0,0},
{0,1,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,1,1,0,0,0,0,1,1,0,0,0,0,0,0,0,0,1,0,0,0,0},
{0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,1,0,0,0,0,0,0,0,1,1,0,0,0,0,1,0,0,0,0,0,0},
{0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,1,1,0,0,0,0,0,0,0,0,1,0,0,0,1,0,1,1,0,0,0,0,0},
{0,0,0,0,1,1,0,0,1,0,0,0,0,0,1,1,1,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0},
{0,0,0,0,0,0,1,0,1,1,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,1,1,1,0,0,0,0,1,0,0,0,0,0,0,1,1,0,0,0,0,0,0,0},
{0,0,0,0,0,0,1,0,1,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,1,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0},
{0,0,0,0,0,0,0,0,0,1,0,1,1,1,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,1,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1},
{1,0,0,0,0,0,0,0,1,1,1,0,1,0,0,0,0,0,0,0,0,0,0,0,0,1,1,1,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1},
{1,1,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1},
{1,0,0,0,0,0,1,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,1,0,0,0,0,0,1,0,0,0,0,0,0,0,0},
{0,0,0,0,0,1,1,1,0,0,1,1,1,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,1,0,0,1,1,1,1,0,0,0,0,0,0,0},
{0,0,0,0,0,0,1,0,0,0,0,1,0,0,0,0,0,0,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,1,1,1,1,0,0,0,0,0,0,0,0},
{0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,0,1,0,0,0,0,0,1,0,1,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0},
{1,1,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,1,1,1,0,0,0,1,1,0,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},
{0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,1,1,1,0,0,0,0,1,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},
{0,0,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},
{0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,1,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0}
}.

% From http://www.sfu.ca/~jtmulhol/math302/puzzles-lo.html
% Set 1, Puzzle 1
%
% SAT: 0.056s
% MIP: 0.477s
% CP: 0.049s
%
% numMoves = 6
% found_moves = [[4,1],[4,3],[4,5],[5,1],[5,3],[5,5]]
%
problem(5,R) => 
R = {{0,0,0,0,0},
     {0,0,0,0,0},
     {1,0,1,0,1},
     {0,0,0,0,0},
     {0,0,0,0,0}}.