根据数独的规则Sudoku Puzzles - The Rules.判断给出的局面是不是一个符合规则的数独局面
数独盘面可以被部分填写,空的位置用字符'.'.表示
这是一个部分填写的符合规则的数独局面
用三个数组分别记录封装到一个for循环int rowNum[9][9] = {0};//按行分为9行
int colNum[9][9] = {0};//按列分为9列
int blockNum[3][3][9] = {0};//按块分(二维3*3)为9块
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; }
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; } }
编程小白写一下解题思路。参考了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;
}
};
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; } };
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; } };
/*行列还有小方格分别做判断即可 小方格用了个技巧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; } };
//使用一个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; } };
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; }
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; } }
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; } }
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; } };
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; } };暴力解法
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; } };
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; } }
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); } };
//代码太长了,冏囧囧冏( ╯□╰ ) 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; } };
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; } }
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;
}
};
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; } };
//一开始我以为是要判断未完成的数独有没有解……
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;
}
};