/* 

  Sudoku using global_cardinality in Picat.

  Using global_cardinality/2 instead of all_different/1.

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

*/


import util.
import cp.


main => go.


go =>
  problem(13, Board),
  print_board(Board),
  time2(sudoku(3,Board)),
  print_board(Board),  
  nl.

% Test all problems 
go2 =>
   foreach(P in 1..13)
      writeln(problem=P),
      problem(P, Board),
      time2(sudoku(3,Board)),
      print_board(Board),
      nl
   end.


sudoku(N, Board) =>
   N2 = N*N,
   Occ = $[I-1 : I in 1..N2],
   Vars = Board.vars(),
   Vars :: 1..N2,
   foreach(Row in Board) global_cardinality(Row,Occ) end,
   foreach(Column in transpose(Board)) global_cardinality(Column,Occ) end,
   foreach(I in 1..N..N2, J in 1..N..N2)
      global_cardinality([Board[I+K,J+L] : K in 0..N-1, L in 0..N-1],Occ)
   end,

   solve([ffd,down], Vars).

print_board(Board) =>
   N = Board.length,
   foreach(I in 1..N)
      foreach(J in 1..N)
         X = Board[I,J],
         if var(X) then printf("  _") else printf("  %w", X) end
      end,
      nl
   end,
   nl.



%----------------------------------------------------------------------
% Sample data
%----------------------------------------------------------------------

problem(1, Data) => 
Data = [
    [_, _, 2, _, _, 5, _, 7, 9],
    [1, _, 5, _, _, 3, _, _, _],
    [_, _, _, _, _, _, 6, _, _],
    [_, 1, _, 4, _, _, 9, _, _],
    [_, 9, _, _, _, _, _, 8, _],
    [_, _, 4, _, _, 9, _, 1, _],
    [_, _, 9, _, _, _, _, _, _],
    [_, _, _, 1, _, _, 3, _, 6],
    [6, 8, _, 3, _, _, 4, _, _]].

problem(2, Data) => 
 Data = [
    [_, _, 3, _, _, 8, _, _, 6],
    [_, _, _, 4, 6, _, _, _, _],
    [_, _, _, 1, _, _, 5, 9, _],
    [_, 9, 8, _, _, _, 6, 4, _],
    [_, _, _, _, 7, _, _, _, _],
    [_, 1, 7, _, _, _, 9, 5, _],
    [_, 2, 4, _, _, 1, _, _, _],
    [_, _, _, _, 4, 6, _, _, _],
    [6, _, _, 5, _, _, 8, _, _]].

problem(3, Data) => 
Data = [
    [_, _, _, 9, _, _, _, _, _],
    [_, _, 7, _, 6, _, 5, _, _],
    [_, _, 3, 5, _, _, _, 7, 9],
    [4, _, 5, _, _, 9, _, _, 1],
    [8, _, _, _, _, _, _, _, 7],
    [1, _, _, 6, _, _, 9, _, 8],
    [6, 4, _, _, _, 8, 7, _, _],
    [_, _, 9, _, 1, _, 2, _, _],
    [_, _, _, _, _, 7, _, _, _]].

problem(4, Data) => 
Data = [
    [_, 5, _, _, _, 1, 4, _, _], 
    [2, _, 3, _, _, _, 7, _, _], 
    [_, 7, _, 3, _, _, 1, 8, 2], 
    [_, _, 4, _, 5, _, _, _, 7], 
    [_, _, _, 1, _, 3, _, _, _], 
    [8, _, _, _, 2, _, 6, _, _], 
    [1, 8, 5, _, _, 6, _, 9, _], 
    [_, _, 2, _, _, _, 8, _, 3], 
    [_, _, 6, 4, _, _, _, 7, _]].

% Problems 5-8 are harder, taken from
% http://www2.ic-net.or.jp/~takaken/auto/guest/bbs46.html
problem(5, Data) => Data = [
    [_, 9, 8, _, _, _, _, _, _],
    [_, _, _, _, 7, _, _, _, _],
    [_, _, _, _, 1, 5, _, _, _],
    [1, _, _, _, _, _, _, _, _],
    [_, _, _, 2, _, _, _, _, 9],
    [_, _, _, 9, _, 6, _, 8, 2],
    [_, _, _, _, _, _, _, 3, _],
    [5, _, 1, _, _, _, _, _, _],
    [_, _, _, 4, _, _, _, 2, _]].

problem(6, Data) => 
Data = [
    [_, _, 1, _, 2, _, 7, _, _],
    [_, 5, _, _, _, _, _, 9, _],
    [_, _, _, 4, _, _, _, _, _],
    [_, 8, _, _, _, 5, _, _, _],
    [_, 9, _, _, _, _, _, _, _],
    [_, _, _, _, 6, _, _, _, 2],
    [_, _, 2, _, _, _, _, _, _],
    [_, _, 6, _, _, _, _, _, 5],
    [_, _, _, _, _, 9, _, 8, 3]].

problem(7, Data) => 
Data = [
    [1, _, _, _, _, _, _, _, _],
    [_, _, 2, 7, 4, _, _, _, _],
    [_, _, _, 5, _, _, _, _, 4],
    [_, 3, _, _, _, _, _, _, _],
    [7, 5, _, _, _, _, _, _, _],
    [_, _, _, _, _, 9, 6, _, _],
    [_, 4, _, _, _, 6, _, _, _],
    [_, _, _, _, _, _, _, 7, 1],
    [_, _, _, _, _, 1, _, 3, _]].

