All the Perl that's Practical to Extract and Report

Sudoku and Quantum::Superpositions

QM on 2005-08-03T21:58:12

My whole family is going crazy playing Sudoku!

I find it mildly entertaining (and a lot of work). I'd rather know how to solve it programmatically, and then smirk when they get stuck.

I've seen some solvers out there, and at least one uses Quantum::Superpositions. But it was only used as a bit vector, and didn't do anything dramatically different from any other solution.

So I'm picking up the gauntlet, and working out whether Q::S can really be useful here or not. For instance, I'd like to develop the constraints and starting state in Q::S, and say "go", and watch it churn.

For the 9x9 version, I recall that there are 324 constraints to be satisfied. Given Q::S's recursive nature, that could be quite a CPU killer...if I can figure out how to code it.

Now to pull out the debugger, and see what I can do with any and all.

Sudoku and Quantum::Superpositions

rats on 2005-08-03T23:52:55

My family is also in thrall of Sudoku and I also have the same feeling about it being more fun to write a Perl script to solve them.

I was thinking more along the lines of a branch-and-bound algorithm (e.g. the Knapsack problem) but Q::S looks even more fun.

Q::S is iterative for some time now

Limbic Region on 2005-08-04T12:16:32

What exactly did you mean by the recursive nature? Not knowing what you might have in mind for the solver, it still may be recursive but normal use has been iterative for some time now.

Re:Q::S is iterative for some time now

QM on 2005-08-04T14:36:32

According to the documentation (2.02):
More interestingly, since the individual states of a superposition are scalar values and a superposition is itself a scalar value, a superposition may have states that are themselves superpositions:

$ideal = any( all("tall", "rich", handsome"), all("rich", "old"), all("smart", "Australian", "rich"));

Operations involving such a composite superposition operate recursively and in parallel on each its states individually and then recompose the result.

I thought to develop the logic in such a way that the operations and comparisons would be applied recursively into some nested structure of QS objects.

But I'm still working out how to build up the nested data structure useful for this problem.

Sudoku and Quantum::Superpositions

mx.2000 on 2005-08-22T22:37:31

I thought about the same thing a while ago. I didn't manage to code it using Q::S, so I ended up writing a simple implementation i.e. guessing and checking the constraints.

If you got an implementation using Q::S I'd really like to see it; maybe you could post it here.

PS: Could you post a link to the solver using bit vectors? That one sounds interesting too.

Thanks
Martin

Re: Sudoku and Quantum::Superpositions

QM on 2005-08-23T14:30:07

The Q::S implementation that I qualified as "just a bit vector": SuDoKu Solver. I don't know if you agree with that. A literal vector implementation could be faster than Q::S, as there'd be less overhead, etc.

I haven't worked on this much since my original post, and I haven't made any breakthroughs with Q::S on it. I got distracted into AI::Prolog, which also looks interesting. I guess I'm more interested in how to ask the question (ala Prolog) than what the answer actually looks like.

Perhaps your interest will spur me on to put aside the real world again and revisit my Perl Hermit Camp.