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 |
ΣB_{i,j}W_{i,j} = (2 × 0) + (4 × 3) + (8 × 4)+ (2 × 5) + (16 × 6) = 12 + 28 + 10 + 96 = 146 |
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 |
ΣB_{i,j}W_{i,j} = (16 × 14) + (2 × -1) = 224 - 8 = 216 |
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) |
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 |
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 |
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 |
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 |
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^{2} (or better). neighbors()
must be in time proportional to n^{3} (or better). As a bonus, neighbors can be done in n^{2} 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:
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.