#!/usr/local/bin/perl

sub dump() {
	my ($i, $j);
	print(sprintf("%s\n", $head));
	for ($i = 0; $i < $size ; $i++) {
		$l = "";
                for ($j = 0; $j < $size; $j++) {
                        if ( $bd[$i * $size + $j] ) {
                                $l .= " O";
                        } else {
                                $l .= " -";
                        }
                }
                print(sprintf("%s\n",$l));
        }
}

sub initBd() {
	for ($i = 0; $i < $size ; $i++) {
                for ($j = 0; $j < $size; $j++) {
			$bd[$i * $size + $j] = 0;
		}
	}
}

sub isValidPos() {
	my ($x, $y) = @_;
	my ($i, $c, $j0, $j1);
        for ($i = $x-1, $c = 1; $i >= 0; $i--, $c++) {
                if ($bd[$i * $size + $y]){
                        return 0;
                }

                $j0 = $y - $c;
                if ($j0 >= 0 && $bd[ $i * $size + $j0] ){
                        return 0;
                }

                $j1 = $y + $c;
                if ($j1 < $size && $bd[$i * $size + $j1] ){
                        return 0;
                }

        }
        return 1;
}

sub checkPos() {
	my ($x, $y) = @_;
	my ($j);
        for ( $j = $y; $j < $size ; $j++) {
                if ( &isValidPos($x, $j)) {
                        $bd[$x * $size + $j] = 1;
                        if ($x + 1 >= $size ) {
                                &dump();
                                $bd[$x * $size + $j] = 0;

				return 0;
                        }
                        if (! &checkPos($x+1, 0)) {
				return 0;
			}
                        $bd[$x * $size + $j] = 0;
                }
        }
	return 1;
}

sub main() {

	$size = 8;
	for ($i = 0; $i <= $#ARGV; $i++) {
		if ("-s" eq $ARGV[$i]) {
			$i++;
			$size = $ARGV[$i];
		} 
	}

	$head = "";
	for ($i = 0; $i < $size; $i++) {
                $head .= "--";
        }


	&initBd();
	$t1 = time();
	&checkPos(0, 0);
	$t2 = time();
	print(sprintf("Elapsed time = %d\n", ($t2 - $t1) * 1000 ));
}

&main();
exit(0);

##</code><code>##

public class NQ {
	boolean[][] bd; 
	int	size;
	String	head;
	int	totalCount;
	static	long st, et;

	NQ(int n) {
		size = n;
		bd = new boolean[n][n];
		head = "";
		totalCount = 0;

		for (int i = 0; i < n; i++) {
			head += "--";
		}
	}

	public void dump() {
		System.out.println("Count: " + totalCount);
		System.out.println(head);
		for (int i = 0; i < size ; i++) {
			String l = "";
			for (int j = 0; j < size; j++) {
				if ( bd[i][j]) {
					l += " O";
				} else {
					l += " -";
				}
			}
			System.out.println(l);
		}
	}

	private boolean isValidPos(int x,  int y) {
		int i, j0, j1, c;
		totalCount++;
		for (i = x-1, c = 1; i >= 0; i--, c++) {
			// hrizontal line check
			if (bd[i][y]){
				return false;
			}

			// diagonal1 check 
			j0 = y - c;
			if (j0 >= 0 && bd[i][j0]){
				return false;
			}

			// diagonal2 check
			j1 = y + c;
			if (j1 < size && bd[i][j1]){
				return false;
			}
		}
		return true;
	}

	private boolean checkPos(int x, int y) {
		int j;
		for ( j = y; j < size ; j++) {
			if (isValidPos(x, j)) {
				bd[x][j] = true;

				if (x + 1 >= size ) {
					dump();
					bd[x][j] = false;

					// if this returns true, it continues searching...
					return false;
				}

				if (!checkPos(x+1, 0)) {
					return false;
				}
				bd[x][j] = false;
			} 
		}
		return true;
	}

	public static void main(String[] argv) {
		int a = 8; // default

		for ( int i = 0; i < argv.length; i++) {
			if (argv[i].equals("-s")) {
				try {
					a = Integer.parseInt(argv[i+1]);
				} catch (Exception e) {
					e.printStackTrace();
				}
			}
		}

		NQ eq = new NQ(a);
		System.out.println("Board Size = " + eq.bd.length);

		st = System.currentTimeMillis();
		eq.checkPos(0, 0);
		et = System.currentTimeMillis();
		String ept = Long.toString(et - st);
		System.out.println("Elapsed time (msec): " + ept);
	}
}

##</code><code>##

use strict;
use vars qw/ @bd $size /;

sub solve
{
    $size   = shift;
    @bd     = (0)x$size**2;

    checkPos(0,0);
#   dump_bd();
}

sub dump_bd
{
    my $i_size;
    for my $i( 0..$size-1 ) {
        $i_size = $i * $size;
        print (
            map{ $_ ? ' 0' : ' -' } @bd[ $i_size .. $i_size + $size - 1 ]
        );
        print "\n";
    }
}

sub checkPos
{
    my ($x, $y) = @_;
    my $x_size = $x * $size;
    my( $i_size, $cur_pos, $j0, $j1 );
OUTER:
    for( my $j = 0; $j < $size; $j++ ) {
        for( my $i = $x-1, my $c = 1; $i >= 0; $i--, $c++) {
             $i_size = $i * $size;
             $bd[$i_size + $j] && next OUTER;
             ( $j0 = $j - $c ) > -1 && $bd[ $i_size + $j0] && next OUTER;
             ( $j1 = $j + $c ) < $size && $bd[$i_size + $j1] && next OUTER;
        }

        $cur_pos = $x_size + $j;
        $bd[ $cur_pos ] = 1;
        ($x + 1 >= $size ) && return 0;
        checkPos($x+1, 0) || return 0;
        $bd[ $cur_pos ] = 0;
    }
    return 1;
}

1;