Clingo 4.5.1 ASP for Sudoku: Success.....almost

new

« Prev
1
Next »

Lars Ericson
Junior Member

Posts: 67

Clingo 4.5.1 ASP for Sudoku: Success.....almost Sept 1, 2015 5:15:00 GMT -8

Quote

Post by Lars Ericson on Sept 1, 2015 5:15:00 GMT -8

Problem was I didn't have T in row, col, square predicates:

#const steps = 51.

time(1..steps).

digit(1..9).

index(1..3).

filler(b).

1{ does(M,T) : input(M) }1 :- time(T), legal(M,T), 1 <= T, T <= steps-1.

filler(X) :- time(T), digit(X).

base(cell(I,J,K,L,X)) :- index(I), index(J), index(K), index(L), filler(X).

input(mark(I,J,K,L,X)) :- index(I), index(J), index(K), index(L), digit(X).

row(K,L,X,T) :- time(T), true(cell(1..3,1..3,K,L,X),T).

col(I,J,X,T) :- time(T), true(cell(I,J,1..3,1..3,X),T).

square(I,K,X,T) :- time(T), true(cell(I,1..3,K,1..3,X),T).

true(cell(I,J,K,L,X),T+1) :- time(T), does(mark(I,J,K,L,X),T).

true(cell(I,J,K,L,X),T+1) :- time(T), true(cell(I,J,K,L,X),T), does(mark(S,T,U,V,Y),T), S!=I.

true(cell(I,J,K,L,X),T+1) :- time(T), true(cell(I,J,K,L,X),T), does(mark(S,T,U,V,Y),T), T!=J.

true(cell(I,J,K,L,X),T+1) :- time(T), true(cell(I,J,K,L,X),T), does(mark(S,T,U,V,Y),T), U!=K.

true(cell(I,J,K,L,X),T+1) :- time(T), true(cell(I,J,K,L,X),T), does(mark(S,T,U,V,Y),T), V!=L.

playable(T) :- time(T), legal(mark(I,J,K,L,X),T).

terminal(T) :- time(T), not playable(T).

open(T) :- time(T), true(cell(I,J,K,L,b),T).

goal(100,T) :- time(T), not open(T).

goal(0,T) :- time(T), open(T).

legal(mark(I,J,K,L,X),T) :- time(T), true(cell(I,J,K,L,b),T), digit(X), not row(K,L,X,T), not col(I,J,X,T), not square(I,K,X,T).

:- not goal(100,steps).

:- does(M,T), not legal(M,T).

true(cell(1,1,1,1,9),1).

true(cell(1,1,1,2,7),1).

true(cell(1,1,1,3,b),1).

true(cell(1,1,2,1,3),1).

true(cell(1,1,2,2,b),1).

true(cell(1,1,2,3,4),1).

true(cell(1,1,3,1,b),1).

true(cell(1,1,3,2,6),1).

true(cell(1,1,3,3,5),1).

true(cell(1,2,1,1,b),1).

true(cell(1,2,1,2,2),1).

true(cell(1,2,1,3,b),1).

true(cell(1,2,2,1,5),1).

true(cell(1,2,2,2,b),1).

true(cell(1,2,2,3,6),1).

true(cell(1,2,3,1,b),1).

true(cell(1,2,3,2,8),1).

true(cell(1,2,3,3,b),1).

true(cell(1,3,1,1,b),1).

true(cell(1,3,1,2,b),1).

true(cell(1,3,1,3,b),1).

true(cell(1,3,2,1,b),1).

true(cell(1,3,2,2,b),1).

true(cell(1,3,2,3,b),1).

true(cell(1,3,3,1,b),1).

true(cell(1,3,3,2,b),1).

true(cell(1,3,3,3,b),1).

true(cell(2,1,1,1,b),1).

true(cell(2,1,1,2,b),1).

true(cell(2,1,1,3,5),1).

true(cell(2,1,2,1,8),1).

true(cell(2,1,2,2,b),1).

true(cell(2,1,2,3,2),1).

true(cell(2,1,3,1,9),1).

true(cell(2,1,3,2,b),1).

true(cell(2,1,3,3,b),1).

true(cell(2,2,1,1,b),1).

true(cell(2,2,1,2,b),1).

true(cell(2,2,1,3,2),1).

true(cell(2,2,2,1,b),1).

true(cell(2,2,2,2,4),1).

true(cell(2,2,2,3,b),1).

