2048 Assignment

• Checklist
• Submit

Write a program that solves the modified version of the game 2048 using the A* search algorithm.

The modified game. 2048, created by Gabriele Cirulli, is a sliding block game played on a 4-by-4 grid consisting of blank tiles and numbered tiles. This assignment uses a modified version of the game. The player may "swipe" the tiles horizontally or vertically, causing each tile to slide in the given direction until it is stopped by either another tile or the border of the grid. If two tiles that have the same value collide during a move, they are combined to form a new tile that is the sum of the previous tiles. Every turn, a new tile (with a value of 2) spawns in the uppermost empty space in the right column. This means that if the upper-right corner is empty, then the new tile will spawn in that space. If that space is filled, then we look down the right column until we find the first empty space, and the new tile will appear there. If the entire right column is filled, then the move is invalid. The objective is to combine tiles with the same value until the 2048 tile is created, without running out of space on the board.

Board data type. To begin, create a data type that models an n-by-n board with sliding tiles. Implement an immutable data type Board with the following API:

public class Board {

    // create a board from an n-by-n array of tiles and int goal,
    // where tiles[row][col] = tile at (row, col) and goal is the
    // value to win the game
    public Board(int[][] tiles, int goal)

    // string representation of this Board
    public String toString()

    // tile at (row, col) or 0 if blank
    public int tileAt(int row, int col)

    // return the largest tile in the board
    public int largestTile()

    // the total weighted value of the board 
    public int distanceWeightedScore()

    // the weighted value of the board based on two leftmost columns
    public int leftWeightedScore()

    // does this board have a tile equal to the goal or larger?
    public boolean hasWon()

    // all neighboring Boards
    public Iterable<Board> neighbors()

    // unit testing (required)
    public static void main(String[] args)

}

Constructor. You may assume that the constructor receives an n-by-n array containing numbered tiles of powers of 2, with blank tiles represented by 0. If either of the arguments to the constructor are null, throw a java.lang.IllegalArgumentException.

String representation. The toString() method returns a string composed of n + 1 lines. The first line contains the length of a side of the board (n); the remaining n lines contains the n-by-n grid of tiles in row-major order, using 0 to designate blank tiles. For example:

4 32 4 0 2 32 2 4 0 64 2 0 0 128 0 0 0

Tile extraction. Throw a java.lang.IllegalArgumentException in tileAt() unless both row and col are between 0 and n - 1.

Largest tile. This method returns the largest tile on the board. For the example above 128 would be returned.

Distance weighted score. This method is computed by taking the sum of the products of the distance of each tile from the upper-right and the tile value at that location. Assume that the upper-right corner is considered (0, n - 1). The upper-right corner is the least desirable location on the board, and therefore has the smallest weight.

Distance	Board
3 2 1 0 4 3 2 1 5 4 3 2 6 5 4 3	0 0 0 2 0 0 0 0 0 0 0 0 16 2 8 4
ΣBi,jWi,j = (2 × 0) + (4 × 3) + (8 × 4)+ (2 × 5) + (16 × 6) = 12 + 28 + 10 + 96 = 146

Left weighted score. This method is computed by first considering the values in the leftmost column. Each row in the leftmost column receives a non-zero weight value, increasing from the top-left corner. For each row, beginning with row 0, the weight is ((n + 2) × (n + 3) / 2) - 1, where n is the row number. Additionally, we give the bottom-right corner (n - 1, n - 1) a weight value of -1. Then, for every value in the board, multiply it by the corresponding weight and then sum the products. The example below shows the weights when n = 4.

Weights	Board
2 0 0 0 5 0 0 0 9 0 0 0 14 0 0 -1	0 0 0 2 0 0 0 0 0 0 0 0 16 2 8 4
ΣBi,jWi,j = (16 × 14) + (2 × -1) = 224 - 8 = 216

We then also wish to consider the second column. For each row, if the value of the second column is either equal to or exactly half of its adjacent value in the first column, we add it to the sum of the products from the weighted score above.

In the example above there are no such tiles in the second column so 216 is the final score (because neither 2 nor 2 × 2 is equal to 16). We consider another Board below to illustrate calculating the second column.

Board

32 16 2 2 64 16 8 0 128 2 0 0 256 0 0 0

sum = (32 × 2 + 16) + (64 × 5) + (128 × 9) + (256 × 14)

The first 16 is added because 16 × 2 = 32 (the leftmost tile in the same row), but the second 16 is not added because it is not equal to 64 (the leftmost tile in the same row), nor (looking in the third row) is 2 or (2 × 2) equal to 128.

Winning. The hasWon() method will return true if there exists a tile on the board equal to or greater than the goal.

Neighboring boards. The neighbors() method returns an Iterable containing the neighbors of the board. A board can have 1, 2, 3, or 4 neighbors, depending on the number of valid moves. A move is considered valid if it changes the state of the board (as in, it changes the location of one or more tiles, or a merge is performed). For example, in the board shown below, swiping up, left, or right does not change the board state. The only valid move is to swipe down, so only one neighbor exists.

