连连看：深度优先搜索实现生成与校验

• 一种校验连连看的算法，使用深度优先算法
• • • entity：btn
    • 校验接口
    • 生成接口
    • 接口实现类
    • 生成实现（完全随机，且未校验棋盘是否可以完成）
    • 生成实现2

public class btn {
//    x,y坐标
    public int x;
    public int y;
//    value判断两个btn是否相等
    public int value;
//    是否已经消去
    public boolean exist;

    public btn(int x, int y, int value, boolean exist) {
        this.x = x;
        this.y = y;
        this.value = value;
        this.exist = exist;
    }

    public btn() {
    }

    public int getX() {
        return x;
    }

    public void setX(int x) {
        this.x = x;
    }

    public int getY() {
        return y;
    }

    public void setY(int y) {
        this.y = y;
    }

    public int getValue() {
        return value;
    }

    public void setValue(int value) {
        this.value = value;
    }

    public boolean isExist() {
        return exist;
    }

    public void setExist(boolean exist) {
        this.exist = exist;
    }

    @Override
    public String toString() {
        return "btn{" +
                "x=" + x +
                ", y=" + y +
                ", value=" + value +
                ", exist=" + exist +
                '}';
    }

    @Override
    public boolean equals(Object o) {
        if (this == o) return true;
        if (o == null || getClass() != o.getClass()) return false;

        btn btn = (btn) o;

        if (x != btn.x) return false;
        if (y != btn.y) return false;
        if (value != btn.value) return false;
        return exist == btn.exist;
    }
}

public interface CheckForAll {

    
    public Boolean Check(btn[][] btns,btn b1, btn b2);

    
    public Boolean isClear(btn[][] btns);

    
    public Boolean CheckAll(btn[][] btns);
}

public interface NewGame {
//    生成一个值为0~4,0~4,顺序随机的数组
    public int[][] NewGame();
}

public class CheckForAllImpl implements CheckForAll {

    
    @Override
    public Boolean Check(btn[][] btns, @NonNull btn b1, @NonNull btn b2) {
        boolean flag = false;
//        判断是否为同一按钮
        if (!b1.equals(b2)){
//            判断是否值相同
            if (b1.getValue() == b2.getValue()) {
//                判断是否已经消去
                if (b1.isExist() && b2.isExist()){
//                    判断是否能连通
                    if(isLink(btns,b1,b2)){
                        flag = true;
                    }
                }
            }
        }
        return flag;
    }

    //    bi = btns.length,bj = btns[0].length
    private static int bi,bj;
    //    标志位,false为未遍历过此格子
    private static boolean[][] flags = new boolean[bi][bj];

    
    @NonNull
    private Boolean isLink(btn[][] btns, btn b1, btn b2) {
//        获取长宽
        bi = btns.length;
        bj = btns[0].length;
        flags = new boolean[bi][bj];
//        若b1,b2均(处于边缘或与边缘相通)
        if (is_Edge(btns,b1) && is_Edge(btns,b2)){
            return true;
        }
//        b1,b2至少有一个不处于边缘或与边缘相通,判断两按钮在不穿过边缘的情况下能否连通
        else {
            return is_Connect(btns, b1, b2);
        }
    }

    @NonNull
    private Boolean is_Edge(@NonNull btn[][] btns, @NonNull btn b) {
//        重置标志位
        for (int i = 0; i < bi; i++) {
            for (int j = 0; j < bj; j++) {
                flags[i][j] = false;
            }
        }
        return isEdge(btns, b);
    }

    
    @NonNull
    private Boolean isEdge(@NonNull btn[][] btns, @NonNull btn b) {
//        若为边缘
        if (b.getX() == 0 || b.getX() == bi - 1 || b.getY() == 0 || b.getY() == bj - 1){
            return true;
        }else {
            int x = b.getX();
            int y = b.getY();
            btn b1 = btns[x-1][y];
            btn b2 = btns[x][y+1];
            btn b3 = btns[x+1][y];
            btn b4 = btns[x][y-1];
//            若不在边缘,不断迭代判断其周围已经消去的button,不再迭代已经迭代过的格子
            if (!flags[x-1][y] && !b1.isExist()){
                flags[x-1][y] = true;
                if (isEdge(btns,b1))
                    return true;
            }
            if (!flags[x][y+1] && !b2.isExist()){
                flags[x][y+1] = true;
                if (isEdge(btns,b2))
                    return true;
            }
            if (!flags[x+1][y] && !b3.isExist()){
                flags[x+1][y] = true;
                if (isEdge(btns,b3))
                    return true;
            }
            if (!flags[x][y-1] && !b4.isExist()){
                flags[x][y-1] = true;
                return isEdge(btns, b4);
            }
        }
        return false;
    }