true(cell(2,2,3,1,3),1).

true(cell(2,2,3,2,b),1).

true(cell(2,2,3,3,b),1).

true(cell(2,3,1,1,b),1).

true(cell(2,3,1,2,b),1).

true(cell(2,3,1,3,8),1).

true(cell(2,3,2,1,7),1).

true(cell(2,3,2,2,b),1).

true(cell(2,3,2,3,5),1).

true(cell(2,3,3,1,1),1).

true(cell(2,3,3,2,b),1).

true(cell(2,3,3,3,b),1).

true(cell(3,1,1,1,b),1).

true(cell(3,1,1,2,b),1).

true(cell(3,1,1,3,b),1).

true(cell(3,1,2,1,b),1).

true(cell(3,1,2,2,b),1).

true(cell(3,1,2,3,b),1).

true(cell(3,1,3,1,b),1).

true(cell(3,1,3,2,b),1).

true(cell(3,1,3,3,b),1).

true(cell(3,2,1,1,b),1).

true(cell(3,2,1,2,6),1).

true(cell(3,2,1,3,b),1).

true(cell(3,2,2,1,2),1).

true(cell(3,2,2,2,b),1).

true(cell(3,2,2,3,8),1).

true(cell(3,2,3,1,b),1).

true(cell(3,2,3,2,3),1).

true(cell(3,2,3,3,b),1).

true(cell(3,3,1,1,8),1).

true(cell(3,3,1,2,4),1).

true(cell(3,3,1,3,b),1).

true(cell(3,3,2,1,1),1).

true(cell(3,3,2,2,b),1).

true(cell(3,3,2,3,9),1).

true(cell(3,3,3,1,b),1).

true(cell(3,3,3,2,2),1).

true(cell(3,3,3,3,7),1).

#show does/2.

#show goal/2.

Solution: On Intel core i5-2320 running 3GHz:

clingo version 4.5.1

Reading from bar1.lp

Solving...

Answer: 1

