Eight Queens problem

Eight Queens in Perl

This is a classic programming problem - place eight queens on a chessboard so that none of them can take each other. I wrote the program as an entry in [H]ard|Soft's inaugral programming contest.

Discussion

Quite simple, really. Just read the comments.

Solution

#!/usr/bin/perl -w

# start of N queens prog
$N=8;      # size of board & number of queens
$tot=0;    # total solutions found
$output=1; # if set to 1, output is of chessboard
           # if set to 0, output is simple values
           # if set to -1, output is skipped

# store the solution, in terms of the occupied row number (1-8) for each column
@sol=   (0)x$N;        

# rows that have been taken (0=unoccupied)
@rows=  (0)x$N;         

# diagonals that have been taken; these run from 
# bottom-left to top-right, and are numbered from 0
# so, the diagonal corresponding to cell $row,$col is 
# [$row+$col-2]
#again, 0 is unoccupied
@diags= (0)x($N*2-1);  

# reverse diagonals that have been taken; these run from top-right to bottom-left 
# so, the diagonal corresponding to cell $row,$col is [($N-$col)+$row-1]
# you guessed it - 0 is unoccupied
@rdiags=(0)x($N*2-1);  

$start=time;
place_queen(1);
$end=time;
print "Found $tot solutions in ",$end-$start,"sec\n";

# main work routine
sub place_queen {
  # get the column number we're trying to put a queen in
  # has to be local so we re-initialise it when backtracking
  local $col=shift;
  
  # loop over possible rows in this column
  foreach $row (1..$N) {
    # is this square valid? Check rows, diagonals,
    # and reverse diagonals.
    if (($rows[$row-1]==0) and 
        ($diags[$row+$col-2]==0) and 
        ($rdiags[($N-$col)+$row-1]==0) ) {

      # it is, so mark it as occupied
      $diags[$row+$col-2]++; 
      $rdiags[($N-$col)+$row-1]++; 
      $rows[$row-1]++;
      
      # record the solution
      $sol[$col-1] = $row;
      if ($col==$N) { 
        # that was the last column! 
        # dump out a solution
        print_solution(@sol) 
      } else { 
        # recursively call the next column
        place_queen($col+1) 
      }
      # things didn't work out, so clear 
      # the gubbins & backtrack
      $diags[$row+$col-2]-- ; 
      $rdiags[($N-$col)+$row-1]--; 
      $rows[$row-1]-- ;
    }
  }
}

sub print_solution {
  # track total solutions found
  $tot++;
  if ($output==1) { # pretty-print output mode
    for (@_) {
      print " " x ($_-1);
      print "X\n";
    }
    print "*"x$N,"\n";
  } elsif ($output==0) {      # simple output mode
    print join " ",@_, "\n"
  } 
}