I started working on a perl program to “solve” Sudoku puzzles. It's not really so much a solver as a way to learn about references, packages and Perl once again.

Here's what it does. It reads a puzzle from a text file. comments start with # and must be in column 0 so they match the pattern /^#/. The rest of the lines must contain 9 digits, 0 for an open space, 1-9 for an answered space.

Then the program builds a guess hash with several features:

• It has an underlaying data table with every possible answer (1-9) stored in a string for every cell.
• It makes list of lists (two dimensional array) of column references to the entire table so the program can easily “rip through” an entire column of answers removing possible answers.
• It makes a list of lists for the blocks. Each block is a 9 element array, containing references to the underlying data table. The idea is that you can quickly (and linearly) rip through a block list to remove any guesses that shouldn't be there.
• Finally, for consistency it makes a row major list of lists so that the guesses can be analyzed rowize and exactly the same way as the columns.

I think the piece of code I like the most is the one that prints all the guesses.

The following are code snipts Here's the current source: sodoku_src.txt And the puzzle text puzzle.txt.

###########################################################################
# Read Puzzle
#
###########################################################################
# ReadPuzzle
# reads a puzzle into an array 
# The puzzle is stored in puzzle.txt in the current folder.
# eventually it should return a 2 D 81 x 81 array.
# Params:
#	none	-- some day file name.
#
# Returns:
#	answerTable - 2D array with values for each cell.
#   		Note: row 0 contains a list with original puzzle text.
 
 
sub ReadPuzzle {
	# no args to start.
	open (FILE, "puzzle.txt");
 
	my @rawLines = <FILE>;		# slurp all the lines in the file.
 
	close(FILE);
 
	my $rowNum = 1;             # Row index
	my @answerTable = ();       # two D array
	my @eatLines = @rawLines;
	$answerTable[0] = \@rawLines;
 
	while (my $line = shift @eatLines) {
		# data is in $_
		chomp($line);               # remove new lines
		next if ($line =~ /^#/);	    # skip this line if it starts with hash
		my @values = (-1, split(//,$line)); # prepend -1 and break line into it's pieces.
		$answerTable[$rowNum++] = [ @values ];  # create a reference
	}
	return @answerTable;
}

###########################################################################
# Make Guess Table
#
###########################################################################
# MakeGuessTable
#
#	Eventually will be called by MakeGuessHash
#
# Params:
#	none	
#
# Returns:
#	guessTable -- an array of arrays.  Basically a 2D table where
#			each element is a scalar with a string of possible
#			answers 123456789.  A single value implies the answer
# 			is known.
#	
 
sub MakeGuessTable {
	my @guessRow = ();
	my @guessTable = ();
 
	for my $row (1..9) {
		for my $col (1..9) {
           $guessRow[$col] = "123456789";
		}
		$guessTable[$row] = [ @guessRow ]; # force creation of a reference
	}
	return @guessTable;
}

###########################################################################
# Make Guess Hash
#
###########################################################################
# MakeGuessHash
#
#	Creates multiple useful views of the guess table.
#	Creates:
#	COLVIEW - for walking columnwise through the array
#   ROWVIEW - for walking rowwise through the array
#   BLOCKVIEW - for walking through the 3x3 blocks
#	DATATABLE - The actual data.
#
# Params:
#	none	
#
# Returns:
#	guessHash -- A hash with references to tables that slice the data
#			in useful ways for trying to analyze a sudoku puzzle.
#	
sub MakeGuessHash {
	my %guessHash = {};				# name the empty hash
	my @colView = ();
	my @rowView = ();
	my @blockView = ();
	my @guessTable = MakeGuessTable;  # this is default row view
 
	$guessHash{DATATABLE} = \@guessTable;  # save the row view of the data

this next chunk of code is what creates the references to to the underlying data table.

	# now create column view of the data. column major.
	# note all of these MUST reference the same values as the row table
	# so modifying one view modifies the underlying data!
	for my $col (1..9) {
		my @colRefs = ();			# contain the verticle slices
		$colRefs[0] = "UNSOLVED";
		for my $row (1..9) {
			$colRefs[$row] = \$guessTable[$row][$col];
		}
		$colView[$col] = [ @colRefs ];	# add the column slice;
	}
	$guessHash{COLVIEW} = \@colView;	# add it to the hash.

	# for consistency create a row centric array of references.
	for my $row (1..9) {
		my @rowRefs = ();			# contain the horizontal slices
		$rowRefs[0] = "UNSOLVED";
		for my $col (1..9) {
			$rowRefs[$row] = \$guessTable[$row][$col];
		}
		$rowView[$row] = [ @rowRefs ];	# add the column slice;
	}
	$guessHash{ROWVIEW} = \@rowView;	# add it to the hash.

	# now the trickiest reference.  the blocks!
	# each block is a 3x3 grid, so like columns and rows
	# there are 9 lists containing 9 numbers.  But they are not
	# nicely broken up into slices.
	# block order is:
	# 		111222333
	# 		111222333
	# 		111222333
	# 		444555666
	# 		444555666
	# 		444555666
	# 		777888999
	# 		777888999	
	# 		777888999
	# this is potentially the most valuable list because it
	# converts a two dimensional block of numbers into a (hopefully) 
	# simple linear list.
 
	my $blockNum = 1;
 
	for my $rblock (0..2) {
		for my $cblock (0..2) {
			my $rbase = $rblock * 3;
			my $cbase = $cblock * 3;
			my $cellNum = 1;
			my @blockRefs = ();			# current block list of references
 
			for my $row (1..3) {
				for my $col (1..3) {
					$blockRefs[$cellNum++] = \$guessTable[$row+$rbase][$col+$cbase];
				}
			}
			$blockView[$blockNum++] = [ @blockRefs ];
		}
	}
 
	$guessHash{BLOCKVIEW} = \@blockView;	# add it to the hash.

	return %guessHash;
}

This is my favorite part. It's the report generator. It does stuff that's a little tricky. To correctly print the cubes it has to get 1/3 of each guess line across. So it has some substr() calls that are if not novel, make good use of the function.

And as I put this in here, I just noticed that the <9 characters guess case may look innefficient because it builds the substr on every pass - except, it has to do that because we grab accross the columns so it has to do it for every column.

###########################################################################
# Print Guesses
#
###########################################################################
# PrintGuesses
#
#	Given a GuessHash, this routine does the hardwork of formatting
#   the data for print out.
#   what makes this tricky is that we want to print each CELL
#   as a 3x3 text line.  That means... we have to get the first
#   text line of all row 1 data, then the second text line of 
#   all row 1 data, and finally the third text line of all 
#   row 1 data.  Then move on to row 2 data.
#
# Params:
#	guessHash - a valid Hash containing the guesses to print
#
# Returns:
#	none.  Just prints to STDOUT the guesses.
#	
 
sub PrintGuesses {
 
# first get the hash.
	my $hashRef = shift(@_);
 
	if (ref($hashRef) ne "HASH") {
		die "Expected a hash reference, not $hashRef\n";
	}
 
	my %guessHash = %$hashRef;
 
	my $dataRef = $guessHash{DATATABLE};
	my @dataTable = @$dataRef;			# make table easier to handle.
 
	for my $row (1..9) {
		for my $subRow (0..2) {
			my $outLine;
			my $subCell;
			for my $col (1..9) {
				my $cell = $dataTable[$row][$col];
				# now the cell data may contain very few characters...
				# so we have to build the line appropriate version
				if ( (length($cell) == 1) and $subCell ne "0") {
					# There's only one value so this must be an answer
					if ($subRow ne 1) {  # row's 0 and 2 are the same;
						$subCell = ".*.";
					} else {
						$subCell = "*".$cell."*";
					}
				} elsif ( length($cell) == 9 ) { #sort of a default simple case 
					$subCell = substr($cell,$subRow*3,3);
				} else { # we have >1 and <9 digits... need to fill in blanks
					$subCell = ".........";
					my @digits = split(//,$cell);
					for my $d (0..$#digits) {
						substr($subCell,$digits[$d]-1,1) = $digits[$d]; # subStr is assignable!  Perl is weird.
					}
					$subCell = substr($subCell,$subRow*3,3);  # now only keep the pieces we need;
				}
				$outLine .= $subCell;
				$outLine .= " ";  # just a bit o space
			}
			print $outLine, "\n";
		}
#		print "\n";
	}
	return 0;
 
}