Sudoku Solver
Um tabuleiro de sudoku é uma grade 9 × 9 dividida em nove quadrados de 3 × 3. Em um tabuleiro resolvido, cada linha, cada coluna e cada quadrado contém cada dígito de 1 a 9 exatamente uma vez.
O quebra-cabeça é fornecido como 9 strings, uma por linha, de cima para baixo; um . representa uma célula vazia. Preencha todas as células vazias e retorne o tabuleiro resolvido no mesmo formato. O tabuleiro tem exatamente uma solução.
Função
- boardstring-array
- as 9 linhas do quebra-cabeça, um ponto em cada célula vazia
- Retornastring-array
- as 9 linhas do tabuleiro resolvido
Restrições
boardcontém 9 strings de comprimento 9.- Cada caractere é
.ou um dos dígitos de1a9. - Os dígitos fornecidos nunca se repetem em uma linha, coluna ou bloco.
- O tabuleiro tem exatamente uma solução.
Exemplos
- Entrada
- board = ["9.7.....6", "824.3....", "..1..9..2", ".9...2.18", "...4....5", "1325.8...", "...687...", "......8.9", ".4.9...5."]
- Saída
- ["957214386", "824736591", "361859742", "495372618", "786491235", "132568974", "519687423", "273145869", "648923157"]
- Explicação
- A linha superior
9.7.....6já contém 9, 7 e 6, então suas seis células vazias recebem 1, 2, 3, 4, 5 e 8. As colunas e os blocos determinam onde cada um deles vai, e a linha se torna957214386.
Para ir além
Em um killer sudoku, os grupos de células também precisam somar os valores indicados. Como você adicionaria essa regra à busca e a usaria para eliminar ramificações antecipadamente?
Dicas
Abra uma de cada vez. Cada uma revela um pouco mais.
Acompanhe quais dígitos cada linha, cada coluna e cada caixa 3 × 3 já contém. Assim, você pode verificar em O(1) se um dígito cabe em uma célula vazia.
Preencha as células vazias uma de cada vez. Experimente cada dígito que caiba na célula, passe para a próxima célula e desfaça a jogada quando não for possível completar o restante do tabuleiro com esse dígito.
A ordem das células importa. Em seguida, preencha a célula vazia com menos dígitos restantes: uma célula com uma opção não exige ramificações, e uma célula sem nenhuma opção indica imediatamente que você deve voltar.
Solução
Resolva usando retrocesso: coloque um dígito que se encaixe, continue e desfaça a jogada quando não for possível completar o tabuleiro. A ordem das células determina a velocidade. Em um tabuleiro difícil, percorrer as células na ordem de leitura pode visitar centenas de milhões de tabuleiros parciais; preencher primeiro a célula com menos opções leva cerca de cem.
Retrocesso na ordem de leitura
Correta, mas não termina nos maiores testes
Intuição
Preencha as células vazias na ordem de leitura, cada uma com o menor dígito que se encaixe. Quando não restar nenhum dígito para uma célula, volte à célula anterior e tente o próximo. Cada combinação que respeita as regras é testada por sua vez, então a busca encontra a solução.
Três tabelas tornam cada teste de encaixe O(1): rowUsed[r][d], colUsed[c][d] e boxUsed[b][d], com a caixa b = (r / 3) * 3 + c / 3. Inserir um dígito define três entradas, e removê-lo as limpa.
A ordem fixa é o ponto fraco: a busca pode preencher uma linha inteira com dígitos que se encaixam localmente e só descobrir, muitas células depois, que eles não deixam espaço. Um tabuleiro cujas linhas superiores quase não têm pistas, com dígitos altos como respostas, faz a busca passar por mais de 300 milhões de tabuleiros parciais.
Algoritmo
- Leia o tabuleiro em uma grade, usando 0 para uma célula vazia, preencha
rowUsed,colUsedeboxUsede liste as células vazias na ordem de leitura. backtrack(k): sekfor igual ao número de células vazias, retorne true.- Para cada dígito
dde 1 a 9 que não esteja sendo usado na linha, coluna e caixa da célulak, coloque-o, marque-o e retorne true sebacktrack(k+1)também retornar true; caso contrário, desmarque-o. - Se nenhum dígito funcionar, limpe a célula e retorne false. Chame
backtrack(0)e transforme a grade de volta em strings.
def solveSudoku(board):
grid = [[0 if ch == "." else int(ch) for ch in row] for row in board]
# row_used[r][d] is True when digit d already sits in row r; same for
# columns and boxes. Box b holds the cells with (r // 3) * 3 + c // 3 == b.
row_used = [[False] * 10 for _ in range(9)]
col_used = [[False] * 10 for _ in range(9)]
box_used = [[False] * 10 for _ in range(9)]
empties = []
for r in range(9):
for c in range(9):
d = grid[r][c]
if d:
row_used[r][d] = col_used[c][d] = box_used[(r // 3) * 3 + c // 3][d] = True
else:
empties.append((r, c))
def backtrack(k):
if k == len(empties):
return True
r, c = empties[k]
b = (r // 3) * 3 + c // 3
for d in range(1, 10):
if not row_used[r][d] and not col_used[c][d] and not box_used[b][d]:
grid[r][c] = d
row_used[r][d] = col_used[c][d] = box_used[b][d] = True
if backtrack(k + 1):
return True
row_used[r][d] = col_used[c][d] = box_used[b][d] = False
grid[r][c] = 0
return False
backtrack(0)
return ["".join(str(d) for d in row) for row in grid]Preencha primeiro a célula mais vazia
Intuição
A solução não depende da ordem de preenchimento, então escolha a ordem que mantenha pequena a busca: a cada etapa, preencha a célula vazia que permite o menor número de dígitos. Uma célula com um único dígito permitido é forçada e não adiciona nenhum ramo. Uma célula sem nenhum dígito permitido é escolhida imediatamente, então um tabuleiro inválido é detectado na hora.
Para contar rapidamente os dígitos permitidos nas 81 células a cada etapa, armazene cada linha, coluna e bloco como uma máscara de bits: o bit d de rows[r] é definido quando o dígito d está na linha r. Uma célula permite ~(rows[r] | cols[c] | boxes[b]) & 0x3FE, em que 0x3FE mantém os bits de 1 a 9, e a contagem corresponde ao número de bits definidos. Ao posicionar d, defina o bit d em três máscaras; um ou exclusivo o remove.
Algoritmo
- Construa a grade e as máscaras
rows,colseboxesa partir dos dígitos fornecidos. backtrack(): percorra todas as células, calcule os dígitos permitidos para cada célula vazia e mantenha a primeira célula com a menor quantidade. Se nenhuma célula estiver vazia, retorne true.- Para cada dígito permitido dessa célula, coloque-o nela, defina seu bit nas três máscaras e retorne true se
backtrack()também retornar true; caso contrário, limpe os bits. - Se nenhum dígito funcionar, esvazie a célula e retorne false. Chame
backtrack()e converta a grade novamente em strings.
def solveSudoku(board):
grid = [[0 if ch == "." else int(ch) for ch in row] for row in board]
# Bit d of rows[r] is set when digit d already sits in row r; same for
# columns and boxes. Box b holds the cells with (r // 3) * 3 + c // 3 == b.
rows, cols, boxes = [0] * 9, [0] * 9, [0] * 9
for r in range(9):
for c in range(9):
d = grid[r][c]
if d:
rows[r] |= 1 << d
cols[c] |= 1 << d
boxes[(r // 3) * 3 + c // 3] |= 1 << d
def backtrack():
# Pick the empty cell with the fewest digits left (the first one on a tie).
best_r, best_c, best_allowed, best_count = -1, -1, 0, 10
for r in range(9):
for c in range(9):
if grid[r][c] == 0:
# Bits 1 to 9 of 0x3FE are the nine digits.
allowed = ~(rows[r] | cols[c] | boxes[(r // 3) * 3 + c // 3]) & 0x3FE
count = bin(allowed).count("1")
if count < best_count:
best_r, best_c, best_allowed, best_count = r, c, allowed, count
if best_r == -1:
return True # no empty cell is left: the board is solved
r, c = best_r, best_c
b = (r // 3) * 3 + c // 3
for d in range(1, 10):
bit = 1 << d
if best_allowed & bit:
grid[r][c] = d
rows[r] |= bit
cols[c] |= bit
boxes[b] |= bit
if backtrack():
return True
rows[r] ^= bit
cols[c] ^= bit
boxes[b] ^= bit
grid[r][c] = 0
return False
backtrack()
return ["".join(str(d) for d in row) for row in grid]
Armadilhas e casos extremos
- Esquecer de limpar um dígito dos registros da linha, da coluna e do bloco ao desfazer a jogada. As células seguintes passam a considerar o dígito como usado, e a busca não encontra a solução.
- Usar
r / 3 + c / 3para o bloco. As células(0, 4)e(4, 0)chegam ambas ao índice 1, então dois blocos compartilham um único registro e o tabuleiro nunca pode ser preenchido. Use(r / 3) * 3 + c / 3com divisão inteira. - Não parar na primeira solução. As etapas de desfazer acabam esvaziando o tabuleiro novamente antes que você o leia.
Perguntas frequentes3
Qual é a complexidade de tempo de um solucionador de sudoku por retrocesso?
Exponencial no pior caso, O(9^m) para m células vazias, porque cada célula pode se ramificar em até 9 dígitos. Em quebra-cabeças reais, as regras de linha, coluna e bloco eliminam a maioria dos ramos, e preencher primeiro a célula mais vazia elimina a maior parte dos restantes.
Como verificar se um sudoku tem exatamente uma solução?
Execute a mesma busca com retrocesso, mas conte as soluções e pare quando a contagem chegar a 2. Uma contagem de 1 significa que o quebra-cabeça tem solução única; 0 significa que não tem solução. Os geradores de quebra-cabeças executam essa verificação após remover cada pista.
Existe uma maneira mais rápida de resolver sudoku do que com retrocesso?
A maioria dos solucionadores rápidos ainda usa retrocesso, mas deduz mais coisas antes de cada tentativa. A propagação de restrições preenche todas as células com uma única opção e todos os dígitos que cabem em apenas uma célula de sua linha, coluna ou bloco, e então repete o processo. O Sudoku também pode ser formulado como um problema de cobertura exata e resolvido com o Algoritmo X de Knuth.
Problemas parecidos
Problemas que usam as mesmas ideias. Resolver dois ou três é o que fixa um padrão.
def solveSudoku(board):
# Escreva o código aquiTeste #1
Argumento
board = ["9.7.....6", "824.3....", "..1..9..2", ".9...2.18", "...4....5", "1325.8...", "...687...", "......8.9", ".4.9...5."]
Saída Esperada
["957214386", "824736591", "361859742", "495372618", "786491235", "132568974", "519687423", "273145869", "648923157"]