网站首页轮播图怎么换,渭南企业网站建设,渭南建网站,网站开发项目分析模板题目描述(困难难度)给定一个数独棋盘#xff0c;输出它的一个解。解法一 回溯法从上到下#xff0c;从左到右遍历每个空位置。在第一个位置#xff0c;随便填一个可以填的数字#xff0c;再在第二个位置填一个可以填的数字#xff0c;一直执行下去直到最后一个位置。期间如…题目描述(困难难度)给定一个数独棋盘输出它的一个解。解法一 回溯法从上到下从左到右遍历每个空位置。在第一个位置随便填一个可以填的数字再在第二个位置填一个可以填的数字一直执行下去直到最后一个位置。期间如果出现没有数字可以填的话就回退到上一个位置换一下数字再向后进行下去。public void solveSudoku(char[][] board) {solver(board);}private boolean solver(char[][] board) {for (int i 0; i 9; i) {for (int j 0; j 9; j) {if (board[i][j] .) {char count 1;while (count 9) {if (isValid(i, j, board, count)) {board[i][j] count;if (solver(board)) {return true;} else {//下一个位置没有数字就还原然后当前位置尝试新的数board[i][j] .;}}count;}return false;}}}return true;}private boolean isValid(int row, int col, char[][] board, char c) {for (int i 0; i 9; i) {if (board[row][i] c) {return false;}}for (int i 0; i 9; i) {if (board[i][col] c) {return false;}}int start_row row / 3 * 3;int start_col col / 3 * 3;for (int i 0; i 3; i) {for (int j 0; j 3; j) {if (board[start_row i][start_col j] c) {return false;}}}return true;}时间复杂度空间复杂度O(1)。总回溯法一个很典型的应用了。