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.."] ]
NOTE: The queen (♕,♛) is the most powerful piece in the game of chess,
able to move any number of squares vertically, horizontally, or diagonally.A:
--------------------2 nd pass----------------------
DFS ---------- Use 2D array
出现的问题,还是在于,测试diagonal的时候, 两条diagonal的表达有问题。比较坐标系不同。而这个问题其实很好解决。就是看(row,col) 所在的对角线有什么特征即可。不用考虑坐标系转换。
public class Solution { public List<List<String>> solveNQueens(int n) { char[][] board = new char[n][n]; for(int i=0;i<n;i++) Arrays.fill(board[i],'.'); List<List<String>> all = new LinkedList<List<String>>(); dfs(board,0,all); return all; } private void dfs(char[][] board, int col, List<List<String>> all){ for(int i =0;i<board.length;i++){ board[i][col] = 'Q'; if(isValid(board,i,col)){ if(col==board.length-1){// done List list = new LinkedList<String>(); for(int j =0;j<board.length;j++) list.add(new String(board[j])); all.add(list); }else{ dfs(board,col+1,all); } } board[i][col] = '.'; } } private boolean isValid(char[][] board, int row ,int col){ // board[i][j] is just been set for(int j=0; j<col; j++) if(board[row][j]=='Q') return false; for(int i=0;i<board.length;i++){ int j = row + col -i;// check diagal / if(i!= row && j>=0 && j< col && board[i][j]=='Q') return false; j = i + col - row; // check diagonal \ if(i!= row && j>=0 && j< col && board[i][j]=='Q') return false; } return true; } }
--------------3rd pass---------------------
这里用了2D array, 如果用一维数组表示的话(类似于N-Queen II) ,
方法是:一维数组的下标表示横坐标(哪一行),而数组的值表示纵坐标(哪一列)。
Mistakes:
1: System.out.print(str[i].charAt(j) + '\t'); 打印出的结果是数字。 哎, 不是char 类型
应该写成System.out.print(""+str[i].charAt(j) + '\t'); 加个"" 就好了。
2:
No comments:
Post a Comment