16 8 4 2 0 0 0 0 0 0 0 0 0 0 0 0	swipe up, left, or right ⟶	16 8 4 2 0 0 0 0 0 0 0 0 0 0 0 0
16 8 4 2 0 0 0 0 0 0 0 0 0 0 0 0	swipe down ⟶	0 0 0 0 0 0 0 0 0 0 0 0 16 8 4 2

Merges. Part of the work of neighbors() is to handle all merges. Any adjacent tiles that have the same value are merged. For left and right swipes, this involves adjacent tiles on the same row that have the same value. For up and down swipes, this involves adjacent tiles in the same column that have the same value. Tiles with the same number only separated by empty spaces should also be merged. If there are three adjacent tiles with the same value, you must combine the two tiles closest in the direction of motion. An example is shown below.

0 0 0 0 0 2 2 2 0 0 0 0 4 4 0 4	swipe left ⟶	0 0 0 0 4 2 0 0 0 0 0 0 8 4 0 0
0 0 0 0 0 2 2 2 0 0 0 0 4 4 0 4	swipe right ⟶	0 0 0 0 0 0 2 4 0 0 0 0 0 0 4 8

Swipes. As well as performing any merges, neighbors() shifts the numbered tiles in the direction of the swipe to replace any zero spaces. You may also think about it as shifting the blank tile (zero tiles) in the opposite direction of the swipe. However, if there are no blank tiles in the given row or column, no changes take place. The order of the non-zero tiles does not change.

2 0 4 0 4 2 0 0 0 0 0 0 2 8 4 2

swipe right ⟶

0 0 2 4 0 0 4 2 0 0 0 0 2 8 4 2

Adding tiles. The final part of neighbors() is to add a 2 in the uppermost empty space in the right column. This should occur after each swipe is completed. If there is no room for the tile to be added -- in other words, if the position in the upper-right corner is a non-zero tile, add a 2 tile in the position below and adjacent to the upper-right corner. If all positions in the right column are taken, then this Board is not a valid neighbor. For example, if the board below appeared before the new tile was added, then the board would not be a valid neighbor.

0 0 0 2 0 0 0 4 0 0 0 8 0 0 0 2

Unit testing. Your main() method must call each public method direclty and help verify that they work as prescribed.

Performance requirements. In the worst case, your implementation must support tileAt(), leftWeightedScore(), and distanceWeightedScore() in constant time. The constructor, largestTile(), hasWon(), and toString() must be supported in time proportional to n² (or better). neighbors() must be in time proportional to n³ (or better). As a bonus, neighbors can be done in n² time. Caching is encouraged.

A* search. Now, we describe a solution (to achieve the goal of having a 2048 tile) that illustrates a general artificial intelligence methodology known as the A* search algorithm. We define a search node of the game to be a Board, and the previous search node. First, insert the initial search node (the initial board will have only a 2 in the upper-right corner and empty spaces elsewhere, 0 moves, and a null previous search node) into a priority queue. Then, delete from the priority queue the search node with the maximum priority, and insert onto the priority queue all neighbors to the search node (those that can be reached in one move from the dequeued search node). Repeat this procedure until the search node dequeues a Board that has won.

The efficacy of this approach hinges on the choice of priority function for a serach node. We will consider two different priority functions:

• the first weighted score, which considers the distance of a space on the board from the upper-right corner
• the second weighted score, which considers the leftmost column as well as the second column in relation to the left column

Solver data type In this part, you will implement an A* search to solve the 2048 puzzle. Create an immutable data type Solver with the following API:

public class Solver {

    // find a solution to the initial Board (using the A* algorithm)
    public Solver(Board initial)

    // number of moves to solve initial Board
    public int moves()

    // sequence of Boards in a solution
    public Iterable<Board> solution()

    // test client (see below)
    public static void main(String[] args)

}

Implementation requirement. To implement the A* algorithm, you must use the MaxPQ data type for the priority queue.

Corner case. Throw a java.lang.IllegalArgumentException in the constructor if the argument is null or if the Board is unsolvable. An initial board is determined to be unsolvable when the MaxPQ is empty.

Test client. Your test client should take the goal to reach and the name of an input file as a command-line argument, and print the number of moves to solve the puzzle as well as a corresponding solution. The input file contains the board size n, followed by the n-by-n. grid of tiles, using 0 to designate blank tiles.

% more Board10.txt
4
 256    8    0    2
 256    8   16    2
 512    4    0    0
1024    0    0    0

% java-algs4 Solver 2048 Board10.txt
Minimum number of moves: 3
4
 256    8    0    2
 256    8   16    2
 512    4    0    0
1024    0    0    0

4
   0    0    0    2
 512    0    0    0
 512   16    0    0
1024    4   16    4

4
   0    0    0    2
   0    0    0    0
1024   16    0    2
1024    4   16    4

4
   0    0    0    2
   0    0    0    0
   0   16    0    4
2048    4   16    4

Deliverables Submit the files Board.java and Solver.java. You may not call any library functions other than those in java.lang, java.util, and algs4.jar. Finally, submit a readme.txt file and answer the questions.