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("");
	}
}