does(mark(1,1,1,3,1),1) does(mark(1,1,2,2,1),1) does(mark(1,1,2,2,2),1) does(mark(1,1,2,2,8),1) does(mark(1,1,3,1,2),1) does(mark(2,1,1,1,1),1) does(mark(2,1,1,1,3),1) does(mark(2,1,1,1,4),1) does(mark(2,1,1,1,6),1) does(mark(2,1,1,1,7),1) does(mark(2,1,1,2,1),1) does(mark(2,1,1,2,3),1) does(mark(2,1,2,2,1),1) does(mark(2,1,2,2,3),1) does(mark(2,1,2,2,6),1) does(mark(2,1,3,2,4),1) does(mark(2,1,3,2,7),1) does(mark(2,1,3,3,4),1) does(mark(2,1,3,3,6),1) does(mark(3,1,1,1,1),1) does(mark(3,1,1,1,2),1) does(mark(3,1,1,1,3),1) does(mark(3,1,1,1,5),1) does(mark(3,1,1,1,7),1) does(mark(3,1,1,2,1),1) does(mark(3,1,1,2,3),1) does(mark(3,1,1,2,5),1) does(mark(3,1,1,2,9),1) does(mark(3,1,1,3,1),1) does(mark(3,1,1,3,3),1) does(mark(3,1,1,3,7),1) does(mark(3,1,1,3,9),1) does(mark(3,1,2,1,4),1) does(mark(3,1,2,1,6),1) does(mark(3,1,2,2,3),1) does(mark(3,1,2,2,5),1) does(mark(3,1,2,2,6),1) does(mark(3,1,2,2,7),1) does(mark(3,1,2,3,3),1) does(mark(3,1,2,3,7),1) does(mark(3,1,3,1,4),1) does(mark(3,1,3,1,5),1) does(mark(3,1,3,1,6),1) does(mark(3,1,3,1,8),1) does(mark(3,1,3,2,1),1) does(mark(3,1,3,2,4),1) does(mark(3,1,3,2,5),1) does(mark(3,1,3,2,9),1) does(mark(3,1,3,3,1),1) does(mark(3,1,3,3,4),1) does(mark(3,1,3,3,6),1) does(mark(3,1,3,3,8),1) does(mark(3,1,3,3,9),1) does(mark(1,2,1,1,1),1) does(mark(1,2,1,1,3),1) does(mark(1,2,1,1,4),1) does(mark(1,2,1,3,1),1) does(mark(1,2,1,3,3),1) does(mark(1,2,1,3,4),1) does(mark(1,2,2,2,1),1) does(mark(1,2,2,2,7),1) does(mark(1,2,2,2,9),1) does(mark(1,2,3,1,4),1) does(mark(1,2,3,1,7),1) does(mark(1,2,3,3,1),1) does(mark(1,2,3,3,3),1) does(mark(1,2,3,3,4),1) does(mark(1,2,3,3,9),1) does(mark(1,3,1,1,1),1) does(mark(1,3,1,1,3),1) does(mark(1,3,1,1,4),1) does(mark(1,3,1,1,5),1) does(mark(1,3,1,1,6),1) does(mark(1,3,1,2,1),1) does(mark(1,3,1,2,3),1) does(mark(1,3,1,2,5),1) does(mark(1,3,1,2,8),1) does(mark(1,3,1,3,1),1) does(mark(1,3,1,3,3),1) does(mark(1,3,1,3,4),1) does(mark(1,3,1,3,6),1) does(mark(1,3,2,1,9),1) does(mark(1,3,2,2,1),1) does(mark(1,3,2,2,2),1) does(mark(1,3,2,2,7),1) does(mark(1,3,2,2,8),1) does(mark(1,3,2,2,9),1) does(mark(1,3,2,3,1),1) does(mark(1,3,2,3,7),1) does(mark(1,3,3,1,2),1) does(mark(1,3,3,1,4),1) does(mark(1,3,3,1,7),1) does(mark(1,3,3,2,1),1) does(mark(1,3,3,2,4),1) does(mark(1,3,3,2,7),1) does(mark(1,3,3,2,9),1) does(mark(1,3,3,3,1),1) does(mark(1,3,3,3,2),1) does(mark(1,3,3,3,3),1) does(mark(1,3,3,3,4),1) does(mark(1,3,3,3,9),1) does(mark(2,2,1,1,1),1) does(mark(2,2,1,1,6),1) does(mark(2,2,1,1,7),1) does(mark(2,2,1,2,1),1) does(mark(2,2,1,2,9),1) does(mark(2,2,2,1,6),1) does(mark(2,2,2,1,9),1) does(mark(2,2,2,3,1),1) does(mark(2,2,3,2,5),1) does(mark(2,2,3,2,7),1) does(mark(2,2,3,3,6),1) does(mark(2,2,3,3,8),1) does(mark(2,3,1,1,3),1) does(mark(2,3,1,1,4),1) does(mark(2,3,1,1,6),1) does(mark(2,3,1,2,3),1) does(mark(2,3,1,2,9),1) does(mark(2,3,2,2,3),1) does(mark(2,3,2,2,6),1) does(mark(2,3,2,2,9),1) does(mark(2,3,3,2,4),1) does(mark(2,3,3,3,2),1) does(mark(2,3,3,3,4),1) does(mark(2,3,3,3,6),1) does(mark(3,2,1,1,1),1) does(mark(3,2,1,1,5),1) does(mark(3,2,1,1,7),1) does(mark(3,2,1,3,1),1) does(mark(3,2,1,3,7),1) does(mark(3,2,1,3,9),1) does(mark(3,2,2,2,5),1) does(mark(3,2,2,2,7),1) does(mark(3,2,3,1,4),1) does(mark(3,2,3,1,5),1) does(mark(3,2,3,3,1),1) does(mark(3,2,3,3,4),1) does(mark(3,2,3,3,9),1) does(mark(3,3,1,3,3),1) does(mark(3,3,2,2,3),1) does(mark(3,3,2,2,5),1) does(mark(3,3,2,2,6),1) does(mark(3,3,3,1,5),1) does(mark(3,3,3,1,6),1) goal(100,3) goal(100,4) goal(100,5) goal(100,6) goal(100,7) goal(100,8) goal(100,9) goal(100,10) goal(100,11) goal(100,12) goal(100,13) goal(100,14) goal(100,15) goal(100,16) goal(100,17) goal(100,18) goal(100,19) goal(100,20) goal(100,21) goal(100,22) goal(100,23) goal(100,24) goal(100,25) goal(100,26) goal(100,27) goal(100,28) goal(100,29) goal(100,30) goal(100,31) goal(100,32) goal(100,33) goal(100,34) goal(100,35) goal(100,36) goal(100,37) goal(100,38) goal(100,39) goal(100,40) goal(100,41) goal(100,42) goal(100,43) goal(100,44) goal(100,45) goal(100,46) goal(100,47) goal(100,48) goal(100,49) goal(100,50) goal(100,51) goal(0,1) goal(0,2)

