Project 0: 2048

在这里贴一个线上2048的网站，link
整体代码仓库：github

TASK 1: emptySpaceExists(Board b)

简单来说就是检测面板上是否还有没有数的地方。直接O(n)遍历。

/** Returns true if at least one space on the Board is empty.
 *  Empty spaces are stored as null.
 * */
public static boolean emptySpaceExists(Board b) {
    int length = b.size();
    for(int i = 0; i < length; i++) {
        for(int j = 0; j < length; j++) {
            if(b.tile(i,j)==null) return true;
        }
    }
    return false;
}

TASK 2: maxTileExists(Board b)

是否有数字已经等于2048。和上面一样遍历即可。

/**
 * Returns true if any tile is equal to the maximum valid value.
 * Maximum valid value is given by MAX_PIECE. Note that
 * given a Tile object t, we get its value with t.value().
 */
public static boolean maxTileExists(Board b) {
    int length = b.size();
    for(int i = 0; i < length; i++) {
        for(int j = 0; j < length; j++) {
            if(b.tile(i,j)==null) continue;
            if(b.tile(i,j).value()==MAX_PIECE) return true;
        }
    }
    return false;
}

TASK 3: atLeastOneMoveExists(Board b)

用户起码还能再走一步的检测函数。首先就是如果有空格子一定可以走，其次是如果有相邻的数相同也可以走。

/**
 * Returns true if there are any valid moves on the board.
 * There are two ways that there can be valid moves:
 * 1. There is at least one empty space on the board.
 * 2. There are two adjacent tiles with the same value.
 */
public static boolean atLeastOneMoveExists(Board b) {
    int[] dx = {1, -1, 0, 0};
    int[] dy = {0, 0, 1, -1};
    int length = b.size();
    for(int i = 0; i < length; i++) {
        for(int j = 0; j < length; j++) {
            if(b.tile(i,j)==null) return true;
            else {
                for(int k = 0; k < 4; k++) {
                    int x = i+dx[k];
                    int y = j+dy[k];
                    if(x<0||x>=length||y<0||y>=length) continue;
                    if(b.tile(x,y)==null) return true;
                    if(b.tile(x,y).value()==b.tile(i,j).value()) return true;
                }
            }
        }
    }
    return false;
}

TASK4: Main Task: Building the Game Logic

最主要的逻辑部分。主要实现了根据不同方向进行move操作，使得数字向指定方向移动并合并。
主要规则：

在一次整体移动中，如果两个数合并过了，那么就不能和其他数字进行合并。
每一次合并得到的值也是玩家得到的分数。

解决方案：

分四个方向进行，先完成NORTH方向的移动，其他方向照猫画虎即可。
根据移动方向选择遍历的次序，如向上移动，我们需要从最上方一行进行遍历，移动后保证最上方没有空格子出现。
对于已经合并的位置进行标记，用merge[][]进行了标记。
对于每个已经移动的方块，要及时break退出
由于向指定方向移动的时候只有在搜索到有数字的格子才进行判断并移动，用nullTileRow和nullTileCol进行记录空格子的位置，防止格子的指定方向上只有空格子的方向而没有进行移动的情况发生。

每当move执行都要更改changed为true。

/** Tilt the board toward SIDE. Return true iff this changes the board.
 *
 * 1. If two Tile objects are adjacent in the direction of motion and have
 *    the same value, they are merged into one Tile of twice the original
 *    value and that new value is added to the score instance variable
 * 2. A tile that is the result of a merge will not merge again on that
 *    tilt. So each move, every tile will only ever be part of at most one
 *    merge (perhaps zero).
 * 3. When three adjacent tiles in the direction of motion have the same
 *    value, then the leading two tiles in the direction of motion merge,
 *    and the trailing tile does not.
 * */
