Last active
March 20, 2017 08:42
-
-
Save charlesreid1/4ce97a5f896ff1c89855a5d038d51535 to your computer and use it in GitHub Desktop.
Solving the N queens problem using Perl. Implementing a verb-based approach.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#!/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; |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#!/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 |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#!/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 |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
************************************** | |
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