Forrest Sheng Bao <http://forrest.bao.googlepages.com>There are two kind of programming languages. One is the algorithmic language, like C++ or Java. We tell algorithms to a computer by programming. Another one is the declarative language, like SQL or Prolog. We just tell the computer what we have and what we want. Then the computer will return what we want. DLV is a system to find answer set defined by A-Prolog.
The Sudoku problem is the one on its Wikipedia page:http://en.wikipedia.org/wiki/Sudoku
node(5,1,1,1).
node(3,1,2,1).
node(6,2,1,1).
node(9,3,2,1).
node(8,3,3,1).
node(7,1,5,2).
node(1,2,4,2).
node(9,2,5,2).
node(5,2,6,2).
node(6,3,8,3).
node(8,4,1,4).
node(4,5,1,4).
node(7,6,1,4).
node(6,4,5,5).
node(8,5,4,5).
node(3,5,6,5).
node(2,6,5,5).
node(3,4,9,6).
node(1,5,9,6).
node(6,6,9,6).
node(6,7,2,7).
node(4,8,4,8).
node(1,8,5,8).
node(9,8,6,8).
node(8,9,5,8).
node(2,7,7,9).
node(8,7,8,9).
node(5,8,9,5).
node(7,9,8,9).
node(9,9,9,9).
%coordinante(row, column, block)
coordinate(1,1,1).
coordinate(1,2,1).
coordinate(1,3,1).
coordinate(2,1,1).
coordinate(2,2,1).
coordinate(2,3,1).
coordinate(3,1,1).
coordinate(3,2,1).
coordinate(3,3,1).
coordinate(1,4,2).
coordinate(1,5,2).
coordinate(1,6,2).
coordinate(2,4,2).
coordinate(2,5,2).
coordinate(2,6,2).
coordinate(3,4,2).
coordinate(3,5,2).
coordinate(3,6,2).
coordinate(1,7,3).
coordinate(1,8,3).
coordinate(1,9,3).
coordinate(2,7,3).
coordinate(2,8,3).
coordinate(2,9,3).
coordinate(3,7,3).
coordinate(3,8,3).
coordinate(3,9,3).
coordinate(4,1,4).
coordinate(4,2,4).
coordinate(4,3,4).
coordinate(5,1,4).
coordinate(5,2,4).
coordinate(5,3,4).
coordinate(6,1,4).
coordinate(6,2,4).
coordinate(6,3,4).
coordinate(4,4,5).
coordinate(4,5,5).
coordinate(4,6,5).
coordinate(5,4,5).
coordinate(5,5,5).
coordinate(5,6,5).
coordinate(6,4,5).
coordinate(6,5,5).
coordinate(6,6,5).
coordinate(4,7,6).
coordinate(4,8,6).
coordinate(4,9,6).
coordinate(5,7,6).
coordinate(5,8,6).
coordinate(5,9,6).
coordinate(6,7,6).
coordinate(6,8,6).
coordinate(6,9,6).
coordinate(7,1,7).
coordinate(7,2,7).
coordinate(7,3,7).
coordinate(8,1,7).
coordinate(8,2,7).
coordinate(8,3,7).
coordinate(9,1,7).
coordinate(9,2,7).
coordinate(9,3,7).
coordinate(7,4,8).
coordinate(7,5,8).
coordinate(7,6,8).
coordinate(8,4,8).
coordinate(8,5,8).
coordinate(8,6,8).
coordinate(9,4,8).
coordinate(9,5,8).
coordinate(9,6,8).
coordinate(7,7,9).
coordinate(7,8,9).
coordinate(7,9,9).
coordinate(8,7,9).
coordinate(8,8,9).
coordinate(8,9,9).
coordinate(9,7,9).
coordinate(9,8,9).
coordinate(9,9,9).
%node(value,X,Y,Block)
node(1,X,Y,B) v node(2,X,Y,B) v node(3,X,Y,B) v node(4,X,Y,B) v node(5,X,Y,B) v node(6,X,Y,B) v node(7,X,Y,B) v node(8,X,Y,B) v node(9,X,Y,B) :- coordinate(X,Y,B).
%uniqueness in colomn
:-node(CommonValue,X1,Y1,B1),node(CommonValue,X2,Y2,B2),X1!=X2,Y1=Y2,coordinate(X1,Y1,B1),coordinate(X2,Y2,B2).
%uniqueness in row
:-node(CommonValue,X1,Y1,B1),node(CommonValue,X2,Y2,B2),X1=X2,Y1!=Y2,coordinate(X1,Y1,B1),coordinate(X2,Y2,B2).
%uniqueness in block
:-node(CommonValue,X1,Y1,CommonBlock),node(CommonValue,X2,Y2,CommonBlock),X1!=X2, Y1!=Y2, coordinate(X1,Y1,CommonBlock),coordinate(X2,Y2,CommonBlock).
Here is the output
DLV [build BEN/Jul 14 2006 gcc 3.4.4 20050314 (prerelease) (Debian 3.4.3-13)]
{node(1,2,4,2), node(1,5,9,6), node(1,8,5,8), node(2,6,5,5), node(2,7,7,9), node(3,1,2,1), node(3,4,9,6), node(3,5,6,5), node(4,5,1,4), node(4,8,4,8), node(5,1,1,1), node(5,2,6,2), node(5,8,9,5), node(6,2,1,1), node(6,3,8,3), node(6,4,5,5), node(6,6,9,6), node(6,7,2,7), node(7,1,5,2), node(7,6,1,4), node(7,9,8,9), node(8,3,3,1), node(8,4,1,4), node(8,5,4,5), node(8,7,8,9), node(8,9,5,8), node(9,2,5,2), node(9,3,2,1), node(9,8,6,8), node(9,9,9,9), node(4,1,3,1), node(6,1,4,2), node(8,1,6,2), node(9,1,7,3), node(1,1,8,3), node(2,1,9,3), node(7,2,2,1), node(2,2,3,1), node(3,2,7,3), node(4,2,8,3), node(8,2,9,3), node(1,3,1,1), node(3,3,4,2), node(4,3,5,2), node(2,3,6,2), node(5,3,7,3), node(7,3,9,3), node(5,4,2,4), node(9,4,3,4), node(7,4,4,5), node(1,4,6,5), node(4,4,7,6), node(2,4,8,6), node(2,5,2,4), node(6,5,3,4), node(5,5,5,5), node(7,5,7,6), node(9,5,8,6), node(1,6,2,4), node(3,6,3,4), node(9,6,4,5), node(4,6,6,5), node(8,6,7,6), node(5,6,8,6), node(9,7,1,7), node(1,7,3,7), node(5,7,4,8), node(3,7,5,8), node(7,7,6,8), node(4,7,9,9), node(2,8,1,7), node(8,8,2,7), node(7,8,3,7), node(6,8,7,9), node(3,8,8,9), node(5,8,9,9), node(3,9,1,7), node(4,9,2,7), node(5,9,3,7), node(2,9,4,8), node(6,9,6,8), node(1,9,7,9)}
No comments:
Post a Comment