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

Eight Queens puzzle More...

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

Namespaces

 backtracking
 Backtracking algorithms.
 
 n_queens
 Functions for Eight Queens puzzle.
 

Functions

template<size_t n>
void backtracking::n_queens::printSolution (const std::array< std::array< int, n >, n > &board)
 
template<size_t n>
bool backtracking::n_queens::isSafe (const std::array< std::array< int, n >, n > &board, const int &row, const int &col)
 
template<size_t n>
void backtracking::n_queens::solveNQ (std::array< std::array< int, n >, n > board, const int &col)
 
int main ()
 

Detailed Description

Eight Queens puzzle

The eight queens puzzle is the problem of placing eight chess queens on an 8×8 chessboard so that no two queens threaten each other; thus, a solution requires that no two queens share the same row, column, or diagonal. The eight queens puzzle is an example of the more general n queens problem of placing n non-attacking queens on an n×n chessboard, for which solutions exist for all natural numbers n with the exception of n = 2 and n = 3.

Author
Unknown author
David Leal

Function Documentation

◆ isSafe()

template<size_t n>
bool backtracking::n_queens::isSafe ( const std::array< std::array< int, n >, n > &  board,
const int &  row,
const 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
58  {
59  int i = 0, j = 0;
60 
61  // Check this row on left side
62  for (i = 0; i < col; i++) {
63  if (board[row][i]) {
64  return false;
65  }
66  }
67 
68  // Check upper diagonal on left side
69  for (i = row, j = col; i >= 0 && j >= 0; i--, j--) {
70  if (board[i][j]) {
71  return false;
72  }
73  }
74  // Check lower diagonal on left side
75  for (i = row, j = col; j >= 0 && i < n; i++, j--) {
76  if (board[i][j]) {
77  return false;
78  }
79  }
80  return true;
81  }

◆ main()

int main ( void  )

Main function

118  {
119  const int n = 4;
120  std::array<std::array<int, n>, n> board = {
121  std::array<int, n>({0, 0, 0, 0}),
122  std::array<int, n>({0, 0, 0, 0}),
123  std::array<int, n>({0, 0, 0, 0}),
124  std::array<int, n>({0, 0, 0, 0})
125  };
126 
127  backtracking::n_queens::solveNQ<n>(board, 0);
128  return 0;
129 }

◆ printSolution()

template<size_t n>
void backtracking::n_queens::printSolution ( 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
37  {
38  std::cout << "\n";
39  for (int i = 0; i < n; i++) {
40  for (int j = 0; j < n; j++) {
41  std::cout << "" << board[i][j] << " ";
42  }
43  std::cout << "\n";
44  }
45  }

◆ solveNQ()

template<size_t n>
void backtracking::n_queens::solveNQ ( std::array< std::array< int, n >, n >  board,
const int &  col 
)

Solve n queens problem

Template Parameters
nnumber of matrix size
Parameters
boardmatrix where numbers are saved
colcurrent index in columns
90  {
91  if (col >= n) {
92  printSolution<n>(board);
93  return;
94  }
95 
96  // Consider this column and try placing
97  // this queen in all rows one by one
98  for (int i = 0; i < n; i++) {
99  // Check if queen can be placed
100  // on board[i][col]
101  if (isSafe<n>(board, i, col)) {
102  // Place this queen in matrix
103  board[i][col] = 1;
104 
105  // Recursive to place rest of the queens
106  solveNQ<n>(board, col + 1);
107 
108  board[i][col] = 0; // backtrack
109  }
110  }
111  }
Here is the call graph for this function:
std::cout
std::array
STL class.