Esta N = 3 Star Battle é insolúvel?

Question

Recentemente, tenho resolvido alguns quebra-cabeças conhecidos como Star Battle, mas me deparei com um quebra-cabeça que, não importa quantas vezes eu reinicie, sempre pareço chegar a uma contradição.

Star Battle é jogado colocando estrelas em caixas de forma que cada linha, coluna e área fechada contenha exatamente $N$estrelas. No entanto, as estrelas não podem ser vertical, horizontal ou diagonalmente adjacentes umas às outras.

Neste quebra-cabeça, $N$ é $3$.

Uma versão jogável deste quebra-cabeça (e o site de onde vem o quebra-cabeça) está aqui: www.puzzle-star-battle.com

Estou sempre cometendo o mesmo erro lógico ou esse quebra-cabeça é insolúvel? Se for possível, forneça a solução, caso contrário, alguma prova de sua insolvência.

Answer 1

Não acompanhei as deduções (e usei a força bruta uma vez), então nenhuma explicação, mas pelo menos posso dizer que

este quebra-cabeça tem solução única!

Bom ver um quebra-cabeça com três estrelas (só vi quebra-cabeças de uma ou duas estrelas até agora) Eu mesmo cometi um erro e me deparei com a contradição, portanto, talvez você precise examinar com mais cuidado cada etapa de sua própria lógica.

Answer 2

Aqui está uma resposta para explicar a lógica passo a passo sem a necessidade de aplicar força bruta à solução, caso outras pessoas fiquem presas nesse quebra-cabeça (que é complicado) e precisem de um recurso para ajudá-las. Ao longo deste artigo, as células verdes indicam uma estrela, as células bege são confirmadas como vazias.

Passo 1:

Centro superior (ângulo reto): Para obter 3 estrelas aqui, é necessário estar no ponto mais baixo da forma. Os outros 2 devem estar em metades diferentes da linha superior da forma. Os espaços adjacentes à estrela conhecida e aos 2 quadrados mais à esquerda dentro desta forma devem estar em branco.

Canto superior direito (anzol): Para obter 3 estrelas aqui, deve haver 1 na coluna da esquerda e 2 na coluna da direita. Os espaços adjacentes devem ficar em branco.

Centro-esquerdo (M distorcido): Para obter 3 estrelas aqui, deve haver 1 no ponto mais baixo da forma, 1 nos primeiros dois espaços de sua segunda linha e 1 na seção em forma de canto. Espaços adjacentes que completariam um bloco 2x2 em outras formas podem ser sombreados.

Parte inferior direita (taco de hóquei):Para obter 3 estrelas aqui, deve haver 1 nos 2 espaços mais à esquerda, 1 nos próximos 2 espaços e uma terceira na seção em forma de canto. Espaços adjacentes que completariam um bloco 2x2 em outras formas podem ser sombreados. (De agora em diante, usarei 'Anular adjacentes' como uma abreviação para isso ...)

Passo 2:

Centro-esquerdo (G longo): Agora vemos que deve haver estrelas na célula inferior e a terceira célula abaixo, com a restante nas 2 células superiores. Anule os adjacentes.

Superior esquerdo (C distorcido): Isso significa que devemos ter uma estrela em uma das 2 células da cauda, ​​uma das 2 células centrais do riser e uma das 3 células da seção em forma de canto. Na verdade, ele não pode ir para a célula superior desta forma ou deixaria apenas 2 estrelas capazes de ser colocadas na forma '7' acima dela. Isso, por sua vez, significa que a estrela no riser deve estar em R5C1 para não ser adjacente à outra. Anule os adjacentes.

Superior esquerdo (forma de 7): Observe a seguir que uma das estrelas com esta forma devevá no riser central, com as outras 2 estrelas nos pares de células restantes em extremidades opostas da forma.

Superior esquerdo (C distorcido): esta seria a estrela final na coluna 3, então a estrela na parte inferior do C distorcido deve estar bem no final. Anule os adjacentes.

Observe também que na coluna 2, dos 3 espaços restantes, os 2 superiores não podem ser ambos uma estrela, ou nenhum pode ser colocado no espelho central do 7-shape. Assim, o mais baixo (na ponta do G distorcido) deve ser uma estrela. Além disso, o segundo espaço abaixo na coluna 3 não pode ser uma estrela, pois deve ser adjacente à última estrela restante na coluna 2. Anule os adjacentes.

