首页 > 试题广场 >

数独

[编程题]数独
  • 热度指数：11604 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 256M，其他语言512M
  • 算法知识视频讲解
请编写一个程序，给数独中的剩余的空格填写上数字
空格用字符'.'表示
假设给定的数独只有唯一的解法

这盘数独的解法是：
红色表示填上的解
示例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]]
算法知识视频讲解
添加回答
moon-star头像 moon-star
// The code is long and complex, but the average time  is one-third or even one-half faster than the general algorithm. Noted that i copyed the code of the no.1 person into web and test it,  the average time is 7ms.
// 这段代码很长也很复杂，但是平均运行时间比一般的算法快三分之一甚至二分之一。值得注意的是，我复制了第一名的算法到网页答题区并测试它，平均运行时间时6~7ms，而我的只需要3~5ms。
class Solution {
public:
    void computeCandidate(const vector<vector<char> > &board, array<array<list<int> ,9> ,9> &arrCandidate) {
        // num has be set
        array<array<bool ,9> ,9> status_row{array<bool ,9>{false}};
        array<array<bool ,9> ,9> status_col{array<bool ,9>{false}};
        array<array<bool ,9> ,9> status_block{array<bool ,9>{false}};
        // status
        for(int i = 0; i < 9; ++i){
            for(int j = 0; j < 9; ++j){
                if(board[i][j] == '.') continue;
                // find candinate at(i,j)
                status_row[i][board[i][j]-'1'] = true;
                status_col[j][board[i][j]-'1'] = true;
                status_block[(i/3*3 + j/3)][board[i][j]-'1'] = true;
            }
        }
        // count status
        for(int i = 0; i < 9; ++i){
            for(int j = 0; j < 9; ++j) {
                if(board[i][j] != '.') continue;
                arrCandidate[i][j].assign({1,2,3,4,5,6,7,8,9});
                for(int m = 0; m < 9; ++m){
                    if(status_row[i][m] || status_col[j][m] || status_block[i/3*3+j/3][m]){
                        arrCandidate[i][j].remove(m+1);
                    }
                }
            }
        }
    }
    bool setValue(vector<vector<char> > &board, array<array<list<int> ,9> ,9> &arrCandidate)
    {
        size_t min_length = 10;
        int min_i = -1, min_j = -1;
        bool solved = true;
        for (int i = 0; i < 9; ++i) {
            for (int j = 0; j < 9; ++j) {
                if(board[i][j] == '.') {
                    solved = false;
                    if (arrCandidate[i][j].size() < min_length) {
                        min_length = arrCandidate[i][j].size();
                        min_i = i;
                        min_j = j;
                    }
                }
            }
        }
        // no empty char
        if(min_length > 9){
            return solved;
        }
        if(min_length < 1 || min_i < 0 || min_j < 0 || min_i >= 9 || min_j >= 9) {
            // can not reach here.
            return false;
        }
        list<int> min_list = arrCandidate[min_i][min_j];

        for(auto num : min_list){
            // try to set value
            board[min_i][min_j] = '0' + static_cast<char>(num);

            vector<int> updated;
            // update row
            for(int m = 0; m < 9; ++m){
                if(board[min_i][m] != '.') continue;
                auto &candidate = arrCandidate[min_i][m];
                auto it = std::find(candidate.cbegin(), candidate.cend(), num);
                if(it != candidate.cend()){
                    candidate.erase(it);
                    updated.push_back(min_i*9 + m);
                }
            }
            // update col
            for(int m = 0; m < 9; ++m){
                if(board[m][min_j] != '.') continue;
                auto &candidate = arrCandidate[m][min_j];
                auto it = std::find(candidate.cbegin(), candidate.cend(), num);
                if(it != candidate.cend()){
                    candidate.erase(it);
                    updated.push_back(m*9 + min_j);
                }
            }
            //update block
            auto m_s = min_i/3*3, n_s = min_j/3*3;
            for(int m = m_s; m < m_s+3; ++m){
                for(int n = n_s; n < n_s+3; ++n) {
                    if(board[m][n] != '.') continue;
                    auto &candidate = arrCandidate[m][n];
                    auto it = std::find(candidate.cbegin(), candidate.cend(), num);
                    if(it != candidate.cend()){
                        candidate.erase(it);
                        updated.push_back(m*9 + n);
                    }
                }
            }

            bool ret = setValue(board, arrCandidate);
            if(ret){// successful
                return true;
            }
            // resore updated
            board[min_i][min_j] = '.';
            for(auto idx : updated){
                arrCandidate[idx/9][idx%9].push_back(num);
            }
        }
        return false;
    }
    void solveSudoku(vector<vector<char> > &board) {
        array<array<list<int> ,9> ,9> arrCandidate{};
        computeCandidate(board, arrCandidate);
        // fill the certain results
        while(true) {
            bool set_one = false;
            for (int i = 0; i < 9; ++i) {
                for (int j = 0; j < 9; ++j) {
                    if (arrCandidate[i][j].size() == 1) {
                        int num = (arrCandidate[i][j].front());
                        board[i][j] = '0' + static_cast<char>(num);
                        arrCandidate[i][j].clear();
                        for(int m = 0; m < 9; ++m){
                            arrCandidate[m][j].remove(num);
                        }
                        for(int m = 0; m < 9; ++m){
                            arrCandidate[i][m].remove(num);
                        }
                        auto m_s = i/3*3, n_s = j/3*3;
                        for(int m = m_s; m < m_s+3; ++m){
                            for(int n = n_s; n < n_s+3; ++n) {
                                arrCandidate[m][n].remove(num);
                            }
                        }
                        set_one = true;
                    }
                }
            }
            if(!set_one) break;
        }
        // try others
        setValue(board, arrCandidate);
    }
};
发表于 2019-07-31 21:38:34 回复(0)
Jerryyyyy头像 Jerryyyyy
40 lines code. 参照valid sudoku，先把已有数字填充至3个验证数组，然后回溯求解，每次填入一个数要同时修改board和验证数组。只有符合sudoku的条件，才下一步，否则返回。求出结果后一直return true 便可退出。 
class Solution {
public:
    void solveSudoku(vector<vector<char>>& board) {
        vector<vector<int>> used1(9,vector<int>(9,0)),used2(9,vector<int>(9,0)),used3(9,vector<int>(9,0));
            fillnum(used1,used2,used3,board);
            solve(used1,used2,used3,board);  
    }
    
