Saltar para o conteúdo

Kuromasu

Origem: Wikipédia, a enciclopédia livre.
Um jogo Kuromasu de dificuldade média numa grelha 11x11
Solução do jogo

Kuromasu (黒どこ (kurodoko?)) é um jogo de lógica publicado pela Nikoli em 1991. Trata-se de um jogo de classificação binária das células de uma matriz.

O Kuromasu é jogado numa grelha retangular. O objetivo é classificar todas as células em brancas ou pretas, ou seja, determinar onde estão todas as células pretas, sendo que as restantes são brancas. Algumas células brancas têm números, e esses números indicam o total de células vizinhas (na mesma linha ou coluna, incluindo uma vez a própria) que não são bloqueadas pelas células pretas, ou seja, formam sequência contínua com a célula com o número. Não há duas células pretas vizinhas.

Matematicamente, o problema de decisão sobre se um puzzle Kuromasu é resolúvel é NP-completo.[1]

Ligações externas

[editar | editar código-fonte]

Referências

  1. Kölker, Jonas (2012). «Kurodoko is NP-complete»