:orphan:

Valid Sudoku
============

.. highlight:: none

Problem
-------
https://leetcode.com/problems/valid-sudoku/

Determine if a ``9 x 9`` Sudoku board is valid. Only the filled cells
need to be validated **according to the following rules**:

#. Each row must contain the digits ``1-9`` without repetition.
#. Each column must contain the digits ``1-9`` without repetition.
#. Each of the nine ``3 x 3`` sub-boxes of the grid must contain the
   digits ``1-9`` without repetition.

**Note:**

- A Sudoku board (partially filled) could be valid but is not
  necessarily solvable.
- Only the filled cells need to be validated according to the
  mentioned rules.

 

**Example 1:**

|image1|

::


   Input: board =
   [["5","3",".",".","7",".",".",".","."]
   ,["6",".",".","1","9","5",".",".","."]
   ,[".","9","8",".",".",".",".","6","."]
   ,["8",".",".",".","6",".",".",".","3"]
   ,["4",".",".","8",".","3",".",".","1"]
   ,["7",".",".",".","2",".",".",".","6"]
   ,[".","6",".",".",".",".","2","8","."]
   ,[".",".",".","4","1","9",".",".","5"]
   ,[".",".",".",".","8",".",".","7","9"]]
   Output: true

**Example 2:**

::


   Input: board =
   [["8","3",".",".","7",".",".",".","."]
   ,["6",".",".","1","9","5",".",".","."]
   ,[".","9","8",".",".",".",".","6","."]
   ,["8",".",".",".","6",".",".",".","3"]
   ,["4",".",".","8",".","3",".",".","1"]
   ,["7",".",".",".","2",".",".",".","6"]
   ,[".","6",".",".",".",".","2","8","."]
   ,[".",".",".","4","1","9",".",".","5"]
   ,[".",".",".",".","8",".",".","7","9"]]
   Output: false
   Explanation: Same as Example 1, except with the 5 in the top left corner being modified to 8. Since there are two 8's in the top left 3x3 sub-box, it is invalid.

 

**Constraints:**

- ``board.length == 9``
- ``board[i].length == 9``
- ``board[i][j]`` is a digit ``1-9`` or ``'.'``.

.. |image1| image:: https://upload.wikimedia.org/wikipedia/commons/thumb/f/ff/Sudoku-by-L2G-20050714.svg/250px-Sudoku-by-L2G-20050714.svg.png

.. highlight:: python

Pattern
-------
Array, Hash Table, Matrix

Solution
--------
Check that each row, column, and 3x3 square contains no duplicates and contains
the digits 1-9. Return ``False`` if these conditions don't hold.

Code
----

.. literalinclude:: ../problems/medium/valid-sudoku/valid_sudoku__approach_1.py
    :language: python
    :lines: 31-

Test
----
>>> from valid_sudoku__approach_1 import isValidSudoku
>>> board = [
...     ['5', '3', '.', '.', '7', '.', '.', '.', '.'],
...     ['6', '.', '.', '1', '9', '5', '.', '.', '.'],
...     ['.', '9', '8', '.', '.', '.', '.', '6', '.'],
...     ['8', '.', '.', '.', '6', '.', '.', '.', '3'],
...     ['4', '.', '.', '8', '.', '3', '.', '.', '1'],
...     ['7', '.', '.', '.', '2', '.', '.', '.', '6'],
...     ['.', '6', '.', '.', '.', '.', '2', '8', '.'],
...     ['.', '.', '.', '4', '1', '9', '.', '.', '5'],
...     ['.', '.', '.', '.', '8', '.', '.', '7', '9'],
... ]
>>> isValidSudoku(board)
True
>>> board = [
...     ['8', '3', '.', '.', '7', '.', '.', '.', '.'],
...     ['6', '.', '.', '1', '9', '5', '.', '.', '.'],
...     ['.', '9', '8', '.', '.', '.', '.', '6', '.'],
...     ['8', '.', '.', '.', '6', '.', '.', '.', '3'],
...     ['4', '.', '.', '8', '.', '3', '.', '.', '1'],
...     ['7', '.', '.', '.', '2', '.', '.', '.', '6'],
...     ['.', '6', '.', '.', '.', '.', '2', '8', '.'],
...     ['.', '.', '.', '4', '1', '9', '.', '.', '5'],
...     ['.', '.', '.', '.', '8', '.', '.', '7', '9'],
... ]
>>> isValidSudoku(board)
False

Complexity
----------
| :math:`n` is the size of a block (3 for a 9x9 board)
| Time: :math:`O(n^4)` — number of rows, columns, and squares to check is :math:`3n^2` and there are :math:`n^2` cells in each row, column, and square
| Auxiliary Space: :math:`O(n^2)` — numbers in each row, column, and square are stored in a set for checking duplicates and valid digits

.. autofunction:: valid_sudoku__approach_1.isValidSudoku

.. autofunction:: valid_sudoku__approach_1.is_valid