SATISFIABLE



Models       : 1     

Calls        : 1

Time         : 1.092s (Solving: 0.06s 1st Model: 0.00s Unsat: 0.06s)

CPU Time     : 1.030s

Almost: Looking at the solution, we can see the clock is not advancing, the computer solves the puzzle all at once! I will have to fiddle with the translation a little bit more to make sure that doesn't happen, so stay tuned.

Andrew Rose
Global Moderator

Posts: 100

Clingo 4.5.1 ASP for Sudoku: Success.....almost Sept 1, 2015 7:42:45 GMT -8

Quote

Post by Andrew Rose on Sept 1, 2015 7:42:45 GMT -8

Lars,

I must confess that I haven't been following your various Clingo posts in great detail. However, I was wondering whether you're writing individual specific Clingo programs for each of the existing GGP puzzles or whether you're refining a general program to convert GDL into Clingo (that will hopefully work for any single-player GDL that's thrown at it)?

Andrew

Lars Ericson
Junior Member

Posts: 67

Clingo 4.5.1 ASP for Sudoku: Success.....almost Sept 1, 2015 8:02:25 GMT -8

Quote

Post by Lars Ericson on Sept 1, 2015 8:02:25 GMT -8

Hi Andrew,

I am writing a general program to translate GDL into Clingo. There are a few versions of this in my other posts here so you can get the idea.

I've been hand-tuning the Sudoku one because I was running into a problem which turned out to be when to extend a predicate to time step and when not to. I have one bug left on Sudoku which is to restrict it to one move per time step, somewhere along the line of hand tuning that constraint got lost. It's getting a good solution now but it's doing it in one shot.

My long-term plan is to get the translation good enough that it works on all of the single-player games, then for multiplayer games to fiddle with it to get it to produce as many solutions as possible in 30 seconds or whatever. Then my move generator would pick the move which most solutions use, assuming there are multiple distinct moves produced in solution paths. That's my strategy. It's not that clever, but if you think of game playing as digging a hole, and Clingo as a backhoe, then I'm just switching on the backhoe to dig the hole, without really knowing much about how to build a backhoe myself.

Andrew Rose
Global Moderator

Posts: 100

Clingo 4.5.1 ASP for Sudoku: Success.....almost Sept 1, 2015 13:18:39 GMT -8

Quote

Post by Andrew Rose on Sept 1, 2015 13:18:39 GMT -8

I've got a couple more puzzles on the way (a small Hidato and a slightly larger one) so it'll be interesting to see how your player gets on with them. They've broken Sancho - which managed to build a propnet which didn't correctly express the rules, so that Sancho submits illegal moves! Also, even with a workaround for that problem, Sancho solves the small version in 250ms but can't solve the larger version in 2 mins.

That sounds like a novel approach to 2-player games. It'll be interesting to see how it gets on. Nice to see something other than propnet + MCTS.

Lars Ericson
Junior Member

Posts: 67

Clingo 4.5.1 ASP for Sudoku: Success.....almost Sept 2, 2015 13:45:53 GMT -8

Quote

Post by Lars Ericson on Sept 2, 2015 13:45:53 GMT -8

Actually solution above is incorrect for more than just making multiple moves in one step, it is also making multiple marks of the same cell in one step:

does(mark(1,1,2,2,1),1)
does(mark(1,1,2,2,2),1)

Adding this constraint:

:- does(mark(I,J,K,L,X),T), does(mark(I,J,K,L,Y),T), X!=Y.
causes Clingo to say it is Unsatisfiable. So back to the drawing board. This is tricky! Also separately adding this constraint causes it to fail:

:- does(M,T), does(N,T), M!=N.

Lars Ericson
Junior Member

Posts: 67

Clingo 4.5.1 ASP for Sudoku: Success.....almost Sept 8, 2015 18:52:19 GMT -8

Quote

Post by Lars Ericson on Sept 8, 2015 18:52:19 GMT -8

Here's a better draft of the translator:

from __future__ import division

import sys



### First a LISP parser copied off the Internet from Peter Norvig: ###

Symbol = str # A Lisp Symbol is implemented as a Python str

