## ams_version=1.0

Model Main_template {
    Comment: {
        "Keywords:
        Mixed Integer Programming, Mixed Integer Formulations, Multiple Solutions, GMP Functions, Pivot Table."
    }
    DeclarationSection Declaration_Sudoku_Model {
        Set AllRows {
            Index: r;
            Parameter: Row;
            Definition: Data{R-1..R-9};
        }
        Set AllColumns {
            Index: c;
            Parameter: Column;
            Definition: Data{C-1..C-9};
        }
        Set AllValues {
            SubsetOf: Integers;
            Index: v;
            Parameter: Value;
            Property: ElementsAreLabels;
            Definition: Data{1..9};
        }
        Set Groups {
            Index: g;
            Parameter: SelectedGroup;
        }
        Set SelectedGroups {
            SubsetOf: Groups;
            Index: sg;
        }
        Set SubAreas {
            Index: sa_r, sa_c;
            Definition: Data{A-1..A-3};
        }
        Set Diagonals {
            Index: d;
            Definition: data { D-1 .. D-9 };
        }
        Set ReverseDiagonals {
            Index: rd;
            Definition: data { RD-1 .. RD-9 };
        }
        Set SubAreaCenters {
            Index: ac;
            Definition: data { AC-1 };
        }
        Set NRCAreas {
            Index: n_r, n_c;
            Definition: data { N-1 .. N-2 };
        }
        ElementParameter FixedValues {
            IndexDomain: (r,c);
            Range: AllValues;
        }
        Variable Solution {
            IndexDomain: (r,c,v);
            Range: binary;
        }
        Constraint FixValues {
            IndexDomain: (r,c) | FixedValues(r, c);
            Definition: Solution(r,c,FixedValues(r,c)) = 1;
        }
        Constraint OneValuePerCell {
            IndexDomain: (r,c);
            Definition: sum[v,Solution(r,c,v)] = 1;
        }
        Parameter GroupDefinition {
            IndexDomain: (g,r,c);
        }
        Constraint ValueOnePerGroup {
            IndexDomain: (g in SelectedGroups,v);
            Definition: {
                sum[(r,c) | GroupDefinition(g,r,c), Solution(r,c,v)] = 1;
            }
        }
        MathematicalProgram Sudoku {
            Objective: RandomObjective;
            Direction: minimize;
            Constraints: AllConstraints;
            Variables: AllVariables;
            Type: MIP;
        }
        Parameter RandomCoefficient {
            IndexDomain: (r,c,v);
        }
        Variable RandomObjective {
            Definition: sum[(r,c,v), RandomCoefficient(r,c,v)*Solution(r,c,v)];
        }
        Parameter UniquenessCoefficient {
            IndexDomain: (r,c,v);
            InitialData: 0;
        }
        Variable UniquenesObjective {
            Definition: sum[(r,c,v), UniquenessCoefficient(r,c,v)*Solution(r,c,v)];
        }
        MathematicalProgram UniquenessSudoku {
            Objective: UniquenesObjective;
            Direction: minimize;
            Constraints: AllConstraints;
            Variables: AllVariables;
            Type: MIP;
        }
        Parameter GeneratedSize;
        Parameter GroupWeight {
            IndexDomain: (sg);
            Definition: sum((r,c), GroupDefinition(sg,r,c) $ FixedValues(r, c));
        }
        Parameter CellWeight {
            IndexDomain: (c,r);
            Definition: sum(sg | GroupDefinition(sg, r, c), GroupWeight(sg));
        }
    }
    DeclarationSection Declaration_GUI_Support {
        ElementParameter ColorGroups {
            IndexDomain: (r,c);
            Range: AllColors;
            Definition: {
                if div(ord(r)+2,3) + div(ord(c)+2,3) = 3 or
                   div(ord(r)+2,3) + div(ord(c)+2,3) = 5 then
                	'Very Light Grey'
                endif;
            }
        }
        ElementParameter InputDataColor {
            IndexDomain: (r,c);
            Range: AllColors;
            Definition: {
                if FixedValues(r,c) then
                	'blue'
                elseif max(ags,GUISolution(ags,r,c)) <> min(ags,GUISolution(ags,r,c)) then
                	'red'
                endif
            }
            Comment: "GUISolution(GUIFirstSolution,r,c) <> GUISolution(GUISecondSolution, r,c)";
        }
        ElementParameter NotUnique {
            IndexDomain: (r,c);
            Range: AllColors;
            Definition: {
                if GUISolution(GUIFirstSolution, r,c) <> GUISolution(GUISecondSolution, r,c) then
                	'red'
                endif;
            }
        }
        Set AllGUISolutions {
            Index: ags;
            Definition: ElementRange(1,NoOfSolutions, prefix:"solution-");
        }
        Parameter NoOfSolutions {
            Range: {
                {0..inf}
            }
        }
        Set SubsetGUISolutions {
            SubsetOf: AllGUISolutions;
            Index: ags_s;
            Definition: {
                {ags | ags > GUIFirstSolution}
            }
        }
        ElementParameter GUISolution {
            IndexDomain: (ags,r,c);
            Range: AllValues;
        }
        ElementParameter GUIFirstSolution {
            Range: AllGUISolutions;
            Definition: first(ags);
        }
        ElementParameter GUISecondSolution {
            Range: AllGUISolutions;
            Definition: element(AllGUISolutions,2);
        }
        ElementParameter ACase {
            Range: AllCases;
        }
        Set MultiSolutionSolvers {
            SubsetOf: AllSolvers;
            Definition: {
                {ms|FindString(Formatstring("%e",ms),"BARON")
                or (FindString(Formatstring("%e",ms),"CPLEX") and SubString(Formatstring("%e",ms),-4,-1)>= "11.0")
                or (FindString(Formatstring("%e",ms),"CPLEX") and SubString(Formatstring("%e",ms),-6,-1)>= "11.0.0")}
            }
        }
        ElementParameter SelectedSolver {
            Range: MultiSolutionSolvers;
        }
        Index ms {
            Range: AllSolvers;
        }
        StringParameter SudokuString;
    }
    Procedure MainInitialization {
        Body: {
            CreateGroups;
            
            ! Select latest CPLEX version as the default.
            SelectedSolver := StringToElement(AllSolvers, max(IndexSolvers|FindString(IndexSolvers,"CPLEX") and not FindString(IndexSolvers,"ODH"),SubString(IndexSolvers,1,50)));
        }
    }
    Procedure CreateGroups {
        Body: {
            empty groups;
            
            ! 3x3 blocks
            for (sa_r,sa_c) do
            	SetElementAdd(Groups,NewGroup,sa_r + "_" + sa_c);
            	SelectedGroups += NewGroup;
            	GroupDefinition(NewGroup,r,c) := [ord(sa_r) = div(ord(r)+2,3)   ] and
                  					 [ord(sa_c) = div(ord(c)+2,3)];
            endfor;
            
            ! rows
            for (r) do
            	SetElementAdd(Groups,NewGroup,r);
            	SelectedGroups += NewGroup;
            	GroupDefinition(NewGroup,r,c) := 1;
            endfor;
            
            ! columns
            for (c) do
            	SetElementAdd(Groups,NewGroup,c);
            	SelectedGroups += NewGroup;
            	GroupDefinition(NewGroup,r,c) := 1;
            endfor;
            
            ! diagonals (not selected by default)
            for (d) do
            	SetElementAdd(Groups,NewGroup,d);
            	GroupDefinition(NewGroup,r,c) := (mod(ord(r) - ord(c), 9) = (ord(d) - 1));
            endfor;
            
            ! reverse diagonals (not selected by default)
            for (rd) do
            	SetElementAdd(Groups,NewGroup,rd);
            	GroupDefinition(NewGroup,r,c) := (mod(ord(r) + ord(c) - 1, 9) = (ord(rd) - 1));
            endfor;
            
            ! block centers (not selected by default)
            for (ac) do
            	SetElementAdd(Groups,NewGroup,ac);
            	GroupDefinition(NewGroup,r,c) := [mod(ord(r), 3) = 2 and mod(ord(c), 3) = 2];
            endfor;
            
            ! NRC sudoku (not selected by default)
            for (n_r,n_c) do
            	SetElementAdd(Groups,NewGroup,n_r + "_" + n_c);
            	GroupDefinition(NewGroup,r,c) := [ord(n_r) = div(ord(r) + (2 - ord(n_r)),3)   ] and
                  					 [ord(n_c) = div(ord(c) + (2 - ord(n_c)),3)];
            endfor;
            
            SelectedGroup := first(Groups);
        }
        ElementParameter NewGroup {
            Range: Groups;
        }
    }
    Procedure MainExecution {
        Body: {
            RandomCoefficient(r,c,v) := 1;
            solve Sudoku where solver = SelectedSolver;
            GUISolution(ags,r,c)|(ord(ags)=1) := first(v | Solution(r,c,v));
            
            NoOfSolutions := 2;
            UniquenessCoefficient(r, c, v) := Solution(r, c, v);
            solve UniquenessSudoku where solver = SelectedSolver;
            GUISolution(ags,r,c)|(ord(ags)=2) := first(v | Solution(r,c,v));
        }
        Comment: {
            "Solution(r,c,FixedValues(r,c)) := 1;"
        }
    }
    Procedure MultipleSolve {
        Body: {
            if SelectedSolver = '' then
            	DialogMessage("No Solver Selected or Available");
            	return;
            endif;
            
            empty GUISolution;
            
            CreateGroups;
            
            if FindString(FormatString("%e", SelectedSolver),"CPLEX") then
            	OptionSetString(FormatString("%e::do_populate", SelectedSolver),"yes");
            	OptionSetString(FormatString("%e::pool_intensity", SelectedSolver),"aggressive");
            endif;
            if FindString(FormatString("%e", SelectedSolver),"BARON") then
            	OptionSetValue(FormatString("%e::number_of_best_solutions", SelectedSolver),5);
            endif;
            solve Sudoku where solver = SelectedSolver;
            
            NoOfSolutions := GMP::Solution::Count('Sudoku');
            for ags do
            	GMP::Solution::SendToModel('Sudoku',ord(ags));
            	GUISolution(ags,r,c) := first(v | Solution(r,c,v));
            endfor;
        }
    }
    Procedure GenerateSudoku1 {
        Body: {
            BestFixedValues(r,c) := FixedValues(r, c);
            
            while (LoopCount <= 25) do
            	FixedValues(r,c) := First(v | Solution(r, c, v));
                empty Tested;
            
            	while (card(Tested) < 81) do
            		! unset the value of a random cell that has not been tested before
            		repeat
            			RandomNumber := floor(uniform(0,81));
            			Row := Element(AllRows, div(RandomNumber,9) + 1);
            			Column := Element(AllColumns, mod(RandomNumber,9) + 1);
            
            			break when not Tested(Row, Column);
            		endrepeat;
            
            		Tested(Row,Column) := 1;
            		Value := FixedValues(Row, Column);
            		FixedValues(Row,Column) := '';
            
            		! if it does not produce the same unique solution, reset
            		solve UniquenessSudoku where solver = SelectedSolver;
            
            		if (UniquenesObjective <> 81) then
            			FixedValues(Row, Column) := Value;
            		endif;
            	endwhile;
            
            	solve UniquenessSudoku where solver = SelectedSolver;
            	GeneratedSize := card(FixedValues);
            	if (GeneratedSize < card(BestFixedValues)) then
            		BestFixedValues(r,c) := FixedValues(r,c);
            	endif;
            
            	PageRefreshAll();
            endwhile;
            
            FixedValues(r, c) := BestFixedValues(r, c);
            empty GUISolution;
            GeneratedSize := card(FixedValues);
            
            empty SudokuString;
            for (r,c) do
            	SudokuString += if (FixedValues(r,c)) then FixedValues(r,c) else "." endif;
            endfor;
        }
        Parameter RandomNumber;
        Parameter Tested {
            IndexDomain: (r,c);
        }
        ElementParameter BestFixedValues {
            IndexDomain: (r,c);
            Range: AllValues;
        }
    }
    Procedure GenerateSudoku2 {
        Body: {
            ! create a random puzzle
            empty FixedValues;
            RandomCoefficient(r,c,v) := uniform(1,10);
            solve sudoku;
            
            ! prepare the uniqueness sudoku to create an alternative (or not)
            UniquenessCoefficient(r, c, v) := Solution(r, c, v);
            RandomCoefficient(r,c,v) := 1;
            
            FixedValues(r,c) := First(v | Solution(r, c, v));
            
            while (card(Tested) < 81) do
            	! find the highest cellweight of all cells
            	MaxWeight := max((c,r) | FixedValues(r, c) and not Tested(r,c), CellWeight(c, r));
            	CellsWithMaxWeight := Count((r,c) | FixedValues(r, c) and CellWeight(c, r) = MaxWeight);
            	RandomNumber := floor(uniform(0,CellsWithMaxWeight));
            	! select a cell with the heighest weight that has not been tested before
            	for ((r,c) | FixedValues(r, c) and not Tested(r,c) and CellWeight(c, r) = MaxWeight) do
            		if (RandomNumber) then
            			RandomNumber -= 1;
            			skip;
            		endif;
            		Row := r;
            		Column := c;
            		break;
            	endfor;
            
            	! unset the value for this cell
            	Tested(Row,Column) := 1;
            	Value := FixedValues(Row, Column);
            	FixedValues(Row,Column) := '';
            
            	! and figure out if it still produces the same solution, if not reset 
            	solve UniquenessSudoku where solver = SelectedSolver;
            
            	if (UniquenesObjective <> 81) then
            		FixedValues(Row, Column) := Value;
            	endif;
            endwhile;
            
            solve UniquenessSudoku where solver = SelectedSolver;
            
            empty GUISolution;
            GeneratedSize := card(FixedValues);
            
            empty SudokuString;
            for (r,c) do
            	SudokuString += if (FixedValues(r,c)) then FixedValues(r,c) else "." endif;
            endfor;
            
            PageRefreshAll();
            GenerateSudoku1;
        }
        Parameter MaxWeight;
        Parameter CellsWithMaxWeight;
        Parameter RandomNumber;
        Parameter Tested {
            IndexDomain: (r,c);
        }
    }
    Procedure MainTermination {
        Body: {
            return 1;
        }
    }
}