#!/usr/bin/perl -w
package EightPuzzle;
use strict;
use warnings;
 
my $gamesize = 9;
my @x;
my @y;
my @goal = (1,2,3,8,0,4,7,6,5);
my @game;
my @game_bak;
my $MAX_MOVES = 50000;
 
main();
 
sub main {
	create_grid();
	my @res;
	my $bad_sum = 0;
	my $manh_sum = 0;
 
	my $bad_moves = 0;
	my $manh_moves = 0;
 
	for(my $i= 1; $i < 6; $i++) {
		print "=== $i. zadani ===\n";
		create_game();
		backup_game();
 
		@res = @{solve(\&fitness_h1)};
		$bad_moves += $res[0];
		$bad_sum += $res[1];
		print_bad(@res);
 
		restore_game();
 
		@res = @{solve(\&fitness_h2)};
		$manh_moves += $res[0];
		$manh_sum += $res[1];
		print_manh(@res);
 
		clear_game();
	}
 
	print "\nCelkem spatne umistenych kostek: $bad_sum v $bad_moves tazich.\n";
	print "Celkova suma manhattanskych vzdalenosti: $manh_sum v $manh_moves tazich.\n";
 
}
 
sub print_bad {
	print "\nPocet spatne umistenych je ".$_[1]." s poctem kroku ".$_[0].".\n"
}
 
sub print_manh {
	print "\nSuma manhattanskych vzdalenosti je ".$_[1]." s poctem kroku ".$_[0].".\n";
}
 
sub backup_game {
	@game_bak = @game;
}
 
sub restore_game {
	@game = @game_bak;
}
 
sub clear_game {
	@game = ();
	@game_bak = ();
}
 
sub solve {
	my $fitness_sub = shift;
	my $i = 0;
	print ">>> VSTUP <<<\n";
	print_game();
 
	print "(probiha vypocet, prosim cekejte)\n";
 
	while(++$i < $MAX_MOVES && &$fitness_sub > 0) {
		move($fitness_sub);
	}
 
	print "\n<<< VYSTUP >>>\n";
	print_game();
 
	# return statistic information
	my @ret = ($i, &$fitness_sub);
	return \@ret;
 
}
 
sub create_grid {
	my $gss = sqrt $gamesize;
	my $k = 0;
	for(my $i=0; $i < $gss; $i++) {
		for(my $j=0; $j < $gss; $j++) {
			$x[$k] = $i;
			$y[$k] = $j;		
			$k++;
		}
	}
}
 
sub print_game {
	my $gss = sqrt $gamesize;
	for(my $i = 0; $i < $gss; $i++) {
		for(my $j = 0; $j < $gss; $j++) {
			print $game[$gss*$i+$j];
		}
		print "\n";
	}
}
 
sub create_game {
	for(my $i=0;$i<$gamesize-1;$i++) {
		my $num = int(rand($gamesize-1))+1;
		while(grep /$num/, @game) {
			$num = int(rand($gamesize-1))+1;
		}
		push @game, $num;
	}
 
	@game[3..8] = @game[2..7];
	$game[2] = 0;
}
 
sub fitness_h1 {
	my $right_count = 0;
	my $goal_count = scalar @goal;
	for(my $i = 0; $i < $goal_count; $i++) {
		if($game[$i] eq $goal[$i]) {
			++$right_count;
		}
	}
	return ($goal_count - $right_count);
}
 
sub fitness_h2 {
	my $total = 0;
	my $goal_count = scalar @goal;
 
	for(my $i=0;$i < $goal_count;$i++) {				
		my $goal_index;
		for(my $j=0; $j < $goal_count; $j++) {
			if($goal[$j] eq $game[$i]) {
				$goal_index = $j;
				$j = $goal_count;
			}
		}
		$total += (abs ($x[$i] - $x[$goal_index]) + abs($y[$i] - $y[$goal_index]));
	}
	return $total;
}
 
 
sub move {
	my $fitness_sub = shift;
 
	my @pm = @{possible_moves()};
	my @pm_bak = @pm;
	my @equal_fitness;
 
	my $zero_idx = undef;
	for(my $i = 0; $i < scalar @game; $i++) {
		$zero_idx = $i if $game[$i] eq 0;
	}
 
	my $bak_fitness = &$fitness_sub;
	my @bak = @game;
 
	my $best_move = $pm[0];
	my $curr_fitness = 5000;
 
	while(my $idx = shift @pm) {
		@game = @bak;
		$game[$zero_idx] = $game[$idx];
		$game[$idx] = 0;
 
		my $new_fitness = &$fitness_sub;
 
		my @f = ($idx, $new_fitness);
		push @equal_fitness, \@f;
 
		if($new_fitness < $curr_fitness) {
			$curr_fitness = $new_fitness;
			$best_move = $idx;
		}
	}
 
	@game = @bak;
 
	$game[$zero_idx] = $game[$best_move];
	$game[$best_move] = 0;
}
 
sub possible_moves {
	my $zero_idx;
	my $pos;
	my @ret;
 
	for(my $i = 0; $i < scalar @game; $i++) {
		if($game[$i] eq 0) {
			$zero_idx = $i;
			$i = scalar @game; # break-command emulation
		}
	}
	my $zero_x = $x[$zero_idx];
	my $zero_y = $y[$zero_idx];
 
	$pos = get_index($zero_x-1, $zero_y);
	push @ret, $pos if defined $pos;
	$pos = get_index($zero_x+1, $zero_y);
	push @ret, $pos if defined $pos;
	$pos = get_index($zero_x, $zero_y-1);
	push @ret, $pos if defined $pos;
	$pos = get_index($zero_x, $zero_y+1);
	push @ret, $pos if defined $pos;
 
	@ret = sort { int(rand(3)-1) } @ret;
 
	return \@ret;
}
 
sub get_index {
	my $xpos = shift;
	my $ypos = shift;
 
	if($xpos > (sqrt $gamesize - 1) || $ypos > (sqrt $gamesize - 1) || $xpos < 0 || $ypos < 0) {
		return undef;
	}
 
	return ((sqrt $gamesize)*$xpos + $ypos);
}