List = list # A Lisp List is implemented as a Python list

Number = (int, float) # A Lisp Number is implemented as a Python int or float



def parse(program):

    "Read a Scheme expression from a string."

    return read_from_tokens(tokenize(program))



def tokenize(s):

    "Convert a string into a list of tokens."

    return s.replace('(',' ( ').replace(')',' ) ').split()



def atom(token):

    "Numbers become numbers; every other token is a symbol."

    try:

        return int(token)

    except ValueError:

        try:

            return float(token)

        except ValueError:

            return Symbol(token)



def read_from_tokens(tokens):

    "Read an expression from a sequence of tokens."

    if len(tokens) == 0:

        raise SyntaxError('unexpected EOF while reading')

    token = tokens.pop(0)

    if '(' == token:

        L = []

        while tokens[0] != ')':

            L.append(read_from_tokens(tokens))

        tokens.pop(0) # pop off ')'

        return L

    elif ')' == token:

        raise SyntaxError('unexpected )')

    else:

        return atom(token)

### End LISP parser ###



def parse_file(kf):

    with open (kf, "r") as myfile:

        lisp = myfile.readlines()

    program = '('+''.join([x for x in lisp if x[0] != ';']).replace('\n', '')+')'

    gdl = parse(program)

    return gdl



# 3. Replace every other atom p(...) by p(...,T), unless

#  	p is either of the keywords role, base, or input; or

#  	p is a supporting concept that depends on neither true nor does.



def replace_atoms_p_by_p_t_unless(x,unless):

    if x[0] == 'true' and len(x) == 3:

        return x

    elif x[0] in unless:

        return x

    elif x[0] == '<=':

        return ['<=']+[replace_atoms_p_by_p_t_unless(y,unless) for y in x[1:]]

    elif x[0] in ['role', 'base', 'input']:

        return x

    elif x[0] == 'not':

        return ['not', replace_atoms_p_by_p_t_unless(x[1],unless)]

    elif type(x) == type([]):

        return [x[0]]+[replace_atoms_p_by_p_t_unless(y,unless) if type(y)==type([]) else y for y in x[1:]]+['T']

    else:

        return [x, 'T']



# http://logic.stanford.edu/ggp/chapters/chapter_15.html: MRG:

# Given a set of GDL rules, time steps can be incorporated as follows.

#

# 1. Replace init(F) by true(F,0).

# 2. Replace next(F) by true(F,T+1).

# 3. Replace every other atom p(...) by p(...,T), unless

#  	p is either of the keywords role, base, or input; or

#  	p is a supporting concept that depends on neither true nor does.

# 4. Add the condition time(T) to the body of every clause to which variable T has been added.



def rule1(gdl):

    asp = []

    g1 = []

    for x in gdl:

        if x[0] == 'init':

            asp.append(['true']+x[1:]+['0'])

        else:

            g1.append(x)

    return (asp,g1)



def rule2(g1):

    asp = []

    g2 = []

    for x in g1:

        if x[0] == '<=':

            nxt = x[1]

            rest = x[2:]

            if nxt[0] == 'next':

                g2.append(['<=', ['true']+nxt[1:]+['T+1']]+rest)

            elif nxt[0] in ['role', 'base', 'input']:

                asp.append(x)

            else:

                g2.append(x)

        else:

            asp.append(x)

    return (asp,g2)



# 4. Add the condition time(T) to the body of every clause to which variable T has been added.



def add_time_T_to_clauses_containing_T(x):

    for atom in x[1:]:

        if atom[-1] in ['T','T+1']:

            return x+[['time', 'T']]

    return x



def aspify(gdl):

    (asp1,temp1) = rule1(gdl)

    (asp2,temp2) = rule2(temp1)

    unless = set([x[0] for x in asp2 if x[0] != '<=']+

                 [x[1][0] for x in asp1 if x[0] == 'true']+

                 [x[1][2][0] for x in asp2 if (x[0] == '<=' and x[1][0] == 'input')])

    asp = asp1 + asp2

    g3 = [replace_atoms_p_by_p_t_unless(x,unless) for x in temp2]

    g4 = [add_time_T_to_clauses_containing_T(x) for x in g3]

    return asp+g4



def add_tests(gdl):

    return gdl + [':- does(R,M,T), not legal(R,M,T)',                  

                  ':- 0{ terminal(T) : time(T) }',

                  ':- terminal(T), role(%s)' % role,

                  'time(1..%d)' % steps,

                  '1{ does(R,M,T) : input(R,M) }1 :- role(R), time(T), 1 <= T, T <= %d.\n' % (steps-1)]



