Skip to content

Instantly share code, notes, and snippets.

@wreczek

wreczek/sudoku_solver.py

Created July 21, 2020 16:27
Show Gist options
  • Save wreczek/d51535c54d0ed895fd31fcff983ddc93 to your computer and use it in GitHub Desktop.
Save wreczek/d51535c54d0ed895fd31fcff983ddc93 to your computer and use it in GitHub Desktop.
Download ZIP
Raw
sudoku_solver.py
BOARD = [
[7,8,0,4,0,0,1,2,0],
[6,0,0,0,7,5,0,0,9],
[0,0,0,6,0,1,0,7,8],
[0,0,7,0,4,0,2,6,0],
[0,0,1,0,5,0,9,3,0],
[9,0,4,0,6,0,0,0,5],
[0,7,0,3,0,0,0,1,2],
[1,2,0,0,0,7,4,0,0],
[0,4,9,2,0,6,0,0,7]
]
def display_board(board):
"""Displays board in the human-readable format."""
for i, row in enumerate(board):
for j, elem in enumerate(row):
spacing = 2 * ' ' if j % 3 == 2 else ' '
print(elem, end=spacing)
spacing = '\n' if i % 3 == 2 else ''
print(spacing)
def get_list_from_square(board, row_index, column_index):
"""Returns list that contains all numbers in given square on sudoku board
Args:
board (list): sudoku board
row_index (int): what is the row of the number we test
column_index (int): what is the column of the number we test
Returns:
list: list of numbers in the proper square on sudoku board
"""
vertical_square_index = row_index // 3
horizontal_square_index = column_index // 3
square_list = []
for i in range(3*vertical_square_index, 3*vertical_square_index+3):
for j in range(3*horizontal_square_index, 3*horizontal_square_index+3):
square_list.append(board[i][j])
return square_list
def get_column_from_board(board, column_index):
"""Returns list that is board's column.
Args:
board (list): sudoku list
column_index (int): index of the column in sudoku board
Returns:
list: column in sudoku board
"""
column = []
for row in board:
column.append(row[column_index])
return column
def is_field_valid(board, row_index, column_index):
"""Tests whether inserted number is valid.
Args:
board (list): sudoku board
row_index (int): what is the row of the number we test
column_index (int): what is the column of the number we test
Returns:
bool: whether inserted number is valid, or not
"""
# We check that the number in field is unique in whole row
field = board[row_index][column_index]
row = board[row_index]
if row.count(field) != 1:
return False
# We check that the number in field is unique in whole column
column = get_column_from_board(board, column_index)
if column.count(field) != 1:
return False
# We check that the number in field is unique in whole 3x3
square_list = get_list_from_square(board, row_index, column_index)
if square_list.count(field) != 1:
return False
# Every test passed positively
return True
def is_board_valid(board):
"""Tests whether board solution is valid
Args:
board (list): sudoku board
Returns:
bool: whether the solution is correct, or not
"""
for i in range(81):
row_index = i // 9
column_index = i % 9
if not is_field_valid(board, row_index, column_index):
return False
if board[row_index][column_index] not in range(1, 10):
return False
return True
def find_empty_field(board):
for row_index, row in enumerate(board):
if 0 in row:
column_index = row.index(0)
return row_index, column_index
def solve_sudoku(board):
"""Main solver function."""
if is_board_valid(board):
display_board(board=board)
exit(0)
# 1. We search for the empty field
row_index, column_index = find_empty_field(board)
# 2. We try to insert different numbers
for j in range(1, 10):
board[row_index][column_index] = j
if is_field_valid(board, row_index, column_index):
solve_sudoku(board=board)
board[row_index][column_index] = 0
# TESTS
def test_getting_list_from_square():
assert [7,8,0,6,0,0,0,0,0] == get_list_from_square(BOARD, 0, 0)
assert [4,0,0,0,7,5,6,0,1] == get_list_from_square(BOARD, 2, 4)
assert [0,4,0,0,5,0,0,6,0] == get_list_from_square(BOARD, 5, 3)
assert [0,1,2,4,0,0,0,0,7] == get_list_from_square(BOARD, 7, 8)
assert [3,0,0,0,0,7,2,0,6] == get_list_from_square(BOARD, 7, 4)
assert [2,6,0,9,3,0,0,0,5] == get_list_from_square(BOARD, 5, 8)
assert [2,6,0,9,3,0,0,0,5] == get_list_from_square(BOARD, 3, 7)
def test_getting_column_from_board():
assert [7,6,0,0,0,9,0,1,0] == get_column_from_board(BOARD, 0)
assert [4,0,6,0,0,0,3,0,2] == get_column_from_board(BOARD, 3)
assert [0,5,1,0,0,0,0,7,6] == get_column_from_board(BOARD, 5)
assert [2,0,7,6,3,0,1,0,0] == get_column_from_board(BOARD, 7)
if __name__ == '__main__':
test_getting_list_from_square()
test_getting_column_from_board()
solve_sudoku(BOARD)
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment