网站怎么建立视频,WordPress和微信公众号自动回复,google网站地图格式,网站优化对企业有什么好处题目描述#xff1a;编写一个程序#xff0c;通过填充空格来解决数独问题。 数独的解法需 遵循如下规则#xff1a; 数字 1-9 在每一行只能出现一次。 数字 1-9 在每一列只能出现一次。 数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。#xff08;请参考示例图编写一个程序通过填充空格来解决数独问题。 数独的解法需 遵循如下规则 数字 1-9 在每一行只能出现一次。 数字 1-9 在每一列只能出现一次。 数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。请参考示例图 数独部分空格内已填入了数字空白格用 ‘.’ 表示。 题目链接LeetCode-37-解数独 解题思路 代码实现 class Solution {/*** 1. 可以看成二维数组的回溯* 2.需要一个isVaild()辅助判断k需要和每个小九宫格和所在的行和列都要判断*/public void solveSudoku(char[][] board) {backTracking(board);}public boolean backTracking(char[][] board){for (int i 0; i board.length; i) {for (int j 0; j board[0].length; j) {if (board[i][j]!.){continue;}for (char k1;k9;k){if (isVaild(board,k,i,j)){// 判断 board[i][j]位置放k是否可行board[i][j]k;//放kif (backTracking(board)){return true;}board[i][j].;// 回溯}}return false;//说明9个数都试完了也找不到看合适的放置位置}}return true;}// 判断当前的val// 1. 所在的row中有没有相同的// 2. 所在的col中有没有相同的// 3. 所在的九宫格中有没有相同的public boolean isVaild(char[][] board, char val, int row,int col){// 1.所在的row中有没有相同的for (int i 0; i board.length; i) {if(board[row][i] val){return false;}}// 2. 所在的col中有没有相同的for (int i 0; i board.length; i) {if(board[i][col] val){return false;}}// 3. 所在的九宫格中有没有相同的int startRow (row /3)*3;int startCol (col /3)*3;for (int i startRow; i startRow3; i) {for (int j startCol; j startCol3; j) {if (board[i][j] val){return false;}}}return true;}
}
