Skip to content

Instantly share code, notes, and snippets.

@charlesreid1
Last active March 20, 2017 08:42
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save charlesreid1/4ce97a5f896ff1c89855a5d038d51535 to your computer and use it in GitHub Desktop.
Save charlesreid1/4ce97a5f896ff1c89855a5d038d51535 to your computer and use it in GitHub Desktop.
Solving the N queens problem using Perl. Implementing a verb-based approach.
#!/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;
#!/bin/sh
#
# Profile the N queens problem using Devel::NYTProf
#
# Install using cpanm:
# $ cpanm Devel::NYTProf
#
for N in 8 9 10 11 12
do
echo "**************************************"
echo "Profiling $N queens problem with Perl..."
# Update N
/usr/local/bin/sed -i "s/board_size = [0-9]\{1,\};/board_size = ${N};/g" nqueens.pl
echo "Running..."
/usr/local/bin/perl -d:NYTProf nqueens.pl
echo "Done."
# CSV contains interesting info
${HOME}/perl5/bin/nytprofcsv nytprof.out
## More information...
#${HOME}/perl5/bin/nytprofcg nytprof.out
#${HOME}/perl5/bin/nytprofhtml nytprof.out
mv nytprof nytprof${N}
done
#!/bin/sh
export OUT="timeout_queens_perl.out"
touch ${OUT}
cat /dev/null > ${OUT}
for N in 8 9 10 11 12 13 14 15
do
echo "**************************************" >> ${OUT}
echo "Running $N queens problem with Perl..." >> ${OUT}
# Update N
/usr/local/bin/sed -i "s/board_size = [0-9]\{1,\};/board_size = ${N};/g" nqueens.pl
# Semicolon is important here
echo "Running..."
{ time /usr/local/bin/perl nqueens.pl >> ${OUT}; } 2>> ${OUT}
echo "Done."
echo "" >> ${OUT}
done
**************************************
Running 8 queens problem with Perl...
Found 92 solutions
Execution time: 0.016 s
real 0m0.099s
user 0m0.035s
sys 0m0.007s
**************************************
Running 9 queens problem with Perl...
Found 352 solutions
Execution time: 0.067 s
real 0m0.091s
user 0m0.082s
sys 0m0.005s
**************************************
Running 10 queens problem with Perl...
Found 724 solutions
Execution time: 0.259 s
real 0m0.282s
user 0m0.273s
sys 0m0.006s
**************************************
Running 11 queens problem with Perl...
Found 2680 solutions
Execution time: 1.542 s
real 0m1.568s
user 0m1.544s
sys 0m0.008s
**************************************
Running 12 queens problem with Perl...
Found 14200 solutions
Execution time: 8.431 s
real 0m8.453s
user 0m8.388s
sys 0m0.020s
**************************************
Running 13 queens problem with Perl...
Found 73712 solutions
Execution time: 48.542 s
real 0m48.565s
user 0m48.236s
sys 0m0.076s
**************************************
Running 14 queens problem with Perl...
Found 365596 solutions
Execution time: 303.278 s
real 5m3.316s
user 5m0.398s
sys 0m0.508s
**************************************
Running 15 queens problem with Perl...
Found 2279184 solutions
Execution time: 2057.052 s
real 34m17.155s
user 33m25.661s
sys 0m5.936s
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment