/* Written by: bornToCode() This method uses backtracking (a type of recursion). */ #include using namespace std; class QueensConfig { public: QueensConfig(int size) : boardSize(size), rowCount(0) { board = new bool*[boardSize]; for(int i = 0; i < boardSize; i++) { board[i] = new bool[boardSize]; } for(int i = 0; i < size; i++) { for(int j = 0; j < size; j++) { board[i][j] = false; } } } ~QueensConfig() { for(int i = 0; i < boardSize; i++) { delete[] board[i]; } delete[] board; } bool isSolved() const { return rowCount == boardSize; } void insert(int col) { if(col >= boardSize) return; board[rowCount][col] = true; rowCount++; } void remove(int col) { if(col >= boardSize) return; board[rowCount - 1][col] = false; rowCount--; } bool unguarded(int col) const { // check the queen's column for(int i = 0; i < rowCount ; i++) { if(board[i][col]) return false; } // check upper left diagonals for(int i = rowCount - 1, j = col - 1; i >= 0 && j >= 0; i--, j--) { if(board[i][j]) return false; } // check upper right diagonals for(int i = rowCount, j = col; i >= 0 && j < boardSize; i--, j++) { if(board[i][j]) return false; } // backtracking, lower diagonals // are uneccessary return true; } int size() const { return boardSize; } void print() const { cout << endl; for(int row = 0; row < boardSize; row++) { cout << endl; for(int col = 0; col < boardSize; col++) { if(board[row][col] == true) cout << "Q "; else cout << "# "; } } cout << endl; } private: int rowCount; int boardSize; bool **board; }; void solveFrom(QueensConfig &config) { if(config.isSolved()) config.print(); else { for(int col = 0; col < config.size(); col++) { if(config.unguarded(col)) { config.insert(col); solveFrom(config); config.remove(col); } } } } int main() { int n; cout << "Enter the number of queens: "; cin >> n; cout << n << endl; QueensConfig config(n); solveFrom(config); return 0; }

[Challenge] N-Queens Problem