SudokuSolver [source code]
public class SudokuSolver {
static
/******************************************************************************/
class Solution {
boolean DEBUG_PRINT = false;
boolean finished;
public void solveSudoku(char[][] board) {
finished = false;
boolean[][] rows = new boolean[9][9], cols = new boolean[9][9];
boolean[][][] cubes = new boolean[3][3][9];
for (int i = 0; i < 9; i++) for (int j = 0; j < 9; j++) if (board[i][j] != '.') {
int index = board[i][j] - '0' - 1;
rows[i][index] = true;
cols[j][index] = true;
cubes[i / 3][j / 3][index] = true;
}
dfs (board, 0, rows, cols, cubes);
return;
}
void dfs (char[][] board, int start, boolean[][] rows, boolean[][] cols, boolean[][][] cubes) {
if (finished)
return;
if (DEBUG_PRINT) System.out.println ();
int x = start / 9, y = start % 9; // don't -1
if (DEBUG_PRINT) System.out.printf ("start:(%d), [%d, %d]: \n%s\n", start, x, y, printMatrix (board));
boolean success = false;
search : for (int i = x, j = y; i < 9 && j < 9; i = i + (j + 1) / 9, j = (j + 1) % 9) {
if (DEBUG_PRINT) System.out.printf ("[%d, %d] ask [%d, %d]\n", x, y, i, j);
if (board[i][j] == '.') {
success = true;
int k;
for (k = 1; k <= 9; k++) {
if (!rows[i][k - 1] && !cols[j][k - 1] && !cubes[i / 3][j / 3][k - 1]) {
board[i][j] = (char) (k + '0');
rows[i][k - 1] = cols[j][k - 1] = cubes[i / 3][j / 3][k - 1] = true;
if (DEBUG_PRINT) System.out.printf ("\t[%d, %d] -> [%d, %d]\n", x, y, i + (j + 1) / 9, (j + 1) % 9);
dfs (board, (i * 9 + j) + 1, rows, cols, cubes);
rows[i][k - 1] = cols[j][k - 1] = cubes[i / 3][j / 3][k - 1] = false;
// Critical backtracking part
if (finished)
return;
board[i][j] = '.';
}
}
if (k == 10) {
if (DEBUG_PRINT) System.out.printf ("[%d, %d]: exhausted at [%d, %d]\n\n", x, y, i, j);
return;
}
break search;
}
}
if (!success) {
finished = true;
if (DEBUG_PRINT) System.out.println ("finish");
}
if (DEBUG_PRINT) System.out.println ();
}
String printMatrix (char[][] board) {
return java.util.Arrays.deepToString (board).replaceAll ("],", "],\n");
}
}
/******************************************************************************/
public static void main(String[] args) {
SudokuSolver.Solution tester = new SudokuSolver.Solution();
char[][][] inputs = {
//1
{{'.','.','9','7','4','8','.','.','.'},
{'7','.','.','.','.','.','.','.','.'},
{'.','2','.','1','.','9','.','.','.'},
{'.','.','7','.','.','.','2','4','.'},
{'.','6','4','.','1','.','5','9','.'},
{'.','9','8','.','.','.','3','.','.'},
{'.','.','.','8','.','3','.','2','.'},
{'.','.','.','.','.','.','.','.','6'},
{'.','.','.','2','7','5','9','.','.'}},
{{'5','1','9','7','4','8','6','3','2'},
{'7','8','3','6','5','2','4','1','9'},
{'4','2','6','1','3','9','8','7','5'},
{'3','5','7','9','8','6','2','4','1'},
{'2','6','4','3','1','7','5','9','8'},
{'1','9','8','5','2','4','3','6','7'},
{'9','7','5','8','6','3','1','2','4'},
{'8','3','2','4','9','1','7','5','6'},
{'6','4','1','2','7','5','9','8','3'}}
};
for (int i = 0; i < inputs.length / 2; i++) {
char[][] board = inputs[2 * i], ans = inputs[2 * i + 1];
String input_str = Matrix.printMatrix (board), ans_str = Matrix.printMatrix (ans);
System.out.println (Printer.separator ());
tester.solveSudoku (board);
String output_str = Matrix.printMatrix (board);
System.out.printf ("%s -> \n%s, expected: \n%s\n",
input_str, Printer.wrapColor (output_str, output_str.equals (ans_str) ? "green" : "red"), ans_str
);
}
}
}
大概瞎写的时候看到了这题的难度: 一个普通的backtracking好像未必能解决问题: 一个board可能含有多个互相隔绝的DFS tree, 但是他们之间又有互相的服从关系; 假如你在一个tree的DFS过程当中失败, 你怎么backtrack到上一个本来已经成功的tree?
好像用DFS没什么好处, 这题的核心应该是backtracking. DFS本身有天生的区域限制; 这题最好把所有的空格看成一个共同的团体, 不然不好backtrack;
不过如果去掉了DFS结构, 你还是要保证一个recursion的顺序, 不能一个点填完了, 下一个点在还没有fail的时候, 想回头就回头; 这个order还是有必要维护的;
写recursion的时候, 虽然我们往往base case的代码在前面, 但是不代表我们就应该先写这个代码. 很多时候因为刚开始动手敲代码的时候, 其实对算法的详细细节还不够那么熟悉, 所以并不知道base case应该怎么写, 这个时候直接写recursive部分的逻辑就行了, 往往把这段核心逻辑先写玩之后, base case怎么写自然而然就知道了;
这个问题刚开始拿到题目的时候觉得非常的简单, 就是一个典型的backtracking题目;
backtracking and state
一般那些特意让你想到backtracking的题目有一个共同的特点, 就是有非常明确的state的概念, 比如board这种是棋盘的状态; 一般有这种state概念的时候, backtrack就特别好用, 一个recursion iteration完成一个部分的change to state就行了; 而那些需要用普通的recursion做的, 一般对于明确的input和output的概念的强调的比较严重;
这题虽然以为很简单, 但是最后花了很多时间, 因为这题要应用各种各样的backtrack的技巧, 下面一个一个的讲. 速度是9ms (95%), 算是爆机了; 因为这题的debug其实占用了很多时间, 所以我保留了print的部分, 告诉你这种难题怎样快速完成debug; 顺带, 看我这里重新快速实现printMatrix的方式; 最后发现这个好像比我自己写的Printer的那个要快一些;
base case vs. loop failure
这个前面说过了, 先写核心逻辑, 然后再考虑base case; 事实上, 这个思想在这题最后显示出来是格外的有效, 因为这题写明确的base case就不怎么使用, 更好的方法就是另外一种terminate的方式: loop failure. 所有的base case都可以写成loop failure (把recursive的部分全部用一个if包裹起来就行了), 但是并不是所有的loop failure都能用base case来写; 而且loop failure, 类似这题, 最后实际上就比较难写; 这里的这个success就是用来完成这个作用的, 实现倒是不难;
另外一个小的细节, 这里comment出来的这个部分, 其实是为了一个conditional undo的操作: 你要预防假如你实际上已经finished了, 结果返回上来的时候自动undo掉了; 所以如果看到已经finished了, 就不能undo了; 这里就是用这个return把下面的undo挡住;
global switch: exit in time
这个其实是以前介绍过的一个prune DFS的方法, 这个方法在backtrack的prune的时候尤其好用; 但是以前只是稍微用了这个方法, 并没有掌握一些细节; global switch的一个重要细节就是, 除了在leaf位置要prune一下, 在post pre leaf的位置也要prune, 就好比我上面那个comment的地方; 这个在mutation类的题目当中格外的重要, 因为假如你在一个pre leaf进入DFS, 然后在这个iteration实际上完成了, 然后你还是会return上来的, 这个时候你传统的undo会把你刚才成功的change和state直接又给删除了;
无脑undo
以前写backtrack的时候, 经常喜欢想, 好像undo不是必须的; 确实有些题目, 你不undo往往也过了; 但是尤其是在mutation类的题目里面, 这个undo非常的重要; 比如这一题, 你看上面那一点的时候, 你可能会想, 如果一个k成功了, 那么我们不undo不就可以保证成功的结果不会被取消了吗? 结果是, 这个做法有一个非常严重的bug: 你在当前的iteration, 一个k成功了, 然后向下, 又一个k成功了, 但是可能下一个iteration, 是死路了, 这个时候就会一层一层网上返回; 看到什么问题没有? 你所有这些看起来成功但是实际上没成功的k最后都留在了board上面; 所以一定要在每一个k的iteration结束复原board的entry;
另外, 注意我这里对i, j的iterate的技巧, 不是简单的for i = x..8: for j = y..8就行了, 我一开始就是for (int i = x; i < 9; i++) for (int j = y; j < 9; j++)这样写的, 但是你自己想想, 这样iterate的其实不是一个一个的扫, 而是只扫右下角的部分, 这个是完全错误的;
另外就是一些关于print的技巧; recursion问题, 往往不是那么好debug; print每一个iteration entry的地方的state和参数, 这个是常规操作了; 但是这题debug的时候感觉这个技巧其实还不太够; 另外一个增强的技巧就是: print success/failure and reasons. 这样可以更好的看清楚flow; 另外, recursive的transition部分, 也最好有一个包含本iteration的参数和下一iteration参数的一个transition的print; 另外tab的使用, 这个应该熟悉了;
另外一个print小技巧, 就是为了分清楚不同的iteration, 最好在recursion函数的开头和结尾的部分分别单独加一个new line; 注意结束, 指的并不是最后一个return或者函数的结尾, 还要包括所有的premature exit, 这里就有;
另外, 这个是精简版本:
class Solution {
boolean finished;
public void solveSudoku(char[][] board) {
finished = false;
boolean[][] rows = new boolean[9][9], cols = new boolean[9][9];
boolean[][][] cubes = new boolean[3][3][9];
for (int i = 0; i < 9; i++) for (int j = 0; j < 9; j++) if (board[i][j] != '.') {
int index = board[i][j] - '0' - 1;
rows[i][index] = true;
cols[j][index] = true;
cubes[i / 3][j / 3][index] = true;
}
dfs (board, 0, rows, cols, cubes);
}
void dfs (char[][] board, int start, boolean[][] rows, boolean[][] cols, boolean[][][] cubes) {
if (finished) return;
int x = start / 9, y = start % 9; // don't -1
boolean success = false;
search : for (int i = x, j = y; i < 9 && j < 9; i = i + (j + 1) / 9, j = (j + 1) % 9) if (board[i][j] == '.') {
success = true;
for (int k = 1; k <= 9; k++) {
if (!rows[i][k - 1] && !cols[j][k - 1] && !cubes[i / 3][j / 3][k - 1]) {
board[i][j] = (char) (k + '0');
rows[i][k - 1] = cols[j][k - 1] = cubes[i / 3][j / 3][k - 1] = true;
dfs (board, (i * 9 + j) + 1, rows, cols, cubes);
rows[i][k - 1] = cols[j][k - 1] = cubes[i / 3][j / 3][k - 1] = false;
// Critical backtracking part
if (finished) return;
board[i][j] = '.';
}
}
break search;
}
if (!success) finished = true;
}
}
没有editorial;
@vinebranch said in Straight Forward Java Solution Using Backtracking:
Try 1 through 9 for each cell. The time complexity should be 9 ^ m (m represents the number of blanks to be filled in), since each blank can have 9 choices. Details see comments inside code.
public class Solution {
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;
}
}
思路是差不多的, 就是他单独check validity这个感觉比较浪费时间; 另外他用返回值来反映一个iteration的成功与失败, 才做起来比global switch的prune要稍微方便一些; 不过你看他undo的部分, 也是一个有conditional的操作, 这个跟我的是类似的;
@cdai said in Straight Forward Java Solution Using Backtracking:
Very straightforward! Many great comments here inspire me a minor improved version as followed for your reference.
1) Start loop from next possible position rather than from the very beginning every time.
2) Simplify isValid() and next position calculation (simply j + 1).
大概知道意思的一个优化;
针对他这里, 另外一个conditional undo的写法:
@firemusume said in Straight Forward Java Solution Using Backtracking:
rewrite solver function. make it more recursive style.
public boolean solve(char[][] board, int i, int j) {
if(i == 9 && j == 0) return true;
if(board[i][j] != '.') return solve(board, (j+1) == 9? i+1 : i, (j+1) == 9? 0 : j+1);
for(char num = '1'; num <= '9'; num++) {
if(isValid(board, i, j, num)){
board[i][j] = num;
if(solve(board, (j+1) == 9? i+1 : i, (j+1) == 9? 0 : j+1)) return true;
board[i][j] = '.';
}
}
return false;
}
同样是用return来屏蔽的思路;
不过第一页以内都没有人发现他这里check validity的方法的不合理;
这题居然有个奇葩用425上面学过的search&propogate来做:
@0xF4 said in Sharing my 2ms C++ solution with comments and explanations.:
Update: there's a [follow-up 0ms solution which is even more optimized][1]
This is one of the fastest Sudoku solvers I've ever written. It is compact enough - just 150 lines of C++ code with comments. I thought it'd be interesting to share it, since it combines several techniques like reactive network update propagation and backtracking with very aggressive pruning.
The algorithm is online - it starts with an empty board and as you add numbers to it, it starts solving the Sudoku.
Unlike in other solutions where you have bitmasks of allowed/disallowed values per row/column/square, this solution track bitmask for every(!) cell, forming a set of constraints for the allowed values for each particular cell. Once a value is written into a cell, new constraints are immediately propagated to row, column and 3x3 square of the cell. If during this process a value of other cell can be unambiguously deduced - then the value is set, new constraints are propagated, so on.... You can think about this as an implicit reactive network of cells.
If we're lucky (and we'll be lucky for 19 of 20 of Sudokus published in magazines) then Sudoku is solved at the end (or even before!) processing of the input.
Otherwise, there will be empty cells which have to be resolved. Algorithm uses backtracking for this purpose. To optimize it, algorithm starts with the cell with the smallest ambiguity. This could be improved even further by using priority queue (but it's not implemented here). Backtracking is more or less standard, however, at each step we guess the number, the reactive update propagation comes back into play and it either quickly proves that the guess is unfeasible or significantly prunes the remaining search space.
It's interesting to note, that in this case taking and restoring snapshots of the compact representation of the state is faster than doing backtracking rollback by "undoing the moves".
class Solution {
struct cell // encapsulates a single cell on a Sudoku board
{
uint8_t value; // cell value 1..9 or 0 if unset
// number of possible (unconstrained) values for the cell
uint8_t numPossibilities;
// if bitset[v] is 1 then value can't be v
bitset<10> constraints;
cell() : value(0), numPossibilities(9),constraints() {};
};
array<array<cell,9>,9> cells;
// sets the value of the cell to [v]
// the function also propagates constraints to other cells and deduce new values where possible
bool set(int i, int j, int v)
{
// updating state of the cell
cell& c = cells[i][j];
if (c.value == v)
return true;
if (c.constraints[v])
return false;
c.constraints = bitset<10>(0x3FE); // all 1s
c.constraints.reset(v);
c.numPossibilities = 1;
c.value = v;
// propagating constraints
for (int k = 0; k<9; k++) {
// to the row:
if (i != k && !updateConstraints(k, j, v))
return false;
// to the column:
if (j != k && !updateConstraints(i, k, v))
return false;
// to the 3x3 square:
int ix = (i / 3) * 3 + k / 3;
int jx = (j / 3) * 3 + k % 3;
if (ix != i && jx != j && !updateConstraints(ix, jx, v))
return false;
}
return true;
}
// update constraints of the cell i,j by excluding possibility of 'excludedValue'
// once there's one possibility left the function recurses back into set()
bool updateConstraints(int i, int j, int excludedValue)
{
cell& c = cells[i][j];
if (c.constraints[excludedValue]) {
return true;
}
if (c.value == excludedValue) {
return false;
}
c.constraints.set(excludedValue);
if (--c.numPossibilities > 1)
return true;
for (int v = 1; v <= 9; v++) {
if (!c.constraints[v]) {
return set(i, j, v);
}
}
assert(false);
}
// backtracking state - list of empty cells
vector<pair<int, int>> bt;
// find values for empty cells
bool findValuesForEmptyCells()
{
// collecting all empty cells
bt.clear();
for (int i = 0; i < 9; i++) {
for (int j = 0; j < 9; j++) {
if (!cells[i][j].value)
bt.push_back(make_pair(i, j));
}
}
// making backtracking efficient by pre-sorting empty cells by numPossibilities
sort(bt.begin(), bt.end(), [this](const pair<int, int>&a, const pair<int, int>&b) {
return cells[a.first][a.second].numPossibilities < cells[b.first][b.second].numPossibilities; });
return backtrack(0);
}
// Finds value for all empty cells with index >=k
bool backtrack(int k)
{
if (k >= bt.size())
return true;
int i = bt[k].first;
int j = bt[k].second;
// fast path - only 1 possibility
if (cells[i][j].value)
return backtrack(k + 1);
auto constraints = cells[i][j].constraints;
// slow path >1 possibility.
// making snapshot of the state
array<array<cell,9>,9> snapshot(cells);
for (int v = 1; v <= 9; v++) {
if (!constraints[v]) {
if (set(i, j, v)) {
if (backtrack(k + 1))
return true;
}
// restoring from snapshot,
// note: computationally this is cheaper
// than alternative implementation with undoing the changes
cells = snapshot;
}
}
return false;
}
public:
void solveSudoku(vector<vector<char>> &board) {
cells = array<array<cell,9>,9>(); // clear array
// Decoding input board into the internal cell matrix.
// As we do it - constraints are propagated and even additional values are set as we go
// (in the case if it is possible to unambiguously deduce them).
for (int i = 0; i < 9; i++)
{
for (int j = 0; j < 9; j++) {
if (board[i][j] != '.' && !set(i, j, board[i][j] - '0'))
return; // sudoku is either incorrect or unsolvable
}
}
// if we're lucky we've already got a solution,
// however, if we have empty cells we need to use backtracking to fill them
if (!findValuesForEmptyCells())
return; // sudoku is unsolvable
// copying the solution back to the board
for (int i = 0; i < 9; i++)
{
for (int j = 0; j < 9; j++) {
if (cells[i][j].value)
board[i][j] = cells[i][j].value + '0';
}
}
}
};
[1]: https://leetcode.com/discuss/59649/yet-another-0ms-c-solution
解释的实际上是非常的详细了, 就是代码有点长的可怕; 不过这个作者的水平极高, 可以看他比如updateConstraints函数的代码, 非常的工整简练; 尤其是注意他的设计部分, 比如他用assert(false)来完成一个对unreached的检测, 这个其实java也可以用不是吗? 以及你看他set和updateConstraints两者之间的boolean返回值的互传, 以及对应的逻辑判断, 设计的非常的巧妙;
TODO: 这个算法写的门道深而且工整, 后面有时间可以重新研究一下;
后面突然意识到一个问题, 他是怎么undo的? 其实我一开始看到他用snapshot来undo的时候, 以为这个snapshot包含的只是一个value的信息, 但是实际上cells的snapshot也是保存了包括numPossibilities, constraints之类的信息的, 所以之前的set, updateConstraints之类的操作其实也是被自动undo了, 这个就显示出了snapshot操作方式的优势了;
@1337c0d3r said in Singapore prime minister Lee Hsien Loong's Sudoku Solver code runs in 1ms:
Singapore's prime minister [Lee Hsien Loong][1] showcased his Sudoku Solver C code. You can read his original Facebook post [here][2] and another news reporting it [here][3].
I have made some slight modification to adapt it so it can be [tested on LeetCode OJ][4]. It passed all 6/6 test cases with a runtime of 1 ms. Pretty impressive for a prime minister, huh?
// Original author: Hsien Loong Lee (http://bit.ly/1zfIGMc)
// Slight modification by @1337c0d3r to adapt to run on LeetCode OJ.
// https://leetcode.com/problems/sudoku-solver/
int InBlock[81], InRow[81], InCol[81];
const int BLANK = 0;
const int ONES = 0x3fe; // Binary 1111111110
int Entry[81]; // Records entries 1-9 in the grid, as the corresponding bit set to 1
int Block[9], Row[9], Col[9]; // Each int is a 9-bit array
int SeqPtr = 0;
int Sequence[81];
void SwapSeqEntries(int S1, int S2)
{
int temp = Sequence[S2];
Sequence[S2] = Sequence[S1];
Sequence[S1] = temp;
}
void InitEntry(int i, int j, int val)
{
int Square = 9 * i + j;
int valbit = 1 << val;
int SeqPtr2;
// add suitable checks for data consistency
Entry[Square] = valbit;
Block[InBlock[Square]] &= ~valbit;
Col[InCol[Square]] &= ~valbit; // Simpler Col[j] &= ~valbit;
Row[InRow[Square]] &= ~valbit; // Simpler Row[i] &= ~valbit;
SeqPtr2 = SeqPtr;
while (SeqPtr2 < 81 && Sequence[SeqPtr2] != Square)
SeqPtr2++ ;
SwapSeqEntries(SeqPtr, SeqPtr2);
SeqPtr++;
}
void PrintArray(char **board)
{
int i, j, valbit, val, Square;
char ch;
Square = 0;
for (i = 0; i < 9; i++) {
for (j = 0; j < 9; j++) {
valbit = Entry[Square++];
if (valbit == 0) ch = '-';
else {
for (val = 1; val <= 9; val++)
if (valbit == (1 << val)) {
ch = '0' + val;
break;
}
}
board[i][j] = ch;
}
}
}
int NextSeq(int S)
{
int S2, Square, Possibles, BitCount;
int T, MinBitCount = 100;
for (T = S; T < 81; T++) {
Square = Sequence[T];
Possibles = Block[InBlock[Square]] & Row[InRow[Square]] & Col[InCol[Square]];
BitCount = 0;
while (Possibles) {
Possibles &= ~(Possibles & -Possibles);
BitCount++;
}
if (BitCount < MinBitCount) {
MinBitCount = BitCount;
S2 = T;
}
}
return S2;
}
void Place(int S, char** board)
{
if (S >= 81) {
PrintArray(board);
return;
}
int S2 = NextSeq(S);
SwapSeqEntries(S, S2);
int Square = Sequence[S];
int BlockIndex = InBlock[Square],
RowIndex = InRow[Square],
ColIndex = InCol[Square];
int Possibles = Block[BlockIndex] & Row[RowIndex] & Col[ColIndex];
while (Possibles) {
int valbit = Possibles & (-Possibles); // Lowest 1 bit in Possibles
Possibles &= ~valbit;
Entry[Square] = valbit;
Block[BlockIndex] &= ~valbit;
Row[RowIndex] &= ~valbit;
Col[ColIndex] &= ~valbit;
Place(S + 1, board);
Entry[Square] = BLANK; // Could be moved out of the loop
Block[BlockIndex] |= valbit;
Row[RowIndex] |= valbit;
Col[ColIndex] |= valbit;
}
SwapSeqEntries(S, S2);
}
void solveSudoku(char **board, int m, int n) {
SeqPtr = 0;
int i, j, Square;
for (i = 0; i < 9; i++)
for (j = 0; j < 9; j++) {
Square = 9 * i + j;
InRow[Square] = i;
InCol[Square] = j;
InBlock[Square] = (i / 3) * 3 + ( j / 3);
}
for (Square = 0; Square < 81; Square++) {
Sequence[Square] = Square;
Entry[Square] = BLANK;
}
for (i = 0; i < 9; i++)
Block[i] = Row[i] = Col[i] = ONES;
for (int i = 0; i < 9; ++i)
for (int j = 0; j < 9; ++j) {
if ('.' != board[i][j])
InitEntry(i, j, board[i][j] - '0');
}
Place(SeqPtr, board);
}
&= ~valbit;是一个clear mask的操作, 写Pintos的时候总结过了;
看这个算法的时候又犯了一个以前犯过的错误, 就是看长算法的时候, 直接从helper开始看了; 代码越长, 这样的看法危害越大, 因为看着看着就忘记了; 最好还是从入口函数开始看, 到了调用的时候再看一眼是什么实现; 当然, 如果有类似这里的全局变量, 要在看入口函数之前先大概记住这些变量的名字和type的对应;
Possibles &= ~(Possibles & -Possibles); 这里有点看不懂, 举例子看看, 比如开始是0101, 那么-P = ~P + 1 = 1011, 那么P & -P = 0001, ~之后再再&回到P, 其实就是clear out last set bit: 0101 & 1110 = 0100. 下一个iteration: (0100) & (1011 + 1) = 0100 & 1100 = 0100; 0100 & ~0100 = 0, 停止, 所以就是找到了两个bit, 这个结果也正好就是Block[InBlock[Square]] & Row[InRow[Square]] & Col[InCol[Square]]得到的搜索空间的大小;
好像P & -P这个操作之前是不是见过一次? 就是last bit的意思好像; 然后看上面那个式子左半边, 整个就是一个P &= ~(..)的结果, 所以实际上就是clear out里面的那个mask代表的位置;
总体来说很有启发性的一个算法, 决定自己重新实现一遍; 实现完了是3(100), 果然很厉害;
以前还看到过一些类似的解决数独的代码, 讲的很好, 有些用了propagate这个做法, 并且表示这个做法实际上就是一个A*算法(min heap, weight is size of the entry's search space, 所以对应的算法其实就类似于425上课讲过的most constrained(least possibility) first). 有些类似上面总理做法的方式做了一个bit的算法, 具体的代码在CBase里面, 因为比较敏感, 不放在这里, 这个repo是迟早要公开的; 文章连接. 建议去看一下, 作者真正是一个大牛中的大牛, 思路清晰, 代码工整.
A*算法其实看完上面那个其实就差不多了, 大牛的实现并不比上面那个discussion看来的实现优越很多; discussion那个基本是已经没得挑剔了, 不仅是算法本身, 代码组织也无可挑剔;
关于bit算法, 大概跟上面总理算法差不多, 比如rows[0] = 1111_11110, 意思就是在row[0]不能再选择数字1了; 这样当你在[i][j]的时候, 你直接可以通过rows[i] & cols[j] & cube[cube_index]来得到当前位置的搜索空间, 这样完成一个效率非常高的pruning; 实际上这个pruning最后的速度是超过A*的; 这个bit的pruning真的是非常的带秀. 另外, 理解了这个技巧, 其实就理解了上面的总理算法; 大概看了一下, 总理的实现方式虽然啰嗦了一点, 但是核心逻辑都把握了, 一点没毛病;
@nilath2 said in Simple and Clean Solution / C++:
bool check(vector<vector<char>> &board, int i, int j, char val)
{
int row = i - i%3, column = j - j%3;
for(int x=0; x<9; x++) if(board[x][j] == val) return false;
for(int y=0; y<9; y++) if(board[i][y] == val) return false;
for(int x=0; x<3; x++)
for(int y=0; y<3; y++)
if(board[row+x][column+y] == val) return false;
return true;
}
bool solveSudoku(vector<vector<char>> &board, int i, int j)
{
if(i==9) return true;
if(j==9) return solveSudoku(board, i+1, 0);
if(board[i][j] != '.') return solveSudoku(board, i, j+1);
for(char c='1'; c<='9'; c++)
{
if(check(board, i, j, c))
{
board[i][j] = c;
if(solveSudoku(board, i, j+1)) return true;
board[i][j] = '.';
}
}
return false;
}
public:
void solveSudoku(vector<vector<char>>& board) {
solveSudoku(board, 0, 0);
}
跟前面见过的几个算法基本是差不多的, 没啥好说的;
submission基本波动, 没有超越总理算法的; 能看见的可见bar其实只到5ms, 但是总理算法其实是3(100), 很牛逼, 在条形图上面都没有显示的;
Problem Description
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.
A sudoku puzzle...
...and its solution numbers marked in red.
Difficulty:Hard
Total Accepted:87.4K
Total Submissions:276.1K
Contributor:LeetCode
Companies
ubersnapchat
Related Topics
hash tablebacktracking
Similar Questions
Valid Sudoku