详细见：leetcode.com/problems/valid-sudoku
Java Solution: github
package leetcode; import java.util.Arrays; /* * A valid Sudoku board (partially filled) is not necessarily solvable. * Only the filled cells need to be validated. * 只需要判断已经存在的数字是否合法就行，不需要管数独是否有解 */ public class P036_ValidSudoku { public static void main(String[] args) { System.out.println(new Solution2().isValidSudoku(new char[][] { ".87654321".toCharArray(), "2........".toCharArray(), "3........".toCharArray(), "4........".toCharArray(), "5........".toCharArray(), "6........".toCharArray(), "7........".toCharArray(), "8........".toCharArray(), "9........".toCharArray() })); } /* * 8 ms * 24.64% */ static class Solution { public boolean isValidSudoku(char[][] board) { boolean[] isExistRow = new boolean[9]; boolean[][] isExistColumn = new boolean[9][9]; boolean[][] isExistNine = new boolean[9][9]; for (int i = 0; i < 9; i ++) { Arrays.fill(isExistRow, false); for (int j = 0; j < 9; j ++) { if (board[i][j] == '.') continue; if (! isValid(isExistRow, board[i][j] - '1') || ! isValid(isExistColumn[j], board[i][j] - '1') || ! isValid(isExistNine[i/3*3+j/3], board[i][j] - '1')) return false; } } return true; } private boolean isValid(boolean[] isExist, int index) { if(isExist[index]) return false; isExist[index] = true; return true; } } /* * 6 ms * 41.76% */ static class Solution2 { public boolean isValidSudoku(char[][] board) { boolean[] isExistRow = new boolean[9]; boolean[] isExistColumn = new boolean[9]; boolean[] isExistNine = new boolean[9]; for (int i = 0; i < 9; i ++) { Arrays.fill(isExistRow, false); Arrays.fill(isExistColumn, false); Arrays.fill(isExistNine, false); for (int j = 0; j < 9; j ++) { if (! isValid(isExistRow, board[i][j] - '1') || ! isValid(isExistColumn, board[j][i] - '1') || ! isValid(isExistNine, board[i/3*3+j/3][i%3*3+j%3] - '1')) return false; } } return true; } private boolean isValid(boolean[] isExist, int index) { if (index < 0) return true; if(isExist[index]) return false; isExist[index] = true; return true; } } static class Solution3 { public boolean isValidSudoku(char[][] board) { return false; } } }C Solution: github
/* url: leetcode.com/problems/valid-sudoku/ 9ms 41.33% */ #include <stdio.h> #include <stdlib.h> #include <string.h> #define bool int bool isValidSudoku(char** b, int rs, int cs) { int row = 0, col = 0, sign = 1, si = 0; int ri = 0, ci = 0; char s[9]; for (row = 0; row < rs; row ++) { memset(s, 0, 9); for (col = 0; col < cs; col ++) { if (b[row][col] != '.') { si = b[row][col] - '1'; if (si < 0 || si > 9) return 0; s[si] ++; if (s[si] > 1) return 0; } } memset(s, 0, 9); for (col = 0; col < cs; col ++) { if (b[col][row] != '.') { si = b[col][row] - '1'; if (si < 0 || si > 9) return 0; s[si] ++; if (s[si] > 1) return 0; } } } for (row = 1; row < 9; row += 3) { for (col = 1; col < 9; col += 3) { memset(s, 0, 9); for (ri = -1; ri < 2; ri ++) { for (ci = -1; ci < 2; ci ++) { if (b[row + ri][col + ci] != '.') { si = b[row + ri][col + ci] - '1'; if (si < 0 || si > 9) return 0; s[si] ++; if (s[si] > 1) return 0; } } } } } return 1; } bool isValid2(char row[], int i) { //'.' if (i < 0 || i > 8) return 1; //invalid if (row[i] == 1) return 0; //valid row[i] = 1; return 1; } bool isValidSudoku2(char** b, int rs, int cs) { int i =0, j = 0; char row[9], col[9], nin[9]; for (i = 0; i < 9; i ++) { memset(row, 0, 9); memset(col, 0, 9); memset(nin, 0, 9); for (j = 0; j < 9; j ++) { if (isValid2(row, b[i][j] - '1') == 0) return 0; if (isValid2(col, b[j][i] - '1') == 0) return 0; if (isValid2(nin, b[i/3*3+j/3][i%3*3+j%3] - '1') == 0) return 0; } } return 1; } int main() { char ** b = (char **) malloc(sizeof(char *) * 9); int rs = 9, cs = 9; b[0] = ".87654321"; b[1] = "2........"; b[2] = "3........"; b[3] = "4........"; b[4] = "5........"; b[5] = "6........"; b[6] = "7........"; b[7] = "8........"; b[8] = "9........"; printf("answer is %d\r\n", isValidSudoku(b, rs, cs)); free(b); return 0; }
Python Solution: github
#coding=utf-8 ''' url: leetcode.com/problems/valid-sudoku/ @author: zxwtry @email: zxwtry@qq.com @date: 2017年4月4日 @details: Solution: 112ms 26.68% ''' class Solution(object): def isValidSudoku(self, b): """ :type b: List[List[str]] :rtype: bool """ for k in range(9): m = [False] * 9 for i in range(9): if b[k][i] == '.': continue v = int(b[k][i]) - 1 if m[v]: return False m[v] = True m = [False] * 9 for i in range(9): if b[i][k] == '.': continue v = int(b[i][k]) - 1 if m[v]: return False m[v] = True m = [False] * 9 x_base, y_base = (k // 3) * 3, (k % 3) * 3 for i in range(9): x = x_base + (i // 3) y = y_base + (i % 3) if b[x][y] == '.':continue v = int(b[x][y]) - 1 if m[v]: return False m[v] = True return True