#!/usr/bin/perl -w
use strict;
use warnings;

# Init
my $K = 5;
my @board;
my @queen_placements;

=begin description
Queens are randomly placed on the board. There's only one queen per row.

This array holds the overview of queens placements.

i.e.: Queen is placed in column 4 in row 2:
$board[2] = 4;
=cut


# Generate board
for (my $i = 0; $i < $K; $i++) {
    for (my $j = 0; $j < $K; $j++) {
        $board[$i][$j] = 0;
    }
    # generate random column
    my $rand_val = int(rand($K));

    # place queen in randomized column
    $board[$i][$rand_val] = 1;

    # update the overview
    $queen_placements[$i] = $rand_val;
}




sub min_conflict
{
    my $max_steps = shift;

    while (is_solution())
    {

        # run thorugh each rows
        for (my $i = 0; $i < $K; $i++) {

            my $column_with_min_conflicts = 0;
            my $conflicts = $K+1;


            # run thorugh each columns
            for (my $j = 0; $j < $K; $j++) {

                # count conflicts for queen placements in each cell on given row
                my $counted_conflicts = (check_column($j, $i) + check_diagonal($i, $j));

                # checks if current cell contains a queen
                if ($queen_placements[$i] == $j) {

                    # if queens current position is the best, then move on.
                    if ($counted_conflicts == 0) {
                        $column_with_min_conflicts = $j;
                        $conflicts = $counted_conflicts;
                        next;
                    }
                }

                # if checked column cell is better then the current best cell, update the cell information
                if ($counted_conflicts < $conflicts) {
                    $column_with_min_conflicts = $j;
                    $conflicts = $counted_conflicts;
                }

            }


            # move the queen to new location
            ## if queens current position is the best, then do nothing. TROR DENNE ØDELEGGER LITT NÅR DEN LÅSER SEG?!
            if ( $queen_placements[$i] != $column_with_min_conflicts ) {
                move_queen($i, $column_with_min_conflicts);
            }

        }


    }

    0;
}

sub move_queen
{
    my ($row, $column_with_min_conflicts) = @_;

    ### move queen away from old location
    $board[$row][$queen_placements[$row]] = 0;

    ### place queen on new location
    $board[$row][$column_with_min_conflicts] = 1;

    ### update queen placement overview
    $queen_placements[$row] = $column_with_min_conflicts;
}



sub is_solution
{
    my $count = 0;

    for (my $i = 0; $i < $K; $i++) {
        $count += check_column($queen_placements[$i], $i) + check_diagonal($i, $queen_placements[$i]);
    }



    return $count;
}

# checks for conflicts diagonaly for given X and Y
sub check_diagonal
{
    my ($x, $y) = @_;
    my $counter = 0;

    for (my ($i, $j) = ($x+1, $y+1); $i < $K && $j < $K; $i++, $j++) {
        if ($board[$i][$j]) {
            $counter++;
        }
    }
    for (my ($i, $j) = ($x-1, $y-1); $i >=0 && $j >= 0; $i--, $j--) {
        if ($board[$i][$j]) {
            $counter++;
        }
    }

    for (my ($i, $j) = ($x+1, $y-1); $i < $K && $j >= 0; $i++, $j--) {
        if ($board[$i][$j]) {
            $counter++;
        }
    }
    for (my ($i, $j) = ($x-1, $y+1); $i >=0 && $j < $K; $i--, $j++) {
        if ($board[$i][$j]) {
            $counter++;
        }
    }

    return $counter;
}


sub check_column
{
    my ($y, $queen_x)   = @_;
    my $counter         = 0;

    for (my $i = 0; $i < $K; $i++) { # row
        if ($board[$i][$y] && $queen_x != $i) {
            $counter++;
        }
    }

    return $counter;
}


sub print_solution
{
    for (my $i = 0; $i < $K; $i++) {
        for (my $j = 0; $j < $K; $j++) {
            if ($board[$i][$j]) {
                print " # ";
            } else {
                print " O ";
            }
        }
        print "\n";
    }
    print "\n";
}


## Start program here =>

# print start position
print "Given board:\n";
for (my $i = 0; $i < $K; $i++) {
    for (my $j = 0; $j < $K; $j++) {
        if ($board[$i][$j]) {
            print " # ";
        } else {
            print " O ";
        }
    }
    print "\n";
}

# run checks
min_conflict();

# print solution
print "\nSolution:\n";
&print_solution;