public boolean tilt(Side side) {
    boolean changed;
    changed = false;

    // TODO: Modify this.board (and perhaps this.score) to account
    // for the tilt to the Side SIDE. If the board changed, set the
    // changed local variable to true.
    boolean[][] merge = new boolean[board.size()][board.size()];
    if(side==Side.NORTH){
        for(int col = 0; col < board.size(); col++){
            for(int row = board.size()-1; row >= 0; row--){
                Tile t = board.tile(col, row);
                if(t!=null){
                    int nullTileRow=row;
                    boolean tchanged=false;
                    for(int k = row+1; k <=3; k++){
                        Tile above = board.tile(col, k);
                        if(above==null){
                            nullTileRow = k;
                        }
                        else{
                            if(above.value()!=t.value()||merge[col][k]){
                                if(k-1!=row){
                                    board.move(col,k-1,t);
                                    changed = true;
                                    tchanged=true;
                                }
                                break;
                            }
                            else {
                                board.move(col,k,t);
                                merge[col][k]=true;
                                this.score += t.value()*2;
                                changed = true;
                                tchanged=true;
                                break;
                            }
                        }
                    }
                    if(!tchanged){
                        if(nullTileRow!=row) {
                            board.move(col,nullTileRow,t);
                            changed = true;
                        }

                    }
                }
            }
        }
    }
    else if(side==Side.SOUTH){
        for(int col = 0; col < board.size(); col++){
            for(int row = 0; row < board.size(); row++){
                Tile t = board.tile(col, row);
                if(t!=null){
                    int nullTileRow=row;
                    boolean tchanged=false;
                    for(int k = row-1; k >=0; k--){
                        Tile above = board.tile(col, k);
                        if(above==null){
                            nullTileRow = k;
                        }
                        else{
                            if(above.value()!=t.value()||merge[col][k]){
                                if(k+1!=row){
                                    board.move(col,k+1,t);
                                    changed = true;
                                    tchanged=true;
                                }
                                break;
                            }
                            else {
                                board.move(col,k,t);
                                merge[col][k]=true;
                                this.score += t.value()*2;
                                changed = true;
                                tchanged=true;
                                break;
                            }
                        }
                    }
                    if(!tchanged){
                        if(nullTileRow!=row) {
                            board.move(col,nullTileRow,t);
                            changed = true;
                        }

                    }
                }
            }
        }
    }
    else if(side==Side.WEST){
        for(int col = 0; col < board.size(); col++){
            for(int row = board.size()-1; row >= 0; row--){
                Tile t = board.tile(col, row);
                if(t!=null){
                    int nullTileCol=col;
                    boolean tchanged=false;
                    for(int k = col-1; k >= 0; k--){
                        Tile above = board.tile(k, row);
                        if(above==null){
                            nullTileCol = k;
                        }
                        else{
                            if(above.value()!=t.value()||merge[k][row]){
                                if(k+1!=col){
                                    board.move(k+1,row,t);
                                    changed = true;
                                    tchanged=true;
                                }
                                break;
                            }
                            else {
                                board.move(k,row,t);
                                merge[k][row]=true;
                                this.score += t.value()*2;
                                changed = true;
                                tchanged=true;
                                break;
                            }
                        }
                    }
                    if(!tchanged){
                        if(nullTileCol!=col) {
                            board.move(nullTileCol,row,t);
                            changed = true;
                        }

                    }
                }
            }
        }
    }
    else if(side==Side.EAST){
        for(int col = board.size()-1; col >= 0; col--){
            for(int row = board.size()-1; row >= 0; row--){
                Tile t = board.tile(col, row);
                if(t!=null){
                    int nullTileCol=col;
                    boolean tchanged=false;
                    for(int k = col+1; k < board.size(); k++){
                        Tile above = board.tile(k, row);
                        if(above==null){
                            nullTileCol = k;
                        }
                        else{
                            if(above.value()!=t.value()||merge[k][row]){
                                if(k-1!=col){
                                    board.move(k-1,row,t);
                                    changed = true;
                                    tchanged=true;
                                }
                                break;
                            }
                            else {
                                board.move(k,row,t);
                                merge[k][row]=true;
                                this.score += t.value()*2;
                                changed = true;
                                tchanged=true;
                                break;
                            }
                        }
                    }
                    if(!tchanged){
                        if(nullTileCol!=col) {
                            board.move(nullTileCol,row,t);
                            changed = true;
                        }
                    }
                }
            }
        }
    }
    checkGameOver();
    if (changed) {
        setChanged();
    }
    return changed;
}