import Prelude;
import vis::Figure;
import vis::Render;

public rel[int,int,int] sudoku(rel[int x, int y, int v] sudoku){
	annotated= annotateGrid(sudoku);
	solved = {<0,0,0,0,{0}>};
	
	while(!isEmpty(solved)){
		for (n <- [0 ..8]){
			column = domainR(annotated, {n});
			annotated -= column;
			annotated += reduceOptions(column);
				
			row = {<x,y,v,g,p> | <x,y,v,g,p> <- annotated, y==n};
			annotated -= row;
			annotated += reduceOptions(row);
				
			grid1 = {<x,y,v,g,p> | <x,y,v,g,p> <- annotated, g==n};
			annotated -= grid1;
			annotated += reduceOptions(grid1);
		}	
		
		solved = {<x,y,v,g,p> | <x,y,v,g,p> <- annotated, size(p)==1};
		annotated -= solved;
		annotated += {<x,y,getOneFrom(p),g,{*[1 .. 9]}> | <x,y,v,g,p> <- solved};
	}

	result = {<x,y,v> | <x,y,v,g,p> <- annotated};
	return result;
}


//adds gridnumber and default set of options
public rel[int,int,int,int,set[int]] annotateGrid(rel[int x, int y, int v] sudoku){
	result = {};
		for (<x, y, v> <- sudoku){
			g = 0;
			if (x<3 && y<3) g = 0;
			if (2<x && x<6 && y<3) g = 1;
			if (x>5 && y<3) g = 2;
				
			if (x<3 && 2<y && y<6) g = 3;
			if (2<x && x<6 && 2<y && y<6) g = 4;
			if (x>5 && 2<y && y<6) g = 5;
				
			if (x<3 && y>5) g=6;
			if (2<x && x<6 && y>5) g=7;
			if (x>5 && y>5) g=8;
			
			result += <x,y,v,g,{*[1 .. 9]}>;
			}
	return result;
}

//reduces set of options
public rel[int,int,int,int,set[int]] reduceOptions(rel[int x, int y, int v, int g, set[int] p] subSudoku){
	solved = {<x,y,v,g,p> | <x,y,v,g,p> <- subSudoku, v!=0};
	numbers = {*[1 .. 9]} - {v | <x,y,v,g,p> <- solved};
	remaining = {<x,y,v,g,numbers&p> | <x,y,v,g,p> <- subSudoku-solved};
	result = remaining + solved;
	return result;
}

//a function to visualize the result
public void displaySudoku(rel[int x, int y, int v] sudoku){
	points = [box(text("<v>"), align(0.111111*(x+1),0.111111*(y+1)),shrink(0.1)) | <x,y,v> <- sudoku];
	print(points);
	render(overlay([*points], aspectRatio(1.0)));
}

//a sudoku
public rel[int, int, int] sudokuA =
{
<0,0,3>, <1,0,9>, <2,0,4>, <3,0,0>, <4,0,0>, <5,0,2>, <6,0,6>, <7,0,7>, <8,0,0>,
<0,1,0>, <1,1,0>, <2,1,0>, <3,1,3>, <4,1,0>, <5,1,0>, <6,1,4>, <7,1,0>, <8,1,0>,
<0,2,5>, <1,2,0>, <2,2,0>, <3,2,6>, <4,2,9>, <5,2,0>, <6,2,0>, <7,2,2>, <8,2,0>,
<0,3,0>, <1,3,4>, <2,3,5>, <3,3,0>, <4,3,0>, <5,3,0>, <6,3,9>, <7,3,0>, <8,3,0>,
<0,4,6>, <1,4,0>, <2,4,0>, <3,4,0>, <4,4,0>, <5,4,0>, <6,4,0>, <7,4,0>, <8,4,7>,
<0,5,0>, <1,5,0>, <2,5,7>, <3,5,0>, <4,5,0>, <5,5,0>, <6,5,5>, <7,5,8>, <8,5,0>,
<0,6,0>, <1,6,1>, <2,6,0>, <3,6,0>, <4,6,6>, <5,6,7>, <6,6,0>, <7,6,0>, <8,6,8>,
<0,7,0>, <1,7,0>, <2,7,9>, <3,7,0>, <4,7,0>, <5,7,8>, <6,7,0>, <7,7,0>, <8,7,0>,
<0,8,0>, <1,8,2>, <2,8,6>, <3,8,4>, <4,8,0>, <5,8,0>, <6,8,7>, <7,8,3>, <8,8,5>
};