Stories
Slash Boxes
Comments
NOTE: use Perl; is on undef hiatus. You can read content, but you can't post it. More info will be forthcoming forthcomingly.

All the Perl that's Practical to Extract and Report

use Perl Log In

Log In

[ Create a new account ]

QM (6116)

QM
  reversethis-{moc ... inahceM.mutnauQ}
My ID and Sig come from a fake ad in a magazine: "Become a Quantum Mechanic!..." I adopted this as my alter ego's vocation (as I know just enough physics to embarass myself in good company).

Journal of QM (6116)

Wednesday August 03, 2005
04:58 PM

Sudoku and Quantum::Superpositions

[ #26075 ]
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.


List all Journal entries
The Fine Print: The following comments are owned by whoever posted them. We are not responsible for them in any way.

Sudoku and Quantum::Superpositions 5 Comments More | Login | Reply /

 Full
 Abbreviated
 Hidden
More | Login | Reply
Loading... please wait.
  • 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.
  • 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.
    • 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

      --
      -QM

      Quantum Mechanics: The dreams stuff is made of

  • 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
    • The Q::S implementation that I qualified as "just a bit vector": SuDoKu Solver [perlmonks.org]. 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 inter

      --
      -QM

      Quantum Mechanics: The dreams stuff is made of

Stories, comments, journals, and other submissions on use Perl; are Copyright 1998-2006, their respective owners.