Hexcellent Minesweeping

13

Hexcells é um jogo baseado no Minesweeper jogado em hexágonos. (Divulgação completa: não tenho nada a ver com Hexcells. Na verdade, eu realmente não gosto do jogo.) A maioria das regras da Hexcells pode ser facilmente expressa no Caça-minas generalizado (o Caça-minas é jogado em um gráfico arbitrário). O que é mais difícil são as regras {X}e -X-.

A {X}regra nos diz que uma célula faz fronteira com Xminas e que todas essas minas fazem fronteira entre si em um caminho contínuo. Por exemplo, se tivéssemos o conselho:

  ?   ?

?  {3}  ?

  ?   ?

As 6 possibilidades para a colocação de minas seriam

  *   .       .   .       .   .       .   *       *   *       *   *

*  {3}  .   *  {3}  .   .  {3}  *   .  {3}  *   .  {3}  *   *  {3}  .

  *   .       *   *       *   *       .   *       .   .       .   .

Seu objetivo é implementar a regra {3}no Campo Minado generalizado.

Específicos

Campo Minado Generalizado é um Campo Minado reproduzido em um gráfico arbitrário. O gráfico possui dois tipos de vértice, um "indicador" ou um "valor". Um valor pode ser ativado ou desativado (uma mina ou um insucesso), porém seu estado é desconhecido para o jogador. Um indicador informa ao jogador quantos vértices adjacentes estão (minas) e não conta como uma mina.

Por exemplo, a seguinte placa para o Campo Minado Generalizado nos diz que as células A e B são minas ou nenhuma delas.

Jogo simples

(No diagrama, os indicadores são marcados em cinza enquanto os valores são em branco)

Diferente do caça-minas normal, em que você clica em valores que estão desativados para revelar indicadores, não existe esse mecânico no caça-minas generalizado. Um jogador simplesmente determina para quais estados do gráfico podem satisfazer seu indicador.

Seu objetivo é criar uma estrutura no Campo Minado Generalizado, de modo que existam 6 células específicas que só podem ter estados que cumpram como se estivessem conectados à regra Hexcells {3}. Ao escrever sua solução, você não deve ter valores específicos em mente para células de valor. (Em resposta à pergunta de H.PWiz, é permitido que algumas células de valor possam ser dedutíveis do estado, mas você sempre pode melhorar sua pontuação removendo essas células)

Pontuação

Suas respostas serão pontuadas pelo número de vértices no gráfico final menos 6 (para as 6 entradas), com uma pontuação menor sendo melhor. Se duas respostas estiverem vinculadas nessa métrica, o desempate será o número de arestas.

Solvabilidade

Esse problema é solucionável, tenho uma solução para esse problema e vou publicá-lo assim que esse desafio tiver uma semana.

Post Rock Garf Hunter
fonte
Então sempre precisa haver 6 arestas entre os 6 vértices de entrada?
Bergi 28/01/19
@Bergi bordas entre as células de valor são redundantes, como eles não têm significado
H.PWiz
@ H.PWiz Mas a " {3}regra" diz " todas essas minas fazem fronteira entre si em um caminho contínuo " - sem bordas, não há caminho.
Bergi
@ Bergi, mas a tarefa é criar um gráfico com 6 células que agem " como se estivessem conectadas à regra das Hexcells {3}". Eles não precisam estar conectados
H.PWiz
1
@Pavel O caça-minas generalizado é uma linguagem de programação para mim. Pode ser muito esotérico, mas não acho que esteja muito longe da prova de golfe .
Post Rock Garf Hunter

Respostas:

15

7 5 vértices, 14 10 arestas

(Gráfico feito com esta ferramenta online e tinta.)

A- Fsão nossos seis nós e Jé um nó auxiliar. Os três 1nós reforçam que os nós opostos são diferentes, enquanto o 2nó garante que A, Ce Enão podem ser todas as minas, nem todas vazias.

Edit: -2 vértices graças a CalculatorFeline e H.PWiz!

Laikoni
fonte
1
Você pode remover 2 vértices.
CalculatorFeline
Observe que a estrutura 2-J também garante que o ACE não esteja todo vazio.
CalculatorFeline
3

9 vértices, 17 arestas

Onde ? é uma célula de valor, não é uma das 6nossas preocupações, precisamos do subgráfico a seguir.

    ___________
?  /    ?      \?
 \|    /|\     /
  3¯¯¯¯ 1 ¯¯¯¯2
  |\    |    /|
  | \ /¯|¯¯¯¯ |
  |  X  |     |
 /  / \_|___  \
A__/    B   \__C

Minha habilidade com arte ASCII é terrível.

Com esses 6 vértices configurar: ABCpodem ter os seguintes estados: 111, 110, 011, 000, 100,001

Com as células correspondentes ao seguinte hexágono, todos nós, em seguida, precisa são mais 3 células indicadoras A-1-D, B-1-E,C-1-F

  B  C
A      D
  F  E
H.PWiz
fonte
Seria muito menor se você fizesse check em A,C,Evez de A,B,C.
CalculatorFeline
@CalculatorFeline eu não posso ver porquê ...
H.PWiz
Se você remover o dispositivo de verificação ABC da sua solução, ele quase funcionará, exceto que também permite ACEe BDF. Nestes, a # de minas ACEé 0 ou 3, mas em uma solução válida é 1 ou 2. Isso permite que você tenha uma pontuação de 5.
CalculatorFeline
@CalculatorFeline Certo, e essa seria a resposta de Laikoni menos 2. Entendo agora. Este é definitivamente difícil transmitir com texto
H.PWiz
@CalculatorFeline Como não contém a ideia principal do meu envio, não o publicarei. Eu acho que Laikoni vai
H.PWiz
3

44 vértices, 66 arestas

Primeiro, começamos com um anel de 6 células de valor, todas conectadas a um 3. Essas células serão as células com a {3}regra.

  A   B
   \ /
F---3---C
   / \
  E   D

Em seguida, conectamos sensores 012 aos pares de células de valor (AB, BC, CD, DE, EF, FA). A estrutura do sensor 012 está abaixo.

O   ?---1---?
 \ /       /
  2---?---1
 / \
A   B

A e B são as entradas para o sensor e O é a saída. O ? células são células de valor genérico. O será uma mina se exatamente um de A e B for uma mina e vazio caso contrário. Em seguida, conectamos um nó 2 a todas as saídas do sensor. Isso garante que haja exatamente 2 pares com exatamente 1 mina e pode-se provar que as únicas configurações que satisfazem isso são as que satisfazem {3}. Cada sensor usa 7 nós, portanto 6 sensores requerem 42. Adicione o 3 nó conectado ao ABCDEF e o 2 nó conectado às saídas e você obterá 44.

Essa solução também pode ser adaptada {1}- {5}alterando o nó 3 para outro valor.

CalculatorFeline
fonte
Quais são as saídas para cada 012sensor? Além disso, eu só contam 6 nós em sua012
H.PWiz
Existe o 2 nó, os 2 1 nós, os 3? nós e C (que não é um dos nós ABCDEF, apenas a saída do sensor).
CalculatorFeline
2
@CalculatorFeline Got-lo, talvez mudar o nome Cpara O, uma vez que C é noABCDEF
H.PWiz
Curiosidade: Esta solução é plana.
CalculatorFeline