Solucionador de Sudoku recursivo usando Python
Um solucionador de Sudoku que funciona recursivamente. Agradeço seus comentários sobre o estilo de codificação, estrutura e como melhorá-los. Muito obrigado pelo seu tempo.
Estrutura de código
O Solver funciona aceitando uma sequência de 81 dígitos para a entrada do quebra-cabeça Sudoku. Zeros são considerados células vazias. Ele o analisa em uma matriz Numpy 9x9.
A get_candidatesfunção cria listas de dígitos possíveis para preencher cada célula seguindo as regras do Sudoku (sem repetição de 1-9 dígitos ao longo de linhas, colunas e subgrades 3x3).
A principal função do solucionador é solve. Primeiro, ele descarta candidatos errados com a filter-candidatesfunção. "Candidatos errados" são aqueles que, quando preenchidos com uma célula vazia, levam a outra célula não tendo mais candidatos em outro lugar na grade do Sudoku.
Após filtrar os candidatos, fill_singlesé chamado para preencher as células vazias que possuem apenas um candidato remanescente. Se esse processo levar a uma grade de Sudoku completamente preenchida, ela será retornada como uma solução. Há uma cláusula de retorno Noneque é usada para retroceder as alterações feitas pela make_guessfunção. Esta função preencherá a próxima célula vazia com a menor quantidade de candidatos com um de seus candidatos, um valor de "estimativa". Em seguida, ele chama recursivamente solvepara encontrar uma solução ou alcançar uma grade sem solução (nesse caso, solveretorna Nonee as últimas alterações de suposição são revertidas).
from copy import deepcopy
import numpy as np
def create_grid(puzzle_str: str) -> np.ndarray:
"""Create a 9x9 Sudoku grid from a string of digits"""
# Deleting whitespaces and newlines (\n)
lines = puzzle_str.replace(' ','').replace('\n','')
digits = list(map(int, lines))
# Turning it to a 9x9 numpy array
grid = np.array(digits).reshape(9,9)
return grid
def get_subgrids(grid: np.ndarray) -> np.ndarray:
"""Divide the input grid into 9 3x3 sub-grids"""
subgrids = []
for box_i in range(3):
for box_j in range(3):
subgrid = []
for i in range(3):
for j in range(3):
subgrid.append(grid[3*box_i + i][3*box_j + j])
subgrids.append(subgrid)
return np.array(subgrids)
def get_candidates(grid : np.ndarray) -> list:
"""Get a list of candidates to fill empty cells of the input grid"""
def subgrid_index(i, j):
return (i//3) * 3 + j // 3
subgrids = get_subgrids(grid)
grid_candidates = []
for i in range(9):
row_candidates = []
for j in range(9):
# Row, column and subgrid digits
row = set(grid[i])
col = set(grid[:, j])
sub = set(subgrids[subgrid_index(i, j)])
common = row | col | sub
candidates = set(range(10)) - common
# If the case is filled take its value as the only candidate
if not grid[i][j]:
row_candidates.append(list(candidates))
else:
row_candidates.append([grid[i][j]])
grid_candidates.append(row_candidates)
return grid_candidates
def is_valid_grid(grid : np.ndarray) -> bool:
"""Verify the input grid has a possible solution"""
candidates = get_candidates(grid)
for i in range(9):
for j in range(9):
if len(candidates[i][j]) == 0:
return False
return True
def is_solution(grid : np.ndarray) -> bool:
"""Verify if the input grid is a solution"""
if np.all(np.sum(grid, axis=1) == 45) and \
np.all(np.sum(grid, axis=0) == 45) and \
np.all(np.sum(get_subgrids(grid), axis=1) == 45):
return True
return False
def filter_candidates(grid : np.ndarray) -> list:
"""Filter input grid's list of candidates"""
test_grid = grid.copy()
candidates = get_candidates(grid)
filtered_candidates = deepcopy(candidates)
for i in range(9):
for j in range(9):
# Check for empty cells
if grid[i][j] == 0:
for candidate in candidates[i][j]:
# Use test candidate
test_grid[i][j] = candidate
# Remove candidate if it produces an invalid grid
if not is_valid_grid(fill_singles(test_grid)):
filtered_candidates[i][j].remove(candidate)
# Revert changes
test_grid[i][j] = 0
return filtered_candidates
def merge(candidates_1 : list, candidates_2 : list) -> list:
"""Take shortest candidate list from inputs for each cell"""
candidates_min = []
for i in range(9):
row = []
for j in range(9):
if len(candidates_1[i][j]) < len(candidates_2[i][j]):
row.append(candidates_1[i][j][:])
else:
row.append(candidates_2[i][j][:])
candidates_min.append(row)
return candidates_min
def fill_singles(grid : np.ndarray, candidates=None) -> np.ndarray:
"""Fill input grid's cells with single candidates"""
grid = grid.copy()
if not candidates:
candidates = get_candidates(grid)
any_fill = True
while any_fill:
any_fill = False
for i in range(9):
for j in range(9):
if len(candidates[i][j]) == 1 and grid[i][j] == 0:
grid[i][j] = candidates[i][j][0]
candidates = merge(get_candidates(grid), candidates)
any_fill = True
return grid
def make_guess(grid : np.ndarray, candidates=None) -> np.ndarray:
"""Fill next empty cell with least candidates with first candidate"""
grid = grid.copy()
if not candidates:
candidates = get_candidates(grid)
# Getting the shortest number of candidates > 1:
min_len = sorted(list(set(map(
len, np.array(candidates).reshape(1,81)[0]))))[1]
for i in range(9):
for j in range(9):
if len(candidates[i][j]) == min_len:
for guess in candidates[i][j]:
grid[i][j] = guess
solution = solve(grid)
if solution is not None:
return solution
# Discarding a wrong guess
grid[i][j] = 0
def solve(grid : np.ndarray) -> np.ndarray:
"""Recursively find a solution filtering candidates and guessing values"""
candidates = filter_candidates(grid)
grid = fill_singles(grid, candidates)
if is_solution(grid):
return grid
if not is_valid_grid(grid):
return None
return make_guess(grid, candidates)
# # Example usage
# puzzle = """100920000
# 524010000
# 000000070
# 050008102
# 000000000
# 402700090
# 060000000
# 000030945
# 000071006"""
# grid = create_grid(puzzle)
# solve(grid)
```
Respostas
Consegui melhorar o desempenho do programa em cerca de 900% sem entender ou alterar muito do algoritmo em cerca de uma hora. Aqui está o que eu fiz:
Em primeiro lugar, você precisa de um benchmark. É muito simples, basta cronometrar seu programa
start = time.time()
solve(grid)
print(time.time()-start)
No meu computador, demorou cerca de 4,5 segundos. Esta é a nossa linha de base.
A próxima coisa é traçar um perfil. A ferramenta que escolhi é o VizTracer, desenvolvido por mim :)https://github.com/gaogaotiantian/viztracer
VizTracer irá gerar um relatório HTML (ou json que pode ser carregado por chrome :: // tracing) da linha do tempo de sua execução de código. É assim na sua versão original:
Como você pode ver, há muitas ligações lá. O que precisamos fazer é descobrir qual é o gargalo aqui. A estrutura não é complicada, muitos fill_singlessão chamados e precisamos aumentar o zoom para verificar o que está lá.
É muito claro que get_candidatesé a função que causou a maior parte do tempo no fill_singles, que está ocupando a maior parte da linha do tempo. Essa é a função que queremos dar uma olhada primeiro.
def get_candidates(grid : np.ndarray) -> list:
"""Get a list of candidates to fill empty cells of the input grid"""
def subgrid_index(i, j):
return (i//3) * 3 + j // 3
subgrids = get_subgrids(grid)
grid_candidates = []
for i in range(9):
row_candidates = []
for j in range(9):
# Row, column and subgrid digits
row = set(grid[i])
col = set(grid[:, j])
sub = set(subgrids[subgrid_index(i, j)])
common = row | col | sub
candidates = set(range(10)) - common
# If the case is filled take its value as the only candidate
if not grid[i][j]:
row_candidates.append(list(candidates))
else:
row_candidates.append([grid[i][j]])
grid_candidates.append(row_candidates)
return grid_candidates
A única coisa que chamou minha atenção primeiro foi o fim do seu loop for aninhado. Você verificou se grid[i][j]está preenchido. Se for, então esse é o único candidato. No entanto, se estiver preenchido, não candidatesterá nada a ver com o que você calculou muito fortemente em seu loop for aninhado.
Portanto, a primeira coisa que fiz foi mover a verificação para o início do loop for.
for i in range(9):
row_candidates = []
for j in range(9):
if grid[i][j]:
row_candidates.append([grid[i][j]])
continue
# Row, column and subgrid digits
row = set(grid[i])
col = set(grid[:, j])
sub = set(subgrids[subgrid_index(i, j)])
common = row | col | sub
candidates = set(range(10)) - common
row_candidates.append(list(candidates))
Esta otimização por si só cortou o tempo de execução pela metade, estamos em cerca de 2.3s agora.
Então eu percebi que em seu loop for aninhado, você está fazendo várias operações de conjunto redundantes. Mesmo row / col / sub só precisa ser computado 9 vezes, você está computando 81 vezes, o que é muito ruim. Então, movi o cálculo do loop for.
def get_candidates(grid : np.ndarray) -> list:
"""Get a list of candidates to fill empty cells of the input grid"""
def subgrid_index(i, j):
return (i//3) * 3 + j // 3
subgrids = get_subgrids(grid)
grid_candidates = []
row_sets = [set(grid[i]) for i in range(9)]
col_sets = [set(grid[:, j]) for j in range(9)]
subgrid_sets = [set(subgrids[i]) for i in range(9)]
total_sets = set(range(10))
for i in range(9):
row_candidates = []
for j in range(9):
if grid[i][j]:
row_candidates.append([grid[i][j]])
continue
# Row, column and subgrid digits
row = row_sets[i]
col = col_sets[j]
sub = subgrid_sets[subgrid_index(i, j)]
common = row | col | sub
candidates = total_sets - common
# If the case is filled take its value as the only candidate
row_candidates.append(list(candidates))
grid_candidates.append(row_candidates)
return grid_candidates
Isso reduziu o tempo de execução para cerca de 1,5s. Observe que ainda não tentei entender seu algoritmo. A única coisa que fiz foi usar o VizTracer para encontrar a função que precisa ser otimizada e fazer a transformação da mesma lógica. Eu melhorei o desempenho em cerca de 300% em cerca de 15 minutos.
Até este ponto, a sobrecarga do VizTracer no WSL é significativa, então desativei o rastreio da função C. Restaram apenas as funções do Python e a sobrecarga foi de cerca de 10%.
Agora que o get_candidatesfoi melhorado (embora possa ser feito melhor), precisamos ter uma visão maior disso. O que posso observar no resultado do VizTracer é que fill_singlesligou com get_candidatesmuita frequência, muitas ligações. (Isso é algo que é difícil de notar no cProfiler)
Portanto, a próxima etapa foi descobrir se podemos fazer fill_singleschamadas com get_candidatesmenos frequência. Aqui, requer algum nível de compreensão do algoritmo.
while any_fill:
any_fill = False
for i in range(9):
for j in range(9):
if len(candidates[i][j]) == 1 and grid[i][j] == 0:
grid[i][j] = candidates[i][j][0]
candidates = merge(get_candidates(grid), candidates)
any_fill = True
Parece que aqui você tentou preencher um espaço em branco com apenas um candidato, e recalcular os candidatos de toda a grade, depois encontrar o próximo espaço em branco com um candidato. Este é um método válido, mas causou muitas chamadas para get_candidates. Se você pensar bem, quando preenchermos uma lacuna com um número n, todas as outras lacunas com apenas um candidato que não foi nnão serão afetadas. Assim, durante uma passagem da grade, poderíamos tentar preencher mais espaços em branco, desde que não preenchamos o mesmo número duas vezes. Dessa forma, podemos ligar com get_candidatesmenos frequência, o que é um grande consumidor de tempo. Usei um conjunto para fazer isso.
filled_number = set()
for i in range(9):
for j in range(9):
if len(candidates[i][j]) == 1 and grid[i][j] == 0 and candidates[i][j][0] not in filled_number:
grid[i][j] = candidates[i][j][0]
filled_number.add(candidates[i][j][0])
any_fill = True
candidates = merge(get_candidates(grid), candidates)
Isso trouxe o tempo de execução para 0,9s.
Então eu olhei para o relatório do VizTracer, percebi que fill_singlesquase sempre é chamado filter_candidatese a única coisa que filter_candidatesinteressa é se fill_singlesretorna uma grade válida. Esta é uma informação que podemos saber com antecedência, desde que fill_singlesencontre uma posição sem candidatos. Se retornarmos mais cedo, não precisaremos fazer cálculos get_candidatestantas vezes.
Então mudei um pouco a estrutura do código, fill_singlesvolto Nonecaso não encontre uma grade válida.
Finalmente consegui aumentar o tempo de execução para 0,5s, que é 900% mais rápido do que a versão original.
Na verdade, foi uma aventura divertida porque eu estava testando meu projeto VizTracer e tentei descobrir se era útil localizar a parte demorada. Funcionou bem :)
Numpyificação
get_subgridsessencialmente reorganiza uma matriz numpy com um mínimo de numpy. Isso poderia ser feito com o próprio numpy, por exemplo:
def get_subgrids(grid: np.ndarray) -> np.ndarray:
"""Divide the input grid into 9 3x3 sub-grids"""
swapped = np.swapaxes(np.reshape(grid, (3, 3, 3, 3)), 1, 2)
return np.reshape(swapped, (9, 9))
A desvantagem, suponho, é que trocar os dois eixos do meio de um array 4D é um pouco complicado.
atuação
Quase todo o tempo é gasto em get_candidates. Acho que as razões para isso são principalmente:
- Ele é chamado com muita frequência. Por exemplo, depois de preencher uma célula (como em
fill_singles), em vez de recalcular os candidatos do zero, seria mais rápido simplesmente remover o novo valor dos candidatos na mesma linha / coluna / casa. - Se uma célula for preenchida, a lista de candidatos é apenas o valor preenchido, mas o cálculo do conjunto caro é feito de qualquer maneira. Isso é fácil de evitar apenas movendo essas instruções dentro do
if.
Desempenho algorítmico
Este solucionador só faz uso de Naked Singles como uma "técnica de propagação", adicionar Hidden Singles é, em minha experiência, um grande passo em direção a um solucionador eficiente.