def kif_to_asp(s):

    if type(s) == type([]):

        try:

            if s[0] == 'distinct':

                 return '%s!=%s' % (kif_to_asp(s[1]), kif_to_asp(s[2]))

            elif s[0] == '<=':

                return kif_to_asp(s[1])+' :- '+', '.join([kif_to_asp(x) for x in s[2:]])

            elif s[0] == 'plus':

                return kif_to_asp(s[1])+'+'+kif_to_asp(s[2])

            elif s[0] == 'not':

                return 'not '+kif_to_asp(s[1])

            else:

                return s[0]+'('+','.join([kif_to_asp(x) for x in s[1:]])+')'

        except:

            return s[0]

    elif type(s)==type('a') and s[0] == '?':

        return s[1:].upper()

    else:

        return str(s)



def p(gdl):

    for i, x in enumerate(gdl):

        print('[%d] %s.' % (i,kif_to_asp(x)))



if __name__ == '__main__':

    root = sys.argv[1]

    steps = int(sys.argv[2])

    role = sys.argv[3]

    goal = int(sys.argv[4])

    kf = root + '.kif'

    lf = root + '_' + role + '.lp'

    gdl = parse_file(kf)

    gdl1 = aspify(gdl)

    with open(lf, 'w') as f:

        for x in gdl1:

            f.write(kif_to_asp(x)+'.\n')

        f.write('1{ does(R,M,T) : input(R,M) }1 :- role(R), time(T), 1 <= T, T <= %d.' % (steps-1))

        f.write(':- does(R,M,T), not legal(R,M,T).')

        f.write(':- 0{ terminal(T) : time(T) }0.')

        f.write(':- terminal(T), role(R), not goal(R,100,T).')

        f.write('time(1..%d).' % steps)

The result for sudoku.kif is still deemed unsatisfiable by Clingo but I feel better about the LP that is generated so I think I'm on the right track:

true(cell(1,1,1,1,9),0).

true(cell(1,1,1,2,7),0).

true(cell(1,1,1,3,b),0).

true(cell(1,1,2,1,3),0).

true(cell(1,1,2,2,b),0).

true(cell(1,1,2,3,4),0).

true(cell(1,1,3,1,b),0).

true(cell(1,1,3,2,6),0).

true(cell(1,1,3,3,5),0).

true(cell(1,2,1,1,b),0).

true(cell(1,2,1,2,2),0).

true(cell(1,2,1,3,b),0).

true(cell(1,2,2,1,5),0).

true(cell(1,2,2,2,b),0).

true(cell(1,2,2,3,6),0).

true(cell(1,2,3,1,b),0).

true(cell(1,2,3,2,8),0).

true(cell(1,2,3,3,b),0).

true(cell(1,3,1,1,b),0).

true(cell(1,3,1,2,b),0).

true(cell(1,3,1,3,b),0).

true(cell(1,3,2,1,b),0).

true(cell(1,3,2,2,b),0).

true(cell(1,3,2,3,b),0).

true(cell(1,3,3,1,b),0).

true(cell(1,3,3,2,b),0).

true(cell(1,3,3,3,b),0).

true(cell(2,1,1,1,b),0).

true(cell(2,1,1,2,b),0).

true(cell(2,1,1,3,5),0).

true(cell(2,1,2,1,8),0).

true(cell(2,1,2,2,b),0).

true(cell(2,1,2,3,2),0).

true(cell(2,1,3,1,9),0).

true(cell(2,1,3,2,b),0).

true(cell(2,1,3,3,b),0).

true(cell(2,2,1,1,b),0).

true(cell(2,2,1,2,b),0).

true(cell(2,2,1,3,2),0).

true(cell(2,2,2,1,b),0).

true(cell(2,2,2,2,4),0).

true(cell(2,2,2,3,b),0).

true(cell(2,2,3,1,3),0).

true(cell(2,2,3,2,b),0).

true(cell(2,2,3,3,b),0).

true(cell(2,3,1,1,b),0).

true(cell(2,3,1,2,b),0).

true(cell(2,3,1,3,8),0).

true(cell(2,3,2,1,7),0).

true(cell(2,3,2,2,b),0).

true(cell(2,3,2,3,5),0).

