This is the 26th day of my participation in the August Text Challenge.More challenges in August
I was happy to win the table tennis match last night. This week’s exercise goals have been achieved, and by the end of this week, the August challenge will be almost complete. Walk a hundred steps of the half of the 90, almost the last week of the time to encourage. Today we’re on problem 37 of Leetcode.
The title
Write a program to solve a sudoku problem by filling in the blanks.
The solution of sudoku must follow the following rules:
The numbers 1-9 can appear only once in each line. The numbers 1-9 May appear only once in each column. The numbers 1-9 can occur only once in each 3×3 palace separated by a thick solid line. (Please refer to the sample figure) Numbers have been filled in the space of the Sudoku part, and the blank space is represented by ‘.’.
Input: board = [[” 5 “, “3”, “”,” “, “7”, “”,” “, “”,” “], [” 6 “, “”,” “, “1”, “9”, “5”, “”,” “, “”], [“.”, “9”, “eight” and “. “, “”,” “, “”,” 6 “, “”], [” 8″, “. “, “”,”. “, “6”, “”,” “, “”,” 3 “], [” 4 “, “”,” “, “eight” and “. “, “3”, “”,” “, “1”], [” 7 “, “”,” “, “”,” 2 “, “”,” “, “”,” 6 “], [“. “, “6”, “. “, “. “, “. “, “. “, “2”, “eight” and “. “], [“. “, “”,” “, “4”, “1”, “9”, “”,” “, “5”], [“. “, “”,” “, “”,” eight “and”. “, “”,” 7 “, “9”]] output: [[” 5 “, “3”, “4”, “6”, 7 “, “eight” and “9”, “1”, “2”], [” 6 “, “7”, “2”, “1”, “9”, “5”, “3”, “4”, “eight”], [” 1 “, “9”, “eight”, “3”, “4”, “2”, “5”, “6”, “7”], [” 8 “, “5”, “9”, “7”, “6”, “1”, “4”, “2”, “3”], [” 4 “, “2”, “6”, “eight” and “5”, “3”, “7”, “9”, “1”], [” 7 “, “1”, “3”, “9”, “2”, “4”, “eight” and “5”, “6”], [” 9 “, “6”, “1 “, “5”, “3”, “7”, “2”, “eight”, “4”], [” 2 “, “eight”, “7”, “4”, “1”, “9”, “6”, “3”, “5”], [” 3 “, “4”, “5”, “2”, “eight” and “6”, “1”, “7”, “9”]] : The input sudoku is shown above, and the only valid solution is as follows:
Train of thought
Today’s problem is a continuation of yesterday’s problem, yesterday was whether the check is valid, today’s problem is to solve. In fact, there is nothing special to say, according to the rules of Sudoku, each row, each column, each small square, are 1-9 each appear once. To reflect the program, use 3 Boolean two-dimensional arrays: The first dimension of line represents rows 0 through 8 of the array, the second dimension represents 1 through 9 and the first dimension of column represents columns 0 through 8 of the array, the second dimension represents 1 through 9 and the first dimension of box represents boxes 0 through 8, The second dimension represents whether the numbers 1 through 9 are present and then a deep search + backtracking.
Java version code
Class Solution {public void solveSudoku(char[][] board) {// For (int I = 0; i < 9; i++) { for (int j = 0; j < 9; j++) { if (board[i][j] ! = '.') { int val = board[i][j] - '0'; line[i][val-1] = true; column[j][val-1] = true; box[i/3*3 + j/3][val-1] = true; } else { space.add(new Point(i, j)); }}} shuduDfs(board, 0); } private static boolean[][] line = new boolean[9][9]; private static boolean[][] column = new boolean[9][9]; private static boolean[][] box = new boolean[9][9]; private static List<Point> space = new ArrayList(); static boolean isValid = false; static class Point { private int x; private int y; public Point(int x, int y) { this.x = x; this.y = y; } public int getX() { return x; } public int getY() { return y; } } private static void shuduDfs(char[][] board, int num) { if (num == space.size()) { isValid = true; return; } Point point = space.get(num); int x = point.getX(); int y = point.getY(); for (int val = 1; val <= 9 && ! isValid; val++) { if (! line[x][val-1] && ! column[y][val-1] && ! box[x/3*3 + y/3][val-1]) { line[x][val-1] = column[y][val-1] = box[x/3*3 + y/3][val-1] = true; board[x][y] = (char) ('0' + val); shuduDfs(board, num + 1); line[x][val-1] = column[y][val-1] = box[x/3*3 + y/3][val-1] = false; }}}}Copy the code