1.递归函数以及参数
递归函数的返回值需要是bool类型,为什么呢?
因为解数独找到一个符合的条件(就在树的叶子节点上)立刻就返回,相当于找从根节点到叶子节点一条唯一路径,所以需要使用bool返回值。
2.递归终止条件
本题递归不用终止条件,解数独是要遍历整个树形结构寻找可能的叶子节点就立刻返回
3.代码
private static boolean shudu(char[][] board) {//只需要找到符合条件的即可返回,所以返回值为boolean,true则直接return//递归没有终止条件,直接遍历到底部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++) {//遍历数字从1-9if (isValid(i, j, k, board)) {//判断是否合法,合法则填入board[i][j] = k;//递归if (shudu(board)) {return true;}//递归返回后,如果递归返回false,则将填入的数字还原,继续尝试下一个数字board[i][j] = '.';}}// 如果一行 Nine 个数字都尝试完,则返回 falsereturn false;}}//全部遍历完也没有false,则返回truereturn true;}private static boolean isValid(int i, int j, char k, char[][] board) {for (int row = 0; row < 9; row++) {//判断行if (board[row][j] == k) {return false;}}for (int col = 0; col < 9; col++) {//判断列if (board[i][col] == k) {return false;}}for (int row = (i / 3) * 3; row < (i / 3) * 3 + 3; row++) {//(i / 3)为第几个九宫格 (i / 3) * 3为这个九宫格的起点//判断九宫格for (int col = (j / 3) * 3; col < (j / 3) * 3 + 3; col++) {if (board[row][col] == k) {return false;}}}return true;}