Eight Queens puzzle, printing all solutions
More...
#include <iostream>
#include <array>
Eight Queens puzzle, printing all solutions
- Author
- Himani Negi
-
David Leal
◆ 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
-
- 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
52 for (
int i = 0; i < col; i++) {
53 if (board[row][i] == 1) {
58 for (
int i = row, j = col; i >= 0 && j >= 0; i--, j--) {
59 if (board[i][j] == 1) {
64 for (
int i = row, j = col; i <= n - 1 && j >= 0; i++, j--) {
65 if (board[i][j] == 1) {
◆ main()
◆ 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
-
- Parameters
-
board | matrix where numbers are saved |
col | current index in columns |
84 for (
int i = 0; i < n; i++) {
85 if (CanIMove(board, i, col)) {
87 NQueenSol(board, col + 1);
◆ 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
-
- Parameters
-
board | matrix where numbers are saved |
31 for (
int i = 0; i < n; i++) {
32 for (
int j = 0; j < n; j++) {