思路
八皇后问题是很经典的递归回溯问题,就是在每一行尝试放置皇后,观察是否会冲突,这里就最简单粗暴的写出来解法吧。
#include <iostream> #include <vector> using namespace std; /* 检查是否冲突 */ bool isVaild(vector<string>& board, int row, int col){ int n = board.size(); for(int i = 0; i < n; i ++) if(board[row][i] == 'Q') return false; for(int i = 0; i < n; i ++) if(board[i][col] == 'Q') return false; for(int i = row - 1, j = col + 1; i >= 0 && j < n; i --, j ++) if(board[i][j] == 'Q') return false; for(int i = row - 1, j = col - 1; i >= 0 && j >= 0; i --, j --) if(board[i][j] == 'Q') return false; return true; } vector<string> ans; void backTrack(vector<string>& board, int row, string s){ if(row == (int)board.size()){ ans.emplace_back(s); return; } /* 在每一行尝试放置皇后 */ for(int i = 0; i < board[0].size(); i++){ if(!isVaild(board, row, i)) continue; board[row][i] = 'Q'; s.push_back(i + 1 + '0'); backTrack(board, row + 1, s); /* 回溯 */ board[row][i] = '.'; s.pop_back(); } } int main(){ int n; vector<string> board(8, string(8, '.')); string s = ""; backTrack(board, 0, s); while(cin >> n){ cout << ans[n - 1] << endl; } }