37. Sudoku Solver 回溯

本文主要是介绍37. Sudoku Solver 回溯，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

Write a program to solve a Sudoku puzzle by filling the empty cells.

Empty cells are indicated by the character '.'.

You may assume that there will be only one unique solution.

回溯问题：

思路：遍历所有的点 判断是否有效，有效则继续判断下一个点，无效则用下一个值尝试

public class Solution {public void solveSudoku(char[][] board) {solveSu(board);}private boolean solveSu(char [][] board){if(board==null||board.length==0) return false;for(int i=0;i<9;i++){                  //杭遍历for(int j=0;j<9;j++){		//列遍历if(board[i][j]=='.'){		//如果是 ‘.’开始试值for(char c='1';c<='9';c++){  if(isValidSu(board,i,j,c)){  //判断这个值在目前已经有的值的情况下 是否是有效的（局部有效） board[i][j]=c;	     //有效则给定这个值	if(solveSu(board))      //递归调用 return true;elseboard[i][j]='.';     //回溯 到上一层进行下一个值的尝试}}return false;//遍历过一遍for循环之后还没有成功就返回错误}}}return true;}private boolean isValidSu(char [][]board,int row,int col,char c){for(int i=0;i<board.length;i++){if(board[i][col]==c)return false;}for(int i=0;i<board[0].length;i++){if(board[row][i]==c)return false;}for(int i=row/3*3;i<row/3*3+3;i++){for(int j=col/3*3;j<col/3*3+3;j++){if(board[i][j]==c)return false;}}return true;}
}

这篇关于37. Sudoku Solver 回溯的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---