Sudoku!
Então, volta e meia eu gosto de passar o tempo com esse tal de sudoku.
Um belo dia peguei um desses livros que vendem nas bancas com um monte desses pra resolver, eis que, após muito tempo resolvendo de boa os puzzles evil do websudoku, não consigo resolver um desses de revista. Explico: aparentemente os puzzles do site são montados de um jeito que só é possível uma solução, enquanto na revista eu mesmo consegui uma solução diferente da que estava nas respostas.
Levando isso em conta, como o meu gosto pelo jogo está na parte lógica e não em ficar chutando e depois apagando os valores, resolvi perder um tempinho e resolver mais rápido todos os sudokus que aparecessem pra mim.
Aí surgiu a idéia do meu programa pra resolver Sudoku. Link aqui.
Esse programa serve pra organizar as idéias na hora de resolver o puzzle.
Não vou falar nenhuma novidade aqui, mas vou tentar mostrar como o jogo pode ser representado de forma simples, e como eu organizo as idéias pra resolvê-lo no programa:
- O tabuleiro é um diagrama de 9 x 9 células, e o objetivo é completar o tabuleiro com os números de 1 a 9 de forma que cada linha, cada coluna e cada sub-tabuleiro de 3 x 3 contenha todos os números de 1 a 9 e, portanto, nenhum repetido;
- Isso quer dizer que nós temos 27 grupos de células: 9 linhas + 9 colunas + 9 sub-tabuleiros;
- Cada um desses grupos precisa conter células com os valores de 1 a 9;
- Cada célula participa de exatamente 3 grupos;
- O desenvolvimento do jogo parte das células que já vem preenchidas, determinando os possíveis valores para as outras células.
- Dado isso, deveria ser possível inferir os valores de todas as outras células a partir do valor inicial.
O programa não resolve sozinho, mas ele cobre algumas inferências mais simples, e faz uma análise do problema ao meu ver, mais organizada pra resolver o problema. Claro que não fiquei muito tempo preocupado com interface e usabilidade, muito menos otimização, mas pelo menos se precisar chutar dá pra salvar o estado (de maneira precária, mas dá =D ), e ele mostra todos os conjuntos, e todos os possíveis valores de cada célula. Além disso, é possível dizer o valor de uma dada célula, e é possível remover um valor da lista de possíveis valores de outra célula.
Para executar, por linha de comando, é só chamar o programa com os 81 valores do tabuleiro, começando de cima para baixo, da esquerda para a direita, usando '.' nas células vazias.
Para chamar o programa, onde quer que você tenha salvo o arquivo (como exemplo o tabuleiro tirado da página da wikipedia, esse meu programa resolve até o fim sozinho :P )
C:\SudokuSolver>SudokuSolver 53..7....6..195....98....6.8...6...34..8.3..17...2...6.6....28....419..5....8..79
Os comandos para o programa:
- ? : ajuda (lista os comandos (sim, eu só consigo programar em inglês))
- c : mostra todas as células e seus possíveis valores
- g : mostra todos os grupos, e cada célula dentro desse grupo
- i (ou somente
) : tenta fazer uma iteração (descobrir uma célula ou remover valores possíveis de várias células) - w[x][y][v] : escreve o valor 'v' na célula ['x','y'] (o desenho do tabuleiro tem as coordenadas, bem como as células quando são listadas) Ex. w001 escreve o valor 1 na célula [0,0], a primeira célula do tabuleiro
- r[x][y][v] : remove o valor 'v' da lista de possíveis valores para a célula ['x','y'] (ainda não fiz na lógica do programa e é basicamente essa parte que mais quebra a cabeça) Ex. r003 remove o valor 3 da lista de possíveis valores para a célula [0,0]
- s : salva o tabuleiro, sempre bom fazer antes de começar a chutar, na verdade o que ele faz é imprimir o valor do tabuleiro como ele precisa ser digitado como parâmetro pra começar o program, assim, se quiser recomeçar desse ponto é só guardar essa linha de texto no bloco de notas e copiar.
O tabuleiro aparece no jogo com '.' nas células vazias e com o valor nas células já preenchidas. O programa nunca vai chutar errado, mas se o usuário marcar o valor errado ou remover o valor certo de alguma célula e isso levar a um impasse vai aparecer um ? no lugar do valor da célula. (quando o conjunto de possíveis valores está vazio)
Bem, qualquer dúvida, comentário, sugestão é bem vinda, mas não sei se vou trabalhar muito em cima desse bixo ainda, me foram umas duas horas pra fazê-lo e mais duas só pra montar esse post, mas anyways, tá aí, enjoy!
P.S. Btw, melhor programa de FTP: Firefox com FireFTP
