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

nqueens.pl 2.9KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120
  1. #!/usr/local/bin/perl
  2. use Time::HiRes qw(time);
  3. use strict;
  4. use warnings;
  5. my $start = time;
  6. ######################################
  7. ########## N Queens Puzzle ###########
  8. #
  9. #
  10. # The 8 queens problem is to place 8 queens on a chessboard
  11. # such that no queen attacks any other queen.
  12. #
  13. # In 1972, Dijkstra published the first depth-first
  14. # backtracking algorithm to solve the problem.
  15. #
  16. # This file implements a recursive backtracking algorithm
  17. # to find solutions to the N queens problem.
  18. #
  19. # This requires a way of choosing queens,
  20. # and a way to check if a configuration is valid (as we go).
  21. # The backtracking algorithm recursively calls a method
  22. # to place one queen at a time, 8 times.
  23. # When there are no more choices left to make, it has reached a leaf,
  24. # and it stores (or prints out) a solution.
  25. #
  26. # Modified and expanded from http://rosettacode.org/wiki/N-queens_problem#Perl
  27. # Create an array to store solutions
  28. my @solutions;
  29. # Create an array to store where queens have been placed
  30. my @queens;
  31. # Mark the rows already used (useful for lookup)
  32. my @occupied;
  33. # Size of board
  34. my $board_size;
  35. # explore() implements a recursive, depth-first backtracking method
  36. sub explore {
  37. # Parameters:
  38. # depth : this is the argument passed by the user
  39. # First argument passed to the function is $depth
  40. # (how many queens we've placed on the board),
  41. # so use shift to pop that out of the parameters
  42. my ($depth, @attacked) = shift;
  43. # Explore is a recursive method,
  44. # so we need a base case and a recursive case.
  45. #
  46. # The base case is, we've reached a leaf node,
  47. # placed 8 queens, and had no problems,
  48. # so we found a solution.
  49. if ($depth==$board_size) {
  50. # Here, we store the stringified version of @queens,
  51. # which are the row numbers of prior queens.
  52. # This is a global variable that is shared across
  53. # instances of this recursive function.
  54. push @solutions, "@queens\n";
  55. return;
  56. }
  57. ##################################
  58. # Method 1
  59. #
  60. # Mark the squares that are attackable,
  61. # so that we can cut down on the search space.
  62. my($ix1, $ix2);
  63. $#attacked = 2 * $board_size;
  64. for( 0 .. $#queens) {
  65. $ix1 = $queens[$_] + $depth - $_ ;
  66. $attacked[ $ix1 ] = 1;
  67. $ix2 = $queens[$_] - $depth + $_ ;
  68. $attacked[ $ix2 ] = 1;
  69. }
  70. #
  71. ####################################
  72. for my $row (0 .. $board_size-1) {
  73. # Cut down on the search space:
  74. # if this square is already occupied
  75. # or will lead to an invalid solution,
  76. # don't bother exploring it.
  77. next if $occupied[$row] || $attacked[$row];
  78. # Make a choice
  79. push @queens, $row;
  80. # Mark the square as occupied
  81. $occupied[$row] = 1;
  82. # Explore the consequences
  83. explore($depth+1);
  84. # Unmake the choice
  85. pop @queens;
  86. # Mark the square as unoccupied
  87. $occupied[$row] = 0;
  88. }
  89. }
  90. $board_size = 11;
  91. explore(0);
  92. my $duration = time - $start;
  93. print "Found ", scalar(@solutions), " solutions\n";
  94. printf "Execution time: %0.3f s \n",$duration;