# LeetCode 37. Sudoku Solver

## Description

https://leetcode.com/problems/sort-colors/

Write a program to solve a Sudoku puzzle by filling the empty cells.

A sudoku solution must satisfy all of the following rules:

1. Each of the digits `1-9` must occur exactly once in each row.
2. Each of the digits `1-9` must occur exactly once in each column.
3. Each of the the digits `1-9` must occur exactly once in each of the 9 `3x3` sub-boxes of the grid.

Empty cells are indicated by the character `'.'`.

A sudoku puzzle…

…and its solution numbers marked in red.

Note:

• The given board contain only digits `1-9` and the character `'.'`.
• You may assume that the given Sudoku puzzle will have a single unique solution.
• The given board size is always `9x9`.

backtracking

## Python Solution

``````class Solution:
def solveSudoku(self, board: List[List[str]]) -> None:
"""
Do not return anything, modify board in-place instead.
"""

board_assignment = self.get_board_assignment(board)
self.backtracking_helper(board, 0, board_assignment)

def backtracking_helper(self, board2d, index, board_assignment):
if index == 81:
return True

row_index = index // 9
column_index = index % 9

if board2d[row_index][column_index] != '.':
return self.backtracking_helper(board2d, index + 1, board_assignment)

unassigned_variables = [i for i in range(1, 10)]
for value in unassigned_variables:
value = str(value)
if not self.is_valid_assignment(row_index, column_index, value, board_assignment):
continue

if self.backtracking_helper(board2d, index + 1, board_assignment):
return True

self.remove_value_from_assignment(board2d, board_assignment, column_index, value, row_index)

return False

def remove_value_from_assignment(self, board2d, board_assignment, column_index, value, row_index):
board2d[row_index][column_index] = '.'

del board_assignment['columns'][column_index][value]
del board_assignment['rows'][row_index][value]
del board_assignment['boxes'][row_index // 3 * 3 + column_index // 3][value]

def add_value_to_assignment(self, board2d, board_assignment, column_index, value, row_index):
board2d[row_index][column_index] = value

board_assignment['rows'][row_index][value] = True
board_assignment['columns'][column_index][value] = True
board_assignment['boxes'][row_index // 3 * 3 + column_index // 3][value] = True

def is_valid_assignment(self, row_index, column_index, digit, board_assignment):
if digit in board_assignment['rows'][row_index]:
return False

if digit in board_assignment['columns'][column_index]:
return False

if digit in board_assignment['boxes'][row_index // 3 * 3 + column_index // 3]:
return False

return True

def get_board_assignment(self, board2d):
rows = [{} for i in range(0, 9)]
columns = [{} for j in range(0, 9)]
boxes = [{} for k in range(0, 9)]

for i in range(0, len(board2d)):
for j in range(0, len(board2d[0])):
value = board2d[i][j]
box_index = (i // 3) * 3 + j // 3

if value != '.':
rows[i][value] = True
columns[j][value] = True
boxes[box_index][value] = True

board_assignment = {'rows': rows, 'columns': columns, 'boxes': boxes}

return board_assignment``````
• Time complexity: O((9!)^9).
• Space complexity: the board size is fixed, and the space is used to store board, rows, columns and boxes structures, each contains 81 elements