A C++ Solution for the Eight Queens Puzzle

  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

/* 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 0
 * \date 2022
 * \copyright (c) 2022 DeepNet42. All rights reserved.
 * This project is released under the Mozilla Public License v. 2.0.	 
 */


#include <iostream>
#include <vector>
#include <stdexcept>


constexpr const int DEFAULT_BOARD_SIZE		= 8;
constexpr const int NONE					= -1;
constexpr const int DIA_SIZE				= 2 * DEFAULT_BOARD_SIZE - 2;

template <class T = int>
	std::ostream& operator << (std::ostream& os, const std::vector<T>& vect) {
		for(auto iter = vect.begin(); iter!=vect.end(); iter++) {
			// make it friendly to read
			os << (*iter) + 1 << (( iter!=(vect.end()-1)) ? ", " : "");  
		}
		return os;
}



class NQqueens {
	public:
	NQqueens(int n = DEFAULT_BOARD_SIZE) : 
	board(n,NONE), 
	horizotal(n,false), 
	diaRise(DIA_SIZE,false), 
	diaFall(DIA_SIZE,false), 
	n{n}, 
	solutions{0},
	solved{false}
	{

	}

	void enumerate() {
		solve(0);
	}

	auto count() const {
		return solutions;
	}
	
	private:

	void solve(int x) {

		if(x == n) {
			solutions++;
			std::cout << board << "\n";
		} else {
			for(int y = 0; y < n; y++) {
				if(good(x,y)) {
					board		[x    ] = y;
					horizotal	[y    ] = true;
					diaRise		[y-x+n] = true;
					diaFall		[x+y  ] = true; 

						solve(x+1);

					board		[x    ] = NONE;
					horizotal	[y    ] = false;
					diaRise		[y-x+n] = false;
					diaFall 	[x+y  ] = false; 
				} else {
				}
			}
		}
	}
	
	bool good(int x, int y) const {
		return !horizotal[y] and !diaRise[y-x+n] and !diaFall[x+y];
	}
	

	private:

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


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

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

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

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

	NQqueens nq(n);
	nq.enumerate();
	std::cout << "n = " << n << " has "<< nq.count() << " solutions\n";
	
	return EXIT_SUCCESS;
}