% Rules: % - Board is a 3 x 3 grid % - Values on the board run from 1 to 9 % - Adjacent values cannot occupy adjacent squares. % So the 4 square cannot be adjacent to the 3 or 5 squares. % - Adjacent means vertical or horizontal, not diagonal. % Otherwise no value could go in the center square, since % it touches all others. % - The board's origin is in the upper left :- module puzzle_solver. :- interface. :- import_module io. :- pred main(io.state, io.state). :- mode main(di, uo) is det. :- implementation. :- import_module int. :- import_module string. :- import_module list. :- import_module maybe. :- type square == maybe(int). :- type board ---> board( squares :: list(square), width :: int, height :: int). % Replace the Nth item in the list with NewItem :- func replace_nth_item(list(T), int, T) = list(T). :- mode replace_nth_item(in, in, in) = out is semidet. replace_nth_item([Hd | Tl], N, NewItem) = (if N = 0 then [NewItem | Tl] else [Hd | replace_nth_item(Tl, N - 1, NewItem)] ). :- func nth(list(T), int) = T. :- mode nth(in, in) = out. nth([Hd | Tl], N) = (if N = 0 then Hd else nth(Tl, N - 1) ). :- func board ^ elem(int, int) = square. :- mode in ^ elem(in, in) = out. board(Squares, _, Height)^elem(X, Y) = nth(Squares, Y * Height + X). :- func ( board ^ elem(int, int) := square ) = board. :- mode ( in ^ elem(in, in) := in ) = out is semidet. ( board(Squares0, Width, Height) ^ elem(X, Y) := Square ) = board(replace_nth_item(Squares0, Y * Height + X, Square), Width, Height). :- pred bounds(board, int, int). :- mode bounds(in, out, out) is det. bounds(board(_, Width, Height), Width, Height). :- pred in_bounds(board, int, int). :- mode in_bounds(in, in, in) is semidet. in_bounds(Board, X, Y) :- X >= 0, X < Board^width, Y >= 0, Y < Board^height. % Produce the square to the north of Square. % Fail if that square is out of bounds. :- pred north(board, int, int, square). :- mode north(in, in, in, out) is semidet. north(Board, X0, Y0, NorthSquare) :- X = X0, Y = Y0 - 1, in_bounds(Board, X, Y), NorthSquare = Board^elem(X, Y). :- pred south(board, int, int, square). :- mode south(in, in, in, out) is semidet. south(Board, X0, Y0, SouthSquare) :- X = X0, Y = Y0 + 1, in_bounds(Board, X, Y), SouthSquare = Board^elem(X, Y). :- pred east(board, int, int, square). :- mode east(in, in, in, out) is semidet. east(Board, X0, Y0, EastSquare) :- X = X0 + 1, Y = Y0, in_bounds(Board, X, Y), EastSquare = Board^elem(X, Y). :- pred west(board, int, int, square). :- mode west(in, in, in, out) is semidet. west(Board, X0, Y0, WestSquare) :- X = X0 - 1, Y = Y0, in_bounds(Board, X, Y), WestSquare = Board^elem(X, Y). % Succeed if one of the square's neighbors has the % given value (V). Fail otherwise. :- pred neighbor_has_value(board, int, int, int). :- mode neighbor_has_value(in, in, in, in) is semidet. neighbor_has_value(Board, X, Y, V) :- north(Board, X, Y, yes(V)); south(Board, X, Y, yes(V)); east(Board, X, Y, yes(V)); west(Board, X, Y, yes(V)). % Is a square allowed to have the given value? :- pred square_can_have_value(board, int, int, int). :- mode square_can_have_value(in, in, in, in) is semidet. square_can_have_value(Board, X, Y, V) :- % Don't look for values out of bounds (max_value(Board, V); not(neighbor_has_value(Board, X, Y, V + 1))), (V = 1; not(neighbor_has_value(Board, X, Y, V - 1))). :- pred solve(int, int, board, list(int), board). :- mode solve(in, in, in, in, out). solve(X, Y, Board, Values, FinishedBoard) :- bounds(Board, XMax, YMax), (if X = XMax, Y = YMax then % At the end. All done! FinishedBoard = Board else if X = XMax then % Move to the next row solve(0, Y + 1, Board, Values, FinishedBoard) else if Board^elem(X, Y) = yes(_) then % This value was already set, possibly as part of the initial condition. solve(X + 1, Y, Board, Values, FinishedBoard) else pick(Values, V, ValuesRemaining), square_can_have_value(Board, X, Y, V), NewBoard = Board^elem(X, Y) := yes(V), solve(X + 1, Y, NewBoard, ValuesRemaining, FinishedBoard) ). :- pred solve_2(board, list(int), board) is semidet. :- mode solve_2(in, in, out). solve_2(Board, Values, FinishedBoard) :- solve(0, 0, Board, Values, FinishedBoard). % The largest value that can be put in a board. :- pred max_value(board, int). :- mode max_value(in, out) is det. max_value(Board, Max) :- bounds(Board, XMax, YMax), Max = XMax * YMax. % Choose an item, any item, from the list :- pred pick(list(T), T, list(T)) is nondet. :- mode pick(in, out, out). pick([X | Xs], X, Xs). pick([X | Xs], Y, [X | Zs]) :- pick(Xs, Y, Zs). % Unit testing: Execute Lambda to get the % actual value. Print a message if (a) the lambda fails % or (b) the actual value isn't the expected value. % % test_case(T) -- a no-arg function that returns a value of type T. :- type func_test_case(T) == ((func) = T). :- pred assert_equals(func_test_case(T), T, string, io.state, io.state). :- mode assert_equals((func) = out is semidet, in, in, di, uo) is det. :- mode assert_equals((func) = out is det, in, in, di, uo) is det. assert_equals(TestCase, Expected, Message, !IO) :- if Actual = apply(TestCase), Actual = Expected then true % test passed. do nothing. else io.format("Fail:\t%s\n", [s(Message)], !IO). :- pred assert_pred_equals(pred(T), T, string, io.state, io.state). :- mode assert_pred_equals(pred(out) is semidet, in, in, di, uo) is det. :- mode assert_pred_equals(pred(out) is det, in, in, di, uo) is det. assert_pred_equals(TestCase, Expected, Message, !IO) :- if call(TestCase, Actual), Actual = Expected then true else io.format("Fail:\t%s\n", [s(Message)], !IO). :- pred assert_fail((pred), string, io.state, io.state). :- mode assert_fail((pred) is semidet, in, di, uo) is det. assert_fail(TestCase, Message, !IO) :- if call(TestCase) then io.format("Failed to fail:\t%s\n", [s(Message)], !IO) else true. :- pred assert_pass((pred), string, io.state, io.state). :- mode assert_pass((pred) is semidet, in, di, uo) is det. assert_pass(TestCase, Message, !IO) :- if call(TestCase) then true else io.format("Failed:\t%s\n", [s(Message)], !IO). :- pred test_nth(io.state::di, io.state::uo) is det. test_nth(!IO) :- List = [1, 2, 3, 4, 5], assert_equals( ((func) = (nth(List, 0)::out) is semidet), 1, "Nth: 1", !IO), assert_equals( ((func) = (nth(List, 2)::out) is semidet), 3, "Nth: 1", !IO). :- pred test_replace_nth_item(io.state::di, io.state::uo) is det. test_replace_nth_item(!IO) :- List = ['A', 'B', 'C', 'D'], assert_equals( ((func) = (replace_nth_item(List, 0, 'X')::out) is semidet), ['X', 'B', 'C', 'D'], "Replace: 0", !IO), assert_equals( ((func) = (replace_nth_item(List, 1, 'X')::out) is semidet), ['A', 'X', 'C', 'D'], "Replace: 1", !IO), assert_equals( ((func) = (replace_nth_item(List, 3, 'X')::out) is semidet), ['A', 'B', 'C', 'X'], "Replace: 3", !IO). :- pred test_board_elem_get(io.state::di, io.state::uo) is det. test_board_elem_get(!IO) :- Squares = [yes(1), yes(2), yes(3), yes(4), yes(5), yes(6), yes(7), yes(8), yes(9)], Board = board(Squares, 3, 3), assert_equals( ((func) = (Board^elem(0, 0)::out) is semidet), yes(1), "^elem get: 0,0", !IO), assert_equals( ((func) = (Board^elem(1, 0)::out) is semidet), yes(2), "^elem get: 1,0", !IO), assert_equals( ((func) = (Board^elem(2, 0)::out) is semidet), yes(3), "^elem get: 2,0", !IO), assert_equals( ((func) = (Board^elem(0, 1)::out) is semidet), yes(4), "^elem get: 0,1", !IO), assert_equals( ((func) = (Board^elem(2, 1)::out) is semidet), yes(6), "^elem get: 2,1", !IO), assert_equals( ((func) = (Board^elem(2, 2)::out) is semidet), yes(9), "^elem get: 2,2", !IO). :- pred test_board_elem_set(io.state::di, io.state::uo) is det. test_board_elem_set(!IO) :- Squares = [no, no, no, no], Board = board(Squares, 2, 2), DesiredBoard0x0 = board([yes(1), no, no, no], 2, 2), assert_equals( ((func) = (Board^elem(0, 0) := yes(1)::out) is semidet), DesiredBoard0x0, "^elem set: 0, 0", !IO), DesiredBoard1x0 = board([no, yes(1), no, no], 2, 2), assert_equals( ((func) = (Board^elem(1, 0) := yes(1)::out) is semidet), DesiredBoard1x0, "^elem set: 1, 0", !IO), DesiredBoard0x1 = board([no, no, yes(1), no], 2, 2), assert_equals( ((func) = (Board^elem(0, 1) := yes(1)::out) is semidet), DesiredBoard0x1, "^elem set: 0, 1", !IO), DesiredBoard1x1 = board([no, no, no, yes(1)], 2, 2), assert_equals( ((func) = (Board^elem(1, 1) := yes(1)::out) is semidet), DesiredBoard1x1, "^elem set: 1, 1", !IO). :- pred test_in_bounds(io.state::di, io.state::uo) is det. test_in_bounds(!IO) :- Squares = [no, no, no, no, no, no], Board = board(Squares, 3, 2), assert_fail( ((pred) is semidet :- in_bounds(Board, 1, 3) ), "in_bounds: 1, 3", !IO), assert_fail( ((pred) is semidet :- in_bounds(Board, 1, 2) ), "in_bounds: 1, 2", !IO), assert_fail( ((pred) is semidet :- in_bounds(Board, 3, 1) ), "in_bounds: 3, 1", !IO), assert_pass( ((pred) is semidet :- in_bounds(Board, 1, 1) ), "in_bounds: 1, 1", !IO), assert_pass( ((pred) is semidet :- in_bounds(Board, 0, 0) ), "in_bounds: 0, 0", !IO), assert_pass( ((pred) is semidet :- in_bounds(Board, 2, 1) ), "in_bounds: 2, 1", !IO). :- pred test_north(io.state::di, io.state::uo) is det. test_north(!IO) :- Squares = [yes(1), yes(2), yes(3), yes(4), yes(5), yes(6), yes(7), yes(8), yes(9)], Board = board(Squares, 3, 3), % use currying to produce a pred with only one output assert_pred_equals(north(Board, 1, 1), yes(2), "north: 1, 1", !IO), assert_pred_equals(north(Board, 0, 2), yes(4), "north: 0, 2", !IO), assert_fail( ((pred) is semidet :- north(Board, 0, 0, _) ), "north: 0, 0", !IO). :- pred test_neighbor_has_value(io.state::di, io.state::uo) is det. test_neighbor_has_value(!IO) :- Squares = [yes(1), yes(2), yes(3), yes(4), yes(5), yes(6), yes(7), yes(8), yes(9)], Board = board(Squares, 3, 3), assert_pass( ((pred) is semidet :- neighbor_has_value(Board, 0, 0, 4) ), "neighbor: 0, 0 = 4", !IO), assert_pass( ((pred) is semidet :- neighbor_has_value(Board, 0, 0, 2) ), "neighbor: 0, 0 = 2", !IO), assert_fail( ((pred) is semidet :- neighbor_has_value(Board, 0, 0, 5) ), "neighbor: 0, 0 != 5", !IO), assert_pass( ((pred) is semidet :- neighbor_has_value(Board, 2, 1, 3) ), "neighbor: 2, 1 = 3", !IO), assert_pass( ((pred) is semidet :- neighbor_has_value(Board, 2, 1, 5) ), "neighbor: 2, 1 = 5", !IO), assert_pass( ((pred) is semidet :- neighbor_has_value(Board, 2, 1, 9) ), "neighbor: 2, 1 = 9", !IO), assert_fail( ((pred) is semidet :- neighbor_has_value(Board, 2, 1, 4) ), "neighbor: 2, 1 != 4", !IO), assert_fail( ((pred) is semidet :- neighbor_has_value(Board, 2, 1, 7) ), "neighbor: 2, 1 != 7", !IO). :- pred test_max_value(io.state::di, io.state::uo) is det. test_max_value(!IO) :- Squares = [yes(1), yes(2), yes(3), yes(4), yes(5), yes(6), yes(7), yes(8), yes(9)], Board = board(Squares, 3, 3), assert_pred_equals(max_value(Board), 9, "max value", !IO). :- pred test_square_can_have_value(io.state::di, io.state::uo) is det. test_square_can_have_value(!IO) :- Squares = [yes(1), no, yes(3), no, no, yes(6), yes(7), no, yes(9)], Board = board(Squares, 3, 3), assert_pass( ((pred) is semidet :- square_can_have_value(Board, 1, 0, 8)), "can_have_value: 1, 0 = 8", !IO), assert_pass( ((pred) is semidet :- square_can_have_value(Board, 2, 2, 8)), "can_have_value: 2, 2 = 8", !IO), assert_fail( ((pred) is semidet :- square_can_have_value(Board, 0, 1, 2)), "can_have_value: 0, 1 != 2", !IO), assert_fail( ((pred) is semidet :- square_can_have_value(Board, 1, 2, 8)), "can_have_value: 1, 2 != 8", !IO). :- pred run_tests(io.state::di, io.state::uo) is det. run_tests(!IO) :- test_nth(!IO), test_replace_nth_item(!IO), test_board_elem_get(!IO), test_board_elem_set(!IO), test_in_bounds(!IO), test_north(!IO), test_neighbor_has_value(!IO), test_max_value(!IO), test_square_can_have_value(!IO). main(!IO) :- % skip tests when debugging (they all pass, anyways...) %run_tests(!IO), Board = board([yes(3), no, no, no, no, no, no, no, no], 3, 3), Values = [1, 2, 4, 5, 6, 7, 8, 9], % no 3; that's on the board already (if solve_2(Board, Values, _) then io__write_string("There is a solution!\n", !IO) else io__write_string("No solution :-( \n", !IO) ).