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