On 31/05/2012 02:20 PM, Francois Labreque wrote:

> Yeah, I know. Cool story bro.

The way I heard it, Prolog caused quite a stir when people first saw it 
back in the 1970s. A few simple lines of Prolog gives you a system with 
approximately the apparent logical deductive skills of a 2 year old 
child. And it's really quite a simple piece of programming. The computer 
scientists of the day must surely have thought that in just a few years' 
time, they would have human or super-human intelligence at their 
fingertips...

...and then it didn't actually happen like that, and the "AI winter" 
came along. The scientists promised everybody the Earth, and then 
couldn't deliver, so their funding was slashed.

Post a reply to this message

On 31/05/2012 02:22 PM, Stephen wrote:

> Your talents are wasted in your job.

What? SERIOUSLY??? :-O

>>> Having written something like this is also very good for CVs and job
>>> interviews :-)
>>
>> ....and you think I'm doing this because...? ;-)
>
> You have too much time on your hands and the job that you get paid for
> does not stretch you.

Well, right now - oh, wait, legally I can't tell you about that. Maybe 
in a few weeks' time...

Post a reply to this message

On 31/05/2012 01:27 PM, scott wrote:
>>> Runs fine here, opened it up and was thinking what it could be useful
>>> for ... could it be used to solve Sudoku puzzles?
>>
>> It... could. Perhaps. With some serious modifications.
>
> You would need a permutation predicate, eg LPerm. It would be solved
> when the first list is a permutation of the second list.

Challenge accepted. ;-)

Actually, there is /already/ an SEqual{} predicate, which is solved if 
two lists are "set-equal". That is, X is a subset of Y and Y is a subset 
of X. More simply, every element of X is also an element of Y and vice 
versa.

Notice that this does not imply that X is a /permutation/ of Y, since 
elements can appear more than once. (Remember, sets do not have 
multiplicity.) If I could fix that, it might work.

> LPerm{ List[1,2,3] , List[3,1,x] }
>
> Would tell you that x := 2

That doesn't quite work for SEqual{}, because every set can be 
represented by infinity distinct lists. But it ought to be fixable.

> I'm guessing that it wouldn't be simple to implement...

I'm guessing that it would. ;-)

The trick appears to be either to get the loop to terminate reliably, or 
else to somehow add a constraint that both lists are the same size.

> If you had that, then you could expand it easily to a sudoku grid. You'd
> need an LPerm for each row, each column and each 3x3 box all ANDed
> together.
>
> Now that would be a very cool solution, as in you wouldn't need to tell
> the computer *how* to solve it (as you have to when writing a
> "traditional" sudoku solver), just what the rules are.

I'll see what I can come up with...

Post a reply to this message

On 31/05/2012 02:32 PM, Invisible wrote:

> Actually, there is /already/ an SEqual{} predicate, which is solved if
> two lists are "set-equal". That is, X is a subset of Y and Y is a subset
> of X. More simply, every element of X is also an element of Y and vice
> versa.

Ha! Yes, SEqual{} is already defined. It also doesn't /work/. o_O

The mistake is simple. SEqual{} calls SSubset{}, and SSubset{} has a 
bug. Its definition is

SSubset{sub, super}:
   (sub = End[]) | (~item ((SMember{item, sub}) & (SMember{item, super})))
;

In other words,

   "S is a subset of T if S is the empty set OR _there exists_ an X 
which is a member of S and a member of T."

What it /should/ of course say is

   "S is a subset of T if S is the empty set OR _for all_ X which is a 
member of S, X is a member of T."

In short, I've mixed up "exists" and "for all". Kind of an important 
distinction, that one.

Logic Box of course doesn't /have/ an explicit for-all construct. At 
this point I am uncertain whether I can work around that...

Post a reply to this message

On 31/05/2012 02:57 PM, Invisible wrote:

> Ha! Yes, SEqual{} is already defined. It also doesn't /work/. o_O
>
> The mistake is simple. SEqual{} calls SSubset{}, and SSubset{} has a
> bug.

> In short, I've mixed up "exists" and "for all". Kind of an important
> distinction, that one.
>
> Logic Box of course doesn't /have/ an explicit for-all construct. At
> this point I am uncertain whether I can work around that...

