Game 2048: Algorithmic Puzzle with Array Reversal Conjugation

Overview

Game 2048 is a Java implementation of the classic sliding-tile puzzle built on the Stanford ACM Graphics Library (acm.jar). The core algorithmic design reduces all four directional moves into a single three-phase 1D array consolidation pipeline (compact → merge → re-compact), with opposite directions unified via array reversal conjugation — reversing the array, applying the canonical left-ward combine, then reversing again. Game-over detection uses a multiplicative triple-product invariant: the product of all cell values × all horizontal differences × all vertical differences is nonzero if and only if no valid move exists. The rendering system maintains a dual-layer board representation — an int[][] model array as the authoritative game state and a parallel GCompound[][] view array of composite graphics objects — with logarithmic color cycling (log2(value) % 6) that automatically scales to arbitrarily high tile values.

Three-Phase Tile Movement Pipeline

Core 1D Consolidation

Every directional move (UP, DOWN, LEFT, RIGHT) is reduced to a 1D array consolidation problem. Rows or columns are extracted from the 4×4 grid, processed through a three-phase pipeline, and written back:

Phase 1 — Compact (moveZerosToEnd): Shifts all non-zero values to the front, pushing zeros to the end via reverse-iteration bubble shift:

private int[] moveZerosToEnd(int[] array) {
    for (int i = length - 1; i >= 0; i--) {
        if (array[i] == 0) {
            for (int j = i; j < length - 1; j++)
                array[j] = array[j+1];
            array[length-1] = 0;
        }
    }
    return array;
}

Phase 2 — Merge (addIdenticalNumbers): After compaction, adjacent equal values are merged by doubling the first and zeroing the second. The left-to-right single-pass correctly prevents chain-merging (e.g., [2,2,2,2] → [4,0,4,0], not [8,0,0,0]):

private int[] addIdenticalNumbers(int[] array) {
    for (int i = 0; i < length - 1; i++) {
        if (array[i] == array[i+1]) {
            array[i] *= 2;
            array[i+1] = 0;
        }
    }
    return array;
}

Phase 3 — Re-compact (moveZerosToEnd again): Zeros created by merging are pushed to the end.

The full pipeline is encapsulated as:

private int[] combineArraytoBeginning(int[] array) {
    return moveZerosToEnd(addIdenticalNumbers(moveZerosToEnd(array)));
}

Array Reversal Conjugation for Directional Symmetry

Rather than implementing four separate movement algorithms, opposite directions are unified via conjugation by reversal — a technique analogous to matrix conjugation in linear algebra:

private int[] combineArraytoEnd(int[] array) {
    return reverseArray(combineArraytoBeginning(reverseArray(array)));
}

Moving “toward the end” = reverse → combine toward beginning → reverse. This cuts the core logic by ~50%.

For UP/DOWN, columns are extracted into temporary 1D arrays via updateColumn(); for LEFT/RIGHT, rows (gridNum[i]) are passed directly via updateRow().

Multiplicative Game-Over Detection

The gameOver() method uses a mathematically elegant triple-product invariant:

private boolean gameOver() {
    int product1 = 1;  // Product of all cell values
    int product2 = 1;  // Product of horizontal differences
    int product3 = 1;  // Product of vertical differences

    for (i, j): product1 *= gridNum[i][j];              // Zero if any cell empty
    for (i, j): product2 *= (gridNum[i][j] - gridNum[i][j+1]);  // Zero if horizontal match
    for (i, j): product3 *= (gridNum[i][j] - gridNum[i+1][j]);  // Zero if vertical match

    return (product1 * product2 * product3 != 0);
}

The game is over if and only if all three products are nonzero simultaneously:

• product1 ≠ 0: No empty cells (all tiles filled)
• product2 ≠ 0: No horizontally adjacent equal tiles (no horizontal merges possible)
• product3 ≠ 0: No vertically adjacent equal tiles (no vertical merges possible)

If ANY condition is unsatisfied, the combined product is zero → game continues. This replaces verbose nested conditionals with a single algebraic expression.

Dual-Layer Board Representation

The game maintains two parallel 4×4 arrays forming a model-view separation:

Full-redraw strategy: After every move, all 16 tiles are removed from the canvas (removeAllSquares()) and redrawn from scratch (updateGraphics()) — a deliberate simplicity tradeoff where the O(n²) cost is negligible for n=4.

Logarithmic Color Cycling

Colors are assigned via log2(value) % 6, creating a cyclic 6-color palette that automatically scales to arbitrarily high tile values without a hardcoded color map:

Empty tiles (value 0) render as LIGHT_GRAY. The logarithmic mapping ensures visually distinct tiles at every power-of-two level while gracefully wrapping at higher values.

Stanford ACM Graphics Library

The application extends GraphicsProgram from Stanford’s acm.jar, which wraps Java AWT/Swing into a pedagogical graphics framework:

Configuration via Interface Constants

All layout parameters are externalized into Game2048Constants, which the main class implements:

public interface Game2048Constants {
    int APPLICATION_WIDTH = 600, APPLICATION_HEIGHT = 800;
    int DIMENSION = 4, WINNING_NUMBER = 2048;
    double SPACE = 10, LOGO_SIZE = 120;
    double SQUARE_SIZE = (APPLICATION_WIDTH - (DIMENSION + 1) * SPACE) / DIMENSION;
}

Using a Java interface for constants means values are implicitly public static final and directly accessible without qualification in implementing classes.

New Tile Spawning

After each move, a single tile with value 2 is placed at a random empty cell via rejection sampling — repeatedly generating random (i, j) coordinates until an empty cell (gridNum[i][j] == 0) is found:

private void addNewNumbers() {
    if (hasEmptySpace()) {
        while (true) {
            int i = rgen.nextInt(0, DIMENSION-1);
            int j = rgen.nextInt(0, DIMENSION-1);
            if (gridNum[i][j] == 0) { gridNum[i][j] = 2; break; }
        }
    }
}

The hasEmptySpace() check uses a multiplicative invariant: the product of all 16 cell values is zero if and only if at least one cell is empty, avoiding explicit branching/short-circuiting.

Event Loop and Win/Loss Detection

public void actionPerformed(ActionEvent e) {
    String cmd = e.getActionCommand();
    if (cmd.equals("UP")) moveUp();
    else if (cmd.equals("DOWN")) moveDown();
    else if (cmd.equals("LEFT")) moveLeft();
    else if (cmd.equals("RIGHT")) moveRight();
    addNewNumbers();
    updateGraphics();
}

Button clicks dispatch directional moves via ActionListener. The win condition checks max >= 2048 but does not terminate play — a congratulatory label appears while the game continues. The game-over condition triggers the triple-product invariant check. The “score” is the maximum tile value on the board, recalculated via full O(n²) scan after every move.

Demo

Tech Stack

Java (8+), Stanford ACM Graphics Library (acm.jar — GraphicsProgram, GCompound, GRect, GLabel, GObject), AWT/Swing (JButton, ActionListener)