// N-Queens Problem
// g++ -std=c++11 -o nqueens nqueens.cpp

#include <iostream>
#include <string>
#include <vector>
#include <locale>
#include <clocale> // For setlocale
using namespace std;


/*
Windows users have to jump through hoops:
wcout << L"u25A0" //black square
wcout << L"u25A1" //white square
wcout << L"u265B" //black queen

board coords vs. chess algebraic notation:
(row,col):
(0,0) is a8
(7,0) is a1
(0,7) is h8
(7,7) is h1
*/

// Function to print the solution board
void printBoard(const vector<vector<int>>& board, int N) {

	setlocale(LC_ALL, "en_US.UTF-8");
	// chessboard variable declarations:
	string ca_cols = "abcdefgh"; // chess algebraic columns
	string ca_rows = "87654321"; // chess algebraic rows
	string whiteKing = "♔";
	string whiteQueen = "♕";
	string whiteRook = "♖";
	string whiteBishop = "♗";
	string whiteKnight = "♘";
	string whitePawn = "♙";
	string blackKing = "♚";
	string blackQueen = "♛";
	string blackRook = "♜";
	string blackBishop = "♝";
	string blackKnight = "♞";
	string blackPawn = "♟";
	string whiteSquare = "■"; // L"u25A1"
	string blackSquare = "□"; // L"u25A0"

	cout << "  ";
	for(int x = 0; x < N; x++){
		cout << ca_cols[x] << " ";
	}
	cout << endl;

	for (int i = 0; i < N; i++) {
		cout << (N - i) << " ";
		for (int j = 0; j < N; j++) {
			if(board[i][j]==1){
				cout << whiteQueen << " ";
			}else{
				// print an empty square on the chessboard
				switch(i%2){
					case 0: // row is even
						switch(j%2){
							case 0: // col is even
								cout << whiteSquare << " ";
								break;
							case 1: // col is odd 
								cout << blackSquare << " ";
								break;
						}
						break;
					case 1: // row is odd
						switch(j%2){
							case 0: // col is even
								cout << blackSquare << " ";
								break;
							case 1: // col is odd
								cout << whiteSquare << " ";
								break;
						}
						break;
				}
			}
		}
		cout << endl;
	}
}


// Function to check if a queen can be placed at board[row][col]
bool isSafe(const vector<vector<int>>& board, int row, int col, int N) {
	string ca_cols = "abcdefgh"; // chess algebraic columns
	string ca_rows = "87654321"; // chess algebraic rows
	// DEBUG
	cout << "DEBUG: isSafe() current board state:\n";
	cout << "attempting to place another Queen at " << ca_cols[col] << ca_rows[row] << " (" << row << "," << col << ")\n";
	printBoard(board, N);

	// cout << "Checking: (" << row << "," << col << ")\n";

	// Check this row on left side
	cout << "Checking row on the left side.\n";
	for (int i = 0; i < col; i++) {
		cout << "Checking: " << ca_cols[col] << ca_rows[i] << " (" << i << "," << col << ")\n";
		if (board[row][i]){
			cout << ca_cols[col] << ca_rows[i] << "(" << i << "," << col << ") is Occupied.\n";
			return false;
		}
	}

	// Check upper diagonal on left side
	cout << "Checking upper left diagonal.\n";
	for (int i = row, j = col; i >= 0 and j >= 0; i--, j--){
		cout << "Checking: " << ca_cols[j] << ca_rows[i] << " (" << i << "," << j << ")\n";
		if (board[i][j]){
			cout << "(" << row << "," << col << ") is Occupied.\n";
			return false;
		}
	}

	// Check upper diagonal on right side
	cout << "Checking upper right diagonal\n";
	for (int i = row, j = col; i >= 0 and j < N; i--, j++){
		cout << "Checking: " << ca_cols[j] << ca_rows[i] << " (" << i << "," << j << ")\n";
		if (board[i][j]){
			cout << "(" << row << "," << col << ") is Occupied.\n";
			return false;
		}
	}
	
	// Check lower diagonal on left side
	cout << "Checking lower left diagonal.\n";
	for (int i = row, j = col; i < N and j >= 0; i++, j--){
		cout << "Checking: " << ca_cols[j] << ca_rows[i] << " (" << i << "," << j << ")\n";
		if (board[i][j]){
			cout << "(" << row << "," << col << ") is Occupied.\n";
			return false;
		}
	}

	// Check lower diagonal on right side
	cout << "Checking upper right diagonal.\n";
	for (int i = row, j = col; i < N and j < N; i++, j++){
		cout << "Checking: " << ca_cols[j] << ca_rows[i] << " (" << i << "," << j << ")\n";
		if (board[i][j]){
			cout << "(" << row << "," << col << ") is Occupied.\n";
			return false;
		}
	}

	return true;
}

// Recursive function to solve N-Queens problem
bool solveNQueens(vector<vector<int>>& board, int col, int N) {
	// Base case: If all Queens are placed, return true
	if (col >= N) {
		return true;
	}

	// Consider this column and try placing the current Queen in each row, one by one
	for (int row = 0; row < N; row++) {
		// Check if Queen can be placed at board[i][col]
		if (isSafe(board, row, col, N)) {
			// Place the queen
			board[row][col] = 1;

			// Recursion to place the rest of the queens
			if (solveNQueens(board, col + 1, N)) {
				return true; // Solution found
			}

			// If placing a Queen at board[i][col] doesn't lead to a solution,
			// then backtrack and remove the Queen (unmake the decision)
			board[row][col] = 0;
		}
	}

	// If queen cannot be placed in any row in this column, return false
	return false;
}


int main() {
	int N = 8; // For a standard 8x8 board
	vector<vector<int>>board(N, vector<int>(N, 0));

	if (solveNQueens(board, 0, N)) {
		cout << "Solution for " << N << "-Queens problem:" << endl;
		printBoard(board, N);
	} else {
		cout << "No solution exists for " << N << "-Queens problem." << endl;
	}

	return 0;
}