Tentei gerar uma versão um pouco mais simples removendo a recursividade e usando técnica de passagem múltiplas.
Primeiro uma inicialização de estrutura de dados auxiliares:
rows = 'ABCDEFGHI'Squares contém um array com todos os nomes das caixinhas do tabuleiro do Sudoku (A1, A2, ...., A9, B1, B2, ...). Vectors contém os vetores dos nomes das caixinhas das linhas, colunas e dos quadrados menores do tabuleiro, aonde cada vetor tem que conter os números de 1 a 9 conforme a regra do Sudoku.
cols = '123456789'
squares = [r+c for r in rows for c in cols]
vectors = ([[r+c for c in cols] for r in rows] +
[[r+c for r in rows] for c in cols] +
[[r+c for r in srows for c in scols]
for srows in ('ABC','DEF','GHI')
for scols in ('123','456','789')])
peers = dict((s, set(s2 for vector in vectors if s in vector for s2 in vector))
for s in squares)
digits = list('123456789')
O dicionário peers é a estrutura mais mágica, ela contém o conjunto dos nomes das caixinhas do tabuleiro que fazem parte da linha, coluna ou quadrado menor de cada caixinha. Com ela consigo rapidamente verificar quais números estão já sendo usados nos vetores.
def parse_grid(grid):parsegrid e printboard são funções auxiliares: parsegrid recebe uma string com números de configuração inicial do tabuleiro aonde a sequência na string descreve a posição no tabuleiro, 0 indicando posição vazia e 1-9 indicando o valor inicial. printboard obviamente imprime o que está no tabuleiro passado como um dicionário de parâmetro.
"Given a string of 81 digits (or . or 0 or -), return a dict of {cell:values}"
grid = [c for c in grid if c in '0,-123456789']
return dict((squares[p], grid[p]) for p in range(len(squares)))
def printboard(values):
width = max(len(values[s]) for s in squares)
sep = '+'.join(['-'*(2+width)*3]*3)
form = '|'.join([(' %%%ds ' % width*3)]*3)
for r in rows:
print form % tuple([values[r+c] for c in cols])
if r in 'CF': print sep
def possibilities(values):Esta função possibilities recebe um dicionário de parâmetro e retorna uma cópia com os espaços em aberto preenchidos com as possibilidades para cada posição no tabuleiro. É basicamente uma versão multi-passagem do algoritmo recursivo do Peter Norvig.
values = values.copy()
while True:
changed = False
for s in squares:
if not values[s] in digits:
values[s] = ''.join(set(digits).difference(set(values[s2] for s2 in peers[s])))
if values[s] == '': return False
for vector in vectors:
for digit in digits:
ocor = [s for s in vector if digit in list(values[s])]
if len(ocor) == 0: return False
if len(ocor) == 1 and len(values[ocor[0]]) > 1:
values[ocor[0]] = digit
changed = True
if not changed: break
return values
Primeiro a função varre o tabuleiro procurando as posições do tabuleiro em aberto e preenche com uma string das possibilidades de acordo com os vetores envolvidos na posição. Em vários casos apenas uma possibilidade é possível, o que já determina o valor da posição só nesta passada.
Em seguida todos os vetores são analisados para verificar possibilidades únicas para os números de 1 a 9. Funciona assim: digamos que na linha A (A1-A9) as posições A1 a A8 contenham os números de 1 a 8, e a posição A9 contenha as possibilidades 7, 8 e 9, é evidente que o valor de A9 é o valor 9.
Estes dois algoritmos são executados várias vezes até que nenhuma alteração não seja mais possível, o que em muitos casos já soluciona o Sudoku.
Os casos aonde o Sudoku não é solucionado apenas através das restrições impostas nos vetores são considerados Sudokus avançados, pois envolvem teste simultâneo de alternativas para sua solução.
Para isso, a força bruta parece ser a solução mais simples:
def solve(values):Esta função solve aplica o possibilities, procura o primeiro caso de uma caixa com múltiplas possibilidades e varre suas alternativas recursivamente tentando solucionar com o próprio solve.
values = possibilities(values)
if not values: return False
for s in squares:
if len(values[s]) > 1:
for p in values[s]:
values[s] = p
res = solve(values)
if res: return res
return False
return values
Agora vamos tentar solucionar o Sudoku mais difícil que existe segundo o próprio post que usei como referência:
grid = """O que dá como resposta:
100007090
030020008
009600500
005300900
010080002
600004000
300000010
040000007
007000300
"""
grid = parse_grid(grid)
printboard(grid)
printboard(possibilities(grid))
printboard(solve(grid))
1 0 0 | 0 0 7 | 0 9 0
0 3 0 | 0 2 0 | 0 0 8
0 0 9 | 6 0 0 | 5 0 0
---------+---------+---------
0 0 5 | 3 0 0 | 9 0 0
0 1 0 | 0 8 0 | 0 0 2
6 0 0 | 0 0 4 | 0 0 0
---------+---------+---------
3 0 0 | 0 0 0 | 0 1 0
0 4 0 | 0 0 0 | 0 0 7
0 0 7 | 0 0 0 | 3 0 0
1 8256 8246 | 854 354 7 | 246 9 346
547 3 46 | 1954 2 195 | 1476 476 8
8247 827 9 | 6 134 183 | 5 3247 134
------------------------+------------------------+------------------------
8247 827 5 | 3 176 126 | 9 8476 146
947 1 34 | 957 8 956 | 476 35476 2
6 9827 832 | 19257 1957 4 | 187 8357 135
------------------------+------------------------+------------------------
3 98256 826 | 254798 95476 98256 | 8246 1 9546
9825 4 1 | 9825 9356 325698 | 826 8256 7
9825 98256 7 | 125498 19546 125698 | 3 82546 9546
1 6 2 | 8 5 7 | 4 9 3
5 3 4 | 1 2 9 | 6 7 8
7 8 9 | 6 4 3 | 5 2 1
---------+---------+---------
4 7 5 | 3 1 2 | 9 8 6
9 1 3 | 5 8 6 | 7 4 2
6 2 8 | 7 9 4 | 1 3 5
---------+---------+---------
3 5 6 | 4 7 8 | 2 1 9
2 4 1 | 9 3 5 | 8 6 7
8 9 7 | 2 6 1 | 3 5 4
Nenhum comentário:
Postar um comentário