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 X
minas 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.
(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.
fonte
{3}
regra" diz " todas essas minas fazem fronteira entre si em um caminho contínuo " - sem bordas, não há caminho.{3}
". Eles não precisam estar conectadosRespostas:
75 vértices,1410 arestas(Gráfico feito com esta ferramenta online e tinta.)
A
-F
são nossos seis nós eJ
é um nó auxiliar. Os três1
nós reforçam que os nós opostos são diferentes, enquanto o2
nó garante queA
,C
eE
não podem ser todas as minas, nem todas vazias.Edit: -2 vértices graças a CalculatorFeline e H.PWiz!
fonte
9 vértices, 17 arestas
Onde ? é uma célula de valor, não é uma das
6
nossas preocupações, precisamos do subgráfico a seguir.Minha habilidade com arte ASCII é terrível.
Com esses 6 vértices configurar:
ABC
podem 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
fonte
A,C,E
vez deA,B,C
.ACE
eBDF
. Nestes, a # de minasACE
é 0 ou 3, mas em uma solução válida é 1 ou 2. Isso permite que você tenha uma pontuação de 5.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.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.
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.fonte
012
sensor? Além disso, eu só contam 6 nós em sua012
C
paraO
, uma vez queC
é noABCDEF