/*
  This model show the evolution of the domains.
  Notes:

  - The 4x4 instance is solved after the constraints of the rows and 
    3 of the columns have been run.
  

  Event statistics for the 9x9 problem (instance 2) and different labelings:
    all_distinct, [ff,split]: 
        Time (including output of all events): 0.048s
        Backtracks 0
        num events: 531
        bound=176
        dom=193
        generated=81
        ins=81

    all_distinct, []: 
        Time (including output of all events): 0.056s
        Backtracks 0
        num events: 531
        bound=176
        dom=193
        generated=81
        ins=81

    all_different, [ff,split]: 
        Time (including output of all events): 1.992s
        Backtracks 0
        num events: 2901
        bound=1043
        dom=892
        generated=81
        ins=884

    all_different, []: 
        Time (including output of all events): 5.104s
        Backtracks 172
        num events: 4352
        bound=1537
        dom=1138
        generated=81
        ins=1596


    all_different, [max]: 
        Time (including output of all events): 202.044s
        Backtracks 1828
        num events: 22827
        bound=7443
        dom=4536
        generated=81
        ins=10767



*/
import cp.
import ordset.
import trace_domains_ar.

main => go.

go ?=> 
  board(1, N, Board), % 4x4
  % board(2, N, Board), % 9x9
  % board(3, N, Board), % 9x9
  time2(sudoku(N, Board, X)),
  println("\nSolution:"),
  foreach(Row in X) println(Row.to_list()) end,
  nl,
  trace_domains_stat.

go => true.

sudoku(N, Board, X) =>
   N1 = ceiling(sqrt(N)),

   X = new_array(N,N),
   X :: 1..N,

   % trace_domain_ar_trace_start_stat(),
   trace_domain_ar(X,"X"),

   foreach(I in 1..N, J in 1..N)
     println("\nHint"=[I,J]),
     if Board[I,J] > 0 then
       X[I,J] #= Board[I,J]
     end
   end, 

   % rows
   println("\nRows:"),
   foreach(I in 1..N) 
     println("\nRow"=I),
     % all_different([X[I,J] : J in 1..N])
     all_distinct([X[I,J] : J in 1..N])
   end,

   % columns
   println("\nColumns:"),
   foreach(J in 1..N) 
     println("\nColumn"=J),
     % all_different([X[I,J] : I in 1..N])
     all_distinct([X[I,J] : I in 1..N])
   end,


   % cells
   println("\nCells:"),
   foreach(I in 1..N1..N, J in 1..N1..N)
     println("Cells"=[I,J]),
     % all_different([X[I+K,J+L] : K in 0..N1-1, L in 0..N1-1])
     all_distinct([X[I+K,J+L] : K in 0..N1-1, L in 0..N1-1])
   end,

   println("\nBefore solve"),
   solve([ff,split],X).



board(1, N, Board) =>
   N = 4,
   Board = [[4, 0,  0, 0],
            [3, 1,  0, 0],
            [0, 0,  4, 1],
            [0, 0,  0, 2]].

board(2, N, Board) => 
   N = 9,
   Board = 
    [[0, 0, 2, 0, 0, 5, 0, 7, 9],
    [1, 0, 5, 0, 0, 3, 0, 0, 0],
    [0, 0, 0, 0, 0, 0, 6, 0, 0],
    [0, 1, 0, 4, 0, 0, 9, 0, 0],
    [0, 9, 0, 0, 0, 0, 0, 8, 0],
    [0, 0, 4, 0, 0, 9, 0, 1, 0],
    [0, 0, 9, 0, 0, 0, 0, 0, 0],
    [0, 0, 0, 1, 0, 0, 3, 0, 6],
    [6, 8, 0, 3, 0, 0, 4, 0, 0]].


% 
% "World's hardest sudoku: can you crack it?"
% http://www.telegraph.co.uk/science/science-news/9359579/Worlds-hardest-sudoku-can-you-crack-it.html
%
board(3, N, Board) =>
  N = 9,
  Board = 
[
[8,0,0, 0,0,0, 0,0,0],
[0,0,3, 6,0,0, 0,0,0],
[0,7,0, 0,9,0, 2,0,0],

[0,5,0, 0,0,7, 0,0,0],
[0,0,0, 0,4,5, 7,0,0],
[0,0,0, 1,0,0, 0,3,0],

[0,0,1, 0,0,0, 0,6,8],
[0,0,8, 5,0,0, 0,1,0],
[0,9,0, 0,0,0, 4,0,0]
].