#!/usr/bin/perl
# Filename:	ttt_combos
# Author:	David Ljung Madison <DaveSource.com>
# See License:	http://MarginalHacks.com/License
# Description:	All legal tic tac toe games
use strict;

##################################################
# Setup the variables
##################################################
my $PROGNAME = $0;
$PROGNAME =~ s|.*/||;

# We create a tree of all possible games first, then
# print out all the legal board positions once (there
# can be more than one route to a single board position)
# Do we want to print out the creation of the tree as well?
my $SHOW_TREE = 0;

# Do we include all intermediate board positions, or just
# the final endgame boards?
my $WIN_GAMES_ONLY = 0;

##################################################
# Main code
##################################################
my %PERMUTATIONS;

sub show {
  my ($board,@moves) = @_;
  my $win = checkwin($board);
  if ($SHOW_TREE && ($win || !$WIN_GAMES_ONLY)) {
    print $win ? "WIN: " : "     " unless $WIN_GAMES_ONLY;
    print "$board\t@moves\n";
  }
  $PERMUTATIONS{$board}++ if $win || !$WIN_GAMES_ONLY;
  return $win;
}

sub show_permutations {
  my @perms = keys %PERMUTATIONS;
  my $num = $#perms+1;
  print "\nLegal board combos: $num\n";
  foreach ( @perms ) {
    print "$_  [$PERMUTATIONS{$_}]\n";
  }
}

sub checkwin {
  my ($board) = @_;

  # across
  return 1 if $board =~ /^(...){0,2}(XXX|OOO)/;

  # down
  return 1 if $board =~ /X..X..X/;
  return 1 if $board =~ /O..O..O/;

  # diagonal
  return 1 if $board =~ /^X...X...X/;
  return 1 if $board =~ /^O...O...O/;
  return 1 if $board =~ /^..X.X.X/;
  return 1 if $board =~ /^..O.O.O/;

  return 0;
}

sub try {
  my ($who,$pos,$board,@moves) = @_;
  push(@moves,$pos);
  substr($board,$pos,1,$who);
  return if show($board,@moves);
  move($who eq "X" ? "O" : "X", $board,@moves);
}

sub move {
  my ($who,$board,@moves) = @_;

  foreach my $pos (0..8) {
    next unless substr($board,$pos,1) eq "-";
    try($who,$pos,$board,@moves);
  }
}

my $board = "-"x9;
my @moves;
move("X",$board,@moves);
show_permutations;