Etapa 3:

Agora considere a linha 1. Sabemos que deve haver uma estrela entre os primeiros 2 espaços e que também deve haver 2 estrelas entre os espaços nas colunas 4-7. Assim, todos os outros espaços na linha 1 não são sombreados, o que coloca todas as estrelas na forma de anzol. Anule os adjacentes.

Superior esquerdo (forma de 7): também sabemos agora que a estrela no riser da forma de 7 deve estar nas 2 células inferiores, o que significa que a célula dentro desta forma na coluna 4 deve ser deixada em branco e uma estrela deve estar no célula à sua direita. Anule os adjacentes. Isso define a posição da estrela na linha 1, as 2 estrelas restantes na coluna 4, a última estrela na linha 2 e a última estrela na coluna 1. Por sua vez, isso define a posição da última estrela na coluna 3 como sendo em R4C3 na base do '7'.

Passo 4:

Não é muito óbvio neste estágio qual deve ser nossa próxima dedução, mas existem pelo menos mais alguns espaços que podemos sombrear, sabendo que uma estrela não pode ocupá-los:

- R5C10 (adjacente a todos os 3 espaços possíveis para a última estrela na linha 4).
- R14C6 e R15C6 (adjacente a ambos os espaços possíveis para a última estrela na coluna 5).
- R11C7 (agora adjacente a 3 espaços que devem conter pelo menos 1 estrela na coluna 6).
- R13C8 (se for uma estrela, apenas 2 estrelas podem ser legalmente colocadas na peça inferior).
- R9C12 (se for uma estrela, apenas 2 estrelas podem ser legalmente colocadas na peça em forma de chave ao lado dela).
- Em seguida, R7C13 e R9C13 (deixaria espaço para apenas 1 das 2 estrelas adicionais necessárias nesta forma).

Etapa 5:

Vamos agora tentar colocar as 3 estrelas na forma inferior. Se assumirmos que R13C5 está em branco, logo terminamos com uma contradição onde há apenas espaço para 2 estrelas na linha 12:

Assim, R13C5 deve ser uma estrela, o que nos permite colocar mais algumas estrelas na linha inferior também:

Etapa 6:

Agora considere as 2 colunas finais. Já temos 2 estrelas da forma de anzol. Precisamos de mais 4 - 2 deles devem ser fornecidos pelo quadrado no canto inferior direito (para obter 6 nas duas filas inferiores) e a forma de canto no final do taco de hóquei acima dele. As 2 restantes devem vir da forma que se estende para baixo na borda direita (só há espaço nas outras colunas para colocar 1 das estrelas desta forma).

Isso significa que R8C12 deve ser uma estrela (e R10C13 não pode ser).

Além disso, podemos agora deduzir as posições de 2 estrelas na forma de 'chave', terminando simultaneamente na linha 9.

Enquanto isso, olhando para a coluna 6, podemos ver que deve haver uma estrela em R1C6, com as 2 estrelas restantes para a coluna pertencentes a pares de células separados, cujos quadrados adjacentes podem ser sombreados como vazios.

Etapa 7:

Agora considere as 4 células centrais da grade (destacadas em rosa abaixo):

No máximo, pode haver uma estrela nesta área. Observe então que se colocarmos uma estrela em R13C7 forçamos uma posição que requer 2 estrelas para compartilhar esta área para que as colunas 7 e 8 tenham 3 estrelas - isso é uma contradição, então R13C7 está vazio e, em vez disso, a última estrela em essa forma inferior deve estar na linha 14.

Isso então força uma estrela em R11C14 (uma vez que não pode ser adjacente à estrela que deve ocupar R13C13 ou R13C14) e outra em R8C14, permitindo que as linhas 8, 10 e 11 sejam completadas:

Etapa 8 (última!):

Observe agora que R12C8 deve estar vazio (a terceira estrela neste formato deve estar na linha 13), o que significa que R12C7 deve conter uma estrela, que completa a coluna 7. Agora há apenas uma maneira de completar a linha 7, depois a coluna 8, então coluna 9, coluna 10 e linha 5.

Finalmente, adicione estrelas em R12C11, R6C12, R6C14 e uma última em R13C13 - o quebra-cabeça está finalmente concluído!