true(cell(2,3,3,1,1),0).

true(cell(2,3,3,2,b),0).

true(cell(2,3,3,3,b),0).

true(cell(3,1,1,1,b),0).

true(cell(3,1,1,2,b),0).

true(cell(3,1,1,3,b),0).

true(cell(3,1,2,1,b),0).

true(cell(3,1,2,2,b),0).

true(cell(3,1,2,3,b),0).

true(cell(3,1,3,1,b),0).

true(cell(3,1,3,2,b),0).

true(cell(3,1,3,3,b),0).

true(cell(3,2,1,1,b),0).

true(cell(3,2,1,2,6),0).

true(cell(3,2,1,3,b),0).

true(cell(3,2,2,1,2),0).

true(cell(3,2,2,2,b),0).

true(cell(3,2,2,3,8),0).

true(cell(3,2,3,1,b),0).

true(cell(3,2,3,2,3),0).

true(cell(3,2,3,3,b),0).

true(cell(3,3,1,1,8),0).

true(cell(3,3,1,2,4),0).

true(cell(3,3,1,3,b),0).

true(cell(3,3,2,1,1),0).

true(cell(3,3,2,2,b),0).

true(cell(3,3,2,3,9),0).

true(cell(3,3,3,1,b),0).

true(cell(3,3,3,2,2),0).

true(cell(3,3,3,3,7),0).

role(robot).

base(cell(I,J,K,L,R)) :- index(I), index(J), index(K), index(L), filler(R).

input(robot,mark(I,J,K,L,R)) :- index(I), index(J), index(K), index(L), digit(R).

filler(b).

index(1).

index(2).

index(3).

digit(1).

digit(2).

digit(3).

digit(4).

digit(5).

digit(6).

digit(7).

digit(8).

digit(9).

legal(robot,mark(I,J,K,L,X),T) :- true(cell(I,J,K,L,b),T), digit(X), not row(K,L,X,T), not col(I,J,X,T), not square(I,K,X,T), time(T).

row(K,L,X,T) :- true(cell(1,1,K,L,X),T), time(T).

row(K,L,X,T) :- true(cell(1,2,K,L,X),T), time(T).

row(K,L,X,T) :- true(cell(1,3,K,L,X),T), time(T).

row(K,L,X,T) :- true(cell(2,1,K,L,X),T), time(T).

row(K,L,X,T) :- true(cell(2,2,K,L,X),T), time(T).

row(K,L,X,T) :- true(cell(2,3,K,L,X),T), time(T).

row(K,L,X,T) :- true(cell(3,1,K,L,X),T), time(T).

row(K,L,X,T) :- true(cell(3,2,K,L,X),T), time(T).

row(K,L,X,T) :- true(cell(3,3,K,L,X),T), time(T).

col(I,J,X,T) :- true(cell(I,J,1,1,X),T), time(T).

col(I,J,X,T) :- true(cell(I,J,1,2,X),T), time(T).

col(I,J,X,T) :- true(cell(I,J,1,3,X),T), time(T).

col(I,J,X,T) :- true(cell(I,J,2,1,X),T), time(T).

col(I,J,X,T) :- true(cell(I,J,2,2,X),T), time(T).

col(I,J,X,T) :- true(cell(I,J,2,3,X),T), time(T).

col(I,J,X,T) :- true(cell(I,J,3,1,X),T), time(T).

col(I,J,X,T) :- true(cell(I,J,3,2,X),T), time(T).

col(I,J,X,T) :- true(cell(I,J,3,3,X),T), time(T).

square(I,K,X,T) :- true(cell(I,1,K,1,X),T), time(T).

square(I,K,X,T) :- true(cell(I,1,K,2,X),T), time(T).

square(I,K,X,T) :- true(cell(I,1,K,3,X),T), time(T).

square(I,K,X,T) :- true(cell(I,2,K,1,X),T), time(T).

square(I,K,X,T) :- true(cell(I,2,K,2,X),T), time(T).

square(I,K,X,T) :- true(cell(I,2,K,3,X),T), time(T).

square(I,K,X,T) :- true(cell(I,3,K,1,X),T), time(T).

square(I,K,X,T) :- true(cell(I,3,K,2,X),T), time(T).

square(I,K,X,T) :- true(cell(I,3,K,3,X),T), time(T).

true(cell(I,J,K,L,X),T+1) :- does(ROLE,mark(I,J,K,L,X),T), time(T).

