Is it right that "You may assume that there will be only one unique solution. "??


  • -1
    K

    My code found correct answer but it was reject because it is different from expected answer
    Input:["..9748...","7........",".2.1.9...","..7...24.",".64.1.59.",".98...3..","...8.3.2.","........6","...2759.."]
    Output:["139748652","712456839","325169478","987631245","864312597","498527361","576893124","253984716","641275983"]
    Expected:["519748632","783652419","426139875","357986241","264317598","198524367","975863124","832491756","641275983"]
    and below is my code.

    class Solution {
    private:
    	int b[9];
    	int v[9];
    	int h[9];
    	vector<vector<char>> board;
    	vector<pair<int, int>> path;
    	void built()
    	{
    		for (int i = 0; i < 9; i++)b[i] = 1 << i;
    		for (int i = 0; i < 9; i++)
    		{
    			v[i] = 0xFFFFFE00;
    			h[i] = 0xFFFFFE00;
    		}
    		for (int i = 0; i < 9; i++)
    		{
    			for (int j = 0; j < 9; j++)
    			{
    				char& c = board[i][j];
    				if (c == '.')path.push_back(make_pair(i, j));
    				else
    				{
    					c = toi(c) - 1;
    					v[j] |= b[c];
    					h[i] |= b[c];
    				}
    				
    			}
    		}
    		for (int i = 0; i < 9; i++)
    		{
    			v[i] = ~v[i];
    			h[i] = ~h[i];
    		}
    	}
    
    	inline int toi(char c)
    	{
    		return c - '0';
    	}
    
    	void set(int i, int j, int bit)
    	{
    		board[i][j] = log2(bit);
    		v[j] ^= bit;
    		h[i] ^= bit;
    	}
    	void unset(int i, int j, int bit)
    	{
    		board[i][j] = '.';
    		v[j] |= bit;
    		h[i] |= bit;
    	}
    	
    	
    	bool dfs(int idx)
    	{
    		if (path.size() == idx)return true;
    		int i = path[idx].first;
    		int j = path[idx].second;
    		int intersection = v[j] & h[i];
    		while (intersection)
    		{
    			int bit = intersection & (~intersection + 1);
    			set(i, j, bit);
    			if (dfs(idx + 1))return true;
    			unset(i, j, bit);
    			intersection ^= bit;
    		}
    		return false;
    	}
    
    public:
    	void solveSudoku(vector<vector<char>>& b)
    	{
    		board = b;
    		built();
    		dfs(0);
    		for (int i = 0; i < 9; i++)
    			for (int j = 0; j < 9; j++)
    				b[i][j] = board[i][j] + '1';
    	}
    };
    

Log in to reply
 

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