Hokachi 2022-01-11 13:31 采纳率: 66.7%

# leetcode37.解数独

###### 问题相关代码，请勿粘贴截图

class Solution {
public void solveSudoku(char[][] board) {
getNext(board);
}

``````private static List<String> getPossibleStatus(char[][] board,int x,int y){
List<String> ans = new ArrayList<String>();

//检查行
for(int i=0;i<9;i++){
if(board[x][i]!='.'){
if(board[x][i]==(char)i){
ans.remove("1");
}else if(board[x][i]=='2'){
ans.remove("2");
}else if(board[x][i]=='3'){
ans.remove("3");
}else if(board[x][i]=='4'){
ans.remove("4");
}else if(board[x][i]=='5'){
ans.remove("5");
}else if(board[x][i]=='6'){
ans.remove("6");
}else if(board[x][i]=='7'){
ans.remove("7");
}else if(board[x][i]=='8'){
ans.remove("8");
}else if(board[x][i]=='9'){
ans.remove("9");
}
}
}
//检查列
for(int i=0;i<9;i++){
if(board[i][y]!='.'){
if(board[i][y]=='1'){
ans.remove("1");
}else if(board[i][y]=='2'){
ans.remove("2");
}else if(board[i][y]=='3'){
ans.remove("3");
}else if(board[i][y]=='4'){
ans.remove("4");
}else if(board[i][y]=='5'){
ans.remove("5");
}else if(board[i][y]=='6'){
ans.remove("6");
}else if(board[i][y]=='7'){
ans.remove("7");
}else if(board[i][y]=='8'){
ans.remove("8");
}else if(board[i][y]=='9'){
ans.remove("9");
}
}
}
//检查九宫格
for(int i=0;i<3;i++){
for(int j=0;j<3;j++){
if(board[(x/3)*3+i][(y/3)*3+j]!='.'){
if(board[(x/3)*3+i][(y/3)*3+j]=='1'){
ans.remove("1");
}else if(board[(x/3)*3+i][(y/3)*3+j]=='2'){
ans.remove("2");
}else if(board[(x/3)*3+i][(y/3)*3+j]=='3'){
ans.remove("3");
}else if(board[(x/3)*3+i][(y/3)*3+j]=='4'){
ans.remove("4");
}else if(board[(x/3)*3+i][(y/3)*3+j]=='5'){
ans.remove("5");
}else if(board[(x/3)*3+i][(y/3)*3+j]=='6'){
ans.remove("6");
}else if(board[(x/3)*3+i][(y/3)*3+j]=='7'){
ans.remove("7");
}else if(board[(x/3)*3+i][(y/3)*3+j]=='8'){
ans.remove("8");
}else if(board[(x/3)*3+i][(y/3)*3+j]=='9'){
ans.remove("9");
}
}
}
}
return ans;
}

//填入数据
private static char[][] fillNum(char[][] board,int x,int y,char ch){
board[x][y] = ch;
return board;
}

//更新
private static void getNext(char[][] board){
boolean flag = true;
for(int a=0;a<9;a++) {
for (int b = 0; b < 9; b++) {
if (board[a][b] == '.') {
flag = false;
}
}
}
if(flag){
return;
}
for(int x=0;x<9;x++) {
for (int y=0;y<9;y++) {
if (board[x][y] == '.') {
List<String> ans = new ArrayList<String>();
ans = getPossibleStatus(board, x, y);
if (ans.size() == 1) {//找到唯一值
String temp = ans.get(0);
char[] target = temp.toCharArray();
board = fillNum(board, x, y, target[0]);
getNext(board);
}
}
}
}
}
``````

}

• 写回答

#### 1条回答默认 最新

• bekote 2022-01-11 15:27
关注

改一下getNext方法，某一步有两个或者以上的选项时依次递归试验填充

