85 lines
2.7 KiB
Plaintext
85 lines
2.7 KiB
Plaintext
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>
|
|
};
|