Eight Queens Puzzle

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!

Advertisements

One thought on “Eight Queens Puzzle

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s