Instantly share code, notes, and snippets.

charlesreid1/nqueens.pl Last active Mar 20, 2017

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