#!/usr/bin/perl -w
# Generate all permutations of a 3x3 sliding puzzle.
#
# Outputs dot graph to stdout.

use strict;

sub shift_up($)
{
   my ($x) = @_;

   return undef if substr($x, 1, 1) ne "_";

   substr($x, 1, 1) = substr($x, 4, 1);
   substr($x, 4, 1) = substr($x, 7, 1);
   substr($x, 7, 1) = "_";
   return $x;
}

sub shift_down($)
{
   my ($x) = @_;

   return undef if substr($x, 7, 1) ne "_";

   substr($x, 7, 1) = substr($x, 4, 1);
   substr($x, 4, 1) = substr($x, 1, 1);
   substr($x, 1, 1) = "_";
   return $x;
}

sub shift_left($)
{
   my ($x) = @_;

   return undef if substr($x, 3, 1) ne "_";

   substr($x, 3, 1) = substr($x, 4, 1);
   substr($x, 4, 1) = substr($x, 5, 1);
   substr($x, 5, 1) = "_";
   return $x;
}

sub shift_right($)
{
   my ($x) = @_;

   return undef if substr($x, 5, 1) ne "_";

   substr($x, 5, 1) = substr($x, 4, 1);
   substr($x, 4, 1) = substr($x, 3, 1);
   substr($x, 3, 1) = "_";
   return $x;
}

sub generate_node_label($)
{
   my ($x) = @_;
   $x =~ s/x/#/g;
   return substr($x, 0, 3) . "\\n" .
          substr($x, 3, 3) . "\\n" .
          substr($x, 6, 3);
}


my @visit_stack = ("x_x" .
                   "21_" .
                   "x5x");
my %seen_state = ();

print "digraph G\n",
      "{\n",
      "   node [font=\"courier\"];\n";
while( my $node = pop @visit_stack )
{
   next if exists $seen_state{$node};
   print "   $node [label=\"", generate_node_label($node), "\"];\n";
   $seen_state{$node} = 1;

   my $neighbor;
   if( defined($neighbor = shift_up($node)) )
   {
      print "   $node -> $neighbor [label=\"up\"];\n";
      push @visit_stack, $neighbor;
   }
   if( defined($neighbor = shift_down($node)) )
   {
      print "   $node -> $neighbor [label=\"down\"];\n";
      push @visit_stack, $neighbor;
   }
   if( defined($neighbor = shift_left($node)) )
   {
      print "   $node -> $neighbor [label=\"left\"];\n";
      push @visit_stack, $neighbor;
   }
   if( defined($neighbor = shift_right($node)) )
   {
      print "   $node -> $neighbor [label=\"right\"];\n";
      push @visit_stack, $neighbor;
   }
}
print "}\n";