A /correct/ definition for SSubset{} is

SSubset{subset, superset}:
   (subset = End[]) |
   (~head ~tail
     subset = Node[head, tail] &
     SMember{head, superset} &
     SSubset{tail, superset}
   )
;

Before SSubset{} would accept any pair of sets where just one element is 
common to both sets. Now it only works if /all/ of the elements of the 
subset are elements of the superset. (I.e., it works correctly now.)

This in turn causes SEqual{} to function correctly.

It's quite slow, but

   SEqual{List[1, 2, 3], List[3, 1, x]}

does eventually yield x := 2.

QED.

Post a reply to this message

On 31/05/2012 2:26 PM, Invisible wrote:
> Well, right now - oh, wait, legally I can't tell you about that. Maybe
> in a few weeks' time...

I am all agog.

-- 
Regards
     Stephen

Post a reply to this message

> This in turn causes SEqual{} to function correctly.
>
> It's quite slow, but
>
> SEqual{List[1, 2, 3], List[3, 1, x]}
>
> does eventually yield x := 2.

So for the first row in a sudoku I'd expect something like this:

SEqual{List[1..9], List[3,a,b,c,1,d,e,f,8]}

That should work, as both lists are the same length (so the 2nd list 
must contain the each of the elements 1-9 once).

But I'm guessing it's going to be very slow, especially when you add in 
the other 26 SEqual statements all ANDed together...

Shame, as I think it's a really neat way to write a solver.

Post a reply to this message

On 31/05/2012 03:56 PM, scott wrote:
>> This in turn causes SEqual{} to function correctly.
>>
>> It's quite slow, but
>>
>> SEqual{List[1, 2, 3], List[3, 1, x]}
>>
>> does eventually yield x := 2.
>
> So for the first row in a sudoku I'd expect something like this:
>
> SEqual{List[1..9], List[3,a,b,c,1,d,e,f,8]}
>
> That should work, as both lists are the same length (so the 2nd list
> must contain the each of the elements 1-9 once).
>
> But I'm guessing it's going to be very slow, especially when you add in
> the other 26 SEqual statements all ANDed together...
>
> Shame, as I think it's a really neat way to write a solver.

When I removed the run time constraint, it took Logic Box about 22 
seconds and 90 MB of RAM to come up with the first 10 solutions to the 
predicate above. Of course, it's going to sit there and search for all 
6! permutations of 6 items.

Think about what's happening under the covers: Logic Box is merely 
searching through all possible combinations, trying to find one for 
which all the constraints apply. I should imagine that for Sudoku, the 
search space is /astronomical/, so it's likely to take a while. If it 
takes 22 seconds to partially process one row, then processing 9 rows, 9 
columns and 9 squares searching for a simultaneous solution to all of 
them is going to take... a while.

I agree, however, that it would be very cool if this actually worked. :-D

Post a reply to this message

scott <sco### [at] scottcom> wrote:
> Also how hard would it be to add support for arithmetic operators?

yes, first thing I tried was changing x=y to x=2*y

hmm, didn't actually tried x=2y...

> Having written something like this is also very good for CVs and job
> interviews :-)

yes, at least if he's willing to change "written by Orphi the AweKid"... :p

On AI, perhaps we don't have bad and mean counscious AI, but OTOH, we have far
more believable game characters than we've ever dreamed for back then... IBM
also got Watson... a few more years and we may get Sherlock level... :)

Post a reply to this message

Attached is release #2.

Only a few things have changed. The laughable bug in SSubset{} is gone, 
and the file requester doesn't keep resetting itself to your home folder 
every single time you open it. I've also adjusted it so that temporary 
variables are labelled with their original names as subscripts, which 
makes things slightly easier to follow. (But only slightly.)

There's a couple of other ideas I have for what could be done with this 
program. (E.g., improving the output, refactoring the code, adding new 
features.) But honestly, I think I'm bored with it now. I don't suppose 
I'll be making any further releases soon. It's time for a different 
project...

Post a reply to this message

Attachments:
Download 'logicbox-02 release2.jar.zip' (197 KB)