#!/usr/bin/perl
# $Id: dominoes.pl,v 1.1 2000/12/01 11:09:42 aqua Exp $
#
# Devin Carraway <dominoes\at\devin.com>
# 
# Note: the Dominoes problem is not Turing-decidable.
#   This program covers a tiny subset of the solution space, hunting for
#   easy solutions.
#

# Domino list
@D = ( ['ab','abab'], ['b','a'], ['aba','b'], ['aa','a'] );

&permute(0,[],[]);

my $c = 0;

sub permute {
	my ($depth,$w,$r) = @_;
	my @w = @{$w};
	my @r = @{$r};

	print "$depth [$#w,$#r]/$c           \r" if ($c % 5)==0; $c++;
	if (@w) {
		&check(\@w,\@r)<0 and return; # no possible matches here
	}
	$depth>=24 and return;
	for $i (0..$#D) {
		&permute($depth+1,[@w,$D[$i]],[@r,$i]);
	}
}

sub check {
	my ($a,$r) = @_;
	my ($s1,$s2) = ('','');

	for (@{$a}) {
		$s1 .= $_->[0];
		$s2 .= $_->[1];
	}
	if ($s1 eq $s2) {
		print "\nmatch: $s1/$s2 from [",join(',',@{$r}),"]\n";
		print STDERR "\nmatch: $s1/$s2 from [",join(',',@{$r}),"]\n";

		return 1;
#		exit;
	} else {
		my $lmin = &min(length($s1),length($s2));
		return -1 if (substr($s1,0,$lmin) ne substr($s2,0,$lmin));
		return 0;
#		print "\nno match: [",join(',',@{$r}),"]\n";
	}
}

sub min { $_[0] < $_[1] ? $_[0] : $_[1] }