    @NonNull
    private Boolean is_Connect(@NonNull btn[][] btns, @NonNull btn b1, @NonNull btn b2){
//        重置标志位
        for (int i = 0; i < bi; i++) {
            for (int j = 0; j < bj; j++) {
                flags[i][j] = false;
            }
        }
        return isConnect(btns, b1, b2);
    }

    
    @NonNull
    private Boolean isConnect(@NonNull btn[][] btns, @NonNull btn b1, @NonNull btn b2) {
        int x = b1.getX();
        int y = b1.getY();
//        不断迭代判断其周围已经消去的button的四周有无b2
        if (x != 0){
            btn bt1 = btns[x-1][y];
            if (!flags[x-1][y]){
                flags[x-1][y] = true;
//                若此格未消去
                if (bt1.isExist()){
                    if (bt1.equals(b2)){
                        return true;
                    }
                }else {
                    if (isConnect(btns,bt1,b2)){
                        return true;
                    }
                }
            }
        }
        if (y != bj - 1){
            btn bt2 = btns[x][y+1];
            if (!flags[x][y+1]){
                flags[x][y+1] = true;
                if (bt2.isExist()){
                    if (bt2.equals(b2)){
                        return true;
                    }
                }else {
                    if (isConnect(btns,bt2,b2)){
                        return true;
                    }
                }
            }
        }
        if (x != bi - 1){
            btn bt3 = btns[x+1][y];
            if (!flags[x+1][y]){
                flags[x+1][y] = true;
                if (bt3.isExist()){
                    if (bt3.equals(b2)){
                        return true;
                    }
                }else {
                    if (isConnect(btns,bt3,b2)){
                        return true;
                    }
                }
            }
        }
        if (y != 0){
            btn bt4 = btns[x][y-1];
            if (!flags[x][y-1]){
                flags[x][y-1] = true;
                if (bt4.isExist()){
                    if (bt4.equals(b2)){
                        return true;
                    }
                }else {
                    if (isConnect(btns,bt4,b2)){
                        return true;
                    }
                }
            }
        }
        return false;
    }

    
    @NonNull
    private Boolean isFullLink(@NonNull btn[][] btns, @NonNull btn b1) {
        int x1 = b1.getX();
        int y1 = b1.getY();
//            若被完全包围
        return btns[x1 - 1][y1].isExist() && btns[x1][y1 - 1].isExist()
                && btns[x1 + 1][y1].isExist() && btns[x1][y1 + 1].isExist();
    }

    
    @NonNull
    private Boolean isSide(@NonNull btn[][] btns, @NonNull btn b1, @NonNull btn b2) {
        int x1 = b1.getX();
        int y1 = b1.getY();
        return b2.equals(btns[x1 - 1][y1]) || b2.equals(btns[x1][y1 + 1])
                || b2.equals(btns[x1 + 1][y1]) || b2.equals(btns[x1][y1 - 1]);
    }

    
    @Override
    public Boolean isClear(@NonNull btn[][] btns) {
        for (cn.ljh.link.entity.btn[] btn : btns) {
            for (cn.ljh.link.entity.btn value : btn) {
                if (value.isExist()) {
                    return false;
                }
            }
        }
        return true;
    }

    
    @Override
    public Boolean CheckAll(@NonNull btn[][] _btns) {
        btn[][] btns = _btns.clone();
//        标志位,false为value未遍历过此格子
        boolean[][] flag = new boolean[btns.length][btns[0].length];
        for (cn.ljh.link.entity.btn[] btn : btns) {
            for (cn.ljh.link.entity.btn value : btn) {
                flag[value.getX()][value.getY()] = true;
                for (cn.ljh.link.entity.btn[] item : btns) {
                    for (cn.ljh.link.entity.btn element : item) {
                        if (!flag[element.getX()][element.getY()]) {
                            if (Check(btns, value, element)) {
                                btns[value.getX()][value.getY()].setExist(false);
                                btns[element.getX()][element.getY()].setExist(false);
                                if (isClear(btns)) {
                                    return true;
                                }
                            }
                        }
                    }
                }
            }
        }
        return isClear(btns);
    }
}

public class NewGameImpl implements NewGame {

    
    @Override
    public int[][] NewGame() {
        int[][] game =new int[4][4];
//        初始化数组
        for (int i = 0; i < 2; i++) {
            for (int j = 0; j < 4; j++) {
                game[i][j] = 4 * i + j;
            }
        }
        for (int i = 2; i < 4; i++) {
            for (int j = 0; j < 4; j++) {
                game[i][j] = 4 * (i - 2) + j;
            }
        }
//        打乱数组
        SecureRandom random = new SecureRandom();
        for (int i = 0; i < 4; i++) {
            for (int j = 0; j < 4; j++) {
                int m = random.nextInt(4);
                int n = random.nextInt(4);
                int M = random.nextInt(4);
                int N = random.nextInt(4);
                int temp = game[m][n];
                game[m][n] = game[M][N];
                game[M][N] = temp;
            }
        }
        return game;
    }
}