    void fillnum(vector<vector<int>> &used1,vector<vector<int>> &used2,vector<vector<int>> &used3,vector<vector<char> > &board) {
        for(int i=0;i<board.size();i++)
            for(int j=0;j<board[0].size();j++)
            if(board[i][j]!='.')
            {
                int num=board[i][j]-'0'-1;
                int k=i/3*3+j/3;
                    used1[i][num]=used2[j][num]=used3[k][num]=1;
            }
    }
     
    bool solve(vector<vector<int>> &used1,vector<vector<int>> &used2,vector<vector<int>> &used3,vector<vector<char>>&board){
       for(int i=0;i<board.size();i++)
            for(int j=0;j<board[0].size();j++){
                int k=i/3*3+j/3;
                if(board[i][j]=='.'){
                    for(int fill=1;fill<10;fill++){
                        if(used1[i][fill-1]==0 && used2[j][fill-1]==0 && used3[k][fill-1]==0){
                        board[i][j]=fill+'0';
                        used1[i][fill-1]=used2[j][fill-1]=used3[k][fill-1]=1;
                        if(solve(used1,used2,used3,board))
                            return true;                            
                        board[i][j]='.';
                        used1[i][fill-1]=used2[j][fill-1]=used3[k][fill-1]=0;
                        }                        
                }   
                    return false;
                }            
            }
        return true;
    }
};

发表于 2018-08-05 10:21:51 回复(0)
潘多拉Boot头像 潘多拉Boot 
class Solution {
public:
    void solveSudoku(vector<vector<char> > &board) {
      solve(board);
    }  
    bool solve(vector<vector<char> > &board){
        for (int i = 0; i < 9; ++i)  
            for (int j = 0; j < 9; j++)  
            {  
                if ( board[i][j]=='.')  
                {  
                    for (int k = 1; k <= 9; k++)  
                    {  
                        board[i][j] = '0' + k;  
                        if (isValidSudoku(board) && solve(board))  
                            return true;  
                        board[i][j] = '.';  
                    }  
                    return false;  
                }  
            }  
        return true;  
    }
     bool isValidSudoku(vector<vector<char> > &board) {
      int row[9][9] = {0};  //创造一个行数组，一行9个格子，一共9行，用来将board中的每一行的数字存放进对应角标的位置，
                            //如row[1][2]=1 代表着第2行已经有一个3存在了，下一次要是在第2行又出现一个3，就返回false
        int col[9][9] = {0};  //创造一个列数组，一列9个格子，一共9列
        int grids[3][3][9] = {0};  //代表全图划分的9个小正方形区域，每个区域里面的九宫格
        for(int i = 0; i < 9; i++){
            for(int j = 0; j < 9; j++){
                if(board[i][j] != '.'){
                    int index = board[i][j] - '1';
                    if(row[i][index]++)      //row[i][index]如果不存在的数字的话（最开始都是0），就使row[i][index]+1；
                        return false;        //下一次在判断的时候如果
                    if(col[j][index]++)
                        return false;
                    if(grids[i/3][j/3][index]++)
                        return false;
                }
            }
        }
        return true;
    }
};

