Solve, time, and profile programs solving the N queens problem in various languages. Solution relies on built-in integer array types.

 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 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; ``````