public class NewGame2Impl implements NewGame2 {

    
    @Override
    public int[][] NewGame2(int i, int j) {

        CheckForAll check = new CheckForAllImpl();

//        棋盘,下标为坐标
        btn[][] chess = new btn[i][j];
//        棋盘每个格子的value,下标为坐标
        int[][] game = new int[i][j];
//        Mark[a][b][c][d] = false:(a,b)(c,d)两格子无法置为value相同
        boolean[][][][] Mark = new boolean[i][j][i][j];
//        存放空格子的坐标
//        2 = (0,2);9 = (3,1)
        List chessList = new ArrayList<>();
//        可以取到的value
        List ValueList = new ArrayList<>();

        for (int a = 0; a < i; a++) {
            for (int b = 0; b < j; b++) {
//                起始格子value置为-1,即为空格子
                game[a][b] = -1;
//                初始化坐标与value
                chess[a][b] = new btn(a, b, -1, false);
            }
        }

//        初始化chessList:0,1,2,...,i * j -1
        for (int k = 0; k < i * j; k++) {
            chessList.add(k);
        }

//        初始化Mark
        for (int k = 0; k < i; k++) {
            for (int l = 0; l < j; l++) {
                for (int m = 0; m < i; m++) {
                    for (int n = 0; n < j; n++) {
                        Mark[k][l][m][n] = true;
                    }
                }
            }
        }

//        初始化value列表:0,0,1,1,2,2,...,n,n
        for (int a = 0; a < (i * j) / 2; a++) {
            for (int k = 0; k < 2; k++) {
                ValueList.add(a);
            }
        }

//        循环加入符合要求的两格
        while (true) {
//        随机找两个空格子,存放其坐标,并从chessList中移除
            int[] canBt = new int[2];
            int[] x = new int[2];
            int[] y = new int[2];
            SecureRandom random = new SecureRandom();
            canBt[0] = chessList.remove(random.nextInt(chessList.size()));
//            若两坐标是同一个或已被标记为value不可相同则重新寻找第二个
            int flag;
            do {
                flag = random.nextInt(chessList.size());
                canBt[1] = chessList.get(flag);
                for (int k = 0; k < 2; k++) {
                    x[k] = canBt[k] / j;
                    y[k] = canBt[k] - j * x[k];
                }
            } while (canBt[1] == canBt[0] || !Mark[x[0]][y[0]][x[1]][y[1]]);
//            取到合适的格子坐标则从chessList中移去
            chessList.remove(flag);
//            实例化两个格子
            btn[] btnTemp = new btn[2];
//            移除可用value中的前两个并赋给btnTemp
            for (int k = 0; k < 2; k++) {
                btnTemp[k] = new btn(x[k], y[k], ValueList.remove(k), true);
            }


//            若仍有空格子则验证新加入的两格
            if (!chessList.isEmpty()) {
//                通过则加入chess,再继续随机两个格子
                if (check.Check(chess, btnTemp[0], btnTemp[1])) {
                    for (int k = 0; k < 2; k++) {
                        chess[x[k]][y[k]] = new btn(x[k], y[k], btnTemp[k].getValue(), true);
                    }
                }
//                若不通过,则回退一步，并做标记，再重新随机两个格子
                else {
                    Mark[x[0]][y[0]][x[1]][y[1]] = false;
                    for (int k = 0; k < 2; k++) {
                        ValueList.add(k, btnTemp[k].getValue());
                        chessList.add(canBt[k]);
                    }
                }
            }
//            若已无空格子，则验证整体,通过则break
            else {
                for (int k = 0; k < 2; k++) {
                    chess[x[k]][y[k]] = new btn(x[k], y[k], btnTemp[k].getValue(), true);
                }
                if (check.CheckAll(chess)) {
                    break;
                }
//                若验证失败,回退到最初
                else {
                    for (int a = 0; a < i; a++) {
                        for (int b = 0; b < j; b++) {
                            game[a][b] = -1;
                            chess[a][b] = new btn(a, b, -1, false);
                        }
                    }
                    for (int k = 0; k < i * j; k++) {
                        chessList.add(k);
                    }
                    for (int k = 0; k < i; k++) {
                        for (int l = 0; l < j; l++) {
                            for (int m = 0; m < i; m++) {
                                for (int n = 0; n < j; n++) {
                                    Mark[k][l][m][n] = true;
                                }
                            }
                        }
                    }
                    for (int a = 0; a < (i * j) / 2; a++) {
                        for (int k = 0; k < 2; k++) {
                            ValueList.add(a);
                        }
                    }
                }
            }
        }

//        返回棋盘的value分布
        for (int k = 0; k < i; k++) {
            for (int l = 0; l < j; l++) {
                game[k][l] = chess[k][l].getValue();
            }
        }
        return game;
    }
}