1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
|
#!/usr/bin/perl
#!/data/data/com.termux/files/usr/bin/perl
if (grep(/^$ARGV[0]$/, ('h', '-h', '--help'))) {
print "queens.pl BOARD_SIZE EMPTY_CHAR QUEEN_CHAR\n";
exit;
}
($board_size, $empty, $queen) = (shift // 8, shift // '.', shift // 'Q');
(@board, $solutions);
place_queen();
sub place_queen {
my $row = shift // 0;
if ($row == $board_size) {
$solutions++;
print_solution();
return;
}
foreach my $col (0 .. $board_size - 1) {
if ($board[$row * $board_size + $col] == 0) {
mark($row, $col, 1);
place_queen($row + 1);
mark($row, $col, -1);
}
}
}
sub mark($$$) {
my ($row, $col, $value) = @_;
foreach my $o (0 .. $board_size - 1) {
$board[$row * $board_size + $o] += $value; # row
$board[$o * $board_size + $col] += $value; # column
# diagonals
my ($row_above, $row_below) = ($row - $o, $row + $o);
my ($col_left , $col_right) = ($col - $o, $col + $o);
if ($row_above >= 0 && $col_right < $board_size) {
$board[$row_above * $board_size + $col_right] += $value;
}
if ($row_above >= 0 && $col_left >= 0) {
$board[$row_above * $board_size + $col_left] += $value;
}
if ($row_below < $board_size && $col_left >= 0) {
$board[$row_below * $board_size + $col_left] += $value;
}
if ($row_below < $board_size && $col_right < $board_size) {
$board[$row_below * $board_size + $col_right] += $value;
}
}
$board[$row * $board_size + $col] += $value;
}
sub print_solution {
print "Solution number $solutions:\n";
foreach my $row (0 .. $board_size - 1) {
foreach my $col (0 .. $board_size - 1) {
print(($board[$row * $board_size + $col] == 7) ? $queen : $empty);
}
print "\n";
}
print "\n";
}
|
