首页 > 代码库 > N-Queens
N-Queens
N皇后问题，经典中的经典。
第一遍的时候，只有点思路，但是想不清楚，看了别人的代码。
方法一(Java)：
public class Solution { int[] row; int[] col; ArrayList<String[]> res; int N; public void dfs(int r) { int j; if(r==N) { String[] sa=getBoard(); res.add(sa); return; } for(int i=0;i<N;i++) { if(col[i]==0) { for(j=0;j<r;++j) { if(Math.abs(j-r)==Math.abs(i-row[j])) break; } if(j==r) { row[r]=i; col[i]=1; dfs(r+1); col[i]=0; row[r]=0; } } } } public String[] getBoard() { char[] ca=new char[N]; Arrays.fill(ca,‘.‘); String line; String[] ret=new String[N]; for(int i=0;i<N;i++) { ca[row[i]]=‘Q‘; line=new String(ca); ca[row[i]]=‘.‘; ret[i]=line; } return ret; } public ArrayList<String[]> solveNQueens(int n) { N=n; row=new int[n]; col=new int[n]; res=new ArrayList<String[]>(); dfs(0); return res; }}
基本思想是dfs，深度就是行数。对于每一层，从左到右依次在可以放的位置放上皇后。用一个行数组和一个列数组来记录当前哪些行、哪些列是放了皇后的。能否放皇后由一个单独的判断函数来执行。这就是典型的dfs+判断函数模式。判断函数就要借助于行数组和列数组。
方法二（c++）：
class Solution {public: int N; vector<string> *pBoard; vector<vector<string>> res; vector<vector<string> > solveNQueens(int n) { N=n; vector<string> board(N,string(N,‘.‘)); pBoard=&board; solve(0); return res; } void solve(int r) { if(r==N) { addSolution(); return; } for(int c=0;c<N;c++) { if(canPlace(r,c)) { (*pBoard)[r][c]=‘Q‘; solve(r+1); (*pBoard)[r][c]=‘.‘; } } } void addSolution(){ res.push_back(*pBoard); } bool canPlace(int r,int c) { for(int i=0;i<r;i++) { if((*pBoard)[i][c]==‘Q‘|| (c+r-i<N&&(*pBoard)[i][c+r-i]==‘Q‘)|| (c-(r-i)>=0&&(*pBoard)[i][c-(r-i)]==‘Q‘)) return false; } return true; }};
第二遍的时候，完全没有意识要另外借助两个数组来记录放置位置。事实上是没有这个必要，因为我们一直都在维护这个棋盘，所有的信息都可以从棋盘中获得，因此判断函数也可以直接对棋盘进行分析而来。这种方式其实是更容易想到的，只是判断函数的条件确实要费一番周折。
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。