``````
class Solution {
public void solveSudoku(char[][] board) {
getNext(board,0,0);
}
private static List<String> getPossibleStatus(char[][] board,int x,int y){
List<String> ans = new ArrayList<String>();

//检查行
for(int i=0;i<9;i++){
if(board[x][i]!='.'){
if(board[x][i]==(char)i){
ans.remove("1");
}else if(board[x][i]=='2'){
ans.remove("2");
}else if(board[x][i]=='3'){
ans.remove("3");
}else if(board[x][i]=='4'){
ans.remove("4");
}else if(board[x][i]=='5'){
ans.remove("5");
}else if(board[x][i]=='6'){
ans.remove("6");
}else if(board[x][i]=='7'){
ans.remove("7");
}else if(board[x][i]=='8'){
ans.remove("8");
}else if(board[x][i]=='9'){
ans.remove("9");
}
}
}
//检查列
for(int i=0;i<9;i++){
if(board[i][y]!='.'){
if(board[i][y]=='1'){
ans.remove("1");
}else if(board[i][y]=='2'){
ans.remove("2");
}else if(board[i][y]=='3'){
ans.remove("3");
}else if(board[i][y]=='4'){
ans.remove("4");
}else if(board[i][y]=='5'){
ans.remove("5");
}else if(board[i][y]=='6'){
ans.remove("6");
}else if(board[i][y]=='7'){
ans.remove("7");
}else if(board[i][y]=='8'){
ans.remove("8");
}else if(board[i][y]=='9'){
ans.remove("9");
}
}
}
//检查九宫格
for(int i=0;i<3;i++){
for(int j=0;j<3;j++){
if(board[(x/3)*3+i][(y/3)*3+j]!='.'){
if(board[(x/3)*3+i][(y/3)*3+j]=='1'){
ans.remove("1");
}else if(board[(x/3)*3+i][(y/3)*3+j]=='2'){
ans.remove("2");
}else if(board[(x/3)*3+i][(y/3)*3+j]=='3'){
ans.remove("3");
}else if(board[(x/3)*3+i][(y/3)*3+j]=='4'){
ans.remove("4");
}else if(board[(x/3)*3+i][(y/3)*3+j]=='5'){
ans.remove("5");
}else if(board[(x/3)*3+i][(y/3)*3+j]=='6'){
ans.remove("6");
}else if(board[(x/3)*3+i][(y/3)*3+j]=='7'){
ans.remove("7");
}else if(board[(x/3)*3+i][(y/3)*3+j]=='8'){
ans.remove("8");
}else if(board[(x/3)*3+i][(y/3)*3+j]=='9'){
ans.remove("9");
}
}
}
}
return ans;
}

//填入数据
private static char[][] fillNum(char[][] board,int x,int y,char ch){
board[x][y] = ch;
return board;
}

//更新方法改为递归
//更新
private static boolean getNext(char[][] board,int x, int y){
if(x==9){
//所有行已填充，返回true，标志该遍历路线填充成功
return true;
}
if(y==9){
//超过最后一列格子时，跳到下一行的第一列
return getNext(board, x+1, 0);
}
if(board[x][y]!='.'){
//已有数字的格子跳过
return getNext(board, x, y+1);
}
//获取所有可以填的数字
List<String> ans = getPossibleStatus(board, x, y);
if(ans.size() == 0){
//没有可以填的数字，返回false，标志该遍历路线填充失败
return false;
}
for(int i=0;i<ans.size();i++){
//所有可以填的数字依次试验
String temp = ans.get(i);
char[] target = temp.toCharArray();
board = fillNum(board, x, y, target[0]);
boolean flag = getNext(board, x, y+1);
//flag表示当前格子填充数字ans[i]后往后遍历是否可以填充成功
if(flag){
//返回true,标志该遍历路线填充成功
return true;
}
//flag为false表示当前格子不能填充数字ans[i]，将其回复为点
fillNum(board, x, y, '.');
}
//没有找到可以填充到当前格子，并使得后续遍历填充成功的数字（说明上一步填充有错误），返回false,标志该遍历路线填充失败
return false;
}
}
``````
本回答被题主选为最佳回答 , 对您是否有帮助呢?
评论

• 系统已结题 1月21日
• 已采纳回答 1月13日
• 创建了问题 1月11日

#### 悬赏问题

• ¥15 斯坦福自动漂移非线性模型反解
• ¥15 学习Python如何找兼职
• ¥15 python结合Matlab仿真忆阻器
• ¥35 有人会注册whatsaop协议号吗？