-
Notifications
You must be signed in to change notification settings - Fork 0
/
Sudoku.prolog
executable file
·86 lines (75 loc) · 3.09 KB
/
Sudoku.prolog
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
/* Sudoku.prolog uses constraint logic programming within finite domains
to solve an incomplete sudoku board by apply sudoku rules as constraints*/
:- use_module(library(clpfd)).
/* Applies sudoku rules to a given 9x9 matrix */
sudoku(RowBoard):-
%Determines the the board for easy use with domain constraints
flatten(RowBoard, FlatBoard),
%Applies constraint to FlatBoard, and thus its related RowBoard,
%that all values must be between 1 and 9
FlatBoard ins 1..9,
%Constrains all members of the rows to be different from each other
constrainListDifferent(RowBoard).
%Constrains all members of the columns to be different from each other
transpose(RowBoard,ColBoard),
constrainListDifferent(ColBoard).
%Substitute variables for all members of the row board so that boxes may be defined
RowBoard = [[X11,X12,X13,X14,X15,X16,X17,X18,X19],
[X21,X22,X23,X24,X25,X26,X27,X28,X29],
[X31,X32,X33,X34,X35,X36,X37,X38,X39],
[X41,X42,X43,X44,X45,X46,X47,X48,X49],
[X51,X52,X53,X54,X55,X56,X57,X58,X59],
[X61,X62,X63,X64,X65,X66,X67,X68,X69],
[X71,X72,X73,X74,X75,X76,X77,X78,X79],
[X81,X82,X83,X84,X85,X86,X87,X88,X89],
[X91,X92,X93,X94,X95,X96,X97,X98,X99]],
%Constrain all members of the boxes to be different from each other
all_different([X11,X12,X13,X21,X22,X23,X31,X32,X33]),
all_different([X41,X42,X43,X51,X52,X53,X61,X62,X63]),
all_different([X71,X72,X73,X81,X82,X83,X91,X92,X93]),
all_different([X14,X15,X16,X24,X25,X26,X34,X35,X36]),
all_different([X44,X45,X46,X54,X55,X56,X64,X65,X66]),
all_different([X74,X75,X76,X84,X85,X86,X94,X95,X96]),
all_different([X17,X18,X19,X27,X28,X29,X37,X38,X39]),
all_different([X47,X48,X49,X57,X58,X59,X67,X68,X69]),
all_different([X77,X78,X79,X87,X88,X89,X97,X98,X99]),
%Tries to unify all elements of the FlatBoard with its domain based
%on the previously defined constraints.
label(FlatBoard).
/* Applies the all different constraint to every list in a list of lists */
constrainListDifferent([]).
constrainListDifferent([H|Tl]):-
all_different(H), constrainListDifferent(Tl).
/* Takes the rows of a matrix and makes them the columns of a new matrix.
In sudoku, this makes comparison against the columns quick and painless */
transpose([Lst], Cols) :- !,
listToCol(Lst, Cols).
transpose([H|Tl], Cs) :- !,
transpose(Tl, Cs0),
putCols(H, Cs0, Cs).
/* listToCol takes a list and puts its elements in the columns of a matrix
This is a helper method for transpose/2 */
listToCol([], []).
listToCol([X|Xs], [[X]|Zs]) :- listToCol(Xs, Zs).
/* putCols puts a given list into the head of the columns of a matrix.
This is a helper method for transpose/2 */
putCols([], Cs, Cs).
putCols([X|Xs], [C|Cs0], [[X|C]|Cs]) :-
putCols(Xs, Cs0, Cs).
/* renamed from printMatrix */
printSudoku([]).
printSudoku([H|Tl]) :-
write(H),nl,
printSudoku(Tl).
testSudoku :-
Sud=[[_,6,_,1,_,4,_,5,_],
[_,_,8,3,_,5,6,_,_],
[2,_,_,_,_,_,_,_,1],
[8,_,_,4,_,7,_,_,6],
[_,_,6,_,_,_,3,_,_],
[7,_,_,9,_,1,_,_,4],
[5,_,_,_,_,_,_,_,2],
[_,_,7,2,_,6,9,_,_],
[_,4,_,5,_,8,_,7,_]],
sudoku(Sud),
printSudoku(Sud).