# BYU CS classes

### Site Tools

sc330_f2016:sudoku
% A Sudoku solver.  The basic idea is for each position,
% check that it is a digit with digit.  Then verify that the digit
% chosen doesn't violate any constraints (row, column, and cube).
% If no constraints were violated, proceed further.  If a constraint
% was violated, then backtrack to the last digit choice and move from
% there (the Prolog engine should handle this for you automatically).
% If we reach the end of the board with this scheme, it means that
% the whole thing is solved.

% YOU SHOULD FILL IN THE SOLVE PROCEDURE, DOWN BELOW.

digit(1).
digit(2).
digit(3).
digit(4).
digit(5).
digit(6).
digit(7).
digit(8).
digit(9).

numBetween(Num, Lower, Upper) :-
Num >= Lower,
Num =< Upper.

% cubeBounds: (RowLow, RowHigh, ColLow, ColHigh, CubeNumber)
cubeBounds(0, 2, 0, 2, 0).
cubeBounds(0, 2, 3, 5, 1).
cubeBounds(0, 2, 6, 8, 2).
cubeBounds(3, 5, 0, 2, 3).
cubeBounds(3, 5, 3, 5, 4).
cubeBounds(3, 5, 6, 8, 5).
cubeBounds(6, 8, 0, 2, 6).
cubeBounds(6, 8, 3, 5, 7).
cubeBounds(6, 8, 6, 8, 8).

% Given a board and the index of a column of interest (0-indexed),
% returns the contents of the column as a list.
% columnAsList: (Board, ColumnNumber, AsRow)
columnAsList([], _, []).
columnAsList(Tail, ColumnNum, Rest).

% given which row and column we are in, gets which cube
% is relevant.  A helper ultimately for getCube.
% cubeNum: (RowNum, ColNum, WhichCube)
cubeNum(RowNum, ColNum, WhichCube) :-
cubeBounds(RowLow, RowHigh, ColLow, ColHigh, WhichCube),
numBetween(RowNum, RowLow, RowHigh),
numBetween(ColNum, ColLow, ColHigh).

% Drops the first N elements from a list.  A helper ultimately
% for getCube.
% drop: (InputList, NumToDrop, ResultList)
drop([], _, []):-!.
drop(List, 0, List):-!.
drop([_|Tail], Num, Rest) :-
Num > 0,
NewNum is Num - 1,
drop(Tail, NewNum, Rest).

% Takes the first N elements from a list.  A helper ultimately
% for getCube.
% take: (InputList, NumToTake, ResultList)
take([], _, []):-!.
take(_, 0, []):-!.
Num > 0,
NewNum is Num - 1,
take(Tail, NewNum, Rest).

% Gets a sublist of a list in the same order, inclusive.
% A helper for getCube.
% sublist: (List, Start, End, NewList)
sublist(List, Start, End, NewList) :-
drop(List, Start, TempList),
NewEnd is End - Start + 1,
take(TempList, NewEnd, NewList).

% Given a board and cube number, gets the corresponding cube as a list.
% Cubes are 3x3 portions, numbered from the top left to the bottom right,
% starting from 0.  For example, they would be numbered like so:
%
% 0  1  2
% 3  4  5
% 6  7  8
%
% getCube: (Board, CubeNumber, ContentsOfCube)
getCube(Board, Number, AsList) :-
cubeBounds(RowLow, RowHigh, ColLow, ColHigh, Number),
sublist(Board, RowLow, RowHigh, [Row1, Row2, Row3]),
sublist(Row1, ColLow, ColHigh, Row1Nums),
sublist(Row2, ColLow, ColHigh, Row2Nums),
sublist(Row3, ColLow, ColHigh, Row3Nums),
append(Row1Nums, Row2Nums, TempRow),
append(TempRow, Row3Nums, AsList).

% Given a board, solve it in-place.
% After calling solve on a board, the board should be fully
% instantiated with a satisfying Sudoku solution.

% ---- PUT CODE HERE ---
% ---- PUT CODE HERE ---

solve(Board) :- true.  % ---PUT CODE HERE---

% ---- PUT CODE HERE ---
% ---- PUT CODE HERE ---

% Prints out the given board.
printBoard([]).
printBoard(Tail).

test1(Board) :-
Board = [[2, _, _, _, 8, 7, _, 5, _],
[_, _, _, _, 3, 4, 9, _, 2],
[_, _, 5, _, _, _, _, _, 8],
[_, 6, 4, 2, 1, _, _, 7, _],
[7, _, 2, _, 6, _, 1, _, 9],
[_, 8, _, _, 7, 3, 2, 4, _],
[8, _, _, _, _, _, 4, _, _],
[3, _, 9, 7, 4, _, _, _, _],
[_, 1, _, 8, 2, _, _, _, 5]],
solve(Board),
printBoard(Board).

test2(Board) :-
Board = [[_, _, _, 7, 9, _, 8, _, _],
[_, _, _, _, _, 4, 3, _, 7],
[_, _, _, 3, _, _, _, 2, 9],
[7, _, _, _, 2, _, _, _, _],
[5, 1, _, _, _, _, _, 4, 8],
[_, _, _, _, 5, _, _, _, 1],
[1, 2, _, _, _, 8, _, _, _],
[6, _, 4, 1, _, _, _, _, _],
[_, _, 3, _, 6, 2, _, _, _]],
solve(Board),
printBoard(Board).