首页 > 代码库 > [LeetCode] N-Queens
[LeetCode] N-Queens
N-Queens
Total Accepted: 9970 Total Submissions: 38919My Submissions
The n-queens puzzle is the problem of placing n queens on an n×n chessboard such that no two queens attack each other.
Given an integer n, return all distinct solutions to the n-queens puzzle.
Each solution contains a distinct board configuration of the n-queens‘ placement, where ‘Q‘ and ‘.‘ both indicate a queen and an empty space respectively.
For example,
There exist two distinct solutions to the 4-queens puzzle:
[
[".Q..", // Solution 1
"...Q",
"Q...",
"..Q."],
["..Q.", // Solution 2
"Q...",
"...Q",
".Q.."]
]
Solution:
//board is 0 for avaliable positons, 1 for the otherint board[100][100];int queenPos[100];int N;int solutionNum = 0;vector<vector<string> > result;void dfs(int k){ if(k == N) {//the last queen has been put properly solutionNum++; vector<string> cur; for(int i = 0;i < N;i++) { string column= ""; for(int j = 0;j < N;j++) { if(queenPos[i] == j) column += "Q"; else column += "."; } // cout << column << endl; cur.push_back(column); } // cout << endl << endl; result.push_back(cur); return; } for(int i = 0;i < N;i++) { //search for a postion for the current queen bool flag = true; if(board[i][k] == 0) { list<int> lastX, lastY; //this is a good postion for the k th column queen. queenPos[k] = i;//in the ith row, kth column //change the board state to mark its attark region. for(int j = 0;j < N;j++) { if(board[i][j] == 0) { board[i][j] = 1; lastX.push_back(i); lastY.push_back(j); // cout << i << " " << j << endl; } if(board[j][k] == 0) { board[j][k] = 1; lastX.push_back(j); lastY.push_back(k); //cout << j << " " << k << endl; } // if(i - j >= 0 && k - j >= 0 && board[i - j][k - j] == 0) { //left up lastX.push_back(i - j); lastY.push_back(k - j); board[i - j][k - j] = 1; //cout << i -j << " " << k - j << endl; } if(i - j >= 0 && k + j < N && board[i - j][k + j] == 0) { lastX.push_back(i - j); lastY.push_back(k + j); board[i - j][k + j] = 1; //cout << i -j << " " << k + j << endl; } if(i + j < N && k - j >= 0 && board[i + j][k - j] == 0) { lastX.push_back(i + j); lastY.push_back(k - j); board[i + j][k - j] = 1; // cout << i + j << " " << k - j << endl; } if(i + j < N && k + j < N && board[i + j][k + j] == 0) { lastX.push_back(i + j); lastY.push_back(k + j); board[i + j][k + j] = 1; // cout << i + j << " " << k + j << endl; } } //cout << "put the " << k << " queen at " << i << " size = " << lastX.size() << endl; dfs(k + 1); //cout << "size = " << lastX.size() << endl; //back to the previous state. int num = lastX.size(); for(int t = 0;t < num;t++) { int x = lastX.front(); lastX.pop_front(); int y = lastY.front(); lastY.pop_front(); board[x][y] = 0; // cout << x << " " << y << endl; } } else continue; }}vector<vector<string> > solveNQueens(int n) { N = n; solutionNum = 0; for(int i = 0;i < 100;i++) { for(int j = 0;j < 100;j++) board[i][j] = 0; queenPos[i] = 0; } dfs(0); return result; }
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。