发表于 2018-05-13 15:59:40 回复(2)
C/C++
nbgao头像 nbgao 
class Solution {
public:
	void solveSudoku(vector<vector<char> > &board) {
		int n=board.size();
		if(board.empty() || n == 0)
			return;
		solve(board);
	}
	
    bool solve(vector<vector<char> > &board) {
        int n = board.size();
        for(int i=0;i<n;i++)
        	for(int j=0;j<n;j++)
        		if(board[i][j] == '.')
        		{
        			for(char c='1';c<='9';c++)
        				if(isValid(board,i,j,c))
        				{
        					board[i][j] = c;
        					if(solve(board))
        						return true;
        					else
        						board[i][j] = '.';
						}
					return false;
				}
		return true;
    }
    
    bool isValid(vector<vector<char> > board,int row,int col,char num)
    {
    	int n = board.size();
    	for(int i=0;i<n;i++)
    	{
    		if(board[i][col] == num || board[row][i] == num)
    			return false;
    		if(board[3*(row/3)+i/3][3*(col/3)+i%3] == num)
    			return false;
		}
		return true; 
	}
};

发表于 2017-08-25 01:29:24 回复(1)
whisky_头像 whisky_
//DFS CPP代码
class Solution {
public:
    void solveSudoku(vector<vector<char> > &board) {
        DFS(board, 0, 0);
    }
    bool DFS(vector<vector<char>> &board, int r, int c){
        if(r>=9||c>=9)
            return true;
        if(board[r][c]!='.')
            return c<8? DFS(board, r, c+1):DFS(board, r+1, 0);
        for(int i=0; i<9; ++i){
            if(check(board, r, c, i+'1')){
                board[r][c]=i+'1';
                if(!DFS(board, r, c))
                    board[r][c]='.';
                else
                    return true; 
            }
        }
        return false;
    }
    
    bool check(vector<vector<char>> &board, int r, int c, char chr){
        for(int i=0; i<9; ++i)
            if(board[r][i]==chr||board[i][c]==chr)
                return false;
        for(int i=r/3*3; i<((r/3)+1)*3; ++i)
            for(int j=c/3*3; j<((c/3)+1)*3; ++j)
                if(board[i][j]==chr)
                    return false;
        return true;
    }
};
发表于 2017-04-17 11:26:43 回复(0)
后劲好大头像 后劲好大 
public class Solution {
    public void solveSudoku(char[][] board) {
		if (board == null || board.length == 0 || board[0].length == 0)
			return;
		solve(board, 0);
	}

	public boolean solve(char[][] board, int num) {
		if(num == 81)
			return true;
		int m = num / 9;
		int n = num % 9;
		// 如果该位已经有数字，则进行下次搜索
		if(board[m][n] != '.'){
			if(solve(board, ++num))
				return true;
			return false;
		}
		// 如果是‘.’，那么就试凑
		for(char c= '1'; c <= '9'; c++){
			if(!isValid(board, m, n, c))
				continue;
			board[m][n] = c;
			if(solve(board, num+1)) 
				return true;
			// 试凑结果不对需要进行回溯
			board[m][n] = '.';
		}
		return false;
	}

	public boolean isValid(char[][] board, int m, int n, char c) {

		int tm = m / 3;
		int tn = n / 3;
		int mbegin = tm * 3;
		int nbegin = tn * 3;

		// 检查小的九宫格
		for (int i = 0; i < 3; i++) {
			for (int j = 0; j < 3; j++) {
				if (board[mbegin + i][nbegin + j] == c)
					return false;
			}
		}
		// 检查行
		for (int i = 0; i < 9; i++) {
			if (board[m][i] == c)
				return false;
		}
		// 检查列
		for (int i = 0; i < 9; i++) {
			if (board[i][n] == c)
				return false;
		}
		return true;
	}
}

发表于 2017-07-02 10:55:34 回复(3)
JacobGo！头像 JacobGo！ 
package go.jacob.day803;

/**
 * 37. Sudoku Solver
 * @author Jacob
 * 思路：
 * 简单地说思路就是循环处理子问题，对于每个格子，带入不同的9个数，
 * 然后判合法，如果成立就递归继续，结束后把数字设回'.'
 *
 */
public class Demo1 {
	public void solveSudoku(char[][] board) {
        if (board == null || board.length == 0)
            return;

        solve(board);
    }

