¿Cuál es el algoritmo detrás del rompecabezas 2048?

Answer 1

almacene el campo en una matriz bidimensional llamada tablero que es 4 × 4.

1. [2] [0] [8] [2] [2] [4] [8] [4]
2. [0] [4] [0] [2] presione [4] [8] [4] [4]
3. [4] [0] [2] [2] tecla arriba [0] [0] [0] [0]
4. [0] [8] [2] [2] [0] [0] [0] [0]

Pase esta matriz a una función que deslice todo el valor hacia la izquierda, así:

1. [2,0,4,0] => [2,4,0,0]
2. [0,4,0,8] => [4,8,0,0]
3. [8,0,2,2] => [8,4,0,0]
4. [2,2,2,2] => [4,4,0,0]

El algoritmo puede usar el tablero [x] para apuntar a una columna y trabajar directamente en eso. En pseudocódigo, esto es lo que hace el algoritmo:

• – caminar sobre la matriz desde el primero hasta el último número

• – para cada número original en la matriz que no es cero

• – mire hacia atrás para una posición de destino que no contiene un cero (a menos que sea la posición cero)

• – si la posición de destino no contiene el número original, use la siguiente posición

• – si la posición de destino es diferente de la posición original

• – agregue el número al número en la posición de destino

• – reemplace el número original por cero

El algoritmo anterior ejecutado hará todas las transformaciones, hará lo siguiente:

[2,2,2,2] => [4,4,0,0]
[0,8,2,2] => [8,4,0,0]
Pero hay un problema, también hará esto:

[2,2,4,4] => [8,4,0,0]

Los dos se fusionan en un cuatro y luego los primeros cuatro se fusionan en un ocho. Esto está mal. Debería estar haciendo esto:

[2,2,4,4] => [4,8,0,0]

Esto se evita agregando una variable de “detención” que inicialmente se establecerá en cero, pero cuando se haya realizado una fusión, se establecerá en la posición de fusión más uno. Esto asegurará que cualquier próxima diapositiva se detendrá antes de fusionarse nuevamente con este número, ya que no se permiten las dobles fusiones.

Para evitar la programación compleja, uso una función rotateBoard que gira la placa 90 grados en sentido antihorario. Esto permite que moveLeft (tablero) se implemente como:

rotateBoard (tablero);
moveUp (tablero);
rotateBoard (tablero);
rotateBoard (tablero);
rotateBoard (tablero);

Siempre y cuando gire cuatro veces en total, todo funciona como se esperaba. Este método no es muy eficiente, pero reduce la complejidad del código.