#!/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);