#!/usr/bin/perl
# wordSearchSolve.pl
# Program to solve a word search puzzle semi-automatically.
# Define the puzzle to be searched as '@puzzle', see the example below.
#
# Christopher Dykes (2009-09-25) - (v1.0)

#Enable the following packages:
use strict;	#Enable strict syntax checking
use warnings;	#Enable diagnostic warnings

#Declare global variables:
our @end = undef;	#The location of the end of the word

#Declare local variables:
my $done = 0;		#Whether we're finished or not
my @start = undef;	#The location of the start of the puzzle
my @puzzle =
(
	['r','e','l','a','e','d','b','y'], 
	['e','s','c','r','e','e','n','t'], 
	['m','i','o','e','i','s','h','l'], 
	['i','s','l','a','t','e','r','a'], 
	['t','n','u','r','c','n','n','u'], 
	['r','g','m','u','a','i','h','s'], 
	['o','u','b','m','t','h','a','a'], 
	['m','e','o','a','n','c','c','c']
);

#Display the header:
print "Wordsearch Solver:\n\n";
print "Enter the term to search for, enter '#quit' to exit\n\n";

#Allow the user to search
while(!$done)
{
	my($word, $found);
	@end = undef;

	#Get the word from the user:
	print "> ";	chomp($word = <STDIN>);
	$done++ if($word eq "#quit");

	unless($done)
	{
		my($i, $j, $k);
		print $word, "\t= ";
		my @word = split(//, $word);

		for($i = 0, $found = 0; $i <= $#puzzle && !$found; $i++)	#Row loop
		{
			for($j = 0; $j <= $#puzzle && !$found; $j++)		#Col loop
			{
				for(my $k = 0; $k < 8 && !$found; $k++)		#Dir loop
				{
					my @gen = ("");
					$found = &search($k, $i, $j, \@puzzle, \@word, @gen);
				}
			}
		}
		print "($i,$j) - ($end[0],$end[1])\n" if($found);
		print "NO RESULT\n" if(!$found);
	}
}

#Subroutines begin here:
sub search ($ $ $ $ $ @)	#Performs a recursive search across the puzzle
{
	#Declare local variables:
	my($dir, $row, $col, $puzRef, $wrdRef, @gen) = @_;
	my @puzzle = @{$puzRef};
	my @word   = @{$wrdRef};

	($end[0], $end[1]) = (($row + 1), ($col + 1));	#Set our end location

	return 0 if($puzzle[$row][$col] ne $word[$#gen]);
	return 1 if($#word == $#gen);

	#Decide what to do:
	$row++ if(($dir == 0 || $dir == 4 || $dir == 5) && $row < $#puzzle);
	$row-- if(($dir == 1 || $dir == 6 || $dir == 7) && $row > 0);
	$col++ if(($dir == 3 || $dir == 5 || $dir == 7) && $col < $#puzzle);
	$col-- if(($dir == 2 || $dir == 4 || $dir == 6) && $col > 0);
	
	#Do the useful stuff:
	push(@gen, $puzzle[$row][$col]);
	return 1 if(&search($dir, $row, $col, \@puzzle, \@word, @gen)) || return 0;
}