¿De cuántas formas diferentes puedes resolver el juego de la clavija del barril de galletas? ¿Y existe una disposición inicial óptima de las clavijas?

Question

El juego de la clavija del barril de galleta es un juego de mesa estratégico que se burla de su confianza en que el jugador no ganará. Déjeme explicarle...

Aquí está la configuración del juego:

El juego en sí es un bloque triangular con 15 agujeros. Estos agujeros están en filas paralelas; comenzando con 1 agujero en la parte superior, luego 2, luego 3, y así sucesivamente hasta que haya 5 agujeros en la parte inferior. El jugador recibe 14 clavijas que puede colocar de la forma que quiera al principio de la partida, siempre que quede un agujero vacío.

Aquí hay una imagen como referencia:

Las reglas son simples:

1. 14 de los 15 agujeros deben tener una clavija para empezar.
2. Sólo se puede mover una clavija a la vez.
3. Para realizar un movimiento, la clavija elegida debe saltar por encima de otra clavija y entrar en un espacio vacío.
4. Una vez que la clavija elegida está colocada en su nuevo agujero, la clavija que ha saltado debe ser retirada del bloque triangular.
5. Sigue saltando clavijas hasta que ya no puedas hacer ningún movimiento.
6. Sólo se puede saltar una clavija a la vez.
7. No se puede saltar sobre agujeros vacíos.
8. No se pueden mover clavijas a agujeros vacíos adyacentes a menos que se haya saltado una clavija distinta.
9. Una vez realizados todos los movimientos... si sólo queda una ficha, ¡has ganado!

Así de engreído es el juego...

• "Deja sólo una eres un genio"
• "Deja dos y eres muy inteligente"
• "Deja tres y eres simplemente tonto"
• "Deja cuatro o más, y eres simplemente 'EG-NO-RA-MOOSE'"

Se trata de comentarios realmente escritos en el tablero de juego, que puede verse en la imagen superior.

Entrar en este juego sin una estrategia te dejará la mayoría de las veces con tres o cuatro clavijas.

Conozco una forma de superar el juego que he encontrado en internet:

• Mueve la clavija 4 a la posición 1.

• Mueve la clavija 6 a la posición 4.

• Mueve la clavija 1 a la posición 6.

• Mueve la clavija 7 a la posición 2.

• Mueve la clavija 13 a la posición 4.

• Mueve la clavija 2 a la posición 7.

• Mueve la clavija 10 a la posición 8.

• Mueve la clavija 7 a la posición 9.

• Mueve la clavija 15 a la posición 13.

• Coloque la clavija 12 en la posición 14.

• Mueve la clavija 6 a la posición 13.

• Mueve la clavija 14 a la posición 12.

• Mueve la clavija 11 a la posición 13.

Aquí está el enlace: https://blog.crackerbarrel.com/2021/08/13/how-to-solve-the-cracker-barrel-peg-game/

Enumeran una forma más de resolver, pero es imposible que sólo haya dos formas de ganar este juego. Por favor, díganme cuántas formas hay de ganar y cómo debo colocar mis clavijas al principio para tener las máximas posibilidades de ganar. :)

Answer 1

Creo que se puede escribir un programa de ordenador para resolver esto, con retroceso para encontrar todas las soluciones posibles.

El pseudocódigo sería:

N = 2 # or whatever number of pins left you consider a solution
solutions = []

def solve(position, moves):
  if no_legal_move(position):
    if count(position) <= N:
      solutions.append(moves)
    else:
      for move in legal_moves(p):
        solve(make_move(p, move), moves + [move])

def main():
  # There should only be 15 starting positions, as there are only 15 initial holes you can have
  for starting positions p in P:
    solve(p), [p])

Creo que esto es más bien una cuestión de CS.

En términos de complejidad, parece que puedes tener como máximo 2 movimientos posibles por etapa, por lo que no hay tantos conjuntos de movimientos por los que pasar, ya que 2^14 es un número relativamente pequeño para los ordenadores.