    private 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++) {
                        if (isValid(board, c, i, j)) {
                            board[i][j] = c;
                            if (solve(board))
                                return true;
                            board[i][j] = '.';
                        }
                    }
                    return false;
                }
            }
        }
        return true;//递归最后一步，所有空位都填满
    }

    private boolean isValid(char[][] board, char c, int row, int col) {
        for (int i = 0; i < board.length; i++) {
            if (board[i][col] == c)
                return false;
            if (board[row][i] == c)
                return false;
        }

        int xBegin = (row / 3) * 3, yBegin = (col / 3) * 3;

        for (int i = xBegin; i < xBegin + 3; i++) {
            for (int j = yBegin; j < yBegin + 3; j++) {
                if (board[i][j] == c)
                    return false;
            }
        }

        return true;
    }

}


编辑于 2018-06-10 12:23:27 回复(0)
小白呱呱呱头像 小白呱呱呱 
public class Solution {
    public char[][] board;
    boolean dfs(int num) {
        if(num == 81) return true;
        int m = num/9,n = num%9;
        if(board[m][n] != '.') {
            if(dfs(++num)) return true;
            return false;
        }
        for(char c = '1';c <= '9';c++) {
            if(!check9(m,n,c)) continue;
        	if(!checkM(m,n,c)) continue;
        	if(!checkN(m,n,c)) continue;
            
            board[m][n] = c;
            if(dfs(num+1)) return true;
            board[m][n] = '.';
        }
        return false;
    }
    
    //check 小九宫
     boolean check9(int m,int n,char c) {
      	int tm = m/3;
        int tn = n/3;
        int mstart = tm*3;
        int nstart = tn*3;
        
        for(int i = 0;i < 3;i++) {
            for(int j = 0;j < 3;j++) {
                if(board[mstart+i][nstart+j] == c)
                    return false;
            }
        }
        return true;
    }
    //check 行
    boolean checkM(int m,int n,char c) {
    	for(int i = 0;i < 9;i++) {
            if(board[m][i] == c) return false;
        }    
    	return true;
    }
    //check 列
    boolean checkN(int m,int n,char c) {
    	for(int i = 0;i < 9;i++) {
            if(board[i][n] == c) return false;
        }    
    	return true;
    }
   
    
    public void solveSudoku(char[][] board) {
    	this.board = board;
        dfs(0);
    }
}

发表于 2016-09-10 10:50:36 回复(0)
牛客2024007号头像 牛客2024007号 
import java.util.*;
public class Solution {
    boolean[][] visitedRow = new boolean[9][10];
    boolean[][] visitedLine = new boolean[9][10];
    boolean[][] visitedBlock = new boolean[9][10];
    public void solveSudoku(char[][] board) {
        int rows = board.length;
        int lines = board[0].length;
        // 初始化访问数组
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < lines; j++) {
                if (board[i][j] != '.') {
                    // 记录
                    int var = (board[i][j] - '0');
                    int block = j / 3 + (i / 3) * 3;
                    visitedRow[i][var] = true;
                    visitedLine[j][var] = true;
                    visitedBlock[block][var] = true;
                }
            }
        }
        backtracing(0, 0, board);
    }

    private boolean backtracing(int row, int line, char[][] board) {
        if (row == 9) return true;

        if (board[row][line] != '.') {
            if (line != 8) {
                return backtracing(row, line + 1, board);
            } else {
                return backtracing(row + 1, 0, board);
            }
        }
        int block = line / 3 + (row / 3) * 3;
        for (int i = 1; i <= 9; i++) {
            if (visitedLine[line][i] || visitedBlock[block][i] ||
                    visitedRow[row][i]) continue;
            visitedLine[line][i] = true;
            visitedRow[row][i] = true;
            visitedBlock[block][i] = true;
            board[row][line] = (char) (i + '0');
            if (line != 8) {
                if(backtracing(row, line + 1, board)) return true;
            } else {
                if(backtracing(row + 1, 0, board)) return true;
            }
            visitedLine[line][i] = false;
            visitedRow[row][i] = false;
            visitedBlock[block][i] = false;
            board[row][line] = '.';
        }
        return false;
    }
}

编辑于 2024-02-04 02:30:26 回复(0)
Java
小谷围做题家头像 小谷围做题家 
public class Solution {
    private char[][] board;
    public void solveSudoku(char[][] board) {
        this.board=board;
        dfs();
    }
    public boolean dfs(){
        for(int i=0;i<9;i++){
            for(int j=0;j<9;j++){
                if(board[i][j]!='.') continue;
                for(int x=1;x<=9;x++){
                    if(check(i,j,x)){
                        board[i][j]=(char)('0'+x);
                        if(dfs()) return true;
                        board[i][j]='.';
                    }
                }
                return false;
            }
        }
        return true;
    }
    public boolean check(int i,int j,int x){
        for(int k=0;k<9;k++){
            if(board[i][k]=='0'+x) return false;
            if(board[k][j]=='0'+x) return false;
        }
        i/=3;
        j/=3;
        for(int c=i*3;c<i*3+3;c++){
            for(int d=j*3;d<j*3+3;d++){
                if(board[c][d]=='0'+x) return false;
            }
        }
        return true;
    }
}

