Still on a bit of a Perl6 high from LCA06, I went looking for something to apply Quantum::Superpositions to. I think I’ve blogged about these before, and the fact that they’re in Perl 6 (as “Junctions“). Today I was looking for a use for them, and realise that the Sudoku booklet I was holding was perfect.

Upon actually reading the CPAN entry for Quantum::Superpositions, I realised that it wasn’t actually what I wanted. Luckily, Quantum::Entanglement also showed up when I searched CPAN for “Quantum”. Quantum::Entanglement *is* what I want.

The idea of Quantum::Entanglement is that you create an entanglement, which has a certain probability of being in a particular state, and a probability of 1 of being in _a_ state. You then operate upon this, and it collapses as appropriate when you actually learn something about it, producing either a result or more entanglements. I’d read the page for more information. And in fact, that’s what I did.

Sudoku on the other hand, is apparently sweeping the world by storm. It’s basically a 9×9 grid, in which you must places digits 1-9 such that each digit appears once in each row, column and each of 9 3×3 disjoint squares. You are given a couple of numbers to start, and then it’s off. If there was ever a candidate for quantum computing quite as good, I can’t imagine what it is. (OK, I can imagine. Breaking cryptography that relies on large primes…)

So the code looks like this:

#! /usr/bin/perl

use strict;

use Quantum::Entanglement;

my $easy = [

[ 0,9,0, 5,2,4, 6,0,0 ],

[ 0,0,0, 0,0,0, 0,5,4 ],

[ 0,0,0, 0,0,3, 0,7,2 ],

[ 0,6,7, 0,0,5, 0,0,0 ],

[ 3,0,4, 7,1,8, 5,9,6 ],

[ 0,0,0, 2,0,0, 3,8,0 ],

[ 5,7,0, 4,0,0, 0,0,0 ],

[ 6,1,0, 0,0,0, 0,0,0 ],

[ 0,0,2, 3,9,7, 0,6,0 ]

];

# Build a board of quantum entanglements.

my $board;

for my $i (0 .. 8) {

for my $j (0 .. 8) {

$board->[$i][$j] =

entangle(1=>1, 1=>2, 1=>3, 1=>4, 1=>5, 1=>6, 1=>7, 1=>8, 1=>9);

print “Initial: ($i,$j) => “,$board->[$i][$j]->show_states();

}

}

# Now entangle the variables together, without collapsing any values

for my $i (0 .. 8) {

for my $j (0 .. 7) {

for my $k (($j+1) .. 8) {

print “($i,$j) != Row ($i,$k)\n”;

p_op $board->[$i][$j], ‘!=’, $board->[$i][$k];

print “($j,$i) != Col ($k,$i)\n”;

p_op $board->[$j][$i], ‘!=’, $board->[$k][$i];

# We don’t need to entangle again a cell that is

# both in the square and shares a row or column

unless ($i-$i%3 + int($j/3) == $i-$i%3 + int($k/3)

or ($i%3)*3 + $j%3 == ($i%3)*3 + $k%3) {

printf “(%d,%d) != Sqr (%d,%d)\n”, $i-$i%3 + int($j/3),

($i%3)*3 + $j%3, $i-$i%3 + int($k/3), ($i%3)*3 + $k%3;

p_op $board->[$i-$i%3 + int($j/3)][($i%3)*3 + $j%3], ‘!=’,

$board->[$i-$i%3 + int($k/3)][($i%3)*3 + $k%3];

}

# print $board->[$i][$j]->show_states(),”\n”;

}

}

}

for my $i (0 .. 8) {

for my $j (0 .. 8) {

if ($easy->[$i][$j] != 0) {

p_op $board->[$i][$j], ‘==’, $easy->[$i][$j];

}

}

}

# Turn on try-for-truth mode

$Quantum::Entanglement::conform = 1;

# At this point, printing any value from the array should

# collapse the entire entanglement.

for my $i (0 .. 8) {

for my $j (0 .. 8) {

print ” “,$board->[$i][$j];

}

print “\n”;

}

And how does it work? I have absolutely no idea. My computer has 512Mb of physical RAM, which is filled within the first five p_ops. The sixth takes it to a gigabyte, and suddenly kswapd0 is doing more work than perl…

I asked on #perl, and was told that Quantum::Entanglement (and Quantum::Superpositions) are crap. >_< So I guess this will remain a thought experiment, unless someone has either a Quantum computer lying around, or a machine with multi-mega-petabytes of RAM…

The reason the RAM usage climbs so high is that entangling two things with 9 states produces 72 possible global states (every combination of 1-9 and 1-9 except equality). Each cell added to this entanglement of the first cell is another 8, so the entire entanglement of the first cell (ie the entire $k loop has run) is 9 * 8^20 or 10376293541461622784 states. That’s 10×10^18 states. Each successive cell actually removes from consideration some of the earlier states, but the multicative effect completely hides that. Which is good news for people relying on GPG to protect their data. ^_^

Of course, now I’m going to be looking for something **practical** I can do with Quantum::Entanglement.

For reference, this is puzzle #1 from Lovatts Super Sudoku issue 8, which I actually fell asleep doing on the plane to LCA06, due to the tonsilitis, Panedine, Strepsils, penicilin and 28 hours (including three of highway driving) of continual awakeness preceeding it.

Oh, and `apt-get install libquantum-entanglement-perl` is the super-final-ultimate-killer proof that Debian is the only way to Linux. ^_^

First “Commercial” Quantum Computer Solves Sudoku Puzzles

Dammit, beaten to it.