A C++ Solution for the Eight Queens Puzzle

N-Queens Solver

In the previous article, we discussed the eight queens puzzle and developed a mathematical intuition needed for solving it; the rest of the article discussed how to apply recursion and backtracking techniques to solve the general n-queens problem. For completeness, we provide a sample solution in the C++ programming language.

The implementation of the algorithm for solving the n-queens problem is highlighted. This is a complete standalone program that will enumerate all valid solutions to the problem for a given n. The explanation for the algorithm can be found in the link above.

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146


/* This Source Code Form is subject to the terms of the Mozilla Public
 * License, v. 2.0. If a copy of the MPL was not distributed with this
 * file, You can obtain one at https://mozilla.org/MPL/2.0/. */

/**
 * \author DeepNet42
 * \file nqueens3_solutions.cpp
 * \version 1
 * \date 2022
 * \copyright (c) 2022 DeepNet42. All rights reserved.
 * This project is released under the Mozilla Public License v. 2.0.	 
 */


/* This Source Code Form is subject to the terms of the Mozilla Public
 * License, v. 2.0. If a copy of the MPL was not distributed with this
 * file, You can obtain one at https://mozilla.org/MPL/2.0/. */

/**
 * \author DeepNet42
 * \file nqueens3_solutions.cpp
 * \version 1
 * \date 2022
 * \copyright (c) 2022 DeepNet42. All rights reserved.
 * This project is released under the Mozilla Public License v. 2.0.	 
 */


#include <print>
#include <vector>
#include <stdexcept>
#include <algorithm>
#include <numeric>
#include <ranges>


constexpr const int DEFAULT_BOARD_SIZE		= 8;
constexpr const int NONE					= -1;
[[nodiscard]] constexpr const int diaSize(const int board_size) {
	return 2 * board_size;
}



class NQueens {
	public:
	NQueens(int n = DEFAULT_BOARD_SIZE) : 
	board(n,NONE), 
	horizontal(n,false), 
	diaRise(diaSize(n),false), 
	diaFall(diaSize(n),false), 
	n{n}, 
	solutions{0},
	solved{false}
	{

	}

	void enumerate() {
		solve(0);
	}

	[[nodiscard]] auto count() const {
		return solutions;
	}
	
	private:
	void placeQueen(int x, int y) {
		updateBoard(x,y,true);
	}

	void removeQueen(int x, int y) {
		updateBoard(x,y,false);
	}

	void updateBoard(int x, int y, bool state) {
		board		[x    ] = (state? y: NONE);
		horizontal	[y    ] = state;
		diaRise		[y-x+n] = state;
		diaFall		[x+y  ] = state; 
	}

	void solve(int x) {

		if(x == n) {
			solutions++;
			std::println("{}", board | std::views::transform([](int val){ return val + 1; }));
		} else {
			for(auto y : std::views::iota(0,n)) {
				if(good(x,y)) {
					placeQueen(x,y);
						solve(x+1);
					removeQueen(x,y);
				} else {
				}
			}
		}
	}
	
	[[nodiscard]] bool good(int x, int y) const {
		return !horizontal[y] and !diaRise[y-x+n] and !diaFall[x+y];
	}
	

	private:

	std::vector<int> board;
	std::vector<int> horizontal;
	std::vector<int> diaRise;
	std::vector<int> diaFall;
	
	int n;
	int solutions;
	bool solved;
};


int main(int argc, char* argv[]) {

	if(argc < 2) {
		std::println("usage: nqueens n");
		std::println("         1<=n<=X");
		return EXIT_FAILURE;
	}

	int n;
	try {
		n = std::stoi(argv[1]);
	} catch(std::invalid_argument& x) {
		std::println(stderr, "argument n is not a number.");
		std::println(stderr, "entered value = {}", argv[1]);
		return EXIT_FAILURE;
	}

	if(n < 1) {
		std::println(stderr, "argument n cannot be negative");
		std::println(stderr, "entered value = {}", argv[1]);
		return EXIT_FAILURE;
	}

	NQueens nq(n);
	nq.enumerate();
	std::println("n = {} has {} solutions", n, nq.count());
	
	return EXIT_SUCCESS;
}

Build

g++ nqueens3_solutions.cpp -o nqueens3_solutions -std=c++23

Sample Output

$./nqueens3_solutions 8 > out.txt
$(head; tail) < out.txt
1, 5, 8, 6, 3, 7, 2, 4
1, 6, 8, 3, 7, 4, 2, 5
1, 7, 4, 6, 8, 2, 5, 3
1, 7, 5, 8, 2, 4, 6, 3
2, 4, 6, 8, 3, 1, 7, 5
2, 5, 7, 1, 3, 8, 6, 4
2, 5, 7, 4, 1, 8, 6, 3
2, 6, 1, 7, 4, 8, 3, 5
2, 6, 8, 3, 1, 4, 7, 5
2, 7, 3, 6, 8, 5, 1, 4
7, 3, 1, 6, 8, 5, 2, 4
7, 3, 8, 2, 5, 1, 6, 4
7, 4, 2, 5, 8, 1, 3, 6
7, 4, 2, 8, 6, 1, 3, 5
7, 5, 3, 1, 6, 8, 2, 4
8, 2, 4, 1, 7, 5, 3, 6
8, 2, 5, 3, 1, 7, 4, 6
8, 3, 1, 6, 2, 5, 7, 4
8, 4, 1, 3, 6, 2, 7, 5
n = 8 has 92 solutions

Below is one solution to the n-queens problem where n = 25.

$./nqueens3_solutions 25
1, 3, 5, 2, 4, 9, 11, 13, 15, 19, 21, 24, 20, 25, 23, 6, 8, 10, 7, 14, 16, 18, 12, 17, 22

Interpreting the output

Suppose the following list of numbers: 8, 4, 1, 3, 6, 2, 7, 5. This can be interpreted as follows:

8, 4, 1, 3, 6, 2, 7, 5  <-- rows    (y)
1  2  3  4  5  6  7  8  <-- columns (x)

Visually the sequence above can be interpreted as:

figure 1: A visual interpretation for a sequence 8, 4, 1, 3, 6, 2, 7, 5

Bookkeeping

Update (2026-03-20): This version updates the source code provided prior to 2026-03-20.