a 6ms cpp solution


  • 0
    Y

    Spoiler
    class Solution {
    public:
    //Fill in the value that can be determined
    void solveSudoku(vector<vector<char>>& board)
    {
    vector<char> tmp;
    while (tmp.size() < 10) tmp.push_back('.');
    int i = 0, j = 0, p = 0, q = 0, k = 0, flag = 0, num = 0, timeflag = 0;

    	for (i = 0; i < 9; i++)
    	{
    		for (j = 0; j < 9; j++)
    		{
    			if (board[i][j] == '.')
    			{
    				p = 0;
    				while (p < 9) { if (board[i][p] != '.' && tmp[board[i][p] - '0'] == '.') tmp[board[i][p] - '0'] = 'f'; p++; }
    				q = 0;
    				while (q < 9) { if (board[q][j] != '.' && tmp[board[q][j] - '0'] == '.') tmp[board[q][j] - '0'] = 'f'; q++; }
    
    				switch (i % 3)
    				{
    				case 0:
    					switch (j % 3)
    					{
    					case 0:
    					{
    						if (board[i + 1][j + 1] != '.' && tmp[board[i + 1][j + 1] - '0'] == '.') tmp[board[i + 1][j + 1] - '0'] = 'f';
    						if (board[i + 1][j + 2] != '.' && tmp[board[i + 1][j + 2] - '0'] == '.') tmp[board[i + 1][j + 2] - '0'] = 'f';
    						if (board[i + 2][j + 1] != '.' && tmp[board[i + 2][j + 1] - '0'] == '.') tmp[board[i + 2][j + 1] - '0'] = 'f';
    						if (board[i + 2][j + 2] != '.' && tmp[board[i + 2][j + 2] - '0'] == '.') tmp[board[i + 2][j + 2] - '0'] = 'f';
    					}break;
    					case 1:
    					{
    						if (board[i + 1][j - 1] != '.' && tmp[board[i + 1][j - 1] - '0'] == '.') tmp[board[i + 1][j - 1] - '0'] = 'f';
    						if (board[i + 1][j + 1] != '.' && tmp[board[i + 1][j + 1] - '0'] == '.') tmp[board[i + 1][j + 1] - '0'] = 'f';
    						if (board[i + 2][j - 1] != '.' && tmp[board[i + 2][j - 1] - '0'] == '.') tmp[board[i + 2][j - 1] - '0'] = 'f';
    						if (board[i + 2][j + 1] != '.' && tmp[board[i + 2][j + 1] - '0'] == '.') tmp[board[i + 2][j + 1] - '0'] = 'f';
    					}break;
    					case 2:
    					{
    						if (board[i + 1][j - 1] != '.' && tmp[board[i + 1][j - 1] - '0'] == '.') tmp[board[i + 1][j - 1] - '0'] = 'f';
    						if (board[i + 1][j - 2] != '.' && tmp[board[i + 1][j - 2] - '0'] == '.') tmp[board[i + 1][j - 2] - '0'] = 'f';
    						if (board[i + 2][j - 1] != '.' && tmp[board[i + 2][j - 1] - '0'] == '.') tmp[board[i + 2][j - 1] - '0'] = 'f';
    						if (board[i + 2][j - 2] != '.' && tmp[board[i + 2][j - 2] - '0'] == '.') tmp[board[i + 2][j - 2] - '0'] = 'f';
    					}break;
    					default: break;
    					}break;
    				case 1:
    					switch (j % 3)
    					{
    					case 0:
    					{
    						if (board[i - 1][j + 1] != '.' && tmp[board[i - 1][j + 1] - '0'] == '.') tmp[board[i - 1][j + 1] - '0'] = 'f';
    						if (board[i - 1][j + 2] != '.' && tmp[board[i - 1][j + 2] - '0'] == '.') tmp[board[i - 1][j + 2] - '0'] = 'f';
    						if (board[i + 1][j + 1] != '.' && tmp[board[i + 1][j + 1] - '0'] == '.') tmp[board[i + 1][j + 1] - '0'] = 'f';
    						if (board[i + 1][j + 2] != '.' && tmp[board[i + 1][j + 2] - '0'] == '.') tmp[board[i + 1][j + 2] - '0'] = 'f';
    					}break;
    					case 1:
    					{
    						if (board[i - 1][j - 1] != '.' && tmp[board[i - 1][j - 1] - '0'] == '.') tmp[board[i - 1][j - 1] - '0'] = 'f';
    						if (board[i - 1][j + 1] != '.' && tmp[board[i - 1][j + 1] - '0'] == '.') tmp[board[i - 1][j + 1] - '0'] = 'f';
    						if (board[i + 1][j - 1] != '.' && tmp[board[i + 1][j - 1] - '0'] == '.') tmp[board[i + 1][j - 1] - '0'] = 'f';
    						if (board[i + 1][j + 1] != '.' && tmp[board[i + 1][j + 1] - '0'] == '.') tmp[board[i + 1][j + 1] - '0'] = 'f';
    					}break;
    					case 2:
    					{
    						if (board[i - 1][j - 1] != '.' && tmp[board[i - 1][j - 1] - '0'] == '.') tmp[board[i - 1][j - 1] - '0'] = 'f';
    						if (board[i - 1][j - 2] != '.' && tmp[board[i - 1][j - 2] - '0'] == '.') tmp[board[i - 1][j - 2] - '0'] = 'f';
    						if (board[i + 1][j - 1] != '.' && tmp[board[i + 1][j - 1] - '0'] == '.') tmp[board[i + 1][j - 1] - '0'] = 'f';
    						if (board[i + 1][j - 2] != '.' && tmp[board[i + 1][j - 2] - '0'] == '.') tmp[board[i + 1][j - 2] - '0'] = 'f';
    					}break;
    					default: break;
    					}break;
    				case 2:
    					switch (j % 3)
    					{
    					case 0:
    					{
    						if (board[i - 1][j + 1] != '.' && tmp[board[i - 1][j + 1] - '0'] == '.') tmp[board[i - 1][j + 1] - '0'] = 'f';
    						if (board[i - 1][j + 2] != '.' && tmp[board[i - 1][j + 2] - '0'] == '.') tmp[board[i - 1][j + 2] - '0'] = 'f';
    						if (board[i - 2][j + 1] != '.' && tmp[board[i - 2][j + 1] - '0'] == '.') tmp[board[i - 2][j + 1] - '0'] = 'f';
    						if (board[i - 2][j + 2] != '.' && tmp[board[i - 2][j + 2] - '0'] == '.') tmp[board[i - 2][j + 2] - '0'] = 'f';
    					}break;
    					case 1:
    					{
    						if (board[i - 1][j - 1] != '.' && tmp[board[i - 1][j - 1] - '0'] == '.') tmp[board[i - 1][j - 1] - '0'] = 'f';
    						if (board[i - 1][j + 1] != '.' && tmp[board[i - 1][j + 1] - '0'] == '.') tmp[board[i - 1][j + 1] - '0'] = 'f';
    						if (board[i - 2][j - 1] != '.' && tmp[board[i - 2][j - 1] - '0'] == '.') tmp[board[i - 2][j - 1] - '0'] = 'f';
    						if (board[i - 2][j + 1] != '.' && tmp[board[i - 2][j + 1] - '0'] == '.') tmp[board[i - 2][j + 1] - '0'] = 'f';
    					}break;
    					case 2:
    					{
    						if (board[i - 1][j - 1] != '.' && tmp[board[i - 1][j - 1] - '0'] == '.') tmp[board[i - 1][j - 1] - '0'] = 'f';
    						if (board[i - 1][j - 2] != '.' && tmp[board[i - 1][j - 2] - '0'] == '.') tmp[board[i - 1][j - 2] - '0'] = 'f';
    						if (board[i - 2][j - 1] != '.' && tmp[board[i - 2][j - 1] - '0'] == '.') tmp[board[i - 2][j - 1] - '0'] = 'f';
    						if (board[i - 2][j - 2] != '.' && tmp[board[i - 2][j - 2] - '0'] == '.') tmp[board[i - 2][j - 2] - '0'] = 'f';
    					}break;
    					default: break;
    					}break;
    				default: break;;
    				}
    				k = 1; flag = 0; num = 0;
    				while (k < 10) { if (tmp[k] == '.') { flag = k; num++; } k++; }
    				if (num == 1) { board[i][j] = flag + '0'; timeflag = 1; }
    				k = 1;
    				while (k < 10) { tmp[k] = '.'; k++; }
    			}
    		}
    	}
    
    	for (i = 0; i < 9; i++)
    	{
    		for (j = 0; j < 9; j++)
    		{
    			if (board[i][j] == '.')
    			{
    				if (timeflag == 1)
    				{
    					timeflag = 0;
    					solveSudoku(board);
    				}
    				else
    				{
    					solveSudokutry(board);//猜值
    				}
    			}
    		}
    	}
    }
    

    public:
    //Guessing and temp
    bool solveSudokutry(vector<vector<char>>& board)
    {
    int i = 0, j = 0, k = 0;
    for (i = 0; i < 9; i++)
    {
    for (j = 0; j < 9; j++)
    {
    if (board[i][j] == '.')
    {
    k = 1;
    while (k < 10)
    {
    board[i][j] = k + '0';
    if (isValid(board, i, j) && solveSudokutry(board))
    {
    return true;
    }
    board[i][j] = '.';
    k++;
    }
    return false;
    }
    }
    }
    return true;
    }

    private:
    //judgment
    bool isValid(vector<vector<char> > &board, int x, int y)
    {
    int i, j;
    for (i = 0; i < 9; i++)
    if (i != x && board[i][y] == board[x][y])
    return false;
    for (j = 0; j < 9; j++)
    if (j != y && board[x][j] == board[x][y])
    return false;
    for (i = 3 * (x / 3); i < 3 * (x / 3 + 1); i++)
    for (j = 3 * (y / 3); j < 3 * (y / 3 + 1); j++)
    if (i != x && j != y && board[i][j] == board[x][y])
    return false;
    return true;
    }
    };

    Spoiler


Log in to reply
 

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