摘要:题目要求也就是给出一个解决数独的方法,假设每个数独只有一个解决方案。并将当前的假象结果带入下一轮的遍历之中。如果最终遍历失败,则逐级返回,恢复上一轮遍历的状态,并填入下一个合理的假想值后继续遍历。
题目要求
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.
也就是给出一个解决数独的方法,假设每个数独只有一个解决方案。
思路一:不使用数据结构不使用数据结构意味着我们自己在每一次遇到一个空格时,需要在board中对该空格所在的行,列以及方块进行遍历,判断填入什么数字是合适的。并将当前的假象结果带入下一轮的遍历之中。如果最终遍历失败,则逐级返回,恢复上一轮遍历的状态,并填入下一个合理的假想值后继续遍历。这里涉及的时间复杂度是很高的,毕竟只是遍历整个board就需要O(n^2),如果遇到一个空格还需要O(n)来判断填入值是否合理。总共O(n^3)的时间复杂度。代码如下:
public void solveSudoku(char[][] board) { if(board == null || board.length == 0) return; solve(board); } public boolean solve(char[][] board){ for(int i = 0; i < board.length; i++){ for(int j = 0; j < board[0].length; j++){ if(board[i][j] == "."){ for(char c = "1"; c <= "9"; c++){//trial. Try 1 through 9 if(isValid(board, i, j, c)){ board[i][j] = c; //Put c for this cell if(solve(board)) return true; //If it"s the solution return true else board[i][j] = "."; //Otherwise go back } } return false; } } } return true; } //横 竖 方块 private boolean isValid(char[][] board, int row, int col, char c){ for(int i = 0; i < 9; i++) { if(board[i][col] != "." && board[i][col] == c) return false; //check row if(board[row][i] != "." && board[row][i] == c) return false; //check column if(board[3 * (row / 3) + i / 3][ 3 * (col / 3) + i % 3] != "." && board[3 * (row / 3) + i / 3][3 * (col / 3) + i % 3] == c) return false; //check 3*3 block } return true; }思路二:使用二维布尔数组分别记录行列和方块的所有值情况
我们使用boolean[][] rows, boolean[][] columns, boolean[][] squares分别记录行列和方块的所有值情况。其中rowsi记录i行是否有值j,columnsi记录i列是否有值j,squaresi记录第i个方块是否有值j。总体思路还是和上一个差不多,只是通过消费了存储空间的基础上提高了性能。
public void solveSudoku2(char[][] board) { int length = board.length; //记录第i行是否出现j数字 boolean[][] rows = new boolean[length][length+1]; //第i列是否出现j数字 boolean[][] columns = new boolean[length][length+1]; //第i个小方格是否出现j数字。 boolean[][] squares = new boolean[length][length+1]; for(int i = 0 ; i < length ; i++){ for(int j = 0 ; j更多解法 看到一个解答 效率很高 但是不是很明白 希望看到的大神解答一下
private boolean solver(int idx, char[][] board, ArrayListstack, int[] store) { if (idx == stack.size()) return true; int n = stack.get(idx); int y = n / 9; int x = n - y * 9; int h = y; int v = 9 + x; int b = 18 + (y / 3 * 3 + x / 3); int available = ~store[h] & ~store[v] & ~store[b] & 0b111111111; while (available > 0) { int bit = available & -available; int num = Integer.numberOfTrailingZeros(bit); store[h] ^= bit; store[v] ^= bit; store[b] ^= bit; board[y][x] = (char)(num + "1"); if (solver(idx + 1, board, stack, store)) return true; store[h] ^= bit; store[v] ^= bit; store[b] ^= bit; // board[y][x] = "."; available &= available - 1; } return false; } public void solveSudoku3(char[][] board) { ArrayList stack = new ArrayList<>(); // int[] stack = new int[81]; int len = 0; int[] store = new int[27]; // 0-8 h, 9 - 17 v, 18 - 26 b for (int i = 0; i < 9; i++) { for (int j = 0; j < 9; j++) { if (board[i][j] == ".") stack.add(i * 9 + j); else { int h = i; int v = 9 + j; int b = 18 + (i / 3 * 3 + j / 3); store[h] ^= 1 << board[i][j] - "1"; store[v] ^= 1 << board[i][j] - "1"; store[b] ^= 1 << board[i][j] - "1"; } } } solver(0, board, stack, store); }
想要了解更多开发技术,面试教程以及互联网公司内推,欢迎关注我的微信公众号!将会不定期的发放福利哦~
文章版权归作者所有,未经允许请勿转载,若此文章存在违规行为,您可以联系管理员删除。
转载请注明本文地址:https://www.ucloud.cn/yun/67363.html
Problem Write a program to solve a Sudoku puzzle by filling the empty cells. A sudoku solution must satisfy all of the following rules: Each of the digits 1-9 must occur exactly once in each row.Each ...
摘要:的可以由确定,这一点在里面的位置可以由确定所以每确定一行,每一个值都可以被转换到一个之中。如果允许的空间复杂度,可以设置一个二维数组来用来判断是否在里重现了重复的数字。将一个数字的每一个位上表示每一个数字。 Leetcode[36] Valid Sudoku Determine if a Sudoku is valid, according to: Sudoku Puzzles - ...
摘要:如果重复则不合法,否则极为合法。在这里我们使用数组代替作为存储行列和小正方形的值得数据结构。我存储这所有的行列小正方形的情况,并判断当前值是否重复。外循环则代表对下一行,下一列和下一个小正方形的遍历。 题目要求 Determine if a Sudoku is valid, according to: Sudoku Puzzles - The Rules. The Sudoku boa...
摘要:要求我们判断已经填入的数字是否满足数独的规则。即满足每一行每一列每一个粗线宫内的数字均含,不重复。没有数字的格子用字符表示。通过两层循环可以方便的检查每一行和每一列有没有重复数字。对于每个,作为纵坐标,作为横坐标。 题目详情 Determine if a Sudoku is valid, according to: Sudoku Puzzles - The Rules.The Sudo...
摘要:每天会折腾一道及以上题目,并将其解题思路记录成文章,发布到和微信公众号上。三汇总返回目录在月日月日这半个月中,做了汇总了数组知识点。或者拉到本文最下面,添加的微信等会根据题解以及留言内容,进行补充,并添加上提供题解的小伙伴的昵称和地址。 LeetCode 汇总 - 2019/08/15 Create by jsliang on 2019-08-12 19:39:34 Recently...
阅读 954·2021-11-25 09:43
阅读 2290·2019-08-30 15:55
阅读 3153·2019-08-30 15:44
阅读 2052·2019-08-29 16:20
阅读 1452·2019-08-29 12:12
阅读 1608·2019-08-26 12:19
阅读 2282·2019-08-26 11:49
阅读 1711·2019-08-26 11:42