Juego de mesa en un tablero de $m\times n$ - ganar estrategia

Question

Dos amigos, $A$$B$, un juego con una sola pieza del juego en un tablero rectangular con $m$ filas y $n$ columnas. $A$ comienza el juego por el movimiento de la pieza del juego desde su punto de partida $(1, 1)$ a $(1, 2)$ o $(2,1)$ i.e uno sólo puede moverse en horisontal o dirección vertical, un paso cada movimiento. No es permitido introducir dos veces. El jugador que no puede hacer cualquier movimiento pierde.

¿Hay alguna estrategia ganadora?

Intuitivamente se siente como que necesita considerar la posibilidad de filas y columnas con la igualdad y la no igualdad de las paridades, y traté de reducir el problema a la menor de los casos, pero no me dio nada. Alguna sugerencia?

Answer 1

Si bien $m$ o $n$ (o ambos) es par, entonces un $m\times n$ directorio puede ser distribuidas por $2\times 1$ rectángulos. Reproductor $A$ tiene una estrategia ganadora: siempre mover la pieza a la otra plaza de la $2\times 1$ rectángulo que se encuentra actualmente. El jugador B se ve obligado a mover la pieza a un nuevo $2\times 1$ rectángulo, y el proceso se repite.

En el caso de que $m$ $n$ son impares, luego de una $m\times n$ junta con la inicial de la esquina de la plaza eliminado puede ser distribuidas por $2\times 1$ rectángulos. El jugador B tiene una estrategia ganadora, que es el mismo que el Jugador a la estrategia anterior: siempre mover la pieza a la otra plaza de la $2\times 1$ rectángulo que se encuentra actualmente. La estrategia está disponible para el Jugador B, en este caso, ya que el Jugador de Un primer movimiento debe colocar la pieza en un nuevo $2\times 1$ rectángulo.

Answer 2

Sí, es una estrategia ganadora. En un juego de dos jugadores con información perfecta que sólo puede terminar en una victoria o una pérdida, es siempre una estrategia ganadora para uno de los jugadores.

Answer 3

Para mantener un seguimiento de lo que las plazas se han utilizado, dicen que las plazas son inicialmente blanco, y el color negro, cuando la pieza sale de ellos. Por lo tanto una posición del juego consiste en una serie de cuadrados negros y un cuadrado blanco que contiene la pieza. Es $A$'s mover si el número de casillas negras es aún.

En principio, puede etiquetar cada posible posición del juego como una victoria para el $A$ o $B$: la posición es una victoria para el jugador cuyo mueve es si hay al menos un movimiento legal que va a una posición que es un triunfo para este jugador, de lo contrario es una victoria para el otro jugador. Comience con las posiciones donde todos pero uno de los cuadrados son de color negro, y trabajar hacia atrás.

Por supuesto, esto no va a ser computacionalmente factible a menos que $m$ $n$ son muy pequeñas, debido a que el número de posiciones posibles es grande.