Skip to main content

Posts

Showing posts from October, 2010

Sudoku in Perl5 #2 - Optimizing the Perl5 implementation

The test in BruteForceTest irritated me .. iterating across the whole row, testing each cell to see if it was the cell we didn't want to test against. And same for each row of the column, and each cell of the block. All those repeated tests must add up to a lot of wasted time, right?

So I came up with BruteForceRange, which doesn't iterate over the whole row, only the portions to the left and right of the current cell. In the column, it iterates over the cells above and below ... the block test is more complicated, we'll get to it.

The program is mostly the same as BruteForceTest. The first difference is the name changes:

package BruteForceRange;

Instead of specifying 0..8 for the row or column for loop ...

for my $c ( 0 .. 8 ) {
next CELL # don't test against self.
if $c == $col;

the new version specifies a portion to the left, and a portion to the right. This is possible because ranges in Perl must increment, a left boundary greater than the right…

Sudoku in Perl5 #1 - a brute-force solution

Having written the Perl6 Sudoku solver, I decided to go back to the Perl5 version I wrote when I was experimenting with Moose, but I couldn't find where I put it. While waiting for my senile memory to function, I implemented a brute-force solution. The basic concept of the brute-force approach is that you begin with a grid, some cells of which have been defined by the puzzle designer. I begin with the first empty cell ( call it A) and set it to '1'. I check to see if that conflicts with any already specified cells in the same row, in the same column, in the same block. If there's a conflict, I try the next element in the list of possible values : 2, 3..9. If a value does not conflict with existing cells, then on to the next cell. If all values create a conflict, then an earlier cell must have the wrong value, so back up. By recursively calling a routine over and over, backing up is easy, just return. If we run out of cells to the right, advance to the next row; when we…

Niagara Escarpment Autumn Photos