Sudoku Solver

A sudoku grid is 4 by 4 (split into 2 by 2 boxes) or 9 by 9 (split into 3 by 3 boxes). A finished grid holds every digit from 1 up to the grid size exactly once in every row, every column and every box.

Write solve_sudoku(rows) that takes a puzzle as a list of strings, one per row, with . for an empty cell, and returns the finished grid in the same form. If the puzzle cannot be finished, including when the digits already given break the rules, return an empty list.

Examples

puzzle = ["....",
          "1.3.",
          "2..3",
          ".1.."]
solve_sudoku(puzzle)                            # returns ['4321', '1234', '2413', '3142']
solve_sudoku(["12..", "..3.", "....", "..4."])  # returns []

The second puzzle has no answer: the third cell of the top row cannot be 1 or 2 (they are already in its row) or 3 or 4 (they are already in its column).

Constraints

• The grid is 4 by 4 or 9 by 9.
• Every puzzle in the tests has at most one solution.
• The hardest 9 by 9 tests have 24 given digits.