weixin_46609088
2021-05-21 11:08
采纳率: 0%
浏览 26

用回溯法解数独问题,结果一直为空

class Solution { public: vector> spaces; bool row[9][9],col[9][9],degree[3][3][9]; int len; void solveSudoku(vector>& board) { memset(row,0,sizeof(row)); memset(col,0,sizeof(col)); memset(degree,0,sizeof(degree)); for(int i=0;i<9;i++){ for(int j=0;j<9;j++){ if(board[i][j]>='1'&&board[i][j]<='9'){ int a=board[i][j]-'0'; row[i][a-1]=col[j][a-1]=degree[i/3][j/3][a-1]=true; } else{ spaces.push_back(make_pair(i,j)); } } } len=spaces.size(); dfs(0,board); return; } bool check(int a,int b,int k){ if(row[a][k]||col[b][k]||degree[a/3][b/3][k]){ return false; } return true; } bool dfs(int start,vector> board){ if(start==len){ return true; } int x=spaces[start].first,y=spaces[start].second; for(int i=1;i<=9;i++){ if(check(x,y,i-1)){ row[x][i-1]=col[y][i-1]=degree[x/3][y/3][i-1]=true; board[x][y]=i+'0'; if(dfs(start+1,board)) return true; row[x][i-1]=col[y][i-1]=degree[x/3][y/3][i-1]=false; } } return false; } };

  • 写回答
  • 好问题 提建议
  • 追加酬金
  • 关注问题
  • 邀请回答

2条回答 默认 最新

相关推荐 更多相似问题