n_queens_all_solution_optimised.cpp File Reference

N queens all optimized More...

#include <array>
#include <iostream>

Include dependency graph for n_queens_all_solution_optimised.cpp:

Go to the source code of this file.

Namespaces
namespace	backtracking
	for vector container
namespace	n_queens_optimized
	Functions for Eight Queens puzzle optimized.

Functions
template<size_t n>
void	backtracking::n_queens_optimized::PrintSol (const std::array< std::array< int, n >, n > &board)
template<size_t n>
bool	backtracking::n_queens_optimized::CanIMove (const std::array< std::array< int, n >, n > &board, int row, int col)
template<size_t n>
void	backtracking::n_queens_optimized::NQueenSol (std::array< std::array< int, n >, n > board, int col)
int	main ()
	Main function.

Detailed Description

N queens all optimized

Author

Sombit Bose

David Leal

Definition in file n_queens_all_solution_optimised.cpp.

Function Documentation

CanIMove()

template<size_t n>

bool backtracking::n_queens_optimized::CanIMove	(	const std::array< std::array< int, n >, n > &	board,
		int	row,
		int	col )

Check if a queen can be placed on matrix

Template Parameters

n	number of matrix size

Parameters

board	matrix where numbers are saved
row	current index in rows
col	current index in columns

Returns

true if queen can be placed on matrix

false if queen can't be placed on matrix

check in the row

check the first diagonal

check the second diagonal

Definition at line 59 of file n_queens_all_solution_optimised.cpp.

                       {
    for (int i = 0; i <= col; i++) {
        if (board[row][i] == 1) {
            return false;
        }
    }
    for (int i = row, j = col; i >= 0 && j >= 0; i--, j--) {
        if (board[i][j] == 1) {
            return false;
        }
    }
    for (int i = row, j = col; i <= n - 1 && j >= 0; i++, j--) {
        if (board[i][j] == 1) {
            return false;
        }
    }
    return true;
}

main()

int main

(

void

)

Main function.

Returns

0 on exit

Definition at line 109 of file n_queens_all_solution_optimised.cpp.

           {
    const int n = 4;
    std::array<std::array<int, n>, n> board{};
 
    if (n % 2 == 0) {
        for (int i = 0; i <= n / 2 - 1; i++) {
            if (backtracking::n_queens_optimized::CanIMove(board, i, 0)) {
                board[i][0] = 1;
                backtracking::n_queens_optimized::NQueenSol(board, 1);
                board[i][0] = 0;
            }
        }
    } else {
        for (int i = 0; i <= n / 2; i++) {
            if (backtracking::n_queens_optimized::CanIMove(board, i, 0)) {
                board[i][0] = 1;
                backtracking::n_queens_optimized::NQueenSol(board, 1);
                board[i][0] = 0;
            }
        }
    }
    return 0;
}

NQueenSol()

template<size_t n>

void backtracking::n_queens_optimized::NQueenSol	(	std::array< std::array< int, n >, n >	board,
		int	col )

Solve n queens problem

Template Parameters

n	number of matrix size

Parameters

board	matrix where numbers are saved
col	current index in columns

Definition at line 89 of file n_queens_all_solution_optimised.cpp.

                                                             {
    if (col >= n) {
        PrintSol<n>(board);
        return;
    }
    for (int i = 0; i < n; i++) {
        if (CanIMove<n>(board, i, col)) {
            board[i][col] = 1;
            NQueenSol<n>(board, col + 1);
            board[i][col] = 0;
        }
    }
}

PrintSol()

template<size_t n>

void backtracking::n_queens_optimized::PrintSol

(

const std::array< std::array< int, n >, n > &

board

)

Utility function to print matrix

Template Parameters

n	number of matrix size

Parameters

board

matrix where numbers are saved

Definition at line 30 of file n_queens_all_solution_optimised.cpp.

                                                          {
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            std::cout << board[i][j] << " ";
        }
        std::cout << std::endl;
    }
    std::cout << std::endl;
    if (n % 2 == 0 || (n % 2 == 1 && board[n / 2 + 1][0] != 1)) {
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                std::cout << board[j][i] << " ";
            }
            std::cout << std::endl;
        }
        std::cout << std::endl;
    }
}