请编写一个程序，给数独中的剩余的空格填写上数字
空格用字符'.'表示
假设给定的数独只有唯一的解法
这盘数独的解法是：
红色表示填上的解
[编程题]数独
- 热度指数：11794 时间限制：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]]
// 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)
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)
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)
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)
//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)
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)
include #include bool isValid(char** board #include <stdbool.h>
#include <stdio.h>
bool isValid(char** board, int row, int col, char c) {
for (int i = 0; i < 9; i++) {
// 检查行、列
if (board[row][i] == c) return false;
if (board[i][col] == c) return false;
// 检查3x3小方格
int boxRow = 3 * (row / 3) + i / 3;
int boxCol = 3 * (col / 3) + i % 3;
if (board[boxRow][boxCol] == c) return false;
}
return true;
}
bool dfs(char** board) {
for (int i = 0; i < 9; i++) {
for (int j = 0; j < 9; j++) {
if (board[i][j] == '.' || board[i][j] == '0') {
for (char c = '1'; c <= '9'; c++) {
if (isValid(board, i, j, c)) {
board[i][j] = c;
if (dfs(board)) return true;
board[i][j] = '.';
}
}
return false; // 9个都不行，回溯
}
}
}
return true; // 填满了
}
void solveSudoku(char** board, int boardRowLen, int* boardColLen) {
dfs(board);
}
, int row, int col, char c) { for (int i = 0; i
发表于 2025-08-29 11:42:25
回复(0)
import java.util.*;
public class Solution {
private boolean completed = false; // 是否完成 (要全局变量)
public void solveSudoku(char[][] board) {
List<int[]> blankList = new ArrayList<>(); // 要填的空格list
for (int i = 0; i < board.length; i++) {
for (int j = 0; j < board[0].length; j++) {
if (board[i][j] == '.') {
blankList.add(new int[] {i, j});
}
}
}
backtrack(board, blankList, 0); // 调用
}
// 回溯
private void backtrack(char[][] board, List<int[]> blankList, int k) {
if (completed || k == blankList.size()) { // 出口
if (!completed && k == blankList.size()) {
completed = true;
}
return;
}
for (char c = '1'; c <= '9'; c++) { // 0-9都尝试
int x = blankList.get(k)[0], y = blankList.get(k)[1];
if (!check(board, x, y, c)) continue;
board[x][y] = c;
backtrack(board, blankList, k + 1);
if (completed) return; // 填完了,不用撤销
board[x][y] = '.';
}
}
// 判断(x,y)能否填数字c
private boolean check(char[][] board, int x, int y, char c) {
//该行
for (int j = 0; j < board[0].length; j++) {
if (board[x][j] == c) return false;
}
//该列
for (int i = 0; i < board.length; i++) {
if (board[i][y] == c) return false;
}
//该小矩形 （x0,y0）左上角
for (int x0 = x / 3 * 3, i = 0; i < 3; i++) {
for (int y0 = y / 3 * 3, j = 0; j < 3; j++) {
if (board[x0 + i][y0 + j] == c) return false;
}
}
return true;
}
}
发表于 2025-03-29 11:06:30
回复(0)
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)
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)
分享题解：
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)
递归+回溯，遍历所有的棋盘格子，如果格子里已经有数字了，就继续下一个，如果没有，就挨个测试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)
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)
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)
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
}
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)
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)
问题信息
难度：
44条回答
186收藏
18235浏览
通过挑战的用户
查看代码-
2022-09-16 10:58:20 -
2022-09-15 14:58:36 -
2022-09-15 14:54:50 -
2022-09-15 14:27:21
-
2022-09-14 09:16:36
相关试题
-
扫描二维码，关注牛客网
- 意见反馈
-
下载牛客APP，随时随地刷题
扫一扫，把题目装进口袋
- 求职之前，先上牛客
-
扫描二维码，进入QQ群
扫描二维码，关注牛客公众号
- 公司地址：北京市朝阳区北苑路北美国际商务中心K1座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备
11010502036488号
