Barrido de minas hexcelente

13

Hexcells es un juego basado en Buscaminas jugado en hexágonos. (Divulgación completa: no tengo nada que ver con Hexcells. De hecho, no me gusta mucho el juego.) La mayoría de las reglas de Hexcells se pueden expresar fácilmente en Buscaminas generalizadas (Buscaminas jugado en un gráfico arbitrario). El que es más difícil es el {X}y las -X-reglas.

La {X}regla nos dice que una celda limita con las Xminas y que todas estas minas se bordean entre sí en un camino continuo. Por ejemplo si tuviéramos el tablero:

  ?   ?

?  {3}  ?

  ?   ?

Las 6 posibilidades para la colocación de minas serían

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

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

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

Su objetivo es implementar la regla {3}en el Buscaminas generalizado.

Detalles específicos

Buscaminas generalizado es Buscaminas jugado en un gráfico arbitrario. El gráfico tiene dos tipos de vértice, un "indicador" o un "valor". Un valor puede estar activado o desactivado (una mina o un fracaso), sin embargo, su estado es desconocido para el jugador. Un indicador le dice al jugador cuántos vértices adyacentes hay (minas) y no cuenta como una mina en sí.

Por ejemplo, la siguiente tabla para el Buscaminas generalizado nos dice que las celdas A y B son minas o ninguna de ellas son minas.

Juego simple

(En el diagrama, los indicadores están marcados en gris mientras que los valores son blancos)

A diferencia del dragaminas normal en el que haces clic en valores que están apagados para revelar indicadores, no existe tal mecánica en el Buscaminas generalizado. Un jugador simplemente determina qué estados del gráfico pueden satisfacer su indicador.

Su objetivo es construir una estructura en el Buscaminas generalizado de modo que haya 6 celdas específicas que solo puedan tener estados que se cumplan como si estuvieran conectados con la regla de Hexcells {3}. Cuando escribe su solución, no debe tener en cuenta valores específicos para las celdas de valores. (En respuesta a la pregunta de H.PWiz, se permite que algunas celdas de valor sean deducibles del estado, pero siempre puede mejorar su puntaje eliminando dichas celdas)

Puntuación

Sus respuestas se puntuarán por el número de vértices en el gráfico final menos 6 (para las 6 entradas) con una puntuación más baja mejor. Si dos respuestas empatan en esta métrica, el separador será el número de bordes.

Solubilidad

Este problema es solucionable, tengo una solución a este problema y lo publicaré una vez que este desafío tenga una semana de antigüedad.

Post Rock Garf Hunter
fuente
Entonces, ¿siempre debe haber 6 aristas entre los 6 vértices de entrada?
Bergi
@Bergi bordes entre celdas de valor son redundantes, ya que no tienen significado
H.PWiz
@ H.PWiz Pero la " {3}regla" dice " todas estas minas bordean entre sí en un camino continuo " - sin bordes no hay camino.
Bergi
@Bergi pero la tarea es crear un gráfico tal que sean 6 celdas que actúen " como si estuvieran conectadas con la regla Hexcells {3}". No necesitan estar conectados
H.PWiz
1
@Pavel Generalized minesweeper es un lenguaje de programación en lo que a mí respecta. Puede ser muy esotérico, pero no creo que esté demasiado lejos del golf de prueba .
Post Rock Garf Hunter

Respuestas:

15

7 5 vértices, 14 10 bordes

(Gráfico realizado con esta herramienta y pintura en línea ).

A-F son nuestros seis nodos, y Jes un nodo auxiliar. Los tres 1-nodes hacer cumplir que los nodos opuestos son diferentes, mientras que el 2-node se asegura de que A, Cy Eno pueden ser todas las minas, ni todas vacías.

Editar: -2 vértices gracias a CalculatorFeline y H.PWiz!

Laikoni
fuente
1
Puedes eliminar 2 vértices.
CalculatorFeline
Tenga en cuenta que la estructura 2-J también asegura que ACE no esté todo vacío.
CalculatorFeline
3

9 vértices, 17 bordes

Dónde ? es una celda de valor, que no es una de las que 6nos interesa, necesitamos el siguiente subgrafo.

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

Mi habilidad de arte ASCII es terrible.

Con esos 6 vértices establecieron: ABCpuede tener los siguientes estados: 111, 110, 011, 000, 100,001

Con las células que responden a la hexagonal, a continuación, todo lo que necesitamos son más de 3 células indicadoras A-1-D, B-1-E,C-1-F

  B  C
A      D
  F  E
H.PWiz
fuente
Sería mucho más pequeño si marcaras en A,C,Elugar de A,B,C.
CalculatorFeline
@CalculatorFeline No puedo ver por qué ...
H.PWiz
Si quita el dispositivo de verificación ABC de su solución, casi funciona, excepto que también permite ACEy BDF. En esos, el número de minas en ACEes 0 o 3, pero en una solución válida es 1 o 2. Esto le permite tener una puntuación de 5.
CalculatorFeline
@CalculatorFeline Correcto, y esa sería la respuesta de Laikoni menos 2. Ahora veo. Esto es definitivamente difícil de transmitir con texto
H.PWiz
@CalculatorFeline Dado que no contiene la idea principal de mi envío, no lo publicaré. Creo que Laikoni lo hará
H.PWiz
3

44 vértices, 66 aristas

Primero, comenzamos con un anillo de 6 celdas de valor, todas conectadas a un 3. Estas celdas serán las celdas con la {3}regla.

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

Luego, conectamos sensores 012 a los pares de celdas de valor (AB, BC, CD, DE, EF, FA). La estructura del sensor 012 está debajo.

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

A y B son las entradas al sensor y O es la salida. Los ? Las celdas son celdas de valor genérico. O será una mina si exactamente una de A y B es una mina y de lo contrario estará vacía. Luego, conectamos un nodo 2 a todas las salidas del sensor. Esto asegura que haya exactamente 2 pares con exactamente 1 mina, y se puede probar que las únicas configuraciones que satisfacen esto son las que satisfacen {3}. Cada sensor toma 7 nodos, por lo que 6 sensores requieren 42. Agregue el nodo 3 conectado a ABCDEF y el nodo 2 conectado a las salidas y obtendrá 44.

Esta solución también puede ser adaptado para {1}- {5}al cambiar el nodo 3 a algún otro valor.

CalculadoraFeline
fuente
¿Cuáles son las salidas para cada 012sensor? Además, solo cuento 6 nodos en su012
H.PWiz
Hay 2 nodos, los 2 1 nodos, los 3? nodos y C (que no es uno de los nodos ABCDEF, solo la salida del sensor).
CalculatorFeline
2
@CalculatorFeline Entendido, tal vez cambie el nombre Ca O, ya que C está enABCDEF
H.PWiz
Dato curioso: esta solución es plana.
CalculatorFeline