true(cell(I,J,K,L,X),T+1) :- true(cell(I,J,K,L,X),T), does(ROLE,mark(S,T,U,V,Y),T), S!=I, time(T).

true(cell(I,J,K,L,X),T+1) :- true(cell(I,J,K,L,X),T), does(ROLE,mark(S,T,U,V,Y),T), T!=J, time(T).

true(cell(I,J,K,L,X),T+1) :- true(cell(I,J,K,L,X),T), does(ROLE,mark(S,T,U,V,Y),T), U!=K, time(T).

true(cell(I,J,K,L,X),T+1) :- true(cell(I,J,K,L,X),T), does(ROLE,mark(S,T,U,V,Y),T), V!=L, time(T).

goal(robot,100,T) :- not open(T), time(T).

goal(robot,0,T) :- open(T), time(T).

terminal(T) :- not playable(T), time(T).

filler(X) :- digit(X).

open(T) :- true(cell(I,J,K,L,b),T), time(T).

playable(T) :- legal(robot,mark(I,J,K,L,X),T), time(T).

1{ does(R,M,T) : input(R,M) }1 :- role(R), time(T), 1 <= T, T <= 50.:- does(R,M,T), not legal(R,M,T).:- 0{ terminal(T) : time(T) }0.:- terminal(T), role(R), not goal(R,100,T).time(1..51).

% Here is a model I can add manually to help with debugging:


does(mark(1,1,1,3,1),1).

does(mark(1,1,3,1,2),2).

does(mark(1,3,2,1,9),3).

does(mark(2,2,2,3,1),4).

does(mark(2,3,3,2,4),5).

does(mark(3,3,1,3,3),6).

does(mark(1,1,2,2,8),7).

does(mark(1,2,1,3,4),8).

does(mark(1,3,2,3,7),9).

does(mark(2,1,3,2,7),10).

does(mark(2,1,3,3,6),11).

does(mark(2,2,1,2,9),12).

does(mark(2,2,2,1,6),13).

does(mark(1,2,1,1,3),14).

does(mark(1,2,2,2,1),15).

does(mark(1,2,3,1,7),16).

does(mark(1,3,1,3,6),17).

does(mark(1,3,3,1,4),18).

does(mark(1,3,3,2,1),19).

does(mark(2,1,2,2,3),20).

does(mark(2,2,1,1,7),21).

does(mark(2,2,3,2,5),22).

does(mark(2,2,3,3,8),23).

does(mark(2,3,1,2,3),24).

does(mark(2,3,3,3,2),25).

does(mark(3,1,2,1,4),26).

does(mark(3,1,2,3,3),27).

does(mark(1,2,3,3,9),28).

does(mark(1,3,1,1,5),29).

does(mark(1,3,2,2,2),30).

does(mark(1,3,3,3,3),31).

does(mark(2,1,1,2,1),32).

does(mark(2,3,1,1,6),33).

does(mark(2,3,2,2,9),34).

does(mark(3,1,3,2,9),35).

does(mark(3,2,3,1,5),36).

does(mark(1,3,1,2,8),37).

does(mark(2,1,1,1,4),38).

does(mark(3,1,1,2,5),39).

does(mark(3,1,1,3,7),40).

does(mark(3,1,3,3,1),41).

does(mark(3,2,1,1,1),42).

does(mark(3,2,2,2,7),43).

does(mark(3,3,3,1,6),44).

does(mark(3,1,1,1,2),45).

does(mark(3,1,2,2,6),46).

does(mark(3,1,3,1,8),47).

does(mark(3,2,1,3,9),48).

does(mark(3,2,3,3,4),49).

does(mark(3,3,2,2,5),50).

Last Edit: Sept 8, 2015 18:56:21 GMT -8 by Lars Ericson

General Game Playing

Clingo 4.5.1 ASP for Sudoku: Success.....almost

Post by Lars Ericson on Sept 1, 2015 5:15:00 GMT -8

Post by Andrew Rose on Sept 1, 2015 7:42:45 GMT -8

Post by Lars Ericson on Sept 1, 2015 8:02:25 GMT -8

Post by Andrew Rose on Sept 1, 2015 13:18:39 GMT -8

Post by Lars Ericson on Sept 2, 2015 13:45:53 GMT -8

Post by Lars Ericson on Sept 8, 2015 18:52:19 GMT -8

Quick Reply