# プラザマップを解くプログラム ver.0.2('05/10/17) by Arui K.
# ※ 回転解チェックはしてません

use strict;

#--------------------------------------------
our $BOARD_X = 3;
our $BOARD_Y = 3;

#--------------------------------------------
# 0
#1 3
# 2
our @piece;
$piece[0] = ['A','B','C','D'];
$piece[1] = ['b','d','C','A'];
$piece[2] = ['b','a','d','c'];
$piece[3] = ['B','C','A','D'];
$piece[4] = ['B','d','A','c'];
$piece[5] = ['D','C','B','A'];
$piece[6] = ['C','a','D','b'];
$piece[7] = ['a','B','c','D'];
$piece[8] = ['c','d','a','b'];

#--------------------------------------------
# ※ 盤の外周１マスは空きとして確保して[1,1]-[3,3]を使います
our @board;		# [x][y] 結果表示用にしか使ってない
our @side;		# [x][y][辺0-3]
our @isused;	# ピース(0-8)が既に使われていたら真
our $answercount;

place(0); # 一箇所目に置く
print "おしまい\n";
exit;

#-- n箇所目にピースを置く
sub place{ # @_ = 位置番号。左上を0として左→右、上→下の順に数える
	my $pos = shift;

	if ($pos > $#piece ){ # どうやら全部置けたらしい
		$answercount++;
		print "解 その$answercount 発見！\n";
		output_board();
		return;
	}

	my $x = ($pos % $BOARD_X)+1;
	my $y = int($pos / $BOARD_X)+1;

	foreach my $pno (0..$#piece){
		next if $isused[$pno];
		@{$side[$x][$y]}[0..3] = @{$piece[$pno]}[0..3]; # 置いてみる

		my $r=0;
		while ( 1 ){
			if ( isok($x,$y) ){
				$isused[$pno]=1;
				$board[$x][$y] = "$pno-$r";
				place($pos+1); # 次に進む
				$isused[$pno]=0;
			}
			# 三回までは回転させてみる
			last if ($r++ >= 3);
			rotate_right($x,$y);
		}
	}
	# どのピースも置けなかったので掃除して一段階戻る
	$side[$x][$y] = undef;
	$board[$x][$y] = undef;
	return;
}

#-- 指定位置のピース (というか四辺) を右回転させる
sub rotate_right { # @_ = (x,y)
	my ($x,$y) = @_;
	@{$side[$x][$y]}[0,1,2,3] = @{$side[$x][$y]}[1,2,3,0];
}

#-- 指定位置のピースの四辺がすべて周囲と噛み合ってるかチェック
sub isok { # @_ = (x,y)
	my ($x,$y) = @_;
	return 1 if arevalid ( $side[$x][$y][0] , $side[$x][$y-1][2] ) and
				arevalid ( $side[$x][$y][1] , $side[$x-1][$y][3] ) and
				arevalid ( $side[$x][$y][2] , $side[$x][$y+1][0] ) and
				arevalid ( $side[$x][$y][3] , $side[$x+1][$y][1] );
	return 0;
}

#-- 二つの辺パターンが噛み合うものかどうかチェック
sub arevalid { # @_ = (辺1の中身,辺2の中身)
	my ($a,$b) = @_;
	return 1 if ( ($a eq '') || ($b eq '') ); # 隣が空きならなんでも置ける
	return 1 if ( ($a eq lc($b)) xor (lc($a) eq $b) );
	return 0;
}

#-- 現在の盤面を出力
sub output_board{
	foreach my $y (1..$BOARD_Y){
		foreach my $x (1..$BOARD_X){
			printf "   <%1s>   ",$side[$x][$y][0];
		}
		print "\n";
		foreach my $x (1..$BOARD_X){
			printf "<%1s>%3s<%1s>",$side[$x][$y][1],$board[$x][$y],$side[$x][$y][3];
		}
		print "\n";
		foreach my $x (1..$BOARD_X){
			printf "   <%1s>   ",$side[$x][$y][2];
		}
		print "\n";
	}
	print "\n";
}