#!/usr/bin/perl -w
use strict;
my @c = (0,8,5,4,1,2,3,6,7);
my $zero = 0;
my @pos = (
[1,3,],
[0,2,4,],
[1,5,],
[0,4,6,],
[1,3,5,7,],
[2,4,8,],
[3,7,],
[6,4,8,],
[5,7,],
);
my @end = 0..8;
my $min = 999_999_999;
my ($r, $count, $cost, @sol, $zerosol);
do {
$r = $pos[$zero][int rand( scalar( @{$pos[$zero]} ))] ;
($c[$zero], $c[$r]) = ($c[$r], $c[$zero]);
$zero = $r;
$cost =0;
$cost += ($_-$c[$_])**2 for (@end);
if ($cost < $min){
print "$cost\n";
$min = $cost;
@sol = @c;
$zerosol = $zero;
}elsif (++$count % 100 ==0){
@c = @sol;
$zero = $zerosol;
}
}until ($cost == 0);
__END__
We have a matrix 3x3 with a hole to slide
other numbers into that position.
An initial arrangement could be:
- 8 5
4 1 2
3 6 7
and we want to play until the numbers
are ordered as
- 1 2
3 4 5
6 7 8
Beware: not all initial positions can
lead to a solution.
Can you write an algorithm that lead
to a solution and predict when there
isn't?
Cheers