in-class-exercise.sh

# Sort by total time, in descending order
cat profiler_output_nqueens.csv | sort -n -r 

# Sort by time per call (third column in file), in descending order
# -d "," means use "," as a field (column) delimiter
# -f 3,4 means grab fields (columns) 3 and 4
cat profiler_output_nqueens.csv | cut -d "," -f 3,4 | sort -n -r

n-queens.pl

#!/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 depth-first
# 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/N-queens_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, depth-first 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_size-1) {
		# 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;

profiler_output_nqueens.csv

# Profile data generated by Devel::NYTProf::Reader
# Version: v6.04
# More information at http://metacpan.org/release/Devel-NYTProf/
# Format: time,calls,time/call,code
0.000000,0,0.000000,#!/usr/local/bin/perl
0.000238,2,0.000119,use Time::HiRes qw(time);
0.000039,2,0.000019,use strict;
0.000491,2,0.000246,use warnings;
0.000021,1,0.000021,my $start = time;
0.000000,0,0.000000,
0.000000,0,0.000000,######################################
0.000000,0,0.000000,########## N Queens Puzzle ###########
0.000000,0,0.000000,#
0.000000,0,0.000000,#
0.000000,0,0.000000,# The 8 queens problem is to place 8 queens on a chessboard
0.000000,0,0.000000,# such that no queen attacks any other queen.
0.000000,0,0.000000,#
0.000000,0,0.000000,# In 1972, Dijkstra published the first depth-first
0.000000,0,0.000000,# backtracking algorithm to solve the problem.
0.000000,0,0.000000,#
0.000000,0,0.000000,# This file implements a recursive backtracking algorithm
0.000000,0,0.000000,# to find solutions to the N queens problem.
0.000000,0,0.000000,#
0.000000,0,0.000000,# This requires a way of choosing queens,
0.000000,0,0.000000,# and a way to check if a configuration is valid (as we go).
0.000000,0,0.000000,# The backtracking algorithm recursively calls a method
0.000000,0,0.000000,# to place one queen at a time, 8 times.
0.000000,0,0.000000,# When there are no more choices left to make, it has reached a leaf,
0.000000,0,0.000000,# and it stores (or prints out) a solution.
0.000000,0,0.000000,#
0.000000,0,0.000000,# Modified and expanded from http://rosettacode.org/wiki/N-queens_problem#Perl
0.000000,0,0.000000,
0.000000,0,0.000000,# Create an array to store solutions
0.000000,1,0.000000,my @solutions;
0.000000,0,0.000000,
0.000000,0,0.000000,# Create an array to store where queens have been placed
0.000000,0,0.000000,my @queens;
0.000000,0,0.000000,
0.000000,0,0.000000,# Mark the rows already used (useful for lookup)
0.000000,0,0.000000,my @occupied;
0.000000,0,0.000000,
0.000000,0,0.000000,# Size of board
0.000000,0,0.000000,my $board_size;
0.000000,0,0.000000,
0.000000,0,0.000000,
0.000000,0,0.000000,# explore() implements a recursive, depth-first backtracking method
0.000000,0,0.000000,sub explore {
0.000000,0,0.000000,# Parameters:
0.000000,0,0.000000,#	depth : this is the argument passed by the user
0.000000,0,0.000000,
0.000000,0,0.000000,# First argument passed to the function is $depth
0.000000,0,0.000000,# (how many queens we've placed on the board),
0.000000,0,0.000000,# so use shift to pop that out of the parameters
0.082965,166926,0.000000,my ($depth, @attacked) = shift;
0.000000,0,0.000000,
0.000000,0,0.000000,# Explore is a recursive method,
0.000000,0,0.000000,# so we need a base case and a recursive case.
0.000000,0,0.000000,#
0.000000,0,0.000000,# The base case is, we've reached a leaf node,
0.000000,0,0.000000,# placed 8 queens, and had no problems,
0.000000,0,0.000000,# so we found a solution.
0.033458,166926,0.000000,if ($depth==$board_size) {
0.000000,0,0.000000,# Here, we store the stringified version of @queens,
0.000000,0,0.000000,# which are the row numbers of prior queens.
0.000000,0,0.000000,# This is a global variable that is shared across
0.000000,0,0.000000,# instances of this recursive function.
0.010338,2680,0.000004,push @solutions, "@queens\n";
0.009993,2680,0.000004,return;
0.000000,0,0.000000,}
0.000000,0,0.000000,
0.000000,0,0.000000,
0.000000,0,0.000000,##################################
0.000000,0,0.000000,# Method 1
0.000000,0,0.000000,#
0.000000,0,0.000000,# Mark the squares that are attackable,
0.000000,0,0.000000,# so that we can cut down on the search space.
0.022082,164246,0.000000,my($ix1, $ix2);
0.186298,164246,0.000001,$#attacked = 2 * $board_size;
0.150338,164246,0.000001,for( 0 .. $#queens) {
0.299961,1.26035e+06,0.000000,$ix1 = $queens[$_] + $depth - $_ ;
0.282226,1.26035e+06,0.000000,$attacked[ $ix1 ] = 1;
0.000000,0,0.000000,
0.270200,1.26035e+06,0.000000,$ix2 = $queens[$_] - $depth + $_ ;
0.675523,1.26035e+06,0.000001,$attacked[ $ix2 ] = 1;
0.000000,0,0.000000,}
0.000000,0,0.000000,#
0.000000,0,0.000000,####################################
0.000000,0,0.000000,
0.000000,0,0.000000,
1.242624,164246,0.000008,for my $row (0 .. $board_size-1) {
0.000000,0,0.000000,# Cut down on the search space:
0.000000,0,0.000000,# if this square is already occupied
0.000000,0,0.000000,# or will lead to an invalid solution,
0.000000,0,0.000000,# don't bother exploring it.
0.407482,1.80671e+06,0.000000,next if $occupied[$row] || $attacked[$row];
0.000000,0,0.000000,
0.000000,0,0.000000,# Make a choice
0.044824,166925,0.000000,push @queens, $row;
0.000000,0,0.000000,# Mark the square as occupied
0.037519,166925,0.000000,$occupied[$row] = 1;
0.000000,0,0.000000,
0.000000,0,0.000000,# Explore the consequences
0.267469,166925,0.000002,explore($depth+1);
0.000000,0,0.000000,
0.000000,0,0.000000,# Unmake the choice
0.046910,166925,0.000000,pop @queens;
0.000000,0,0.000000,
0.000000,0,0.000000,# Mark the square as unoccupied
0.125272,166925,0.000001,$occupied[$row] = 0;
0.000000,0,0.000000,
0.000000,0,0.000000,}
0.000000,0,0.000000,}
0.000000,0,0.000000,
0.000000,1,0.000000,$board_size = 11;
0.000000,0,0.000000,
0.000002,1,0.000002,explore(0);
0.000000,0,0.000000,
0.000011,1,0.000011,my $duration = time - $start;
0.000000,0,0.000000,
0.000075,1,0.000075,print "Found ", scalar(@solutions), " solutions\n";
0.000050,1,0.000050,printf "Execution time: %0.3f s \n",$duration;
0.000000,0,0.000000,
0.000000,0,0.000000,