#!/usr/bin/perl -w

use strict;

# Nonspecific N-Queens Solution Generator by Elgon
# Not sure whether truly crafty, but I'm happy with it!
# Update: Added regexp to make the end result prettier.

# Set up parameters
my $n = 8;
my $row_counter = 0;
my @board;
$board[0] = ('x'x$n);

# Start the loop
while ()
{
    # Are there any free spaces in the current row?

    if ($board[$row_counter] =~ m/x/)
    {
        # If yes, then place a piece in the first available slot
        my @row = split(//, $board[$row_counter]);
        foreach $_(@row)
        {
            if ($_ eq 'x')
	    {
                $_ = 'q';
                last;
            }    
        }

        $board[$row_counter] = join ('', @row);
        ++$row_counter;

        # Have we finished 'n' rows?

        if ($row_counter == $n)
        {

            # If so we have a valid solution. Save it to a file.
            open (DEST, ">> solutions.q") or die ('Couldn\'t open dest file!');
            print DEST "\n\n";
            foreach $_(@board)
            {
                my $temp_row = $_;
                $temp_row =~ tr/q/X;
                $temp_row =~ tr/yx/O/;
                print DEST "$temp_row\n";
	    }
            print DEST "\n";
            close DEST;

            # Now go back one row and make the old queen's spot invalid

            --$row_counter;
            pop @board;
            --$row_counter;
            $board[$row_counter] =~ tr/q/y/;
	}

        #  Otherwise out which slots in the next row down will be unavailable

        else
        {
            my @current_row;
            for ($_ = 0; $_ < $n; ++$_)
            {
                push @current_row, 'x';
	    }
            my $row;
            for ($row = 0; $row < scalar(@board); ++$row)
            {
                @row = split '', $board[$row];
                my $square;
                for ($square = 0; $square < scalar(@row); ++$square)
                {
                    if ($row[$square] eq 'q')
                    {
                        $current_row[$square] = 'y';
                        if (($square - ($row_counter - $row)) >= 0)
                        {
                            $current_row[($square - ($row_counter - $row))] = 'y';
		        }
                        if (($square + ($row_counter - $row)) <= ($n - 1))
                        {
                            $current_row[($square + ($row_counter - $row))] = 'y';
		        }
		    }
	        }
            }

            # Add the row to the board and go round again
            $board[$row_counter] = join ('', @current_row); 
        }
    }

    # If there are no available slots then we need to go back a row

    else
    {

        # But if we've used up the whole first row then all solutions are done

        if (!$row_counter && defined($row_counter))
        {
            print "\n\nCompleted!";
            exit;
        }
        else

        # Otherwise, go back a row...

        {
            pop @board;
            --$row_counter;
            $board[$row_counter] =~ tr/q/y/;
        }
    }
}