I tried to solve the Eight Queens Puzzle in my own way. The script written in Perl prints only the 1st possible solution and exits. But this can be modified to print all the solutions. The program is given below.

use strict;
use warnings;
no warnings 'recursion';
use constant BLANK => '~';
use constant OCCUP => 'x';
use constant BRDSZ => 8;
my @qpos = ();
sub print_board {
my @qpos = @_;
print "\n";
for my $r (0 .. BRDSZ - 1) {
for my $c1 (0 .. BRDSZ - 1) {
my $c2 = $qpos[$r];
print ($c1 == $c2 ? OCCUP : BLANK);
}
print "\n";
}
print "\n";
}
sub col_presence {
my $c = shift;
for my $r (0 .. @qpos - 1) {
return 1 if $qpos[$r] == $c;
}
}
sub diag_presence {
my ($r, $c) = @_;
my ($i, $j);
$i = $r - 1; $j = $c - 1;
while($i >= 0 and $j >= 0) {
return 1 if $qpos[$i--] == $j--;
}
$i = $r - 1; $j = $c + 1;
while($i >= 0 and $j <= BRDSZ - 1) {
return 1 if $qpos[$i--] == $j++;
}
return 0;
}
sub try_pos {
my ($r, $c) = @_;
if($r == BRDSZ) {
print_board @qpos;
return;
}
if($c == BRDSZ and @qpos >= 1) {
my $lastr = @qpos - 1;
my $lastc = $qpos[$lastr];
if($lastr < $r) {
pop @qpos;
try_pos($lastr, $lastc + 1);
}
} elsif(col_presence($c) or diag_presence($r, $c)) {
try_pos($r, $c + 1);
} else {
push @qpos, $c;
try_pos($r + 1, 0);
}
}
try_pos(0, 0); @qpos = ();
try_pos(0, 1); @qpos = ();
try_pos(0, 2); @qpos = ();
try_pos(0, 3); @qpos = ();
try_pos(0, 4); @qpos = ();
try_pos(0, 5); @qpos = ();
try_pos(0, 6); @qpos = ();
try_pos(0, 7);

As I am calling `try_pos`

function for all eight columns of 1st row, we get eight different solutions. This algorithm uses backtracking (see the call to the function `pop`

). WARNING: This program may not be the best possible algorithm. Please refer wikipedia or google for various algorithms.

How to convert this program to use loops instead of recursion?

Happy Programming!

### Like this:

Like Loading...

*Related*

[…] the earlier post about the 8-queens problem, we arrived at the final solution. We couldn’t get a chance on deeper insights on the […]