Perl-Sensitive Sunglasses PerlMonks

Solving the Eight Queens problem

by liverpole (Monsignor)
 on Dec 26, 2005 at 17:10 UTC ( #519169=CUFP: print w/replies, xml ) Need Help??

I've been working on creating a data structure in Perl to hold all legal chess moves, as a prerequisite for building a "Chess Problem Generator".  It's implemented as an HoHoAoA, with each key a different piece and each subhash key a single square on the board.  (I should point out that the data structure isn't complete (eg. castles, en-passant moves, and promotions aren't taken into account), but it contains everything else).

It occurred to me this morning that I could use the data structure to solve the "Eight Queens" problem of chess, whereby 8 queens must be placed on a chessboard in such a way that no queen is under attack by any other queen.  Using a brute force method where each valid position is tried (but as soon as a given queen attacks one of the already-placed queens, no further queens are attempted for that configuration), the entire set of solutions can quickly be generated.

I erroneously thought there were only 8 or so solutions, but to my surprise, there's a total of 92!  I was off by an order of magnitude!  Doing a 'google' of "8 queens problem" verifies that this is the correct answer; which makes me more sure that I haven't made a mistake with the original data structure.  (As a side note, once I had generated the bishop and rook moves, the queen moves were simply the combination of the two).

Here is the data structure (I've omitted all but the queen moves for brevity), which goes in a file called "Legal.pm":

```package Legal;

my \$p_legal_moves = {
'q' => {
'a1' => [
[ qw( b2 c3 d4 e5 f6 g7 h8 ) ],
[ qw( a2 a3 a4 a5 a6 a7 a8 ) ],
[ qw( b1 c1 d1 e1 f1 g1 h1 ) ],
],
'a2' => [
[ qw( b3 c4 d5 e6 f7 g8 ) ],
[ qw( b1 ) ],
[ qw( a3 a4 a5 a6 a7 a8 ) ],
[ qw( a1 ) ],
[ qw( b2 c2 d2 e2 f2 g2 h2 ) ],
],
'a3' => [
[ qw( b4 c5 d6 e7 f8 ) ],
[ qw( b2 c1 ) ],
[ qw( a4 a5 a6 a7 a8 ) ],
[ qw( b3 c3 d3 e3 f3 g3 h3 ) ],
[ qw( a2 a1 ) ],
],
'a4' => [
[ qw( b5 c6 d7 e8 ) ],
[ qw( b3 c2 d1 ) ],
[ qw( a5 a6 a7 a8 ) ],
[ qw( b4 c4 d4 e4 f4 g4 h4 ) ],
[ qw( a3 a2 a1 ) ],
],
'a5' => [
[ qw( b6 c7 d8 ) ],
[ qw( b4 c3 d2 e1 ) ],
[ qw( a6 a7 a8 ) ],
[ qw( b5 c5 d5 e5 f5 g5 h5 ) ],
[ qw( a4 a3 a2 a1 ) ],
],
'a6' => [
[ qw( b7 c8 ) ],
[ qw( b5 c4 d3 e2 f1 ) ],
[ qw( a7 a8 ) ],
[ qw( b6 c6 d6 e6 f6 g6 h6 ) ],
[ qw( a5 a4 a3 a2 a1 ) ],
],
'a7' => [
[ qw( b8 ) ],
[ qw( b6 c5 d4 e3 f2 g1 ) ],
[ qw( a8 ) ],
[ qw( b7 c7 d7 e7 f7 g7 h7 ) ],
[ qw( a6 a5 a4 a3 a2 a1 ) ],
],
'a8' => [
[ qw( b7 c6 d5 e4 f3 g2 h1 ) ],
[ qw( b8 c8 d8 e8 f8 g8 h8 ) ],
[ qw( a7 a6 a5 a4 a3 a2 a1 ) ],
],
'b1' => [
[ qw( a2 ) ],
[ qw( c2 d3 e4 f5 g6 h7 ) ],
[ qw( a1 ) ],
[ qw( b2 b3 b4 b5 b6 b7 b8 ) ],
[ qw( c1 d1 e1 f1 g1 h1 ) ],
],
'b2' => [
[ qw( a3 ) ],
[ qw( c3 d4 e5 f6 g7 h8 ) ],
[ qw( c1 ) ],
[ qw( a1 ) ],
[ qw( a2 ) ],
[ qw( b3 b4 b5 b6 b7 b8 ) ],
[ qw( c2 d2 e2 f2 g2 h2 ) ],
[ qw( b1 ) ],
],
'b3' => [
[ qw( a4 ) ],
[ qw( c4 d5 e6 f7 g8 ) ],
[ qw( c2 d1 ) ],
[ qw( a2 ) ],
[ qw( a3 ) ],
[ qw( b4 b5 b6 b7 b8 ) ],
[ qw( c3 d3 e3 f3 g3 h3 ) ],
[ qw( b2 b1 ) ],
],
'b4' => [
[ qw( a5 ) ],
[ qw( c5 d6 e7 f8 ) ],
[ qw( c3 d2 e1 ) ],
[ qw( a3 ) ],
[ qw( a4 ) ],
[ qw( b5 b6 b7 b8 ) ],
[ qw( c4 d4 e4 f4 g4 h4 ) ],
[ qw( b3 b2 b1 ) ],
],
'b5' => [
[ qw( a6 ) ],
[ qw( c6 d7 e8 ) ],
[ qw( c4 d3 e2 f1 ) ],
[ qw( a4 ) ],
[ qw( a5 ) ],
[ qw( b6 b7 b8 ) ],
[ qw( c5 d5 e5 f5 g5 h5 ) ],
[ qw( b4 b3 b2 b1 ) ],
],
'b6' => [
[ qw( a7 ) ],
[ qw( c7 d8 ) ],
[ qw( c5 d4 e3 f2 g1 ) ],
[ qw( a5 ) ],
[ qw( a6 ) ],
[ qw( b7 b8 ) ],
[ qw( c6 d6 e6 f6 g6 h6 ) ],
[ qw( b5 b4 b3 b2 b1 ) ],
],
'b7' => [
[ qw( a8 ) ],
[ qw( c8 ) ],
[ qw( c6 d5 e4 f3 h1 ) ],
[ qw( a6 ) ],
[ qw( a7 ) ],
[ qw( b8 ) ],
[ qw( c7 d7 e7 f7 g7 h7 ) ],
[ qw( b6 b5 b4 b3 b2 b1 ) ],
],
'b8' => [
[ qw( c7 d6 e5 f4 g3 h2 ) ],
[ qw( a7 ) ],
[ qw( a8 ) ],
[ qw( c8 d8 e8 f8 g8 h8 ) ],
[ qw( b7 b6 b5 b4 b3 b2 b1 ) ],
],
'c1' => [
[ qw( b2 a3 ) ],
[ qw( d2 e3 f4 g5 h6 ) ],
[ qw( b1 a1 ) ],
[ qw( c2 c3 c4 c5 c6 c7 c8 ) ],
[ qw( d1 e1 f1 g1 h1 ) ],
],
'c2' => [
[ qw( b3 a4 ) ],
[ qw( d3 e4 f5 g6 h7 ) ],
[ qw( d1 ) ],
[ qw( b1 ) ],
[ qw( b2 a2 ) ],
[ qw( c3 c4 c5 c6 c7 c8 ) ],
[ qw( d2 e2 f2 g2 h2 ) ],
[ qw( c1 ) ],
],
'c3' => [
[ qw( b4 a5 ) ],
[ qw( d4 e5 f6 g7 h8 ) ],
[ qw( d2 e1 ) ],
[ qw( b2 a1 ) ],
[ qw( b3 a3 ) ],
[ qw( c4 c5 c6 c7 c8 ) ],
[ qw( d3 e3 f3 g3 h3 ) ],
[ qw( c2 c1 ) ],
],
'c4' => [
[ qw( b5 a6 ) ],
[ qw( d5 e6 f7 g8 ) ],
[ qw( d3 e2 f1 ) ],
[ qw( b3 a2 ) ],
[ qw( b4 a4 ) ],
[ qw( c5 c6 c7 c8 ) ],
[ qw( d4 e4 f4 g4 h4 ) ],
[ qw( c3 c2 c1 ) ],
],
'c5' => [
[ qw( b6 a7 ) ],
[ qw( d6 e7 f8 ) ],
[ qw( d4 e3 f2 g1 ) ],
[ qw( b4 a3 ) ],
[ qw( b5 a5 ) ],
[ qw( c6 c7 c8 ) ],
[ qw( d5 e5 f5 g5 h5 ) ],
[ qw( c4 c3 c2 c1 ) ],
],
'c6' => [
[ qw( b7 a8 ) ],
[ qw( d7 e8 ) ],
[ qw( d5 e4 f3 g2 h1 ) ],
[ qw( b5 a4 ) ],
[ qw( b6 a6 ) ],
[ qw( c7 c8 ) ],
[ qw( d6 e6 f6 g6 h6 ) ],
[ qw( c5 c4 c3 c2 c1 ) ],
],
'c7' => [
[ qw( b8 ) ],
[ qw( d8 ) ],
[ qw( d6 e5 f4 g3 h2 ) ],
[ qw( b6 a5 ) ],
[ qw( b7 a7 ) ],
[ qw( c8 ) ],
[ qw( d7 e7 f7 g7 h7 ) ],
[ qw( c6 c5 c4 c3 c2 c1 ) ],
],
'c8' => [
[ qw( d7 e6 f5 g4 h3 ) ],
[ qw( b7 a6 ) ],
[ qw( b8 a8 ) ],
[ qw( d8 e8 f8 g8 h8 ) ],
[ qw( c7 c6 c5 c4 c3 c2 c1 ) ],
],
'd1' => [
[ qw( c2 b3 a4 ) ],
[ qw( e2 f3 g4 h5 ) ],
[ qw( c1 b1 a1 ) ],
[ qw( d2 d3 d4 d5 d6 d7 d8 ) ],
[ qw( e1 f1 g1 h1 ) ],
],
'd2' => [
[ qw( c3 b4 a5 ) ],
[ qw( e3 f4 g5 h6 ) ],
[ qw( e1 ) ],
[ qw( c1 ) ],
[ qw( c2 b2 a2 ) ],
[ qw( d3 d4 d5 d6 d7 d8 ) ],
[ qw( e2 f2 g2 h2 ) ],
[ qw( d1 ) ],
],
'd3' => [
[ qw( c4 b5 a6 ) ],
[ qw( e4 f5 g6 h7 ) ],
[ qw( e2 f1 ) ],
[ qw( c2 b1 ) ],
[ qw( c3 b3 a3 ) ],
[ qw( d4 d5 d6 d7 d8 ) ],
[ qw( e3 f3 g3 h3 ) ],
[ qw( d2 d1 ) ],
],
'd4' => [
[ qw( c5 b6 a7 ) ],
[ qw( e5 f6 g7 h8 ) ],
[ qw( e3 f2 g1 ) ],
[ qw( c3 b2 a1 ) ],
[ qw( c4 b4 a4 ) ],
[ qw( d5 d6 d7 d8 ) ],
[ qw( e4 f4 g4 h4 ) ],
[ qw( d3 d2 d1 ) ],
],
'd5' => [
[ qw( c6 b7 a8 ) ],
[ qw( e6 f7 g8 ) ],
[ qw( e4 f3 g2 h1 ) ],
[ qw( c4 b3 a2 ) ],
[ qw( c5 b5 a5 ) ],
[ qw( d6 d7 d8 ) ],
[ qw( e5 f5 g5 h5 ) ],
[ qw( d4 d3 d2 d1 ) ],
],
'd6' => [
[ qw( c7 b8 ) ],
[ qw( e7 f8 ) ],
[ qw( e5 f4 g3 h2 ) ],
[ qw( c5 b4 a3 ) ],
[ qw( c6 b6 a6 ) ],
[ qw( d7 d8 ) ],
[ qw( e6 f6 g6 h6 ) ],
[ qw( d5 d4 d3 d2 d1 ) ],
],
'd7' => [
[ qw( c8 ) ],
[ qw( e8 ) ],
[ qw( e6 f5 g4 h3 ) ],
[ qw( c6 b5 a4 ) ],
[ qw( c7 b7 a7 ) ],
[ qw( d8 ) ],
[ qw( e7 f7 g7 h7 ) ],
[ qw( d6 d5 d4 d3 d2 d1 ) ],
],
'd8' => [
[ qw( e7 f6 g5 h4 ) ],
[ qw( c7 b6 a5 ) ],
[ qw( c8 b8 a8 ) ],
[ qw( e8 f8 g8 h8 ) ],
[ qw( d7 d6 d5 d4 d3 d2 d1 ) ],
],
'e1' => [
[ qw( d2 c3 b4 a5 ) ],
[ qw( f2 g3 h4 ) ],
[ qw( d1 c1 b1 a1 ) ],
[ qw( e2 e3 e4 e5 e6 e7 e8 ) ],
[ qw( f1 g1 h1 ) ],
],
'e2' => [
[ qw( d3 c4 b5 a6 ) ],
[ qw( f3 g4 h5 ) ],
[ qw( f1 ) ],
[ qw( d1 ) ],
[ qw( d2 c2 b2 a2 ) ],
[ qw( e3 e4 e5 e6 e7 e8 ) ],
[ qw( f2 g2 h2 ) ],
[ qw( e1 ) ],
],
'e3' => [
[ qw( d4 c5 b6 a7 ) ],
[ qw( f4 g5 h6 ) ],
[ qw( f2 g1 ) ],
[ qw( d2 c1 ) ],
[ qw( d3 c3 b3 a3 ) ],
[ qw( e4 e5 e6 e7 e8 ) ],
[ qw( f3 g3 h3 ) ],
[ qw( e2 e1 ) ],
],
'e4' => [
[ qw( d5 c6 b7 a8 ) ],
[ qw( f5 g6 h7 ) ],
[ qw( f3 g2 h1 ) ],
[ qw( d3 c2 b1 ) ],
[ qw( d4 c4 b4 a4 ) ],
[ qw( e5 e6 e7 e8 ) ],
[ qw( f4 g4 h4 ) ],
[ qw( e3 e2 e1 ) ],
],
'e5' => [
[ qw( d6 c7 b8 ) ],
[ qw( f6 g7 h8 ) ],
[ qw( f4 g3 h2 ) ],
[ qw( d4 c3 b2 a1 ) ],
[ qw( d5 c5 b5 a5 ) ],
[ qw( e6 e7 e8 ) ],
[ qw( f5 g5 h5 ) ],
[ qw( e4 e3 e2 e1 ) ],
],
'e6' => [
[ qw( d7 c8 ) ],
[ qw( f7 g8 ) ],
[ qw( f5 g4 h3 ) ],
[ qw( d5 c4 b3 a2 ) ],
[ qw( d6 c6 b6 a6 ) ],
[ qw( e7 e8 ) ],
[ qw( f6 g6 h6 ) ],
[ qw( e5 e4 e3 e2 e1 ) ],
],
'e7' => [
[ qw( d8 ) ],
[ qw( f8 ) ],
[ qw( f6 g5 h4 ) ],
[ qw( d6 c5 b4 a3 ) ],
[ qw( d7 c7 b7 a7 ) ],
[ qw( e8 ) ],
[ qw( f7 g7 h7 ) ],
[ qw( e6 e5 e4 e3 e2 e1 ) ],
],
'e8' => [
[ qw( f7 g6 h5 ) ],
[ qw( d7 c6 b5 a4 ) ],
[ qw( d8 c8 b8 a8 ) ],
[ qw( f8 g8 h8 ) ],
[ qw( e7 e6 e5 e4 e3 e2 e1 ) ],
],
'f1' => [
[ qw( e2 d3 c4 b5 a6 ) ],
[ qw( g2 h3 ) ],
[ qw( e1 d1 c1 b1 a1 ) ],
[ qw( f2 f3 f4 f5 f6 f7 f8 ) ],
[ qw( g1 h1 ) ],
],
'f2' => [
[ qw( e3 d4 c5 b6 a7 ) ],
[ qw( g3 h4 ) ],
[ qw( g1 ) ],
[ qw( e1 ) ],
[ qw( e2 d2 c2 b2 a2 ) ],
[ qw( f3 f4 f5 f6 f7 f8 ) ],
[ qw( g2 h2 ) ],
[ qw( f1 ) ],
],
'f3' => [
[ qw( e4 d5 c6 b7 a8 ) ],
[ qw( g4 h5 ) ],
[ qw( g2 h1 ) ],
[ qw( e2 d1 ) ],
[ qw( e3 d3 c3 b3 a3 ) ],
[ qw( f4 f5 f6 f7 f8 ) ],
[ qw( g3 h3 ) ],
[ qw( f2 f1 ) ],
],
'f4' => [
[ qw( e5 d6 c7 b8 ) ],
[ qw( g5 h6 ) ],
[ qw( g3 h2 ) ],
[ qw( e3 d2 c1 ) ],
[ qw( e4 d4 c4 b4 a4 ) ],
[ qw( f5 f6 f7 f8 ) ],
[ qw( g4 h4 ) ],
[ qw( f3 f2 f1 ) ],
],
'f5' => [
[ qw( e6 d7 c8 ) ],
[ qw( g6 h7 ) ],
[ qw( g4 h3 ) ],
[ qw( e4 d3 c2 b1 ) ],
[ qw( e5 d5 c5 b5 a5 ) ],
[ qw( f6 f7 f8 ) ],
[ qw( g5 h5 ) ],
[ qw( f4 f3 f2 f1 ) ],
],
'f6' => [
[ qw( e7 d8 ) ],
[ qw( g7 h8 ) ],
[ qw( g5 h4 ) ],
[ qw( e5 d4 c3 b2 a1 ) ],
[ qw( e6 d6 c6 b6 a6 ) ],
[ qw( f7 f8 ) ],
[ qw( g6 h6 ) ],
[ qw( f5 f4 f3 f2 f1 ) ],
],
'f7' => [
[ qw( e8 ) ],
[ qw( g8 ) ],
[ qw( g6 h5 ) ],
[ qw( e6 d5 c4 b3 a2 ) ],
[ qw( e7 d7 c7 b7 a7 ) ],
[ qw( f8 ) ],
[ qw( g7 h7 ) ],
[ qw( f6 f5 f4 f3 f2 f1 ) ],
],
'f8' => [
[ qw( g7 h6 ) ],
[ qw( e7 d6 c5 b4 a3 ) ],
[ qw( e8 d8 c8 b8 a8 ) ],
[ qw( g8 h8 ) ],
[ qw( f7 f6 f5 f4 f3 f2 f1 ) ],
],
'g1' => [
[ qw( f2 e3 d4 c5 b6 a7 ) ],
[ qw( h2 ) ],
[ qw( f1 e1 d1 c1 b1 a1 ) ],
[ qw( g2 g3 g4 g5 g6 g7 g8 ) ],
[ qw( h1 ) ],
],
'g2' => [
[ qw( f3 e4 d5 c6 b7 a8 ) ],
[ qw( h3 ) ],
[ qw( h1 ) ],
[ qw( f1 ) ],
[ qw( f2 e2 d2 c2 b2 a2 ) ],
[ qw( g3 g4 g5 g6 g7 g8 ) ],
[ qw( h2 ) ],
[ qw( g1 ) ],
],
'g3' => [
[ qw( f4 e5 d6 c7 b8 ) ],
[ qw( h4 ) ],
[ qw( h2 ) ],
[ qw( f2 e1 ) ],
[ qw( f3 e3 d3 c3 b3 a3 ) ],
[ qw( g4 g5 g6 g7 g8 ) ],
[ qw( h3 ) ],
[ qw( g2 g1 ) ],
],
'g4' => [
[ qw( f5 e6 d7 c8 ) ],
[ qw( h5 ) ],
[ qw( h3 ) ],
[ qw( f3 e2 d1 ) ],
[ qw( f4 e4 d4 c4 b4 a4 ) ],
[ qw( g5 g6 g7 g8 ) ],
[ qw( h4 ) ],
[ qw( g3 g2 g1 ) ],
],
'g5' => [
[ qw( f6 e7 d8 ) ],
[ qw( h6 ) ],
[ qw( h4 ) ],
[ qw( f4 e3 d2 c1 ) ],
[ qw( f5 e5 d5 c5 b5 a5 ) ],
[ qw( g6 g7 g8 ) ],
[ qw( h5 ) ],
[ qw( g4 g3 g2 g1 ) ],
],
'g6' => [
[ qw( f7 e8 ) ],
[ qw( h7 ) ],
[ qw( h5 ) ],
[ qw( f5 e4 d3 c2 b1 ) ],
[ qw( f6 e6 d6 c6 b6 a6 ) ],
[ qw( g7 g8 ) ],
[ qw( h6 ) ],
[ qw( g5 g4 g3 g2 g1 ) ],
],
'g7' => [
[ qw( f8 ) ],
[ qw( h8 ) ],
[ qw( h6 ) ],
[ qw( f6 e5 d4 c3 b2 a1 ) ],
[ qw( f7 e7 d7 c7 b7 a7 ) ],
[ qw( g8 ) ],
[ qw( h7 ) ],
[ qw( g6 g5 g4 g3 g2 g1 ) ],
],
'g8' => [
[ qw( h7 ) ],
[ qw( f7 e6 d5 c4 b3 a2 ) ],
[ qw( f8 e8 d8 c8 b8 a8 ) ],
[ qw( h8 ) ],
[ qw( g7 g6 g5 g4 g3 g2 g1 ) ],
],
'h1' => [
[ qw( g2 f3 e4 d5 c6 b7 a8 ) ],
[ qw( g1 f1 e1 d1 c1 b1 a1 ) ],
[ qw( h2 h3 h4 h5 h6 h7 h8 ) ],
],
'h2' => [
[ qw( g3 f4 e5 d6 c7 b8 ) ],
[ qw( g1 ) ],
[ qw( g2 f2 e2 d2 c2 b2 a2 ) ],
[ qw( h3 h4 h5 h6 h7 h8 ) ],
[ qw( h1 ) ],
],
'h3' => [
[ qw( g4 f5 e6 d7 c8 ) ],
[ qw( g2 f1 ) ],
[ qw( g3 f3 e3 d3 c3 b3 a3 ) ],
[ qw( h4 h5 h6 h7 h8 ) ],
[ qw( h2 h1 ) ],
],
'h4' => [
[ qw( g5 f6 e7 d8 ) ],
[ qw( g3 f2 e1 ) ],
[ qw( g4 f4 e4 d4 c4 b4 a4 ) ],
[ qw( h5 h6 h7 h8 ) ],
[ qw( h3 h2 h1 ) ],
],
'h5' => [
[ qw( g6 f7 e8 ) ],
[ qw( g4 f3 e2 d1 ) ],
[ qw( g5 f5 e5 d5 c5 b5 a5 ) ],
[ qw( h6 h7 h8 ) ],
[ qw( h4 h3 h2 h1 ) ],
],
'h6' => [
[ qw( g7 f8 ) ],
[ qw( g5 f4 e3 d2 c1 ) ],
[ qw( g6 f6 e6 d6 c6 b6 a6 ) ],
[ qw( h7 h8 ) ],
[ qw( h5 h4 h3 h2 h1 ) ],
],
'h7' => [
[ qw( g8 ) ],
[ qw( g6 f5 e4 d3 c2 b1 ) ],
[ qw( g7 f7 e7 d7 c7 b7 a7 ) ],
[ qw( h8 ) ],
[ qw( h6 h5 h4 h3 h2 h1 ) ],
],
'h8' => [
[ qw( g7 f6 e5 d4 c3 b2 a1 ) ],
[ qw( g8 f8 e8 d8 c8 b8 a8 ) ],
[ qw( h7 h6 h5 h4 h3 h2 h1 ) ],
],
},
}

sub legal_moves() {
return \$p_legal_moves;
}

1;

and here is the code for solving the eight-queens problem ... enjoy!

```#!/usr/bin/perl -w
#
#  Solves the "Eight Queens" problems on a standard chess board.
#
#  051226 by liverpole
#

##############
### Strict ###
##############
use strict;
use warnings;

####################
### User-defined ###
####################
my \$border = " +---+---+---+---+---+---+---+---+";
my @rows   = qw( 1 2 3 4 5 6 7 8 );
my @cols   = qw( a b c d e f g h );

#################
### Libraries ###
#################
use Legal;

##################
### Prototypes ###
##################
sub legal(\$\$);
sub show_board(\$\$);

####################
### Main program ###
####################
my \$plegal = Legal::legal_moves();
my \$psquares = \$plegal->{'q'};
my \$count = 0;
map {
my \$p = { "a\$_" => 1 };
map {
legal(\$p, "b\$_") and map {
legal(\$p, "c\$_") and map {
legal(\$p, "d\$_") and map {
legal(\$p, "e\$_") and map {
legal(\$p, "f\$_") and map {
legal(\$p, "g\$_") and map {
legal(\$p, "h\$_") and show_board(\$p, ++
+\$count);
delete \$p->{"h\$_"};
} @rows;
delete \$p->{"g\$_"};
} @rows;
delete \$p->{"f\$_"};
} @rows;
delete \$p->{"e\$_"};
} @rows;
delete \$p->{"d\$_"};
} @rows;
delete \$p->{"c\$_"};
} @rows;
delete \$p->{"b\$_"};
} @rows;
} @rows;

###################
### Subroutines ###
###################
sub legal(\$\$) {
my (\$pboard, \$move) = @_;
my \$psquare = \$psquares->{\$move};
foreach my \$plist (@\$psquare) {
# Return 0 if placing the queen at \$move attacks any other que
+en
map { (\$pboard->{\$_} || 0) and return 0 } @\$plist;
}
\$pboard->{\$move} = 1;    # Put the queen on the board
return 1;
}

sub show_board(\$\$) {
my (\$pboard, \$count) = @_;
printf "Board #\${count} [%s]\n\$border\n", join(' ', sort keys %\$pb
+oard);
foreach my \$row (reverse @rows) {
print " | ";
map { printf "%s | ", (\$pboard->{"\$_\$row"} || 0)? "Q": " " } @
+cols;
print "\$row\n\$border\n";
}
printf "   %s\n\n\n", join('   ', @cols);
}

@ARGV=split//,"/:L"; map{print substr crypt(\$_,ord pop),2,3}qw"PerlyouC READPIPE provides"

Replies are listed 'Best First'.
Re: Solving the Eight Queens problem
by BrowserUk (Pope) on Dec 26, 2005 at 17:26 UTC

You might also find this prior art interesting.

Examine what is said, not who speaks -- Silence betokens consent -- Love the truth but pardon error.
Lingua non convalesco, consenesco et abolesco. -- Rule 1 has a caveat! -- Who broke the cabal?
"Science is about questioning the status quo. Questioning authority".
In the absence of evidence, opinion is indistinguishable from prejudice.
It is very interesting, and extremely clever.

However, I was thinking more along the lines of a solution yielding all possible answers in a short amount of time.

@ARGV=split//,"/:L"; map{print substr crypt(\$_,ord pop),2,3}qw"PerlyouC READPIPE provides"

If you follow the thread, it gives several interations of a non-regex solution that is really quite fast.

Examine what is said, not who speaks -- Silence betokens consent -- Love the truth but pardon error.
Lingua non convalesco, consenesco et abolesco. -- Rule 1 has a caveat! -- Who broke the cabal?
"Science is about questioning the status quo. Questioning authority".
In the absence of evidence, opinion is indistinguishable from prejudice.
Re: Solving the Eight Queens problem
by fergal (Chaplain) on Dec 27, 2005 at 13:50 UTC

A chess board is 8x8 and

```2^8 - 1
-------
8 - 1
is 255/7 = 36.4285714285... Take the first 8 digits and write the letters a..h beside them to get
```a3, b6, c4, d2, e8, f5, g7, h1
this is a solution to the problem.

Create A New User
Node Status?
node history
Node Type: CUFP [id://519169]
Approved by BrowserUk
help
Chatterbox?
and all is quiet...

How do I use this? | Other CB clients
Other Users?
Others cooling their heels in the Monastery: (4)
As of 2017-08-16 17:45 GMT
Sections?
Information?
Find Nodes?
Leftovers?
Voting Booth?
Who is your favorite scientist and why?

Results (271 votes). Check out past polls.

Notices?