Mercurial > repos > other > SevenLanguagesInSevenWeeks

annotate 3-Prolog/day3-sudoku.pl @ 68:b4f994693f7b

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Fix condition check that was letting it backtrack to build a different set of rows
author IBBoard <dev@ibboard.co.uk>
date Sat, 07 Oct 2017 15:43:52 +0100
parents 8906b5a4517f
children
Ignore whitespace changes - Everywhere: Within whitespace: At end of lines:
rev   line source
66
2acc1ad8d365 Add half-completed sudoku solver
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
1 % Create a generic sudoku reader
2acc1ad8d365 Add half-completed sudoku solver
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
2
2acc1ad8d365 Add half-completed sudoku solver
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
3 valid([]).
2acc1ad8d365 Add half-completed sudoku solver
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
4 valid([Head|Tail]) :-
2acc1ad8d365 Add half-completed sudoku solver
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
5 fd_all_different(Head),
2acc1ad8d365 Add half-completed sudoku solver
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
6 valid(Tail).
2acc1ad8d365 Add half-completed sudoku solver
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
7
2acc1ad8d365 Add half-completed sudoku solver
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
8 sudoku(Board, X, Y, Solution) :-
2acc1ad8d365 Add half-completed sudoku solver
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
9 Solution = Board,
2acc1ad8d365 Add half-completed sudoku solver
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
10 Max is X * Y,
2acc1ad8d365 Add half-completed sudoku solver
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
11 fd_domain(Solution, 1, Max),
2acc1ad8d365 Add half-completed sudoku solver
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
12 board(X, Y, Board),
2acc1ad8d365 Add half-completed sudoku solver
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
13 rows(Board, Max, Rows),
2acc1ad8d365 Add half-completed sudoku solver
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
14 cols(Board, Max, Cols),
67
8906b5a4517f Calculate and validate boxes
IBBoard <dev@ibboard.co.uk>
parents: 66
diff changeset
15 boxes(Board, X, Y, Boxes),
66
2acc1ad8d365 Add half-completed sudoku solver
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
16 valid(Rows),
67
8906b5a4517f Calculate and validate boxes
IBBoard <dev@ibboard.co.uk>
parents: 66
diff changeset
17 valid(Cols),
8906b5a4517f Calculate and validate boxes
IBBoard <dev@ibboard.co.uk>
parents: 66
diff changeset
18 valid(Boxes).
66
2acc1ad8d365 Add half-completed sudoku solver
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
19
2acc1ad8d365 Add half-completed sudoku solver
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
20 board(X, Y, Board) :-
67
8906b5a4517f Calculate and validate boxes
IBBoard <dev@ibboard.co.uk>
parents: 66
diff changeset
21 % Y * X boxes of size X * Y
8906b5a4517f Calculate and validate boxes
IBBoard <dev@ibboard.co.uk>
parents: 66
diff changeset
22 Size is (Y * X) * (X * Y),
66
2acc1ad8d365 Add half-completed sudoku solver
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
23 board(Size, Board).
2acc1ad8d365 Add half-completed sudoku solver
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
24 board(1, [_]).
2acc1ad8d365 Add half-completed sudoku solver
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
25 board(Size, [_|Board]) :- SmallerSize is Size - 1, board(SmallerSize, Board).
2acc1ad8d365 Add half-completed sudoku solver
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
26
2acc1ad8d365 Add half-completed sudoku solver
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
27 sublist(Start, Length, Input, Output) :- End is Start + Length - 1, sublist(Start, End, 1, Input, Output).
2acc1ad8d365 Add half-completed sudoku solver
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
28 sublist(Start, End, Pos, [Head|TailIn], [Head|TailOut]) :- Pos >= Start, Pos =< End, NextPos is Pos + 1, sublist(Start, End, NextPos, TailIn, TailOut).
2acc1ad8d365 Add half-completed sudoku solver
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
29 sublist(Start, End, Pos, [_|TailIn], Output) :- Pos < Start, NextPos is Pos + 1, sublist(Start, End, NextPos, TailIn, Output).
2acc1ad8d365 Add half-completed sudoku solver
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
30 sublist(_, End, Pos, _, []) :- Pos > End.
2acc1ad8d365 Add half-completed sudoku solver
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
31
2acc1ad8d365 Add half-completed sudoku solver
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
32 rows(Board, RowLength, Rows) :- rows(Board, RowLength, 1, Rows).
2acc1ad8d365 Add half-completed sudoku solver
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
33 rows(Board, RowLength, RowNum, [NewRow|Rows]) :- RowNum =< RowLength, NextRowNum is RowNum + 1,
2acc1ad8d365 Add half-completed sudoku solver
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
34 Start is ((RowNum - 1) * RowLength) + 1, sublist(Start, RowLength, Board, NewRow),
2acc1ad8d365 Add half-completed sudoku solver
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
35 rows(Board, RowLength, NextRowNum, Rows).
2acc1ad8d365 Add half-completed sudoku solver
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
36 rows(_, RowLength, RowNum, []) :- RowNum > RowLength.
2acc1ad8d365 Add half-completed sudoku solver
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
37
2acc1ad8d365 Add half-completed sudoku solver
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
38 nth_from_list(Start, N, Input, Output) :- nth_from_list(N, Start, 1, Input, Output).
2acc1ad8d365 Add half-completed sudoku solver
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
39 nth_from_list(N, Next, Pos, [Head|TailIn], [Head|TailOut]) :- Pos == Next, NewNext is Next + N, NewPos is Pos + 1,
2acc1ad8d365 Add half-completed sudoku solver
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
40 nth_from_list(N, NewNext, NewPos, TailIn, TailOut).
68
b4f994693f7b Fix condition check that was letting it backtrack to build a different set of rows
IBBoard <dev@ibboard.co.uk>
parents: 67
diff changeset
41 nth_from_list(N, Next, Pos, [_|TailIn], Output) :- Pos < Next, NewPos is Pos + 1, nth_from_list(N, Next, NewPos, TailIn, Output).
66
2acc1ad8d365 Add half-completed sudoku solver
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
42 nth_from_list(_, _, _, [], []).
2acc1ad8d365 Add half-completed sudoku solver
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
43
2acc1ad8d365 Add half-completed sudoku solver
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
44 cols(Board, ColLength, Cols) :- cols(Board, ColLength, 1, Cols).
2acc1ad8d365 Add half-completed sudoku solver
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
45 cols(Board, ColLength, ColNum, [NewCol|Cols]) :- ColNum =< ColLength, NextColNum is ColNum + 1,
2acc1ad8d365 Add half-completed sudoku solver
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
46 nth_from_list(ColNum, ColLength, Board, NewCol),
2acc1ad8d365 Add half-completed sudoku solver
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
47 cols(Board, ColLength, NextColNum, Cols).
67
8906b5a4517f Calculate and validate boxes
IBBoard <dev@ibboard.co.uk>
parents: 66
diff changeset
48 cols(_, ColLength, ColNum, []) :- ColNum > ColLength.
8906b5a4517f Calculate and validate boxes
IBBoard <dev@ibboard.co.uk>
parents: 66
diff changeset
49
8906b5a4517f Calculate and validate boxes
IBBoard <dev@ibboard.co.uk>
parents: 66
diff changeset
50 in_box(BoxX, BoxY, MaxBoxWidth, MaxBoxHeight, PosX, PosY) :-
8906b5a4517f Calculate and validate boxes
IBBoard <dev@ibboard.co.uk>
parents: 66
diff changeset
51 PosX >= BoxX * MaxBoxWidth, PosX < (BoxX + 1) * MaxBoxWidth,
8906b5a4517f Calculate and validate boxes
IBBoard <dev@ibboard.co.uk>
parents: 66
diff changeset
52 PosY >= BoxY * MaxBoxHeight, PosY < (BoxY + 1) * MaxBoxHeight.
8906b5a4517f Calculate and validate boxes
IBBoard <dev@ibboard.co.uk>
parents: 66
diff changeset
53
8906b5a4517f Calculate and validate boxes
IBBoard <dev@ibboard.co.uk>
parents: 66
diff changeset
54 box(_, _, _, MaxBoxWidth, MaxBoxHeight, _, PosY, []) :- PosY >= MaxBoxWidth * MaxBoxHeight.
8906b5a4517f Calculate and validate boxes
IBBoard <dev@ibboard.co.uk>
parents: 66
diff changeset
55 box([Head|Tail], BoxX, BoxY, MaxBoxWidth, MaxBoxHeight, PosX, PosY, [Head|Box]) :-
8906b5a4517f Calculate and validate boxes
IBBoard <dev@ibboard.co.uk>
parents: 66
diff changeset
56 in_box(BoxX, BoxY, MaxBoxWidth, MaxBoxHeight, PosX, PosY),
8906b5a4517f Calculate and validate boxes
IBBoard <dev@ibboard.co.uk>
parents: 66
diff changeset
57 PosX < (MaxBoxWidth * MaxBoxHeight) - 1, NextX is PosX + 1,
8906b5a4517f Calculate and validate boxes
IBBoard <dev@ibboard.co.uk>
parents: 66
diff changeset
58 box(Tail, BoxX, BoxY, MaxBoxWidth, MaxBoxHeight, NextX, PosY, Box).
8906b5a4517f Calculate and validate boxes
IBBoard <dev@ibboard.co.uk>
parents: 66
diff changeset
59 box([Head|Tail], BoxX, BoxY, MaxBoxWidth, MaxBoxHeight, PosX, PosY, [Head|Box]) :-
8906b5a4517f Calculate and validate boxes
IBBoard <dev@ibboard.co.uk>
parents: 66
diff changeset
60 in_box(BoxX, BoxY, MaxBoxWidth, MaxBoxHeight, PosX, PosY),
8906b5a4517f Calculate and validate boxes
IBBoard <dev@ibboard.co.uk>
parents: 66
diff changeset
61 PosX >= (MaxBoxWidth * MaxBoxHeight) - 1, NextX is 0, NextY is PosY + 1,
8906b5a4517f Calculate and validate boxes
IBBoard <dev@ibboard.co.uk>
parents: 66
diff changeset
62 box(Tail, BoxX, BoxY, MaxBoxWidth, MaxBoxHeight, NextX, NextY, Box).
8906b5a4517f Calculate and validate boxes
IBBoard <dev@ibboard.co.uk>
parents: 66
diff changeset
63 box([_|Tail], BoxX, BoxY, MaxBoxWidth, MaxBoxHeight, PosX, PosY, Box) :-
8906b5a4517f Calculate and validate boxes
IBBoard <dev@ibboard.co.uk>
parents: 66
diff changeset
64 \+ in_box(BoxX, BoxY, MaxBoxWidth, MaxBoxHeight, PosX, PosY), PosX < (MaxBoxWidth * MaxBoxHeight) - 1, NextX is PosX + 1, box(Tail, BoxX, BoxY, MaxBoxWidth, MaxBoxHeight, NextX, PosY, Box).
8906b5a4517f Calculate and validate boxes
IBBoard <dev@ibboard.co.uk>
parents: 66
diff changeset
65 box([_|Tail], BoxX, BoxY, MaxBoxWidth, MaxBoxHeight, PosX, PosY, Box) :-
8906b5a4517f Calculate and validate boxes
IBBoard <dev@ibboard.co.uk>
parents: 66
diff changeset
66 \+ in_box(BoxX, BoxY, MaxBoxWidth, MaxBoxHeight, PosX, PosY), PosX >= (MaxBoxWidth * MaxBoxHeight) - 1, NextX is 0, NextY is PosY + 1, box(Tail, BoxX, BoxY, MaxBoxWidth, MaxBoxHeight, NextX, NextY, Box).
8906b5a4517f Calculate and validate boxes
IBBoard <dev@ibboard.co.uk>
parents: 66
diff changeset
67
8906b5a4517f Calculate and validate boxes
IBBoard <dev@ibboard.co.uk>
parents: 66
diff changeset
68 boxes(Board, BoxWidth, BoxHeight, Boxes) :- boxes(Board, BoxWidth, BoxHeight, 0, 0, Boxes).
8906b5a4517f Calculate and validate boxes
IBBoard <dev@ibboard.co.uk>
parents: 66
diff changeset
69 boxes(_, MaxBoxY, MaxBoxX, BoxX, BoxY, []) :- BoxY >= MaxBoxY.
8906b5a4517f Calculate and validate boxes
IBBoard <dev@ibboard.co.uk>
parents: 66
diff changeset
70 boxes(Board, MaxBoxY, MaxBoxX, BoxX, BoxY, [Box|Boxes]) :- BoxX < (MaxBoxX - 1), BoxY < MaxBoxY, box(Board, BoxX, BoxY, MaxBoxY, MaxBoxX, 0, 0, Box), NextX is BoxX + 1, boxes(Board, MaxBoxY, MaxBoxX, NextX, BoxY, Boxes).
8906b5a4517f Calculate and validate boxes
IBBoard <dev@ibboard.co.uk>
parents: 66
diff changeset
71 boxes(Board, MaxBoxY, MaxBoxX, BoxX, BoxY, [Box|Boxes]) :- BoxX >= (MaxBoxX - 1), BoxY < MaxBoxY, box(Board, BoxX, BoxY, MaxBoxY, MaxBoxX, 0, 0, Box), NextY is BoxY + 1, boxes(Board, MaxBoxY, MaxBoxX, 0, NextY, Boxes).