Estude este código cuidadosamente e descubra uma maneira inteligente de usar a recursão para resolver esses complicados quebra-cabeças de sudoku.
Sudoku é um popular quebra-cabeça numérico que consiste em uma grade 9x9 com dígitos de 1 a 9. O quebra-cabeça inclui uma combinação de números e alguns espaços vazios, que você precisa preencher.
Ao preencher os espaços vazios, cada linha, coluna e subgrade 3x3 deve conter todos os dígitos de 1 a 9.
Um script Python simples pode ajudar a resolver um quebra-cabeça de Sudoku para você. Ele pode analisar todos os espaços vazios no tabuleiro de Sudoku e encontrar um número possível para preencher cada espaço em branco.
Como criar e exibir o tabuleiro de Sudoku
Dentro de um script Python, você precisará usar uma lista de arrays para armazenar os valores do quebra-cabeça Sudoku não resolvido.
O código utilizado neste projeto está disponível neste repositório GitHub sob a licença do MIT.
- Dentro de um novo script Python chamado sudoku.py, armazene todos os valores para a grade 9x9. Cada linha e coluna representa os nove números do quebra-cabeça Sudoku. Adicione 0s para representar os espaços que precisam ser resolvidos:
placa = [
[5, 3, 0, 0, 7, 0, 0, 0, 0],
[6, 0, 0, 1, 9, 5, 0, 0, 0],
[0, 9, 8, 0, 0, 0, 0, 6, 0],
[8, 0, 0, 0, 6, 0, 0, 0, 3],
[4, 0, 0, 8, 0, 3, 0, 0, 1],
[7, 0, 0, 0, 2, 0, 0, 0, 6],
[0, 6, 0, 0, 0, 0, 2, 8, 0],
[0, 0, 0, 4, 1, 9, 0, 0, 5],
[0, 0, 0, 0, 8, 0, 0, 7, 9]
] - Dentro de uma nova função chamada print_board, usar um loop for para processar cada linha na grade:
defprint_board(quadro):
para linha em faixa(9): - Para separar cada linha em terços, verifique se a linha é divisível por três e adicione uma linha:
se linha % 3 == 0e fila != 0:
imprimir("- - - - - - - - - - - - - - ") - Dentro de cada linha, percorra cada coluna. Você também pode dividir colunas em terços verificando se a coluna é divisível por três:
para col em faixa(9):
se col % 3 == 0e col != 0:
imprimir(" | ", fim="") - Imprima o valor do número armazenado na grade. Se a coluna for a última coluna dessa linha específica, adicione uma linha de quebra, para que a seguinte linha apareça em uma nova linha:
se col == 8:
imprimir (tabuleiro[linha][coluna])
outro:
print (str (tabuleiro[linha][coluna]) + " ", fim="") - Chame a função para imprimir a placa:
print_board (placa) - Em uma linha de comando, navegue até a pasta onde você armazenou seu script python, por exemplo:
área de trabalho cd - Use o comando python para executar seu script Sudoku. Veja o quebra-cabeça impresso na tela:
python sudoku.py
Como identificar os espaços vazios para resolver
Você pode percorrer as listas para encontrar os espaços que consistem em 0s. Estes determinam quais espaços precisavam ser resolvidos.
- Em uma nova função chamada find_empty(), percorra cada linha e coluna no quadro:
defencontrar_vazio(quadro):
para linha em faixa(9):
para col em faixa(9): - Se o valor da célula atual for 0, retorne a posição atual da célula vazia:
se quadro[fila][coluna] == 0:
retornar (linha, coluna) - Se o script atingir o final da função, isso significa que o script não encontrou nenhuma célula com o valor 0. Nesse caso, não retorne nada:
retornarNenhum - Em uma nova função chamada solve(), use a função find para encontrar o primeiro espaço vazio no tabuleiro:
defresolver(quadro):
encontrar = encontrar_vazio (tabuleiro) - A função find_empty() retorna a posição da célula em formato de tupla, por exemplo, (0, 2). Salve esses valores separadamente no linha e col variáveis. Caso contrário, retorne true para indicar que não há espaços vazios para resolver:
senão encontrar:
retornarVerdadeiro
outro:
linha, coluna = encontrar
Como resolver o quebra-cabeça para cada linha, coluna e grade 3x3
Agora que você pode identificar o primeiro espaço vazio a ser resolvido, você precisará tentar encontrar um número apropriado para preencher esse espaço e resolver o quebra-cabeça.
Usando recursão, chame a função solve() dentro dela mesma para tentar todas as combinações possíveis de valores para todos os outros espaços também.
- Dentro da função solve(), depois de encontrar o primeiro espaço vazio, percorra cada número de 1 a 9. Esses números representam os números possíveis que poderiam preencher o espaço não resolvido:
para num em faixa(1, 10): - Insira o tabuleiro, o número possível e a posição da célula vazia em uma nova função. A nova função retornará true se esse número for um número válido que possa resolver esse espaço vazio. Se for válido, atribua esse número à célula do quadro:
se is_valid (board, num, (row, col)):
tabuleiro[linha][coluna] = num - Crie a função is_valid(), com parâmetros correspondentes:
defé válido(tabuleiro, num, pos): - Use a função para verificar se colocar o número naquela posição viola alguma regra do jogo Sudoku. Primeiro, verifique se esse número já existe na linha ou coluna da célula:
para col em faixa(9):
se tabuleiro[pos[0]][col] == num e pos[1] != col:
retornarFalsopara linha em faixa(9):
se quadro[linha][pos[1]] == num e pos[0] != linha:
retornarFalso - Obtenha a grade 3x3 à qual a célula pertence. Você pode fazer isso dividindo a posição da célula por três:
linha_caixa = pos[0] // 3
box_col = pos[1] // 3 - Para cada linha e coluna nessa grade 3x3, verifique se o número já existe. Em caso afirmativo, retorne false:
para linha em intervalo (box_row*3, linha_caixa*3 + 3):
para col em intervalo (box_col*3, box_col*3 + 3):
se tabuleiro[linha][col] == num e (linha, coluna) != pos:
retornarFalso - Se o script atingir o final da função, isso significa que nenhuma das regras do Sudoku falhou. Retorno verdadeiro:
retornarVerdadeiro - A função is_valid() apenas verifica se o posicionamento do número é válido, mas isso não significa que seja a resposta correta para a solução geral. Dentro da função solve(), chame a função solve() novamente com a placa atualizada. A função solve() pode atingir um estado em que não pode mais usar números para preencher espaços. Nesse caso, toda a função retorna falso, redefine essa célula específica de volta para 0 e retrocede. A função solve() só retorna true quando o script pode preencher todos os espaços:
para num em faixa(1, 10):
se is_valid (board, num, (row, col)):
tabuleiro[linha][coluna] = num
se resolver (tabela):
retornarVerdadeiro
quadro[linha][coluna] = 0retornarFalso - Para começar a resolver o quebra-cabeça, chame a função solve() com o tabuleiro original, na parte inferior do script, após declarar a função solve():
resolver (tabela) - Imprima o resultado final:
imprimir("Resolvido:")
print_board (placa) - Na linha de comando, use o comando python para executar novamente o script. Veja o quebra-cabeça resolvido impresso na tela:
python sudoku.py
Criando jogos usando Python
Sudoku é apenas um dos muitos jogos que você pode criar e resolver usando Python. Você pode usar o Python para criar vários outros jogos, como uma confusão de palavras, um jogo de aventura baseado em texto ou um jogo de cores, para citar apenas alguns.