发表于 2023-08-10 19:15:31 回复(0)
C++
虚戈戈头像 虚戈戈
分享题解： 
class Solution {
  public:
    bitset<10> row[9];
    bitset<10> col[9];
    bitset<10> block[9][9];

    bool _solveSudoku(vector<vector<char> >& board) {
        for (int i = 0; i < 9; i++)
            for (int j = 0; j < 9; j++) {
                if (board[i][j] == '.') {
                    for (int k = 1; k <= 9; k++) {
                        if (!row[i][k] && !col[j][k] && !block[i / 3][j / 3][k]) {
                            row[i][k] = 1;
                            col[j][k] = 1;
                            block[i / 3][j / 3][k] = 1;
                            board[i][j] = '0' + k;
                            if (_solveSudoku(board))
                                return true;
                            row[i][k] = 0;
                            col[j][k] = 0;
                            block[i / 3][j / 3][k] = 0;
                            board[i][j] = '.';
                        }
                    }
                    return false;
                }
            }
        return true;
    }

    void solveSudoku(vector<vector<char> >& board) {
        for (int i = 0; i < 9; i++)
            for (int j = 0; j < 9; j++) {
                if (board[i][j] == '.');
                else {
                    row[i][board[i][j] - '0'] = 1;
                    col[j][board[i][j] - '0'] = 1;
                    block[i / 3][j / 3][board[i][j] - '0'] = 1;
                }
            }
        _solveSudoku(board);
    }
};


发表于 2023-02-28 15:01:13 回复(0)
C++
爱萝莉头像 爱萝莉
递归+回溯，遍历所有的棋盘格子，如果格子里已经有数字了，就继续下一个，如果没有，就挨个测试1-9是否合法，并尝试填入合法数字，继续下一个，如果失败就回溯，成功则直接返回结果（因为题目答案唯一，找到就直接返回即可）。 
class Solution {
  public:
    bool flag = false;//全局变量flag，判断是否找到了答案。
    //递归部分，参数为棋盘，行判断数组，列判断数组，九宫格区域判断数组，行，列，大小。
    void work(vector<vector<char>>& res, vector<int>& hang_check,
              vector<int>& lie_check, vector<int>& cube_check, int hang, int lie, int size) {
        if (flag)return;//如果找到了就返回。
        if (lie == size) {//如果列超过大小了，就到下一行。
            ++hang;
            lie = 0;
        }
        if (hang == size) {//如果行超过大小了，就说明找完了。
            flag = true;
            return;
        }//行列判断也可以简化为一个int，用整除和求余来获取行列号。

        if (res[hang][lie] != '.') {//如果不是'.'，说明这里已经有数字了，找下一个
            work(res, hang_check, lie_check, cube_check, hang, lie + 1, size);
        } else {
            for (int i = 1; i <= 9; ++i) {//在1-9里寻找
                if (!check(hang_check[hang], i) && !check(lie_check[lie], i) &&
                        !check(cube_check[hang / 3 * 3 + lie / 3], i)) {//行、列、九宫格检查
                    hang_check[hang] += (1 << i);//把该数字记录进检查数组
                    lie_check[lie] += (1 << i);
                    cube_check[hang / 3 * 3 + lie / 3] += (1 << i);
                    res[hang][lie] = i + '0';
                    work(res, hang_check, lie_check, cube_check, hang, lie + 1, size);
                    if (flag)return;//如果找到了就直接返回不必回溯
                    hang_check[hang] -= (1 << i);//没找到就回溯。
                    lie_check[lie] -= (1 << i);
                    cube_check[hang / 3 * 3 + lie / 3] -= (1 << i);
                    res[hang][lie] = '.';
                }
            }
        }
    }

    bool check(int check, int num) {
        return check & (1 << num);//判断函数，本质是位运算与。
    }

