What's time complexity of this algorithm for solving Sudoku?
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 .
Personally I think,
time complexity = O((n^2)!), n is the number of rows(cols) of the board.
C++
class Solution {
public:
void solveSudoku(vector<vector<char> > &board) {
// Input validation.
if (board.size() == 0 ||
board.size() != board[0].size() ||
board.size() % 3 != 0) return;
helper(board);
}
bool helper(vector<vector<char>>& board) {
// Base case.
// ... ...
for (int row = 0; row < board.size(); row ++) {
for (int col = 0; col < board[0].size(); col ++) {
if (board[row][col] != '.') continue;
for (char num = '1'; num <= '9'; num ++) {
if (isValid(board, num, row, col)) {
// Have a try.
board[row][col] = num;
// Do recursion.
if (helper(board)) return true;;
// Roll back.
board[row][col] = '.';
}
}
// Can not find a suitable number[1-9].
return false;
}
}
return true;
}
bool isValid(const vector<vector<char>>& board, char num, int row, int col) {
// Check row.
for (int tmp_col = 0; tmp_col < board[0].size(); tmp_col ++) {
if (board[row][tmp_col] == num) return false;
}
// Check col.
for (int tmp_row = 0; tmp_row < board.size(); tmp_row ++) {
if (board[tmp_row][col] == num) return false;
}
// Check sub square.
int start_row = (row / 3) * 3;
int start_col = (col / 3) * 3;
for (int row = start_row; row < start_row + 3; row ++) {
for (int col = start_col; col < start_col + 3; col ++) {
if (board[row][col] == num) return false;
}
}
return true;
}
};
What are your reasons for assuming O((n^2)!) ? Since it is a classic recursion with backtracking I would, without having analyzed the problem in depth, think it is O(n^n). Try to make a counter which increments each time the function is recursively called. Then see if at the end of the algorithm it is closer to 387 420 489 (my guess) or 579 712 600 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 (your guess).
If you want a more complicated explanation, I am happy to give one.
edit: While thinking up the detailed explanation, I noticed I was wrong about the numbers, they should actually be quite a bit higher.
Many recursive searches can be modeled as a tree. In Sodoku, you have 9 possibilities each time you try out a new field. At maximum, you have to put solutions into all 81 fields. At this point it can help drawing it up in order to see, that the resulting search space is a tree with a depth of 81 and a branching factor of 9 at each node of each layer, and each leaf is a possible solution. Given these numbers, the search space is 9^81.
Since you don't check if the solution is correct after trying 81 times but after each try, the actual search space is way smaller. I don't know how to put it into numbers really, maybe the branching factor gets smaller by 1 each time you set n tries, as a rough estimate. But given any Sodoku with k pre-set numbers, you can with 100% certainty say, that you will need at most n^(n²-k) tries.
Did that make sense?
链接地址: http://www.djcxy.com/p/96166.html上一篇: 我的数独解算器不工作