N Queens I II

Leave a comment

September 15, 2016 by oneOokay

33. N Queens I

花了好一阵子才理解TOT

  1. 这题用DFS来找到所有的solution
  2. 用一个int[N] oneResult的array来存一组答案:其中oneResult[i]表示:在棋盘的row index = i, column index = oneResult[i]放置了一个Queen。节省了存储空间,而且单行只放一个Queen,省去了对放置同一行的判断。
  3. 判断在棋盘的<i,j>位置放置Queen是否valid的方法:
    1. 若(x1,y1)与(x2,y2)在对角线位置上,则:Math.abs(x1-x2) == Math.abs(y1-y2)
  4. 把一组答案数组int[]转化为标准输出的translate method

另一个解法是所谓的位操作法,以后有空可以看一下:https://getpocket.com/a/read/214778320

ArrayList<ArrayList<String>> solveNQueens(int n) {
ArrayList<ArrayList<String>> result = new ArrayList<ArrayList<String>>();
if (n <= 0) {
return result;}
int[] row = new int[n];
solveNQueensCore(result, row, n, 0); //从第0行开始
return result;}
//dfs主体
private void solveNQueensCore(ArrayList<ArrayList<String>> result, int[] oneResult, int N, int rowIndex){ //N为棋盘的size不变,rowIndex表示现在正在对row index = rowIndex的行做bfs,这里rowIndex随着bfs的深入逐渐 + 1
if (rowIndex == N) { //rowIndex是0开始的,所以当rowIndex == N时表示上一次的dfs是棋盘的最后一行并且找到了放置Queen的点,由此找到了一个solution,将其加入result中,结束bfs
result.add(translate(oneResult));
return;}
//开始对row index = rowIndex的行的所有元素,从列为0的元素开始处理一个一个的开始处理
for (int i = 0; i < N; i ++) {
if (isValid(oneResult, rowIndex, i)){//<rowIndex, i> 该位置可以放置一个Queen,标记该点,从该点开始向下一层进行dfs
oneResult[rowIndex] = i;
solveNQueensCore(result, oneResult, N, rowIndex + 1);
oneResult[rowIndex] = 0; //<rowIndex,i>这一点放置Queen的dfs完成了,把该点位置清楚,继续对<rowIndex, i+1>进行处理
}}}
//result是存储Queen放置位置的集,判断若把Queen放在<row, column>这个坐标上,对于result这个已放置一些Queens的棋盘来说,是否valid
private boolean isValid(int[] result, int row, int column){
for (int i = 0; i < row; i ++) {//这里不能用result.length.应该只判断已经放置过Queen的行
if (result[i] == column){ //若在<row, column>放置,已存在棋面中有一个Queen与她同列
return false;
}
if (Math.abs(row – i) == Math.abs(result[i] – column)){ //存在对角线,invalid
return false;
}}
return true;
}

private ArrayList<String> translate(int[] oneResult) {
ArrayList<String> result = new ArrayList<String>();
for (int i = 0; i < oneResult.length; i ++) {
StringBuilder sb = new StringBuilder();
for (int j = 0; j < oneResult.length; j ++){
if (j == oneResult[i]) {
sb.append(“Q”);
}else {
sb.append(“.”);}}
result.add(sb.toString());}
return result;}

34. NQueens II

解决了NQueens I 之后对于 II看上去就简单了点。省去了ArrayList<ArrayList<String>> 来存result,直接在dfs中,当rowIndex == N的时候, solutionNumber + 1.

private int solution = 0;
public int totalNQueens(int n) {
if ( n <= 0){
return 0;
}
int[] oneResult = new int[n];
solveNQueens(oneResult, n, 0);
return solution;
}

private void solveNQueens(int[] oneResult, int N, int rowIndex) {
if( rowIndex == N) {
solution ++;
return;
}

for (int i = 0; i < oneResult.length; i ++) {
if (isValid(oneResult, rowIndex, i)){
oneResult[rowIndex] = i;
solveNQueens(oneResult, N, rowIndex + 1);
oneResult[rowIndex] = 0;}}}

private boolean isValid(int[] result, int row, int col) {
for (int i = 0; i < row; i ++) {
if (result[i] == col) {
return false;
}
if (Math.abs(result[i] – col) == Math.abs(i – row)){
return false;
}}
return true;
}

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: