#!/usr/bin/perl
#use Data::Dumper;
use Term::ANSIColor;

#######################
# Board size = (n x n)
# Also dictates n queens
our $n = 8;
#######################



# Build "n" size column
my @nsizecol = (); for(1..$n) { push(@nsizecol, 0); }

# Store entire board - list of "column" arrays (ref them for now)
my @board = (); for(1..$n) { push(@board, \@nsizecol); }

# Show Initial Board
##show_board(\@board);

# NEW "rough" LOGIC:
# 1.) Take col and insert in "queen" (1) in first position
# 2.) put col in board and check board
# 3.) 	if good, move to next col (col+1), and call #1
# 4.) 	else, advance queen in col in second position, and call #2
# 5.)		if last position, go one col back
# 6.)			if no more calls, quit

# Use "$c" as the column count (list used as vector)
# Use "$r" as the row count. (list of vectors)
my $c = 0; my $r = 0;
my @successful_c = ();
my @solutions = ();
run($r, $c);


#######################################################################
sub run {
	my $r = shift; my $c = shift;
 	my $ref_col = $board[$r];

	my $ref_p_col = add_queen($ref_col, $c);
	$board[$r] = $ref_p_col;


	if( vertical_check(\@board) && horizontal_check(\@board)
		&& down_diagonal_check(\@board, $r, $c) && up_diagonal_check(\@board, $r, $c) ) {
		# MOVE IS SUCCESSFUL = doesn't hit another queen in any way
		#print ">>> CHECK\n"; print "N: $n | R: $r | C: $c <<<\n";
		if($r == ($n-1)) {
			show_board(\@board);
			push(@solutions, \@board);

			$board[$r] = $ref_col;

			if($c < ($n-1)) { 
				$c += 1;
			}
			else {
				$r -= 1; 
				$c = pop(@successful_c);
				my @col = @{$ref_col};
				splice(@col, $c, 1, (0));
				$board[$r] = \@col;
				$c += 1; 
			}
			run($r, $c);
		}
		elsif($r < 0) {
			print "!!! DONE !!!\n";
			$solutions = @solutions; 
			print "There are $solutions solutions to $n-queens in a ($n x $n) chessboard\n";
			exit;
		}
		else {
			$r += 1;

			push(@successful_c, $c);
			$c = 0;
			# temp comment out
			###show_board(\@board);
			run($r, $c);
		}
	}


	else {
		# BACK OUT - bring the board to "as was" and increase col
		$board[$r] = $ref_col;


		#print "TEST: n:$n | c:$c | r:$r\n";
		if($c == ($n-1)) {
			# If we are on the first column, no where else to go,
			# end the game, and show the board
			if($r == 0) {
				show_board(\@board);
				exit;
			}
			# Otherwise, go to previous row
			else {
				$c = pop(@successful_c);

				$r -= 1;
				$board[$r] = $ref_col;
				my @col = @{$ref_col};
				splice(@col, $c, 1, (0));
				$board[$r] = \@col;

				if($c < ($n-1)) { $c += 1; }
				elsif($c == ($n-1)) { 
					$c = pop(@successful_c);
					if($c < ($n-1)) { $c += 1; }
					$r -= 1; 
					$board[$r] = $ref_col;
					my @col = @{$ref_col};
					splice(@col, $c, 1, (0));
					$board[$r] = \@col;
				}

				#show_board(\@board);
				run($r, $c);
			}
		}
		else {
			$c += 1;
			run($r, $c);
		}
	}
}
#######################################################################



# Insert queen in given col and given postion (start at 0)
sub add_queen {
	my $ref_col = shift;
	my $position = shift;

	my @col = @{$ref_col};
	splice(@col, $position, 1, (1));
	$ref_col = \@col;
	return $ref_col;
}



# Take board and check up-diagonal
# Note -- you only need to check the piece and "BEFORE" it.
# Return:
#	1 = OK - all is good
#	0 = NOT-OK - there is 1 queen.
sub up_diagonal_check {
	my $ref_board = shift;
	my $r = shift; my $c = shift;
	my @board = @{$ref_board};
	my @array = ();

	$tc = $c; $tr = $r;
	# Get Initial Item too
	while($tc <= ($n-1) && $tr >= 0) {
		my $ref_col = $board[$tr];
		my @col = @{$ref_col};
		push(@array, $col[$tc]);
		$tc += 1; $tr -= 1;
	}
	return (list_check(\@array));
}



# Take board and check down-diagonal
# Note -- you only need to check the piece and "BEFORE" it.
# Return:
#	1 = OK - all is good
#	0 = NOT-OK - there is 1 queen.
sub down_diagonal_check {
	my $ref_board = shift;
	my $r = shift; my $c = shift;
	my @board = @{$ref_board};
	my @array = ();

	$tc = $c; $tr = $r;
	# Get Initial Item too
	while($tc >= 0 && $tr >= 0) {
		my $ref_col = $board[$tr];
		my @col = @{$ref_col};
		push(@array, $col[$tc]);
		$tc -= 1; $tr -= 1;
	}
	return (list_check(\@array));
}



# Take board and check horizontally,
# by using list_check for _each_ row
# Return:
#	1 = OK - all is good
#	0 = NOT-OK - there is 1 queen.
sub horizontal_check {
	my $ref_board = shift;
	my @board = @{$ref_board};

	my $r = 1;
	for my $i (1..$n) {
		$i-=1;
		my @nsizerow = ();
		for my $ref_col (@board) {
			my @col = @{$ref_col};
			my $square = $col[$i];
			push(@nsizerow, $square)
		}
		my $ref_nsizerow = \@nsizerow;
		if(list_check($ref_nsizerow)) { $r *= 1; }
		else { $r *= 0; }
	}
	return $r;
}



# Take board and check vertically,
# Return:
#	1 = OK - all is good
#	0 = NOT-OK - there is 1 queen.
sub vertical_check {
	my $ref_board = shift;
	my @board = @{$ref_board};

	my $r = 1;
	for my $ref_col (@board) {
		if(list_check($ref_col)) { $r *= 1; }
		else { $r *= 0; }
	}
	return $r;
}



# Take only 1 column/list, and check for validity
# Return:
#	1 = OK - all is good
#	0 = NOT-OK - there is 1 queen.
sub list_check {
	my $ref_array = shift;
	my @array = @{$ref_array};
	my $sum = 0; for (@array) { $sum += $_; }
	if($sum > 1) { return 0; }
	else { return 1; }
}



# Show the board visually!
sub show_board {
	my $ref_board = shift;
	my @board = @{$ref_board};

	print "\n\nChess Board ($n x $n)\n";
	print "   "; for(0..($n-1)) { print " $_  "; } print "\n  ";
	print "++++" x $n; print "+\n";
	for my $i (1..$n) {
		$i-=1;
		print "$i ";
		for my $ref_col (@board) {
			my @col = @{$ref_col};
			my $square = $col[$i];
			print "|";
			if($square == 1) { print color 'bold red'; print " $square "; print color 'reset'; }
			# For less/more "view", comment above, uncomment bellow - deals with colors
			#if($square == 1) {print " $square ";}
			else { print "   ";}
		}
		print "|\n"; print "  "; print "++++" x $n; print "+\n";
	}
}
