Queen's problem (was Re^2: How to debug a long while loop)

nbezalla:

I recalled another amusing chess puzzle--specifically the "queens problem". It's another one that's easily solved with recursion. It might be too much of a hint, so I've put spoiler tags on it (below) so you don't see the solution to it if you don't want to. Anyway, the queens problem (on the offhand chance that you're unfamiliar with it) is basically to place eight queens on a chessboard such that none can attack another.

My solution is:

#!/usr/bin/perl -w
#--------------------------------------------------------------------
# queen.pl
#
# Print a solution to the "queens problem"--i.e., place eight queens
# on a chessboard such that none may attack another.
#--------------------------------------------------------------------

use strict;
use warnings;

my @queens = (99, 0, 0, 0, 0, 0, 0, 0, 0);

sub print_solution {
        for my $r (1..8) {
                for my $c (1..8) {
                        my $s=' ';
                        $s='*' if ($r+$c) & 1;
                        $s='Q' if $queens[$r] == $c;
                        print $s, " ";
                }
                print "\n";
        }
}

sub solve {
        my ($x, $y) = @_;

        # Can any queen attack the proposed move?
        my $row=1;
        while ($row < $y) {
                # Can't put another queen in same column
                return 0 if $queens[$row] == $x;

                # Check the diagonals too
                return 0 if $queens[$row]-($y-$row) == $x;
                return 0 if $queens[$row]+($y-$row) == $x;

                ++$row;
        }

        # Mark square as "occupied"
        $queens[$y]=$x;

        if ($y==8) {
                # We found a solution!
                print_solution();
                return 1;
        }
        else {
                # Try all positions on the next row
                for my $tx (1..8) {
                        solve($tx, $y+1) && return 1;
                }
        }
}

solve(2, 1);
[download]

...roboticus

Comment on Queen's problem (was Re^2: How to debug a long while loop) Download Code