/*

  Sudoku solver in Picat.

  From
  https://www.facebook.com/hakan.holgersson.39/posts/2175578379248649
  """
  This is a sudoku I made 2 years ago. If it weren't for the frames it would 
  have 2515 solutions. It's called "No 5's in the frames", and has the rule 
  that the yellow squares can't contain any 5's. That takes away 2514 solutions. 
  """

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

*/

import util.
import cp.

main => go.

go ?=>
   nolog,
   sudoku(holgersson),
   nl,
   fail,
   nl.
go => true.

%
% Wrappers for 9x9 problems
%
sudoku(ProblemName) =>
	problem(ProblemName, Board,Frame),
	print_board(Board),
	sudoku(3, Board,Frame),
	print_board(Board).


sudoku(N, Board,Frame) =>
   N2 = N*N,

   Vars = Board.vars(),
   Vars :: 1..N2,

   foreach(Row in Board) all_different(Row) end,
   foreach(Column in transpose(Board)) all_different(Column) end,
   foreach(I in 1..N..N2, J in 1..N..N2)
      all_different([Board[I+K,J+L] : K in 0..N-1, L in 0..N-1])
   end,
   foreach(F in Frame)
     Board[F[1],F[2]] #!= 5
   end,
   solve([ffd,down], Vars). % faster overall


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("%3w", "_")
         else
            printf("%3w", X)
         end
      end,
      nl
   end,
   nl.



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

problem(holgersson, Grid, Frame) => 
Grid = [
    [_, _, _,   _, _, 8,   _, _, _],
    [_, 4, _,   7, _, _,   _, 3, _],
    [_, _, 9,   _, _, _,   _, _, 4],
    
    [_, _, _,   1, _, 2,   4, _, 9],
    [_, _, _,   _, _, _,   _, _, _],
    [7, _, 2,   4, _, 3,   _, _, _],
    
    [2, _, _,   _, _, _,   7, _, _],
    [_, 1, _,   _, _, 9,   _, 2, _],
    [_, _, _,   6, _, _,   _, _, _]],
Frame = [ [2,J] : J in 2..8] ++
        [ [I,2] : I in 3..7] ++
        [ [I,8] : I in 3..7] ++
        [ [8,J] : J in 2..8] ++
        [ [4,J] : J in 4..6] ++
        [ [5,J] : J in [4,6]] ++
        [ [6,J] : J in 4..6].