Why my solution take such lot of time?489ms


  • 0
    Q

    I try to fill ‘.’ one by one, before filling, I will use validNum() to get valid numbers.
    Then, check those numbers, if not suitable, use tryFill(i - 1) backtracking.
    why it takes so long!! please help.

    class Solution {
    public:
       vector<int> validNum(int u, vector<vector<char>> board)
    	{
    		vector<int> ans;
    		vector<bool> used(9, false);
    		int x = u / 9, y = u % 9;
    		for (int i = 0; i < 9; i++)
    		{
    			if (board[x][i] != '.'){
    
    				used[board[x][i] - '0' - 1] = true;
    			}
    			if (board[i][y] != '.'){
    
    				used[board[i][y] - '0' - 1] = true;
    			}
    			int bx = (x / 3) * 3 + i / 3, by = (y / 3) * 3 + i % 3;
    			if (board[bx][by] != '.'){
    
    				used[board[bx][by] - '0' - 1] = true;
    			}
    
    		}
    
    		if (board[x][y] != '.') used[board[x][y] - '0' - 1] = false;
    		for (int i = 0; i < 9; i++)
    		{
    			if (!used[i]) ans.push_back(i + 1);// 不要忘记+1
    		}
    		return ans;
    
    	}
    
    	void tryFill(int start, vector<int> unknown, vector<vector<char>>& board)
    	{if(start > 50)
    		cout<<start<<" ";
    		if (start < 0) return;
    		int i = start;
    		for (; i < unknown.size(); i++)
    		{
    			int u = unknown[i];
    			int x = u / 9, y = u % 9;
    
    			vector<int> validN = validNum(u, board);
    			int validLen = validN.size();
    
    
    			int index;
    			if (board[x][y] == '.')
    				index = 0;
    			else
    				for (int i = 0; i < 9; i++)
    					if (validN[i] == board[x][y] - '0')
    					{
    						index = i + 1;
    						break;
    					}
    			for (; index < validLen; index++)
    			{
    				board[x][y] = validN[index] + '0';
    				if (i != unknown.size() - 1){
    					vector<int> NextValidN = validNum(unknown[i + 1], board);
    					if (NextValidN.size() != 0)
    						break;
    				}
    			}
    			if (index == validLen && i != unknown.size() - 1 )//这里一定要有i != unknown.size() - 1, 因为当填入最后一个空格,这个一定是有效的
    			{
    				board[x][y] = '.';
    				tryFill(i - 1, unknown, board);
    				break;//太重要了 这个break
    			}
    
    		}
    
    	}
    
    	void solveSudoku(vector<vector<char>>& board) {
    		//先用hash 去看每个cell可能的数字
    		//再回溯法 
    
    		//bool hrow[9][9] = {false}, hcol[9][9] = {false}, hblock[9][9] = {false};
    		vector<int> unknown;//x = u / 9 , y = u % 9 u->[0, 80];
    		for (int i = 0; i < 9; i++){
    			for (int j = 0; j < 9; j++)
    				if (board[i][j] == '.')
    
    					unknown.push_back(i * 9 + j);
    		}
    		tryFill(0, unknown, board);
    		cout << "";
    	}
    
    	
    };
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.