nqueen_print_all_solutions.cpp File Reference

Eight Queens puzzle, printing all solutions More...

#include <array>
#include <iostream>

Include dependency graph for nqueen_print_all_solutions.cpp:

Go to the source code of this file.

Namespaces
namespace	backtracking
	for vector container
namespace	n_queens_all_solutions
	Functions for the Eight Queens puzzle with all solutions.

Functions
template<size_t n>
void	backtracking::n_queens_all_solutions::PrintSol (const std::array< std::array< int, n >, n > &board)
	Utility function to print matrix.
template<size_t n>
bool	backtracking::n_queens_all_solutions::CanIMove (const std::array< std::array< int, n >, n > &board, int row, int col)
	Check if a queen can be placed on the matrix.
template<size_t n>
void	backtracking::n_queens_all_solutions::NQueenSol (std::array< std::array< int, n >, n > board, int col)
	Main function to solve the N Queens problem.
int	main ()
	Main function.

Detailed Description

Eight Queens puzzle, printing all solutions

Author

Himani Negi

David Leal

Definition in file nqueen_print_all_solutions.cpp.

Function Documentation

CanIMove()

template<size_t n>

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

Check if a queen can be placed on the 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 51 of file nqueen_print_all_solutions.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 101 of file nqueen_print_all_solutions.cpp.

           {
    const int n = 4;
    std::array<std::array<int, n>, n> board{0};
 
    backtracking::n_queens_all_solutions::NQueenSol(board, 0);
}

NQueenSol()

template<size_t n>

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

Main function to solve the 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 81 of file nqueen_print_all_solutions.cpp.

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

PrintSol()

template<size_t n>

void backtracking::n_queens_all_solutions::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 31 of file nqueen_print_all_solutions.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;
}