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!
