Valid Sudoku

Question

  1. Determine whether a Sudoku is valid.
  3. The Sudoku board could be partially filled,
  4. where empty cells are filled with the character ..
  6. Example
  7. The following partially filed sudoku is valid.

valid-sudoku.png

  1. Valid Sudoku
  3. Note
  4. A valid Sudoku board (partially filled) is not necessarily solvable.
  5. Only the filled cells need to be validated.
  6. Clarification
  7. What is Sudoku?
  9. http://sudoku.com.au/TheRules.aspx
  10. https://zh.wikipedia.org/wiki/%E6%95%B8%E7%8D%A8
  11. https://en.wikipedia.org/wiki/Sudoku
  12. http://baike.baidu.com/subview/961/10842669.htm

题解

看懂数独的含义就好了，分为三点考虑，一是每行无重复数字；二是每列无重复数字；三是小的九宫格中无重复数字。

Java

  1. class Solution {
  2.     /**
  3.       * @param board: the board
  4.         @return: wether the Sudoku is valid
  5.       */
  6.     public boolean isValidSudoku(char[][] board) {
  7.         if (board == null || board.length == 0) return false;
  9.         // check row
  10.         for (int i = 0; i < 9; i++) {
  11.             boolean[] numUsed = new boolean[9];
  12.             for (int j = 0; j < 9; j++) {
  13.                 if (isDuplicate(board[i][j], numUsed)) {
  14.                     return false;
  15.                 }
  16.             }
  17.         }
  19.         // check column
  20.         for (int i = 0; i < 9; i++) {
  21.             boolean[] numUsed = new boolean[9];
  22.             for (int j = 0; j < 9; j++) {
  23.                 if (isDuplicate(board[j][i], numUsed)) {
  24.                     return false;
  25.                 }
  26.             }
  27.         }
  29.         // check sub box
  30.         for (int i = 0; i < 9; i = i + 3) {
  31.             for (int j = 0; j < 9; j = j + 3) {
  32.                 if (!isValidBox(board, i, j)) {
  33.                     return false;
  34.                 }
  35.             }
  36.         }
  38.         return true;
  39.     }
  41.     private boolean isValidBox(char[][] box, int x, int y) {
  42.         boolean[] numUsed = new boolean[9];
  43.         for (int i = x; i < x + 3; i++) {
  44.             for (int j = y; j < y + 3; j++) {
  45.                 if (isDuplicate(box[i][j], numUsed)) {
  46.                     return false;
  47.                 }
  48.             }
  49.         }
  50.         return true;
  51.     }
  53.     private boolean isDuplicate(char c, boolean[] numUsed) {
  54.         if (c == '.') {
  55.             return false;
  56.         } else if (numUsed[c - '1']) {
  57.             return true;
  58.         } else {
  59.             numUsed[c - '1'] = true;
  60.             return false;
  61.         }
  62.     }
  63. }

源码分析

首先实现两个小的子功能模块判断是否有重复和小的九宫格是否重复。

复杂度分析

略

Reference

  • Soulmachine 的 leetcode 题解