Submission #5198

Source Code Expand

#!perl

use strict;
use warnings;

our @result_board;

my @board = (); 
for my $i (0..7) {
    my @temp = split(//, <>);
    push(@board, [@temp]);
}
my $result = &Q(0, @board);

if ($result == 0) {
    print "No Answer\n";
} else {
    for my $i (0..7) {
        for my $j (0..7) {
            print $board[$i][$j];
        }   
        print "\n";
    }   
}

sub Q {
    my ($depth, @board) = @_; 

    my $flag = 0;
    for (my $i=0; $i<8; $i++) {
        $board[$depth][$i] eq 'Q' && ($flag = 1); 
    }   
    if ($flag == 1) {
        #すでにQがあるので次に行く
        if ($depth == 7) {
            @result_board = @board;
            return 1;
        } else {
            &Q($depth+1, @board);
        }   
    }   

    for (my $i=0; $i<8; $i++) {
        my $r = &isCheck($depth, $i, @board);

        if ($r == 1) {
            next;
        } else {
            $board[$depth][$i] = 'Q';

            if ($depth == 7) {
                @result_board = @board;
                return 1;
            }

            my $c = &Q($depth+1, @board);
            if ($c == 1) {
                @result_board = @board;
                return 1;
            } else {
                $board[$depth][$i] = '.';
            }
        }
    }

    return 0;
}


# 0:ok 1:no
sub isCheck {
    my ($depth, $position, @board) = @_;
    my $po;
    my $flag = 0;

    #上
    $po = $position;
    for (my $i=$depth-1; $i>=0; $i--) {
        $flag=1,last if ($board[$i][$po] eq 'Q');
    }

    #下
    $po = $position;
    for (my $i=$depth+1; $i<8; $i++) {
        $flag=1,last if ($board[$i][$po] eq 'Q');
    }

    #左上
    $po = $position;
    for (my $i=$depth-1; $i>=0; $i--) {
        $po -= 1;
        last if $po<0;

        $flag=1,last if ($board[$i][$po] eq 'Q');
    }

    #右上
    $po = $position;
    for (my $i=$depth-1; $i>=0; $i--) {
        $po += 1;
        last if $po>=8;

        $flag=1,last if ($board[$i][$po] eq 'Q');
    }

    #左下
    $po = $position;
    for (my $i=$depth+1; $i<8; $i++) {
        $po -= 1;
        last if $po<0;

        $flag=1,last if ($board[$i][$po] eq 'Q');
    }

    #右下
    $po = $position;
    for (my $i=$depth+1; $i<8; $i++) {
        $po +=1;
        last if $po>=8;

        $flag=1,last if ($board[$i][$po] eq 'Q');
    }

    return $flag;
}

Submission Info