    void solveSudoku(vector<vector<char> >& board) {
        int size = board.size();
        vector<int>h_check(size, 0);
        vector<int>l_check(size, 0);
        vector<int>c_check(size, 0);
        for (int i = 0; i < size; ++i) {
            for (int j = 0; j < size; ++j) {
                if (board[i][j] != '.') {
                    h_check[i] += (1 << (board[i][j] - '0'));//初始化各个判断数组
                    l_check[j] += (1 << (board[i][j] - '0'));
                    c_check[i / 3 * 3 + j / 3] += (1 << (board[i][j] - '0'));
                    //关于九宫格区域定位：通过列号来判断九宫格的列号0,1,2对应0；3，4，5对应1；6，7，8对应2.
                    //因此用i整除3获得该对应。第0行的第一个九宫格号为0号，第1行的第一个九宫格号对应为3号，以此类推
                    //所以用i/3*3,之后就用列号来确定九宫格的列号即可，同理。
                }
            }
        }
        work(board, h_check, l_check, c_check, 0, 0, size);
    }
};
可能需要注意的点：
    返回问题：第一次找到答案就返回，避免回溯擦去答案。
   检查问题：需要检查行、列、九宫格三个。
   数据问题：题目给的是char型，要注意与int型的混用转换（用'0'）。

发表于 2023-01-07 19:17:46 回复(0)
牛娃牛娃头像 牛娃牛娃 
class Solution {
private:
    bool backtracking(vector<vector<char>> &board){
        for(int i =0;i<board.size();i++){//遍历行
            for(int j =0;j<board[0].size();j++){//遍历列
                if(board[i][j]!='.')continue;
                for(char k='1';k<='9';k++){// （i，j）可以放k是否合适
                    if(isvaild(i,j,k,board)){
                        board[i][j]=k;//放置k
                        if(backtracking(board))return true;
                        board[i][j]='.';//回溯k
                    }
                }
                return false;//九个数都试完了 都不行 就返回 false
            }
        }
        return true;//如果遍历完没有返回false 就说明找到了合适的解
    }
    
    
    bool isvaild(int row,int col,char val,vector<vector<char>>& board){
        //row是行  col是列
        //先判断同一行有没有相同的数
        for(int i=0;i<9;i++){
            if(board[row][i]==val)return false;
        }
        
        //先判断同一列有没有相同的数
        for(int j=0;j<9;j++){
            if(board[j][col]==val)return false;
        }
        
        //判断小的九宫格是否有重复的数
        int startrow =(row/3)*3 ; //每个九宫格行的起始位置
        int startcol =(col/3)*3 ;//每个九宫格列的起始位置
        for(int i = startrow;i<startrow+3;i++){
            for(int j = startcol;j<startcol+3;j++){
                if(board[i][j]==val)return false;
            }
        }
        
        return true;
    }
    
    
public:
    void solveSudoku(vector<vector<char> > &board) {
        backtracking(board);
    }
};

发表于 2022-03-19 13:58:36 回复(0)
Java
シkid~头像 シkid~ 
public class Solution {
    // 判断行列是否冲突的hash数组
    boolean[][][] flag = new boolean[2][9][9];
    // 判断小宫格是否冲突的hash数组
    boolean[][][] flagMini = new boolean[3][3][9];
    
    public void solveSudoku(char[][] board) {
        // 初始化hash数组
        for(int i=0; i<9; i++) {
            for(int j=0; j<9; j++) {
                if (board[i][j] != '.') {
                    int value = board[i][j] - '1';
                    flag[0][i][value] = true;
                    flag[1][value][j] = true;
                    flagMini[i/3][j/3][value] = true;
                }
            }
        }
        sudoku(board, 0, 0);
    }

    // 判断数独是否合法
    public boolean judgeLegal(int row, int col, int value) {
        // 判断行列是否合法 和小三宫格是否合法
        if (flag[0][row][value-1] || flag[1][value-1][col] || flagMini[row/3][col/3][value-1]) {
            return false;
        }
        return true;
    }
    
    
    public boolean sudoku(char[][] board, int rowStart, int colStart) {
        if (rowStart == 9) { // 如果到达了超尾行，说明该数独成立
            return true;
        }
        if (board[rowStart][colStart] != '.') {
            if (colStart == 8) {
                return sudoku(board, rowStart+1, 0);
            } else {
                return sudoku(board, rowStart, colStart+1);
            }
        }
        // 尝试填入数字
        for(int k=1; k<=9; k++) {
            if (judgeLegal(rowStart, colStart, k)) { // 判断是否合法
                // 更新hash数组
                flag[0][rowStart][k-1] = true;
                flag[1][k-1][colStart] = true;
                flagMini[rowStart/3][colStart/3][k-1] = true;
                board[rowStart][colStart] = (char) (k + '0');
                if (colStart == 8) {
                    if (sudoku(board, rowStart+1, 0)) {
                        return true;
                    }
                } else {
                    if (sudoku(board, rowStart, colStart+1)) {
                        return true;
                    }
                }
                // 回溯
                flag[0][rowStart][k-1] = false;
                flag[1][k-1][colStart] = false;
                flagMini[rowStart/3][colStart/3][k-1] = false;
                board[rowStart][colStart] = '.';
            }
        }
        return false;
    }
}

