Solving the Eight Queens problem
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).
@ARGV=split//,"/:L"; map{print substr crypt($_,ord pop),2,3}qw"PerlyouC READPIPE provides"
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 queen
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 %$pboard);
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"
Re: Solving the Eight Queens problem
created: 2005-12-26 12:26:27
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.
Re^2: Solving the Eight Queens problem
created: 2005-12-26 13:09:23
It is very interesting, and extremely clever.
@ARGV=split//,"/:L"; map{print substr crypt($_,ord pop),2,3}qw"PerlyouC READPIPE provides"
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"
Re^3: Solving the Eight Queens problem
created: 2005-12-26 13:23:49
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
created: 2005-12-27 08:50:29
A chess board is 8x8 and
2^8 - 1 ------- 8 - 1is 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, h1this is a solution to the problem.
Update: added "explanation".
As far as I know, there is no explanation, it's just a coincidence that this works!