s**x
发帖数: 7506 | | F**r
发帖数: 84 | 2 dancing links
【在 s**x 的大作中提到】
: 这次 onsite 就这一题没做好。
| r*****l
发帖数: 216 | | l*****a
发帖数: 559 | 4 恩，网上曾经贴过详解的。
depth-first-search，现场写有点难度。 | g**********y
发帖数: 14569 | 5 写了个最原始的，一点智能都没有的：
public class Sudoku {
private int[] t = new int[9];
public boolean solve(int[][] matrix) {
Point p = nextUnknown(matrix);
if (p == null) {
print(matrix);
return true;
}
for (int i=1; i<10; i++) {
matrix[p.x][p.y] = i;
if (pass(matrix) && solve(matrix)) return true;
}
matrix[p.x][p.y] = 0;
return false;
}
private Point nextUnknown(int[][] matrix) {
for (int i=0; i<9; i++) {
for (int j=0; j<9; j++) {
if (matrix[i][j] == 0) return new Point(i, j);
}
}
return null;
}
private boolean pass(int[][] matrix) {
for (int i=0; i<9; i++) {
clearTest();
for (int j=0; j<9; j++) {
int a = matrix[i][j];
if (a > 0) {
t[a-1]++;
if (t[a-1] > 1) return false;
}
}
}
for (int i=0; i<9; i++) {
clearTest();
for (int j=0; j<9; j++) {
int a = matrix[j][i];
if (a > 0) {
t[a-1]++;
if (t[a-1] > 1) return false;
}
}
}
for (int i=0; i<3; i++) {
for (int j=0; j<3; j++) {
clearTest();
for (int x=0; x<3; x++) {
for (int y=0; y<3; y++) {
int a = matrix[3*i+x][3*j+y];
if (a > 0) {
t[a-1]++;
if (t[a-1] > 1) return false;
}
}
}
}
}
return true;
}
private void clearTest() {
for (int i=0; i<9; i++) t[i] = 0;
}
private void print(int[][] matrix) {
for (int i=0; i<9; i++) {
for (int j=0; j<9; j++) {
System.out.print(matrix[i][j] + " ");
}
System.out.println();
}
}
private class Point {
int x;
int y;
public Point(int x, int y) {
this.x = x;
this.y = y;
}
}
} | i**********e
发帖数: 1145 | 6 这题作为面试题应该考察的就是基础 DFS 和 coding skills，如果要智能的话在面试那么短的时间内是写不出来的。
这题思路不难的，只是 coding 方面要注意，不要出错就行。基本思路就是先实现 isValid() 函数，检测这个 board 是否valid。然后，找出第一个空格内填 1-9，如果 isValid() 的话继续 DFS，直到没有空格为止（那就是找到答案了）。要注意函数返回之前把空格还原。
这个函数:
private boolean pass(int[][] matrix)
里面用了一些重复的代码，可以 refactor 成更简洁些，也可以减少错误发生的机率：
private boolean passHelper(int [][] matrix, int startRow, int startCol, int
endRow, int endCol)
这样你在 pass 函数里只要传叫 passHelper() 三次即可。
1）startRow = 0, startCol = col, endRow = 8, endCol = col { for col = 0->8 }
2) startRow = row, startCol = 0, endRow = row, endCol = 8 { for row = 0->8
}
3) startRow = row, startCol = col, endRow = row+2, endCol = col+2 { for row
= 0->2, col = 0->2 }
也说下复杂度：
DFS 暴力解法的复杂度应该是 O(9^n），n = 空格的个数。
那么为什么以下的 board，在电脑运行暴力 DFS 一秒以内就找出答案？
"1...7..3.",
"83.6.....",
"..29..6.8",
"6....49.7",
".9.....5.",
"3.75....4",
"2.3..91..",
".....2.43",
".4..8...9"
原因是因为这个条件 （请参考 gloomyturkey 的代码）：
if (pass(matrix) && solve(matrix))
当这个 board 不是 valid 的时候，就没必要搜索下去了。这个简单的剪枝方法可以大
大的缩小搜索的范围。如果你不相信的话，把 pass(matrix) 这个条件去掉，然后只有
在填满 board 的时候再检测是否 valid，那么你这个 DFS 是跑了一百年都不会有答案
的。(以上的 board , n = 51, 复杂度 = 9^51 = 4.63839769 × 10^48)
一些常见面试题的答案与总结 -
http://www.ihas1337code.com
【在 g**********y 的大作中提到】
: 写了个最原始的，一点智能都没有的：
: public class Sudoku {
: private int[] t = new int[9];
: public boolean solve(int[][] matrix) {
: Point p = nextUnknown(matrix);
: if (p == null) {
: print(matrix);
: return true;
: }
:
| c*********t
发帖数: 2921 | 7 ihasleetcode，
这个sodoku solver到底是什么个问题？
是说生成所有的sodoku的9*9矩阵？那样的组合可就太多了。
还是说给了一个没有填满的9*9矩阵，解决去填空缺的数字？
还是说给了一个填满的9*9矩阵，判断是不是个有效的solution?
到底是这三者中的哪一个？
谢谢！
试那么短的时间内是写不出来的。
isValid() 函数，检测这个 board 是否valid。然后，找出第一个空格内填 1-9，如果
isValid() 的话继续 DFS，直到没有空格为止（那就是找到答案了）。要注意函数返
回之前把空格还原。
int
8 }
>8
【在 i**********e 的大作中提到】
: 这题作为面试题应该考察的就是基础 DFS 和 coding skills，如果要智能的话在面试那么短的时间内是写不出来的。
: 这题思路不难的，只是 coding 方面要注意，不要出错就行。基本思路就是先实现 isValid() 函数，检测这个 board 是否valid。然后，找出第一个空格内填 1-9，如果 isValid() 的话继续 DFS，直到没有空格为止（那就是找到答案了）。要注意函数返回之前把空格还原。
: 这个函数:
: private boolean pass(int[][] matrix)
: 里面用了一些重复的代码，可以 refactor 成更简洁些，也可以减少错误发生的机率：
: private boolean passHelper(int [][] matrix, int startRow, int startCol, int
: endRow, int endCol)
: 这样你在 pass 函数里只要传叫 passHelper() 三次即可。
: 1）startRow = 0, startCol = col, endRow = 8, endCol = col { for col = 0->8 }
: 2) startRow = row, startCol = 0, endRow = row, endCol = 8 { for row = 0->8
| h*********n
发帖数: 11319 | 8 2 of course
率：
->
0-
【在 c*********t 的大作中提到】
: ihasleetcode，
: 这个sodoku solver到底是什么个问题？
: 是说生成所有的sodoku的9*9矩阵？那样的组合可就太多了。
: 还是说给了一个没有填满的9*9矩阵，解决去填空缺的数字？
: 还是说给了一个填满的9*9矩阵，判断是不是个有效的solution?
: 到底是这三者中的哪一个？
: 谢谢！
:
: 试那么短的时间内是写不出来的。
: isValid() 函数，检测这个 board 是否valid。然后，找出第一个空格内填 1-9，如果
| c*********t
发帖数: 2921 | 9 如果是2的话，
如果给定的数很少，就是说这个矩阵很稀疏，那么solution有可能会有很多种，答案不
是唯一的，对吧？
【在 h*********n 的大作中提到】
: 2 of course
:
: 率：
: ->
: 0-
| A***M
发帖数: 18 | 10 我的理解是sodoku solver应该包含如下两部分
1）生成一个合理的sodoku,使27个区(9行9列9个3*3)都满足条件
2）去掉一些number产生一个合理的puzzle, 不会产生多解的情况。
网上搜一下， 有很多这方面的讨论。 | i**********e
发帖数: 1145 | 11 是填满空缺的数字.
>>如果给定的数很少，就是说这个矩阵很稀疏，那么solution有可能会有很多种，答案
不是唯一的，对吧？
假设只有唯一一个答案。
另外，如果有兴趣的话，可以参考 Peter Norvig 写的有关 sudoku solver 文章（里
面还介绍了怎么生成一个 sudoku puzzle，附有完整代码）。
从他那里转载：
What is the search algorithm? Simple: first make sure we haven't already
found a solution or a contradiction, and if not, choose one unfilled square
and consider all its possible values. One at a time, try assigning the
square each value, and searching from the resulting position. In other words
, we search for a value d such that we can successfully search for a
solution from the result of assigning square s to d. If the search leads to
an failed position, go back and consider another value of d. This is a
recursive search, and we call it a depth-first search because we (
recursively) consider all possibilities under values[s] = d before we
consider a different value for s.
一些常见面试题的答案与总结 -
http://www.ihas1337code.com
【在 c*********t 的大作中提到】
: ihasleetcode，
: 这个sodoku solver到底是什么个问题？
: 是说生成所有的sodoku的9*9矩阵？那样的组合可就太多了。
: 还是说给了一个没有填满的9*9矩阵，解决去填空缺的数字？
: 还是说给了一个填满的9*9矩阵，判断是不是个有效的solution?
: 到底是这三者中的哪一个？
: 谢谢！
:
: 试那么短的时间内是写不出来的。
: isValid() 函数，检测这个 board 是否valid。然后，找出第一个空格内填 1-9，如果
| h**k
发帖数: 3368 | 12 说到唯一解，有这么个问题。
在给定的数满足什么条件下，sudoku有而且仅有一个解？
square
【在 i**********e 的大作中提到】
: 是填满空缺的数字.
: >>如果给定的数很少，就是说这个矩阵很稀疏，那么solution有可能会有很多种，答案
: 不是唯一的，对吧？
: 假设只有唯一一个答案。
: 另外，如果有兴趣的话，可以参考 Peter Norvig 写的有关 sudoku solver 文章（里
: 面还介绍了怎么生成一个 sudoku puzzle，附有完整代码）。
: 从他那里转载：
: What is the search algorithm? Simple: first make sure we haven't already
: found a solution or a contradiction, and if not, choose one unfilled square
: and consider all its possible values. One at a time, try assigning the
|
|