发表于 2022-02-27 12:58:08 回复(0)
C++
木析头像 木析 
class Solution {
public:
    
    bool dfs(vector<pair<int,int>>& spot, int id, vector<vector<char> > &board, vector<vector<int>>& rows, vector<vector<int>>& cols, vector<vector<int>>& small) {
        if(id==spot.size())
            return true;
        auto [x,y]=spot[id];
        for(int i=1;i<=9;++i) {
            if(rows[x][i]==0 && cols[y][i]==0 && small[x/3*3+y/3][i]==0) {
                board[x][y]=('0'+i);
                rows[x][i]=1;
                cols[y][i]=1;
                small[x/3*3+y/3][i]=1;
                if(dfs(spot,id+1,board, rows,cols,small)) {
                    return true;
                }
                rows[x][i]=0;
                cols[y][i]=0;
                small[x/3*3+y/3][i]=0;
                board[x][y]='.';
            }
        }
        return false;
    }
    void solveSudoku(vector<vector<char> > &board) {
        vector<pair<int,int>> spot;
        vector<vector<int>> rows(10,vector<int>(10,0)); //rows[i][j]:在第i行，数字j是否出现过
    vector<vector<int>> cols(10,vector<int>(10,0)); //cols[i][j]:在第i列、数字j是否出现过
    vector<vector<int>> small(10,vector<int>(10,0)); //small[i][j]:在第i个小方格内、数字j是否出现过
        
        for(int i=0;i<9;++i) {
            for(int j=0;j<9;++j) {
                if(board[i][j]=='.') {
                    spot.push_back(pair<int,int>{i,j});
                } else {
                    rows[i][board[i][j]-'0']++;
                    cols[j][board[i][j]-'0']++;
                    small[i/3*3+j/3][board[i][j]-'0']++;
                }
            }
        }
        if(spot.size()==0) {
            return ;
        }
        dfs(spot,0,board,rows,cols,small);
    }
};

发表于 2021-10-04 10:16:08 回复(0)
Go
bigkai头像 bigkai
var row, col int
var rows, cols, tmp [][]bool
func solveSudoku( board [][]byte ) {
    if row = len(board); row == 0 {
        return
    }
    if col = len(board[0]); col == 0 {
        return
    }
    rows, cols, tmp = make([][]bool, row), make([][]bool, row), make([][]bool, row)
    for i := 0; i < row; i++ {
        rows[i] = make([]bool, col)
        cols[i] = make([]bool, col)
        tmp[i] = make([]bool, col)
    }

    for i := 0; i < row; i++ {
        for j := 0; j < col; j++ {
            if (board[i][j] != '.') {
                num := int(board[i][j] - '1')
                rows[i][num] = true
                cols[j][num] = true
                tmp[i / 3 * 3 + j / 3][num] = true
            }
        }
    }

    dfs(board, 0, 0)
}

func dfs(board [][]byte, i, j int) bool {
    for board[i][j] != '.' {
        j++
        if j >= col {
            i++
            j = 0
        }
        if i >= row {
            return true
        }
    }

    for k := 0; k < row; k++ {
        idx := i / 3 * 3 + j / 3
        if !rows[i][k] && !cols[j][k] && !tmp[idx][k] {
            board[i][j] = byte(k + '1')
            rows[i][k], cols[j][k], tmp[idx][k] = true, true, true
            if dfs(board, i, j) {
                return true
            }
            board[i][j] = '.'
            rows[i][k], cols[j][k], tmp[idx][k] = false, false, false
        }
    }

    return false
}
发表于 2021-08-14 14:14:30 回复(0)
惠灵顿靖头像 惠灵顿靖 
//好难啊
public class Solution {
    public void solveSudoku(char[][] board) {
        dfs(board,0,0);
    }
    boolean dfs(char[][] board,int x,int y){
        if(x==9)return true;
        if(y==9)return dfs(board,x+1,0);
        if(board[x][y] != '.')return dfs(board,x,y+1);
        for(char c='1';c<='9';++c){
            if(!isValid(board,x,y,c))continue;
            board[x][y]=c;
            if(dfs(board,x,y+1))return true;
            board[x][y] = '.';
        }
        return false;
    }
    boolean isValid(char[][] board,int x,int y,char ch){
        for(int i=0;i<9;++i){
            if(board[x][i] == ch)return false;
            if(board[i][y] == ch)return false;
            if(board[(x/3)*3+ i/3][(y/3)*3 + i%3]==ch)return false;
        }
        return true;
    }
}


发表于 2021-07-29 14:51:24 回复(0)
让我们Dawn起双桨头像 让我们Dawn起双桨 
public class Solution {
    public void solveSudoku(char[][] board) {
        backtrack(board, 0, 0);
    }


