12 May 2011

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

25 March 2011

Noisy

Já faz um tempo, mas não esqueci do blog não. Estava tentando entender como funciona o tal do Perlin Noise pra ver se dá pra aproveitar pra minha idéia de gerar coisas proceduralmente.

Por enquanto está um pouco pesado, e ainda tem alguns bugs que eu vi e não sei ainda o que tá pegando, mas bem, aí vai a nova versão, não tem mais paredes, não tem mais moedas, voltei ao visual 3D e agora dá pra pular também (barra de espaço).


O que rola aí é um Perlin Noise 2D com os parâmetros passados ali na tela de início. Pra cada ponto o noise determina a altura e a cor do quadrado. Se aumentar muito os números pode dar crash no browser, cuidado!

Anyways, a persistência em tese deveria ficar abaixo de 1, 0 oitavas não gera noise nenhum, o viewrange determina basicamente um farplane pra criação dos quadrados e o height multiplica a altura deles.

O Sub é mais fácil pra entender olhar pros valores de posição e referência quando estiver jogando.

Agora sei fazer no braço Noise em 1, 2 ou 3 dimensões. Meu plano é usar esse noise pra gerar de forma determinística uma semente aleatória pra construir "salas" ou pedaços de uma dungeon.
Tantas idéias, tão pouco tempo pra botar elas em prática...

That's all folks!

Grenade
Bruno Mars

25 February 2011

Coins!

Bom, mais uma horinha em cima do meu projeto e tá aí a versão nova:




Agora com um timer, e moedas, pode ser que fique mais pesado agora o jogo porque eu não otimizei o modo de guardar as moedas na memória, mas bem, agora já tem alguma coisa pra pontuar, já posso chamar isso aí de jogo, há!

Mudei a câmera por uma 2D pra ver como fica.

Bem, qual o próximo passo? Ainda não decidi pra onde levar isso, sugestões, críticas ou qualquer outra coisa é só deixar nos comentários aí embaixo... till next time!

Loose Yourself
Eminem

23 February 2011

3D Maze

Então, de volta a postar no blog.


Isso aqui eu fiz agora pouco, umas 2h mexendo no pc em casa:


Instruções:
Clique em START para jogar, os valores SeedHi e SeedLo servem para gerar o labirinto
WASD ou as setas do teclado para se mover
Clique em STOP se quiser voltar para a tela inicial e criar outro labirinto

Isso é um protótipo de absolutamente nada, sempre quis mexer com coisas procedurais e isso aí que saiu, basicamente os dois valores que são fornecidos no início servem pra gerar o labirinto, que é teoricamente infinito. Cada pedaço do labirinto é criado dinâmicamente quando necessário, enquanto o boneco anda. Não tem saída, ou solução, e também dependendo do valor da seed você pode ficar preso. Ainda não fiz esse tipo de checagem e não sei se vou.

Minha idéia aqui é testar, explorar possibilidades, não é como se eu tivesse muito tempo pra mexer nessas coisas, mas na medida do possível, vamos brincando pra ver no que vai dar.

Qualquer sugestões, críticas, comentários são bem vindos. E vou colocando aqui sempre que tiver um tempo pra mexer nesse bixo.

You Never Can Tell
Chuck Berry

21 February 2011

Back to the bloggin'

Isso é só um teste, mas se tudo der certo, o blog deve voltar :D



Bang Bang Boom
The Moffats