import structure FD from "x-alice:/lib/gecode/FD"
import structure FS from "x-alice:/lib/gecode/FS"
import structure Modeling from "x-alice:/lib/gecode/Modeling"
import structure Explorer from "x-alice:/lib/tools/Explorer"

open Modeling

(* the inputlist is a list of triples(a,b,c) where
   (a,b) is the address of the variable in the grid
   and c is its value  *)

val inputlist=[(0,1,2),(0,2,6),(0,6,8),(0,7,1),(1,0,3),
               (1,3,7),(1,5,8),(1,8,6),(2,0,4),(2,4,5),
               (2,8,7),(3,1,5),(3,3,1),(3,5,7),(3,7,9),
               (4,2,3),(4,3,9),(4,5,5),(4,6,1),(5,1,4),
               (5,3,3),(5,5,2),(5,7,5),(6,0,1),(6,4,3),
               (6,8,2),(7,0,5),(7,3,2),(7,5,4),(7,8,9),
               (8,1,3),(8,2,8),(8,6,4),(8,7,6)]
                 
val inputlist_hard=[(0,5,3),(0,7,6),(1,7,1),(2,1,9),
                    (2,2,7),(2,3,5),(2,7,8),(3,4,9),
                    (3,6,2),(4,2,8),(4,4,7),(4,6,4),
                    (5,2,3),(5,4,6),(6,1,1),(6,5,2),
                    (6,6,8),(6,7,9),(7,1,4),(8,1,5),
                    (8,3,1)]
                      
fun sudoku1 inputlist space =
    let
        val grid = Vector.tabulate(9,fn x => 
                           FD.rangeVec(space,9,(1,9)))
        val grid' = Vector.concat(Vector.toList(grid))
        fun flatten([])= []
	      | flatten(x::xs)= x@flatten(xs)
	(* box constructs a list of elements representing
	   one 3 x 3 box *)
        fun box(x,y)= flatten(List.tabulate(3,fn k => 
                   List.tabulate(3,fn z =>(k+x,z+y))))
    in 
        (* use next constraint,only when imputlist is used;
           updates the values from inputlist to grid *)
        List.app(fn(x,y,z) => FD.relI(space,
            Vector.sub(Vector.sub(grid,x),y),FD.EQ,z))inputlist;
        (* distinct values in rows *)
        Vector.app(fn x => FD.distinct(space,x,FD.DOM))grid;
        (* distinct values in columns *)
        Vector.appi(fn(i,y)=> FD.distinct(space,Vector.map
                     (fn x => Vector.sub(x,i))grid,FD.DOM))grid;
        (* distinct values in 3 x 3 boxes *)
        Vector.app(fn(k,l)=> 
          let
             val box' = Vector.map(fn(x,y) => 
                              Vector.sub(Vector.sub(grid,x),y))
                             (Vector.fromList(box(k,l)))
          in
             FD.distinct(space,box',FD.DOM)
          end)
         (#[(0,0),(0,3),(0,6),(3,0),(3,3),(3,6),(6,0),(6,3),(6,6)]);
        FD.branch(space,grid',FD.B_MIN_MIN,FD.B_SPLIT_MIN);
        grid
    end
    
 (* Explorer.exploreAll(sudoku1 inputlist) *)
 (*  Explorer.exploreOne(sudoku1) *)
 (* Explorer.exploreAll(sudoku1 inputlist_hard) *)