- 解数独
class Solution {
public void solveSudoku(char[][] board) {
backTrace(board);
}
public boolean backTrace(char[][] board){
//仅收集一个结果
for(int i = 0;i<9;i++){
for(int j = 0;j<9;j++){
if(board[i][j] != '.') continue;
for (char k = '1'; k <= '9'; k++){
if (isValid(i, j, k, board)){
board[i][j] = k;
if (backTrace(board)) // 如果找到合适一组立刻返回
return true;
board[i][j] = '.';
}
}
// 9个数都试完了,都不行,那么就返回false
return false;
}
}
// 遍历完没有返回false,说明找到了合适棋盘位置了
return true;
}
/**
* 判断棋盘是否合法有如下三个维度:
* 同行是否重复
* 同列是否重复
* 9宫格里是否重复
*/
private boolean isValid(int row, int col, char val, char[][] board){
// 同行是否重复
for (int i = 0; i < 9; i++){
if (board[row][i] == val){
return false;
}
}
// 同列是否重复
for (int j = 0; j < 9; j++){
if (board[j][col] == val){
return false;
}
}
// 9宫格里是否重复
int startRow = (row / 3) * 3;
int startCol = (col / 3) * 3;
for (int i = startRow; i < startRow + 3; i++){
for (int j = startCol; j < startCol + 3; j++){
if (board[i][j] == val){
return false;
}
}
}
return true;
}
}
- N 皇后
class Solution {
List<List<String>> res = new ArrayList();
public List<List<String>> solveNQueens(int n) {
char[][] chessboard = new char[n][n];
for(char[] c : chessboard){
Arrays.fill(c,'.');
}
backTrace(chessboard,n,0);
return res;
}
public void backTrace(char[][] chessboard,int n,int row){
if(row == n){
res.add(arrays2String(chessboard));
}
//从0到第n列
for(int i = 0;i<n;i++){
if(!isValid(row,i,chessboard,n)) continue;
chessboard[row][i] = 'Q';
backTrace(chessboard,n,row+1);
chessboard[row][i] = '.';
}
}
public List<String> arrays2String(char[][] chessboard){
List<String> list = new ArrayList<>();
for (char[] c : chessboard) {
list.add(String.copyValueOf(c));
}
return list;
}
public boolean isValid(int row,int col,char[][] chessboard,int n){
//检查列
for(int i = 0;i<row;i++){
if(chessboard[i][col] == 'Q') return false;
}
// 检查45度对角线,从当前位置往左上
for(int i = row-1,j=col-1; i>=0&&j>=0;i--,j--){
if(chessboard[i][j] == 'Q') return false;
}
// 从当前位置往右上
for (int i=row-1, j=col+1; i>=0 && j<=n-1; i--, j++) {
if (chessboard[i][j] == 'Q') {
return false;
}
}
return true;
}
}
标签:row,return,int,chessboard,37,char,board,解数,hard51
From: https://blog.csdn.net/qq_51059003/article/details/136946253