module sudoku; // -*-C-*-ish abstract data Sudoku<a>([[Maybe<a>]] grid, [a] valid); // List of all possible values in each position abstract data SState<a>([[[a]]] grid); Exception MustBeNinePossible; public Sudoku<a> blank([a] valid) { if (size(valid)!=9) { throw(MustBeNinePossible); } sudoku = Sudoku([],valid); // TODO: Check for repetitions. for x in [0..8] { for y in [0..8] { sudoku.grid[x][y] = nothing; } } return sudoku; } Exception InvalidValue; Exception NotInValidValues(String val); public Void setValue(Sudoku<a> s, Int x, Int y, a val) { if (!(elem(val,s.valid))) { throw(NotInValidValues(marshal(val,0))); } if (!(elem(val,getPossibleValues(s,x,y)))) { throw(InvalidValue); } s.grid[y][x]=just(val); } Void setValueFast(Sudoku<a> s, Int x, Int y, a val) { s.grid[y][x]=just(val); } public Maybe<a> getValue(Sudoku<a> s, Int x, Int y) { return s.grid[y][x]; } public [a] getRowUsed(Sudoku<a> s, Int x, Int y) { used = []; for z in [0..8] { if (z!=x) { case getValue(s,z,y) of { nothing -> ; | just(val) -> push(used,val); } } } return used; } public [a] getColumnUsed(Sudoku<a> s, Int x, Int y) { used = []; for z in [0..8] { if (z!=y) { case getValue(s,x,z) of { nothing -> ; | just(val) -> push(used,val); } } } return used; } public [a] getBoxUsed(Sudoku<a> s, Int x, Int y) { used = []; // Find start of 3x3 box we're in. xstart = (x/3)*3; ystart = (y/3)*3; for xv in [xstart..xstart+2] { for yv in [ystart..ystart+2] { if (xv!=x || yv!=y) { case getValue(s,xv,yv) of { nothing -> ; | just(val) -> push(used,val); } } } } return used; } public [a] getInvalidValues(Sudoku<a> s, Int x, Int y) { row = getRowUsed(s,x,y); column = getColumnUsed(s,x,y); box = getBoxUsed(s,x,y); concat(row,column); concat(row,box); all = []; while(size(row)>0) { val = shift(row); if (!elem(val,all)) push(all,val); } return all; } public [a] getPossibleValues(Sudoku<a> s, Int x, Int y) { all = []; // If it's set, there's only one possible, obviously... case getValue(s,x,y) of { just(val) -> return [val]; | nothing -> invalid = getInvalidValues(s,x,y); for val in s.valid { if (!elem(val,invalid)) push(all,val); } return all; } } "Go through adding values which are trivial to deduce. Returns true if the grid was modified." public Bool addSimple(Sudoku<a> s) { modified = false; for x in [0..8] { for y in [0..8] { case getValue(s,x,y) of { just(val) -> ; | nothing -> pvs = getPossibleValues(s,x,y); if (size(pvs)==1) { setValueFast(s,x,y,pvs[0]); modified = true; } } } } return modified; } /* "Do some magic to establish what goes in a row" public Bool addRowWise(Sudoku<a> s) { modified = false; for row in [0..8] { // Start by getting all the possible values for each entry in the row possibles = []; for x in [0..8] { push(possibles,getPossibleValues(s,x,row)); } // Now for each position, if a value appears which can be in no // other row, it must be the value here so add it. for x in [0..8] { pvals = checkPossibles(s, possibles,x); if (size(pvals)==1) { setValueFast(s,x,row,pvals[0]); } } } return modified; } "Do some magic to establish what goes in a column" public Bool addColumnWise(Sudoku<a> s) { modified = false; for column in [0..8] { // Start by getting all the possible values for each entry in the row possibles = []; for y in [0..8] { push(possibles,getPossibleValues(s,column,y)); } // Now for each position, if a value appears which can be in no // other row, it must be the value here so add it. for y in [0..8] { pvals = checkPossibles(s, possibles, y); if (size(pvals)==1) { setValueFast(s,column,y,pvals[0]); } } } return modified; } */ public [a] checkPossibles(Sudoku<a> s, [[a]] possibles, Int x) { pvals = possibles[x]; novals = []; // If some value in pvals appears in another list, it doesn't help us, // so add it to novals. for v in pvals { for other in [0..8] { if (other!=x) { if (elem(v,possibles[other])) { push(novals,v); } } } } vals = []; for v in pvals { if (!elem(v,novals)) { push(vals,v); } } if (size(vals)==1) return vals; else return pvals; } public SState<a> mkPossibles(Sudoku<a> s) { for x in [0..8] { for y in [0..8] { pvals = getPossibleValues(s,x,y); pstate[y][x] = pvals; } } return SState(pstate); } public Bool refinePossibles(Sudoku<a> s, SState<a> pvals) { refineRows(s,pvals); refineColumns(s,pvals); refineBoxes(s,pvals); return refineGrid(s,pvals); } public Void refineRows(Sudoku<a> s, SState<a> sp) { for row in sp.grid { for col in [0..8] { pvals = checkPossibles(s,row,col); row[col] = pvals; } } } public Void refineColumns(Sudoku<a> s, SState<a> sp) { for col in [0..8] { colvals = []; for row in [0..8] { push(colvals,sp.grid[row][col]); } for row in [0..8] { pvals = checkPossibles(s,colvals,row); sp.grid[row][col] = pvals; } } } public Void refineBoxes(Sudoku<a> s, SState<a> sp) { for xstart in [0,3,6] { for ystart in [0,3,6] { boxvals = []; for row in [ystart..ystart+2] { for col in [xstart..xstart+2] { push(boxvals,sp.grid[row][col]); } } for v in [0..8] { pvals = checkPossibles(s,boxvals,v); // Now work out where to put it! colloc = xstart + (v % 3); rowloc = ystart + (v / 3); sp.grid[rowloc][colloc] = pvals; } } } } // Go through the possible values, if there's only one, set it in the grid. public Bool refineGrid(Sudoku<a> s, SState<a> sp) { modified = false; for x in [0..8] { for y in [0..8] { if (size(sp.grid[y][x])==1) { if (getValue(s,x,y)==nothing) { setValue(s,x,y,sp.grid[y][x][0]); modified = true; } } } } return modified; } public Void show(Sudoku<Int> s) { r = 0; for row in s.grid { if (r%3 == 0) putStrLn("+---------+----------+--------+"); r++; c = 0; for x in row { if (c%3 == 0) putStr("|"); c++; case x of { nothing -> putStr("[ ]"); | just(num) -> putStr("["+num+"]"); } } putStrLn("|"); } putStrLn("+---------+----------+--------+"); } public Void showPossibles(SState<Int> s) { // case s of { // SState(rows) -> ; // } // [[[Int]]] rows = s.grid; for row in s.grid { for ps in row { putStr("("); for v in ps { putStr(v+","); } putStr(") "); } putStrLn(""); } }