根据数独的规则Sudoku Puzzles - The Rules.判断给出的局面是不是一个符合规则的数独局面
数独盘面可以被部分填写，空的位置用字符'.'.表示
这是一个部分填写的符合规则的数独局面
[编程题]有效的数独
package go.jacob.day802;
import java.util.HashSet;
import java.util.Set;
/**
* 36. Valid Sudoku
*
* @author Jacob
*
*/
public class Demo1 {
/*
* 题意：让你判断这是否是一个正确的数独，
* 即确定每一行，每一列以及每一个九宫格是否有相同的数字
* HashSet的add方法，当添加成功（即set中不含有该元素）返回true
*/
public boolean isValidSudoku(char[][] board) {
// 每一个大循环确定一行，一列，一个九宫格
for (int i = 0; i < 9; i++) {
Set<Character> row = new HashSet<Character>();
Set<Character> col = new HashSet<Character>();
Set<Character> cube = new HashSet<Character>();
for (int j = 0; j < 9; j++) {
// 第i行
if (board[i][j] != '.' && !row.add(board[i][j]))
return false;
// 第i列
if (board[j][i] != '.' && !col.add(board[j][i]))
return false;
//
int cubeRow = 3 * (i / 3) + j / 3, cubeCol = 3 * (i % 3) + j % 3;
if (board[cubeRow][cubeCol] != '.' && !cube.add(board[cubeRow][cubeCol]))
return false;
}
}
return true;
}
}
发表于 2017-08-02 11:06:36
回复(5)
更多回答
用三个数组分别记录封装到一个for循环int rowNum[9][9] = {0};//按行分为9行
int colNum[9][9] = {0};//按列分为9列
int blockNum[3][3][9] = {0};//按块分(二维3*3)为9块
block[0][0]为row:0-2 col:0-2此块
block[0][1]为row:0-2 col:3-5此块
...依次类推
bool isValidSudoku(vector<vector<char>>& board) {
int rowNum[9][9] = {0};
int colNum[9][9] = {0};
int blockNum[3][3][9] = {0};
for(int i = 0; i < 9; ++i){
for(int j = 0; j < 9; ++j){
if(board[i][j] != '.'){
//一行行遍历时格子的数,下标从0
int curNum = board[i][j] - '1';
if(rowNum[i][curNum]++) return false;
if(colNum[j][curNum]++) return false;
if(blockNum[i/3][j/3][curNum]++) return false;
}
}
}
return true;
}
编辑于 2019-05-15 10:56:15
回复(0)
import java.util.*;
public class Solution {
public boolean isValidSudoku(char[][] board) {
Set set = new HashSet();
for(int i = 0 ; i < 9; ++i){
for(int j = 0 ; j < 9 ; ++j){
if (board[i][j] != '.') {
String ss = "(" + board[i][j] + ")";
if(!set.add(i + ss) || !set.add(ss + j) || !set.add(i / 3 + ss + j / 3)){
return false;
}
}
}
}
return true;
}
}
发表于 2018-11-06 20:08:01
回复(0)
编程小白写一下解题思路。参考了LeetCode官网上别人的代码，终于理解了这道题怎么解了。
关键点：
- 使用
9×9的row，col，box数组，分别表示行，列，和子box里，数字是否重复出现了。出现记为true。比如，row[0][3]表示第0行是否出现过4（因为数组的索引只能是0-8），col[0][3]表示第0列是都出现过4，box[0][3]表示第0号box是否出现过4。 - 将
9×9的网格划分为9个子box。k = i / 3 * 3 + j / 3，可以将任意一个（i,j）位置映射到索引为0-8的子box里。
比如（5,6）：k = 5 / 3 * 3 + 6 / 3 = 5。这个位置在索引为5的box里。class Solution { public: bool isValidSudoku(vector<vector<char> > &board) { bool row[9][9] = {false}, col[9][9] = {false}, box[9][9] = {false}; 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; if(row[i][num] || col[j][num] || box[k][num]) return false; row[i][num] = col[j][num] = box[k][num] = true; } } } return true; } };
发表于 2018-03-07 10:32:21
回复(0)
class Solution {
public:
bool isValidSudoku(vector<vector<char> > &board) {
//记录已经出现的数，如3出现，则row[3]=1
int row[10] = {0};//之所以是10，因为下标最大是9
int col[9][10] = {0};
int square[9][10] = {0};
//行遍历，两层循环即可，只要找到重复的数即返回false
for(int i=0; i<9; i++){
//由于行重复使用了，所以每次都要清空
memset(row, 0, sizeof(row));
for(int j=0; j<9; j++){
if(board[i][j] != '.'){
if(!check(row, board[i][j] - '0') ||
!check(col[j], board[i][j] - '0') ||
//九宫格的序号：i/3*3 + j/3
!check(square[i/3*3 + j/3], board[i][j] - '0')
)
return false;
}
}
}
return true;
}
bool check(int a[], int v){
//如果每行或每列或每个九宫格出现了重复的数，那么返回false
if(a[v] == 1) return false;
a[v] = 1;
return true;
}
};
编辑于 2016-08-16 17:30:04
回复(0)
class Solution {
public:
bool isValidSudoku(vector<vector<char> > &board) {
int rows[9][9]={0},cols[9][9]={0},cube[9][9]={0};
for(int i=0;i<9;i++)
{
for(int j=0;j<9;j++)
{
int num = board[i][j];
if(num != '.')
{
if(rows[i][num-'1'] == 1) //判断当前行
return false;
else
rows[i][num-'1']++;
if(cols[j][num-'1'] == 1) //判断当前列
return false;
else
cols[j][num-'1']++;
if(cube[3*(i/3)+j/3][num-'1'] == 1) //判断当前块
return false;
else
cube[3*(i/3)+j/3][num-'1']++;
}
}
}
return true;
}
};
发表于 2017-08-08 02:47:07
回复(0)
/*行列还有小方格分别做判断即可
小方格用了个技巧i表示小方格的序号，j表示小方格里面每个方格的序号
遍历时每个方格的坐标为board[i%3*3+j%3][((int)i/3)*3+j/3]
*/
class Solution {
public:
bool isValidSudoku(vector<vector<char> > &board) {
for(int i=0;i<9;i++){
int flag[10]={0};
for(int j=0;j<9;j++){
if(board[i][j]!='.'){
if(!flag[board[i][j]-'0'])
flag[board[i][j]-'0']++;
else{
return false;
}
}
}
}
for(int i=0;i<9;i++){
int flag[10]={0};
for(int j=0;j<9;j++){
if(board[j][i]!='.'){
if( !flag[ board[j][i]-'0' ] )
flag[board[j][i]-'0']++;
else{
return false;
}
}
}
}
for(int i=0 ;i <9;i++){
int flag[10]={0};
for(int j=0;j<9;j++){
int left=(i%3)*3+j%3;
int top=((int)i/3)*3+j/3;
if(board[left][top]!='.'){
if(! flag[ board[left][top]-'0' ]){
flag[ board[left][top]-'0' ]++;
}
else{
return false;
}
}
}
}
return true;
}
};
发表于 2017-07-04 23:11:08
回复(0)
//使用一个bool[9]数组记录使用次数。
class Solution {
public:
bool isValidSudoku(vector<vector<char> > &board) {
bool used[9];
for (int i = 0; i < 9; i++) {
//先按行检查
memset(used, 0, 9);
for (int j = 0; j < 9; j++)
if (!check(board[i][j], used))
return false;
//按列检查
memset(used, 0, 9);
for (int j = 0; j < 9; j++)
if (!check(board[j][i], used))
return false;
}
//从上到下，检查9方格
for (int x = 0; x < 3; x++)
for (int y = 0; y < 3; y++) {
//按行，从左到右检查3个9方格；
memset(used, 0, 9);
for (int i = x*3; i < x*3 + 3; i++)
for (int j = y*3; j < y*3 + 3; j++)
if (!check(board[i][j], used))
return false;
}
return true;
}
//private:
//检查ch是否被使用，没用过返回true
bool check(char ch, bool used[]) {
if (ch == '.') return true;
if (used[ch-'1'])
return false;
used[ch-'1'] = true;
return true;
}
};
发表于 2016-08-31 19:22:59
回复(0)
public boolean isValidSudoku(char[][] board) { for(int i = 0; i<9; i++){ HashSet<Character> rows = new HashSet<Character>(); HashSet<Character> columns = new HashSet<Character>(); HashSet<Character> cube = new HashSet<Character>(); for (int j = 0; j < 9;j++){ if(board[i][j]!='.' && !rows.add(board[i][j])) return false; if(board[j][i]!='.' && !columns.add(board[j][i])) return false; int RowIndex = 3*(i/3); int ColIndex = 3*(i%3); if(board[RowIndex + j/3][ColIndex + j%3]!='.' && !cube.add(board[RowIndex + j/3][ColIndex + j%3])) return false; } } return true; }
发表于 2017-03-12 14:59:07
回复(0)
不要无脑上哈希表
class Solution {
public boolean isValidSudoku(char[][] board) {
boolean[][] rowVisited = new boolean[9][9];
boolean[][] colVisited = new boolean[9][9];
boolean[][] blockVisited = new boolean[9][9];
for(int i = 0; i < 9; i++){
for(int j = 0; j < 9; j++){
char c = board[i][j];
if(c == '.'){
continue;
}
int num = c - '0' - 1;
if(rowVisited[i][num] || colVisited[j][num] || blockVisited[i / 3 * 3 + j / 3][num]){
return false;
}
rowVisited[i][num] = true;
colVisited[j][num] = true;
blockVisited[i / 3 * 3 + j / 3][num] = true;
}
}
return true;
}
}
发表于 2019-04-30 14:57:27
回复(0)
class Solution {
public:
bool isValidSudoku(vector<vector<char> > &board) {
for(int i=0;i<board.size();i++)
{
unordered_map<char,bool> row;
unordered_map<char,bool> col;
unordered_map<char,bool> nine;
for(int j=0;j<board[0].size();j++)
{
if(board[i][j]!='.')//检查每一行
{
if(row[board[i][j]]==true)
return false;
else
row[board[i][j]]=true;
}
if(board[j][i]!='.')//检查每一列
{
if(col[board[j][i]]==true)
return false;
else
col[board[j][i]]=true;
}
if(board[i/3*3+j/3][i%3*3+j%3]!='.')//第i个九宫格第j个格子
{
if((nine[board[i/3*3+j/3][i%3*3+j%3]]==true))
return false;
else
nine[board[i/3*3+j/3][i%3*3+j%3]]=true;
}
}
}
return true;
}
};
发表于 2017-10-19 13:18:31
回复(0)
class Solution {
public:
bool check(int i, int j, vector<vector<char>>&b){
bool flag=true;
for(int p=0;p<b.size();p++){
if((p!=j&&b[i][p]==b[i][j])||(p!=i&&b[p][j]==b[i][j]))
flag=false;
}
for(int p=(i/3)*3;p<(i/3)*3+3;p++){
for(int q=(j/3)*3;q<(j/3)*3+3;q++){
if((p!=i||q!=j)&&b[i][j]==b[p][q])
flag=false;
}
}
return flag;
}
bool isValidSudoku(vector<vector<char> > &board) {
bool res=true;
for(int i=0;i<board.size();i++){
for(int j=0;j<board.size();j++){
char num = board[i][j];
if(num>='0'&&num<='9')
if(!check(i, j, board))
res=false;
}
}
return res;
}
}; 暴力解法
发表于 2020-09-08 09:42:10
回复(0)
class Solution {
public:
bool row[9][9];// row[i][j]=true 第i行已经包含了数字j+1
bool col[9][9];// col[i][j]=true 第i列已经包含了数字j+1
bool sub[9][9];
bool isValidSudoku(vector<vector<char> > &board) {
for(int i=0;i<9;i++){
for(int j=0;j<9;j++){
row[i][j]=col[i][j]=sub[i][j]=false;
}
}
for(int i=0;i<9;i++){
for(int j=0;j<9;j++){
if(board[i][j]!='.'){
int t = board[i][j]-'0';
if(row[i][t-1] || col[j][t-1] || sub[i/3*3+j/3][t-1])
return false;
row[i][t-1] = col[j][t-1] = sub[i/3*3+j/3][t-1] = true;
}
}
}
return true;
}
};
发表于 2020-04-29 21:54:48
回复(0)
public class ValidSudoku_Problem36 {
public boolean isValidSudoku(char[][] board) {
boolean element[] = new boolean[9];
for (int i = 0; i < 9; i++) {
Arrays.fill(element, false);
//判断行
for (int j = 0; j < 9; j++) {
if (checkElement(board[i][j], element)) return false;
}
Arrays.fill(element, false);
//判断列
for (int j = 0; j < 9; j++) {
if (checkElement(board[j][i], element)) return false;
}
}
//判断9个格子
for (int i = 0; i < 9; i += 3) {
for (int j = 0; j < 9; j += 3) {
Arrays.fill(element, false);
for (int k = i; k < 3 + i; k++) {
for (int l = j; l < 3 + j; l++) {
if (checkElement(board[k][l], element)) return false;
}
}
}
}
return true;
}
private boolean checkElement(char c, boolean[] element) {
if (c == '.') return false;
if (element[c - '1'] == true) return true;
element[c - '1'] = true;
return false;
}
}
编辑于 2020-01-29 10:20:12
回复(0)
class Solution { public: bool isValidSudoku(vector<vector<char> > &board) { if (board.size() == 0 || board.size() != 9 || board[0].size() != 9) { return false; } return isValid(board, 0); } bool isValid(vector<vector<char> > &board, int k) { if (k == 81) { return true; } int m = k / 9; int n = k % 9; if (board[m][n] == '.') { return isValid(board, k + 1); } int mStart = (m / 3) * 3; int nStart = (n / 3) * 3; for (int i = mStart;i < mStart + 3;i++) { for (int j = nStart;j < nStart + 3;j++) { if (i != m && j != n && board[i][j] == board[m][n]) { return false; } } } for (int i = 0;i < 9;i++) { if (i != m && board[i][n] == board[m][n]) { return false; } if (i != n && board[m][i] == board[m][n]) { return false; } } return isValid(board, k + 1); } };
编辑于 2020-01-11 15:58:36
回复(0)
//代码太长了，冏囧囧冏( ╯□╰ )
class Solution {
public:
bool isValidSudoku(vector<vector<char> > &board) {
int m = board.size();
int n = board[0].size();
int flag[10] ;
for(int r = 0; r <= 9; r++) flag[r] = 0;
for(int i = 0; i <= m-1; i++){
for(int r = 0; r <= 9; r++) flag[r] = 0;
for(int j = 0; j <= n-1; j++)
if(board[i][j] >= '0' && board[i][j] <= '9'){
if(flag[board[i][j]-'0'] == 1) return false;
else flag[board[i][j]-'0'] = 1;
}
}
for(int i = 0; i <= n-1; i++){
for(int r = 0; r <= 9; r++) flag[r] = 0;
for(int j = 0; j <= m-1; j++)
if(board[j][i] >= '0' && board[j][i] <= '9'){
if(flag[board[j][i]-'0'] == 1) return false;
else flag[board[j][i]-'0'] = 1;
}
}
for(int p = 0; p <= 6; p = p+3)
for(int q = 0; q <= 6; q = q+3){
for(int r = 0; r <= 9; r++) flag[r] = 0;
for(int i = 0; i <= 2; i++)
for(int j = 0; j <= 2; j++)
if(board[p+i][q+j] >= '0' && board[p+i][q+j] <= '9'){
if(flag[board[p+i][q+j]-'0'] == 1) return false;
else flag[board[p+i][q+j]-'0'] = 1;
}
}
return true;
}
};
发表于 2019-08-04 00:04:40
回复(0)
import java.util.*;
public class Solution {
List<HashSet<Character>> r = null;
List<HashSet<Character>> c = null;
List<HashSet<Character>> g = null;
public boolean isValidSudoku(char[][] b) {
r = new ArrayList<>();
c = new ArrayList<>();
g = new ArrayList<>();
for(int i = 0;i<9;i++){
r.add(new HashSet<Character>());
c.add(new HashSet<Character>());
g.add(new HashSet<Character>());
}
for(int i=0;i<9;i++){
for(int j=0;j<9;j++){
char ch = b[i][j];
if(ch == '.') continue;
if(r.get(i).contains(ch)) return false;
if(c.get(j).contains(ch)) return false;
int gt = grid(i,j);
if(g.get(gt).contains(ch)) return false;
r.get(i).add(ch);
c.get(j).add(ch);
g.get(gt).add(ch);
}
}
return true;
}
private int grid(int r,int c) {
int[][] g ={{0,1,2},
{3,4,5},
{6,7,8}};
int i = aux(r);
int j = aux(c);
return g[i][j];
}
private int aux(int s){
if(s>=0&&s<=2)
return 0;
else if(s>=3&&s<=5)
return 1;
else
return 2;
}
}
发表于 2018-09-06 17:05:02
回复(0)
class Solution {
public:
bool isValidSudoku(vector<vector<char> > &board) {
if(board.size() <= 0)
return false;
return solve(board, 0);
}
bool solve(vector<vector<char> > &board, int num) {
if(num >= 81)
return true;
int m = num / 9;
int n = num % 9;
if(board[m][n] != '.') {
if(isValid(board, m, n, board[m][n])) {
if(solve(board, num + 1))
return true;
}
}
else{
if(solve(board, num + 1))
return true;
}
return false;
}
bool isValid(vector<vector<char> > &board, int m, int n, char c) {
int tempm = m / 3;
int tempn = n / 3;
int beginm = tempm * 3;
int beginn = tempn * 3;
for(int i = 0; i < 3; ++i) {
for(int j = 0; j < 3; ++j) {
if(beginm + i == m && beginn + j == n)
continue;
if(board[beginm + i][beginn + j] == c)
return false;
}
}
for(int i = 0; i < 9; ++i) {
if(board[m][i] == c && i != n)
return false;
if(board[i][n] == c && i != m)
return false;
}
return true;
}
};
发表于 2018-09-06 14:07:54
回复(0)
class Solution {
public:
bool isValidSudoku(vector<vector<char> > &board) {
int n = board.size(), m = board[0].size();
for(int i=0;i<n;i++){
int sum=0;
for(int j=0;j<m;j++){
if(board[i][j]=='.') continue;
if(sum & (1<<board[i][j])) return false;
sum |= (1<<board[i][j]);
}
}
for(int j=0;j<m;j++){
int sum=0;
for(int i=0;i<n;i++){
if(board[i][j]=='.') continue;
if(sum & (1<<board[i][j])) return false;
sum |= (1<<board[i][j]);
}
}
for(int i0=0;i0<3;i0++){
for(int j0=0;j0<3;j0++){
int sum=0;
for(int i=3*i0;i<3*i0+3;i++){
for(int j=3*j0;j<3*j0+3;j++){
if(board[i][j]=='.')continue;
if(sum&(1<<board[i][j])) return false;
sum |= (1<<board[i][j]);
}
}
}
}
return true;
}
};
发表于 2018-07-27 21:47:06
回复(0)
//一开始我以为是要判断未完成的数独有没有解……
class Solution {
public:
bool isValidSudoku(vector<vector<char> > &board) {
for (int i = 0; i < 9; i++)
{
set<int> rows;
set<int> cols;
set<int> cubes;
for (int j = 0; j < 9; j++)
{
if (board[i][j] != '.'&& rows.find(board[i][j])!=rows.end())
return false;
rows.insert(board[i][j]);
if (board[j][i] != '.'&& cols.find(board[j][i])!=cols.end())
return false;
cols.insert(board[j][i]);
int cc=3*(i/3)+j/3;
int cr =3*(i%3)+j%3;
if (board[cr][cc] != '.' && cubes.find(board[cr][cc])!=cubes.end())
return false;
cubes.insert(board[cr][cc]);
}
}
return true;
}
};
发表于 2018-06-21 10:51:01
回复(0)
问题信息
难度：
36条回答
35收藏
17994浏览
通过挑战的用户
查看代码-
2023-01-09 18:04:44
-
2022-08-22 17:26:44
-
2022-08-20 16:47:59
-
2022-05-11 19:52:14
-
2022-04-10 11:04:01
相关试题
-
扫描二维码，关注牛客网
- 意见反馈
-
下载牛客APP，随时随地刷题
扫一扫，把题目装进口袋
- 求职之前，先上牛客
-
扫描二维码，进入QQ群
扫描二维码，关注牛客公众号
- 公司地址：北京市朝阳区北苑路北美国际商务中心K1座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备
11010502036488号