problem(8, Data) => 
Data = [
    [1, _, 4, _, _, _, _, _, _],
    [_, _, 2, 7, 4, _, _, _, _],
    [_, _, _, 5, _, _, _, _, _],
    [_, 3, _, _, _, _, _, _, _],
    [7, 5, _, _, _, _, _, _, _],
    [_, _, _, _, _, 9, 6, _, _],
    [_, 4, _, _, _, 6, _, _, _],
    [_, _, _, _, _, _, _, 7, 1],
    [_, _, _, _, _, 1, _, 3, _]].


% BBC Focus magazine October 2005
problem(9, Data) => 
Data = [
    [_, 6, _, 3, 2, _, _, 7, _],
    [4, 7, _, _, _, _, _, 3, 2],
    [_, _, _, 9, _, _, 1, 4, 6],
    [2, 4, _, 8, _, _, _, _, _],
    [_, _, 8, _, _, _, 2, _, 1],
    [1, _, _, _, _, 2, _, _, _],
    [_, _, 2, 4, 7, 6, 8, _, _],
    [6, 8, 9, _, _, _, _, 5, 4],
    [_, _, _, _, 8, _, _, _, _]].

problem(10, Data) => 
Data = [
    [1, 8, 2, 7, 5, _, 3, _, 9],
    [9, 5, 6, _, 3, _, _, 8, _],
    [3, 4, 7, _, _, 9, _, 5, _],
    [2, _, 3, _, 4, _, _, 9, 8],
    [4, _, 8, 9, _, 2, 5, _, 3],
    [5, 7, 9, 3, 6, 8, 1, 2, 4],
    [_, 2, _, 4, 9, _, 8, 3, _],
    [_, 3, _, _, 2, _, 9, _, 5],
    [_, 9, _, _, _, 3, _, 1, _]].

/*
  These are from J:s sudoku.ijs
*/ 
% Roger Huis example
problem(11,Data) => 
Data = [
       [2,_,_,6,7,_,_,_,_],
       [_,_,6,_,_,_,2,_,1],
       [4,_,_,_,_,_,8,_,_],
       [5,_,_,_,_,9,3,_,_],
       [_,3,_,_,_,_,_,5,_],
       [_,_,2,8,_,_,_,_,7],
       [_,_,1,_,_,_,_,_,4],
       [7,_,8,_,_,_,6,_,_],
       [_,_,_,_,5,3,_,_,8]].


% This puzzle is the evil puzzle from
% Perl's Games::Sudoku examples
problem(12, Data) => 
Data = [
       [_,7,6,4,_,_,5,_,_],
       [_,_,_,_,_,5,_,_,4],
       [_,_,_,_,7,_,_,6,9],
       [5,_,_,_,_,2,_,9,_],
       [_,3,1,_,_,_,2,5,_],
       [_,6,_,5,_,_,_,_,1],
       [6,2,_,_,4,_,_,_,_],
       [8,_,_,3,_,_,_,_,_],
       [_,_,5,_,_,7,4,3,_]].



% From https://groups.google.com/d/topic/comp.lang.prolog/sTSzJMflBDw/discussion
problem(13, Data) => 
Data = [
       [_,_,_,_,_,_,_,1,2],
       [_,_,_,_,_,_,_,_,3],   
       [_,_,2,3,_,_,4,_,_],
       [_,_,1,8,_,_,_,_,5],
       [_,6,_,_,7,_,8,_,_],
       [_,_,_,_,_,9,_,_,_],
       [_,_,8,5,_,_,_,_,_],
       [9,_,_,_,4,_,5,_,_],
       [4,7,_,_,_,6,_,_,_]].

% First problem from Project Euler #96:
% http://projecteuler.net/problem=96
problem(14,Data) => 
Data = 
[
[_,_,3,_,2,_,6,_,_],
[9,_,_,3,_,5,_,_,1],
[_,_,1,8,_,6,4,_,_],
[_,_,8,1,_,2,9,_,_],
[7,_,_,_,_,_,_,_,8],
[_,_,6,7,_,8,2,_,_],
[_,_,2,6,_,9,5,_,_],
[8,_,_,2,_,3,_,_,9],
[_,_,5,_,1,_,3,_,_]
].


% http://blag.nullteilerfrei.de/2014/07/03/why-someone-thought-that-sudoku-might-not-be-boring-while-actually-you-should-learn-how-to-properly-implement-backtracking/
problem(15, Data) =>
  Data =
 [
  [_, _, _, _, 6, _, _, 8, _],
  [_, 2, _, _, _, _, _, _, _],
  [_, _, 1, _, _, _, _, _, _],
  [_, 7, _, _, _, _, 1, _, 2],
  [5, _, _, _, 3, _, _, _, _],
  [_, _, _, _, _, _, 4, _, _],
  [_, _, 4, 2, _, 1, _, _, _],
  [3, _, _, 7, _, _, 6, _, _],
  [_, _, _, _, _, _, _, 5, _] 
].