    private boolean backtrack(char[][] board, int r, int c) {
        int m = 9, n = 9;
        if (c == 9) {
            return backtrack(board, r+1, 0);
        }

        if (r == m) return true;

        for (int i = c; i < n; i++) {
            if (board[r][i]  != '.') {
                return backtrack(board, r, i+1);
            }
            for (char ch = '1'; ch <= '9'; ch++) {
                if (!isValid(board, r, i, ch)) continue;
                board[r][i] = ch;
                if (backtrack(board, r, i)) return true;
                board[r][i] = '.';
            }
            return false;
        }
        return false;
    }

    private boolean isValid(char[][] board, int r, int c, char ch) {
        for (int i = 0; i < 9; i++) {
            if (board[r][i] == ch) return false;
            if (board[i][c] == ch) return false;
            if (board[r/3*3+i/3][c/3*3+i%3] == ch) return false;
        }
        return true;
    }
}
发表于 2021-07-12 01:31:46 回复(0)
害群之马头像 害群之马
对于未知的点，如果只有一个合理的数值，则进行填充。否则，填上可能的数值，入栈 
class Solution {
public:
    void change(int A[9], char c){
        if(c!='.'){
            int idx=c-'1';
            A[idx]=1;
        }
    }
    int fillij(  vector<vector<char> > &board, int i, int j ){
        int A[9];
        for(int i=0;i<9;i++) A[i]=0;
        for(int k=0;k<9;k++){
            change(A,board[i][k]);
            change(A,board[k][j]);
            change(A,board[3*(i/3)+k/3][3*(j/3)+k%3]);
        }
        
        int num=0;
        int v=0;
        for(int i=0;i<9;i++){
            if(A[i]==0){num++;v=i;}
        }
        if(num==1) board[i][j]='1'+v;
        return num;
    }
    
    int fillmore( vector<vector<char> > &board ){
        // fill a board, return 1 if wrong
        int count;
        do{
            count=0;
            for(int i=0;i<9;i++)
                for(int j=0;j<9;j++){
                    if( board[i][j]=='.'){
                        int num=fillij(board,i,j);
                        if(num==0) return 1;
                        if(num==1 ) count++;
                    }
                }
        }while(count!=0);
        return 0;
    }
    void fillstk( vector<vector<char> > &board, stack<vector<vector<char> > >& stk ){
            for(int i=0;i<9;i++)
                for(int j=0;j<9;j++){
                    if( board[i][j]=='.'){
                        int A[9];
                        for(int k=0;k<9;k++) A[k]=0;
                        for(int k=0;k<9;k++){
                        change(A,board[i][k]);
                        change(A,board[k][j]);
                        change(A,board[3*(i/3)+k/3][3*(j/3)+k%3]);
                        }
                        for(int k=0;k<9;k++){
                            if(A[k]==1) continue;
                            vector<vector<char> > newboard=board;
                            newboard[i][j]='1'+k;
                            stk.push(newboard);
                        }
                                                return;
                    }
                }
    }
    bool isok(vector<vector<char> > &board){
        for(int i=0;i<9;i++)
            for(int j=0;j<9;j++){
                if(board[i][j]=='.') return false;
                }
        return true;
    }
    void solveSudoku(vector<vector<char> > &board) {
        stack<vector<vector<char> > > stk;
        stk.push(board);
        while(!stk.empty()){
            vector<vector<char> > top=stk.top();
            stk.pop();
            int vv=fillmore(top);
            if(vv==1) continue;
            if(isok(top)){
                board=top;
                return;
            }
            fillstk( top, stk);
        }
    }
};



编辑于 2021-06-02 15:51:33 回复(0)
叮铃铃铛铛铛头像 叮铃铃铛铛铛
class Solution:
    def solveSudoku(self , board ):
        # write code here
        def backtrack(board,r,c):
            def isValid(board,r,c,ch):
                for i in range(9):
                    if board[i][c]==ch:return False
                    if board[r][i]==ch:return False
                    if board[(r//3)*3+i//3][(c//3)*3+i%3]==ch:return False
                return True
            if r==9:return True
            if c==9:
                return backtrack(board,r+1,0)
            if board[r][c]!='.':
                return backtrack(board,r,c+1)
            for ch in range(1,10):
                s=str(ch)
                if not isValid(board,r,c,s):
                    continue
                board[r][c]=s
                if backtrack(board,r,c+1):return True
                board[r][c]='.'
        backtrack(board,0,0)
发表于 2021-05-05 11:18:33 回复(0)
提交观点

问题信息

回溯 哈希
难度：
42条回答 16871浏览

热门推荐

通过挑战的用户

相关试题

数独

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号