Algorithms_in_C++ 1.0.0
Set of algorithms implemented in C++.
Loading...
Searching...
No Matches
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:

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

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
nnumber of matrix size
Parameters
boardmatrix where numbers are saved
rowcurrent index in rows
colcurrent 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

60 {
61 /// check in the row
62 for (int i = 0; i <= col; i++) {
63 if (board[row][i] == 1) {
64 return false;
65 }
66 }
67 /// check the first diagonal
68 for (int i = row, j = col; i >= 0 && j >= 0; i--, j--) {
69 if (board[i][j] == 1) {
70 return false;
71 }
72 }
73 /// check the second diagonal
74 for (int i = row, j = col; i <= n - 1 && j >= 0; i++, j--) {
75 if (board[i][j] == 1) {
76 return false;
77 }
78 }
79 return true;
80}
Here is the call graph for this function:

◆ main()

int main ( void )

Main function.

Returns
0 on exit
109 {
110 const int n = 4;
112
113 if (n % 2 == 0) {
114 for (int i = 0; i <= n / 2 - 1; i++) {
115 if (backtracking::n_queens_optimized::CanIMove(board, i, 0)) {
116 board[i][0] = 1;
118 board[i][0] = 0;
119 }
120 }
121 } else {
122 for (int i = 0; i <= n / 2; i++) {
123 if (backtracking::n_queens_optimized::CanIMove(board, i, 0)) {
124 board[i][0] = 1;
126 board[i][0] = 0;
127 }
128 }
129 }
130 return 0;
131}
void NQueenSol(std::array< std::array< int, n >, n > board, int col)
Definition n_queens_all_solution_optimised.cpp:89

◆ 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
nnumber of matrix size
Parameters
boardmatrix where numbers are saved
colcurrent index in columns
89 {
90 if (col >= n) {
91 PrintSol<n>(board);
92 return;
93 }
94 for (int i = 0; i < n; i++) {
95 if (CanIMove<n>(board, i, col)) {
96 board[i][col] = 1;
97 NQueenSol<n>(board, col + 1);
98 board[i][col] = 0;
99 }
100 }
101}
Here is the call graph for this function:

◆ 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
nnumber of matrix size
Parameters
boardmatrix where numbers are saved
30 {
31 for (int i = 0; i < n; i++) {
32 for (int j = 0; j < n; j++) {
33 std::cout << board[i][j] << " ";
34 }
36 }
38 if (n % 2 == 0 || (n % 2 == 1 && board[n / 2 + 1][0] != 1)) {
39 for (int i = 0; i < n; i++) {
40 for (int j = 0; j < n; j++) {
41 std::cout << board[j][i] << " ";
42 }
44 }
46 }
47}
T endl(T... args)
Here is the call graph for this function: