Algorithms_in_C++  1.0.0
Set of algorithms implemented in C++.
nqueen_print_all_solutions.cpp File Reference

Eight Queens puzzle, printing all solutions More...

#include <iostream>
#include <array>
Include dependency graph for nqueen_print_all_solutions.cpp:

Namespaces

 backtracking
 Backtracking algorithms.
 
 n_queens_all_solutions
 Functions for 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)
 
template<size_t n>
bool backtracking::n_queens_all_solutions::CanIMove (const std::array< std::array< int, n >, n > &board, int row, int col)
 
template<size_t n>
void backtracking::n_queens_all_solutions::NQueenSol (std::array< std::array< int, n >, n > board, int col)
 
int main ()
 

Detailed Description

Eight Queens puzzle, printing all solutions

Author
Himani Negi
David Leal

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 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

50  {
51  /// check in the row
52  for (int i = 0; i < col; i++) {
53  if (board[row][i] == 1) {
54  return false;
55  }
56  }
57  /// check the first diagonal
58  for (int i = row, j = col; i >= 0 && j >= 0; i--, j--) {
59  if (board[i][j] == 1) {
60  return false;
61  }
62  }
63  /// check the second diagonal
64  for (int i = row, j = col; i <= n - 1 && j >= 0; i++, j--) {
65  if (board[i][j] == 1) {
66  return false;
67  }
68  }
69  return true;
70 }

◆ main()

int main ( void  )

Main function

98  {
99  const int n = 4;
100  std::array<std::array<int, n>, n> board{0};
101 
103 }

◆ NQueenSol()

template<size_t n>
void backtracking::n_queens_all_solutions::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
79  {
80  if (col >= n) {
81  PrintSol(board);
82  return;
83  }
84  for (int i = 0; i < n; i++) {
85  if (CanIMove(board, i, col)) {
86  board[i][col] = 1;
87  NQueenSol(board, col + 1);
88  board[i][col] = 0;
89  }
90  }
91 }

◆ 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
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 }
Here is the call graph for this function:
backtracking::n_queens_all_solutions::NQueenSol
void NQueenSol(std::array< std::array< int, n >, n > board, int col)
Definition: nqueen_print_all_solutions.cpp:79
std::cout
std::array
STL class.
std::endl
T endl(T... args)