Introdução
Escreva um solucionador para os quebra-cabeças Hitori usando menos bytes.
Desafio
Sua tarefa é escrever um solucionador para os quebra-cabeças lógicos Hitori (ひ と り, em japonês; o significado do nome do jogo é "Deixe-me em paz"). As regras são as seguintes:
- Você é apresentado com uma grade de células n por n, cada célula contém um número inteiro entre 1 e n (inclusive).
- Seu objetivo é garantir que nenhum número apareça mais de uma vez em cada linha e em cada coluna da grade, removendo números da grade especificada, sujeito à restrição indicada nas duas próximas regras,
- Você não pode remover dois números de duas células adjacentes (horizontal ou verticalmente).
- As células numeradas restantes devem estar todas conectadas umas às outras. Isso significa que quaisquer duas células numeradas restantes podem ser conectadas com uma curva composta apenas por segmentos que conectam números restantes adjacentes (horizontal ou verticalmente). (Obrigado a @ user202729 por apontar que isso está faltando)
Espero que as regras estejam claras agora. Se houver algo pouco claro sobre as regras, consulte a página da Wikipedia .
Casos de teste
As células das quais os números são removidos são representadas com 0s.
Input -> Output
4
2 2 2 4 0 2 0 4
1 4 2 3 -> 1 4 2 3
2 3 2 1 2 3 0 1
3 4 1 2 3 0 1 2
4
4 2 4 3 0 2 4 3
4 1 1 2 -> 4 1 0 2
3 1 2 1 3 0 2 1
4 3 1 3 0 3 1 0
5
1 5 3 1 2 1 5 3 0 2
5 4 1 3 4 5 0 1 3 4
3 4 3 1 5 -> 3 4 0 1 5
4 4 2 3 3 4 0 2 0 3
2 1 5 4 4 2 1 5 4 0
8
4 8 1 6 3 2 5 7 0 8 0 6 3 2 0 7
3 6 7 2 1 6 5 4 3 6 7 2 1 0 5 4
2 3 4 8 2 8 6 1 0 3 4 0 2 8 6 1
4 1 6 5 7 7 3 5 -> 4 1 0 5 7 0 3 0
7 2 3 1 8 5 1 2 7 0 3 0 8 5 1 2
3 5 6 7 3 1 8 4 0 5 6 7 0 1 8 0
6 4 2 3 5 4 7 8 6 0 2 3 5 4 7 8
8 7 1 4 2 3 5 6 8 7 1 4 0 3 0 6
9
8 6 5 6 8 1 2 2 9 8 0 5 6 0 1 2 0 9
5 6 2 4 1 7 9 8 3 5 6 2 4 1 7 9 8 3
5 8 2 5 9 9 8 2 6 0 8 0 5 0 9 0 2 0
9 5 6 6 4 3 8 4 1 9 5 6 0 4 3 8 0 1
1 1 6 3 9 9 5 6 2 -> 0 1 0 3 9 0 5 6 2
1 1 4 7 3 8 3 8 6 1 0 4 7 0 8 3 0 6
3 7 4 1 2 6 4 5 5 3 7 0 1 2 6 4 5 0
3 3 1 9 8 7 7 4 5 0 3 1 9 8 0 7 4 5
2 9 7 5 3 5 9 1 3 2 9 7 0 3 5 0 1 0
Esses casos de teste são retirados de Concept Is Puzzles , PuzzleBooks , Concept Is Puzzles , Wikipedia e Youtube , respectivamente.
Especificações
Não precisa se preocupar com o tratamento de exceções.
Você pode assumir que a entrada é sempre um quebra-cabeça válido com uma solução exclusiva e pode tirar proveito disso ao escrever seu código.
Isso é código-golfe , o menor número de bytes vence.
4 <= n <= 9 (16 originalmente, alterado para 9 seguindo a sugestão de Stewie Griffin, também economiza alguns problemas de IO)
Você pode receber e fornecer saída através de qualquer formulário padrão e pode escolher o formato.
Algumas sugestões para o formato de saída são (mas você não está restrito a elas)
- Saída da grade final
- Saída da grade contendo todos os números removidos
- Emita uma lista de coordenadas de uma das opções acima
Como de costume, as brechas padrão se aplicam aqui.
Relacionado (inspirado neste desafio): Verifique se todos os elementos de uma matriz estão conectados
Meu último desafio: extensão do jogo dos setes
4 <= n <= 16
, mas o maior caso de teste é paran=9
. Sugiro que você publique umn=16
caso de teste ou diga4 <= n <= 9
. Bom desafio pela maneira :)Respostas:
Haskell , 374 bytes
Experimente online!
fonte
APL (Dyalog Unicode) , SBCS de 133 bytes
Experimente online!
Minha implementação da regra nº 4 (as células devem formar um único componente conectado) é um desperdício, mas ainda assim é aprovada em todos os testes em cerca de 10 segundos no TIO.
O algoritmo geral: armazene duas matrizes booleanas
b
ew
para células que certamente serão preto e branco, respectivamente. Inicializeb
como zero. Inicializew
como 1 apenas para as células que possuem vizinhos correspondentes opostos.Repita até
b
ew
se acalme:adicione às
b
células que estão na mesma linha (horizontal ou vertical) e com o mesmo valor que uma célula emw
adicionar aos
w
vizinhos imediatos de todas as células emb
adicionar a
w
todos os pontos de corte - células cuja remoção dividiria o gráfico de células não pretas em vários componentes conectadosPor fim, o resultado
not(b)
multiplicado pela matriz original.fonte
Geléia , 62 bytes
Usa o link monádico isConnected de user202729 de outra pergunta.
Um programa completo que imprime uma representação de uma lista de listas.
Funciona com força bruta e é estupidamente ineficiente.
Experimente online! - 3 por 3, uma vez que é muito ineficiente para executar até um tamanho 4 dentro do limite de TIO de 60 segundos!
Quão?
fonte