123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120 
 #!/usr/local/bin/perl
 use Time::HiRes qw(time);
 use strict;
 use warnings;
 my $start = time;

 ######################################
 ########## N Queens Puzzle ###########
 #
 #
 # The 8 queens problem is to place 8 queens on a chessboard
 # such that no queen attacks any other queen.
 #
 # In 1972, Dijkstra published the first depthfirst
 # backtracking algorithm to solve the problem.
 #
 # This file implements a recursive backtracking algorithm
 # to find solutions to the N queens problem.
 #
 # This requires a way of choosing queens,
 # and a way to check if a configuration is valid (as we go).
 # The backtracking algorithm recursively calls a method
 # to place one queen at a time, 8 times.
 # When there are no more choices left to make, it has reached a leaf,
 # and it stores (or prints out) a solution.
 #
 # Modified and expanded from http://rosettacode.org/wiki/Nqueens_problem#Perl

 # Create an array to store solutions
 my @solutions;

 # Create an array to store where queens have been placed
 my @queens;

 # Mark the rows already used (useful for lookup)
 my @occupied;

 # Size of board
 my $board_size;


 # explore() implements a recursive, depthfirst backtracking method
 sub explore {
 # Parameters:
 # depth : this is the argument passed by the user

 # First argument passed to the function is $depth
 # (how many queens we've placed on the board),
 # so use shift to pop that out of the parameters
 my ($depth, @attacked) = shift;

 # Explore is a recursive method,
 # so we need a base case and a recursive case.
 #
 # The base case is, we've reached a leaf node,
 # placed 8 queens, and had no problems,
 # so we found a solution.
 if ($depth==$board_size) {
 # Here, we store the stringified version of @queens,
 # which are the row numbers of prior queens.
 # This is a global variable that is shared across
 # instances of this recursive function.
 push @solutions, "@queens\n";
 return;
 }


 ##################################
 # Method 1
 #
 # Mark the squares that are attackable,
 # so that we can cut down on the search space.
 my($ix1, $ix2);
 $#attacked = 2 * $board_size;
 for( 0 .. $#queens) {
 $ix1 = $queens[$_] + $depth  $_ ;
 $attacked[ $ix1 ] = 1;

 $ix2 = $queens[$_]  $depth + $_ ;
 $attacked[ $ix2 ] = 1;
 }
 #
 ####################################


 for my $row (0 .. $board_size1) {
 # Cut down on the search space:
 # if this square is already occupied
 # or will lead to an invalid solution,
 # don't bother exploring it.
 next if $occupied[$row]  $attacked[$row];

 # Make a choice
 push @queens, $row;
 # Mark the square as occupied
 $occupied[$row] = 1;

 # Explore the consequences
 explore($depth+1);

 # Unmake the choice
 pop @queens;

 # Mark the square as unoccupied
 $occupied[$row] = 0;

 }
 }

 $board_size = 11;

 explore(0);

 my $duration = time  $start;

 print "Found ", scalar(@solutions), " solutions\n";
 printf "Execution time: %0.3f s \n",$duration;


