[LeetCode 3637] Valid Sudoku Sudoku Solver (数独问题）

题目链接：valid-sudoku

import java.util.Arrays;/** * Determine if a Sudoku is valid, according to: Sudoku Puzzles – The Rules.The Sudoku board could be partially filled, where empty cells are filled with the character '.'.A partially filled sudoku which is valid.Note:A valid Sudoku board (partially filled) is not necessarily solvable. Only the filled cells need to be validated. * */public class ValidSudoku {//数度有解的条件//Every digit from 1 to 9 must appear:1-9 这九个数字必须在下面各种情况只出现一次//In each of the columns,每列//in each of the rows,每行//and in each of the nine boxes.每个九宫格//501 / 501 test cases passed.//Status: Accepted//Runtime: 369 ms//Submitted: 1 minute ago//检查该数独是否有效//时间复杂度O(n^2) 空间复杂度O(n)public boolean isValidSudoku(char[][] board) {boolean[] flag = new boolean[10];//标记// 检查九行for (int i = 0; i < 9; i++) {Arrays.fill(flag, false);for (int j = 0; j < 9; j++) {if(board[i][j] == '.')continue;if (!flag[board[i][j] – '0']) {flag[board[i][j] – '0'] = true;} else {return false;}}}// 检查九列for (int j = 0; j < 9; j++) {Arrays.fill(flag, false);for (int i = 0; i < 9; i++) {if(board[i][j] == '.')continue;if (!flag[board[i][j] – '0']) {flag[board[i][j] – '0'] = true;} else {return false;}}}//检查九个九宫格for (int i = 0; i < 9; i += 3) {for (int j = 0; j < 9; j += 3) {Arrays.fill(flag, false);for (int i1 = 0; i1 < 3; i1++) {for (int j1 = 0; j1 < 3; j1++) {if(board[i + i1][j + j1] == '.')continue;if (!flag[board[i + i1][j + j1] – '0']) {flag[board[i + i1][j + j1] – '0'] = true;} else {return false;}}}}}return true;}public static void main(String[] args) {// TODO Auto-generated method stub}}

题目链接：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 SudokuSolver {//6 / 6 test cases passed.//Status: Accepted//Runtime: 260 ms//Submitted: 0 minutes ago//输入的数独只有唯一解//回溯法//时间复杂度O(n^4) 空间复杂度O(1)public void solveSudoku(char[][] board) {solveSudoku1(board);}public boolean solveSudoku1(char[][] board) {for (int i = 0; i < 9; i++) {for (int j = 0; j < 9; j++) {if(board[i][j] == '.') {for (int k = 1; k <= 9; k++) {board[i][j] = (char) ('0' + k);if(isValid(board, i, j) && solveSudoku1(board)) {return true;} else {board[i][j] = '.';//回溯法}}return false;}}}return true;}public boolean isValid(char[][] board, int i, int j) {//检查所属行for (int k = 0; k < 9; k++) {if(i != k && board[i][j] == board[k][j])return false;}//检查所属列for (int k = 0; k < 9; k++) {if(j != k && board[i][j] == board[i][k])return false;}//检查所属九宫格for (int i1 = 3 * (i / 3); i1 < (i / 3 + 1) * 3; i1 ++) {for (int j1 = 3 * (j / 3); j1 < (j / 3 + 1) * 3; j1 ++) {if(i1 != i && j1 != j && board[i][j] == board[i1][j1])return false;}}return true;}public static void main(String[] args) {// TODO Auto-generated method stub}}

，一个人的心胸宽阔，可以容不能容的事，可以赢难以赢的人。