#!/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