连接4检查获胜算法

Question

我知道有很多关于Connect 4 Check获胜的问题。问题在于大多数其他算法使我的程序出现运行时错误，因为它们尝试访问数组之外的索引。我的算法是这样的：private int checkWin(int[][] gridTable,int rowNum,int colNum, int maxRow, int maxCol) {//  For checking whether any win or lose condition is reached. Returns 1 if win or lose is reached. else returns 0//  gridTable[][] is the game matrix(can be any number of rows and columns between 4 and 40)//  colNum is the column number where the last token was placed//  rowNum is the row number where the last token was placed//  maxRow is the number of rows in my grid//  maxCol is the number of columns in my gridint player = gridTable[rowNum][colNum]; //player IDint count=0;// Horizontal checkfor (int i=0;i<maxCol;i++){    if (gridTable[rowNum][i]==player)        count++;    else        count=0;    if (count>=4)        return 1;}//Vertical checkfor (int i=0;i<maxRow;i++){    if (gridTable[i][colNum]==player)        count++;    else        count=0;    if (count>=4)        return 1;} count=0;// 4 in a row diagonallyfor(int i=colNum+1,j=rowNum+1;i<maxRow && j<maxCol;i++,j++) {     if(gridTable[j][i]!=player)    {        count=1;        break;            }    count++;}// 4 in a row diagonallyfor(int i=colNum-1,j=rowNum-1;i>=0 && j>=0;i--,j--) {     if(gridTable[j][i]!=player)    {        count=1;        break;            }    count++;}// 4 in a row diagonallyfor(int i=colNum+1,j=rowNum-1;i<maxRow && j>=0;i++,j--) {     if(gridTable[j][i]!=player)    {        count=1;        break;            }    count++;}for(int i=colNum-1,j=rowNum+1;i>=0 && j<maxCol;i--,j++) { // 4 in a row diagonally    if(gridTable[j][i]!=player)    {        count=1;        break;            }    count++;}if(count>=4)    return 1;return 0;}count是用于检查是否等于或大于4的胜利的变量，这意味着它们应为同一玩家的4个或更多连续标记。问题：有时该方法检查获胜的顺序是否为4个令牌，而有时不检查获胜的顺序为4个令牌。

Answer 1

看起来您的代码对于水平和垂直情况都是正确的。棘手的部分是对角线情况。

让我们尝试一下图片：

在此处输入图片说明

对于绿线，您的起始行位置为0 ... maxRow-4。该列将为0 ... startingRow-

伪代码：

// top-left to bottom-right - green diagonals

for( rowStart = 0; rowStart < rowMax - 4; rowStart++){

    count = 0;

    int row, col;

    for( row = rowStart, col = 0; row < rowMax && col < colMax; row++, col++ ){

        if(gridTable[row][col] == player){

            count++;

            if(count >= 4) return 1;

        }

        else {

            count = 0;

        }

    }

}

// top-left to bottom-right - red diagonals

for( colStart = 1; colStart < colMax - 4; rowStart++){

    count = 0;

    int row, col;

    for( row = 0, col = colStart; row < rowMax && col < colMax; row++, col++ ){

        if(gridTable[row][col] == player){

            count++;

            if(count >= 4) return 1;

        }

        else {

            count = 0;

        }

    }

}

对于对角线的另一种方式（从左下到右上），您可以执行类似的操作。

Answer 2

由于某种原因，我不喜欢计数器，所以我这样做（它适用于不同尺寸的电路板）。

public boolean areFourConnected(int player){

    // horizontalCheck 

    for (int j = 0; j<getHeight()-3 ; j++ ){

        for (int i = 0; i<getWidth(); i++){

            if (this.board[i][j] == player && this.board[i][j+1] == player && this.board[i][j+2] == player && this.board[i][j+3] == player){

                return true;

            }           

        }

    }

    // verticalCheck

    for (int i = 0; i<getWidth()-3 ; i++ ){

        for (int j = 0; j<this.getHeight(); j++){

            if (this.board[i][j] == player && this.board[i+1][j] == player && this.board[i+2][j] == player && this.board[i+3][j] == player){

                return true;

            }           

        }

    }

    // ascendingDiagonalCheck 

    for (int i=3; i<getWidth(); i++){

        for (int j=0; j<getHeight()-3; j++){

            if (this.board[i][j] == player && this.board[i-1][j+1] == player && this.board[i-2][j+2] == player && this.board[i-3][j+3] == player)

                return true;

        }

    }

    // descendingDiagonalCheck

    for (int i=3; i<getWidth(); i++){

        for (int j=3; j<getHeight(); j++){

            if (this.board[i][j] == player && this.board[i-1][j-1] == player && this.board[i-2][j-2] == player && this.board[i-3][j-3] == player)

                return true;

        }

    }

    return false;

}

Answer 3

因此，浏览完您的代码后，似乎对角线检查只能在一个方向上获胜（如果我在最低行和最低列中添加标记，会发生什么情况？）

而是，基本检查算法始终是相同的过程，而不管您要检查的方向是什么。

您需要一个起点（x / y）和x / y增量（运动方向）。您可以将其归纳为一个方法...

public boolean didWin(int[][] grid, int check, int row, int col, int rowDelta, int colDelta) {

    boolean win = true;

    for (int count = 0; count < 4; count++) {

        if (row < ROWS && row >= 0 && col < COLUMNS && col >= 0) {

            int test = grid[row][col];

            if (test != check) {

                win = false;

                break;

            }

        }

        row += rowDelta;

        col += colDelta;

    }

    return win;

}

基本上，您可以从四个方向检查，也可以向后检查

所以，如果我们要使用类似...

int[][] gridTable = new int[ROWS][COLUMNS];

gridTable[ROWS - 1][3] = 1;

gridTable[ROWS - 2][3] = 1;

gridTable[ROWS - 3][3] = 1;

gridTable[ROWS - 4][3] = 1;

System.out.println("Vertical");

System.out.println(didWin(gridTable, 1, ROWS - 4, 3, 1, 0) ? "Win" : "Lose");

System.out.println(didWin(gridTable, 1, ROWS - 1, 3, -1, 0) ? "Win" : "Lose");

System.out.println(didWin(gridTable, 1, 0, 3, 1, 0) ? "Win" : "Lose");

gridTable = new int[ROWS][COLUMNS];

gridTable[3][1] = 1;

gridTable[3][2] = 1;

gridTable[3][3] = 1;

gridTable[3][4] = 1;

System.out.println("");

System.out.println("Horizontal");

System.out.println(didWin(gridTable, 1, 3, 1, 0, 1) ? "Win" : "Lose");

System.out.println(didWin(gridTable, 1, 3, 4, 0, -1) ? "Win" : "Lose");

System.out.println(didWin(gridTable, 1, 3, 0, 0, 1) ? "Win" : "Lose");

gridTable = new int[ROWS][COLUMNS];

gridTable[0][1] = 1;

gridTable[1][2] = 1;

gridTable[2][3] = 1;

gridTable[3][4] = 1;

System.out.println("");

System.out.println("Diag");

System.out.println(didWin(gridTable, 1, 0, 1, 1, 1) ? "Win" : "Lose");

System.out.println(didWin(gridTable, 1, 3, 4, -1, -1) ? "Win" : "Lose");

System.out.println(didWin(gridTable, 1, 1, 2, 1, 1) ? "Win" : "Lose");

哪个输出...

Vertical

Win

Win

Lose

Horizontal

Win

Win

Lose

Diag

Win

Win

Lose

现在，您可以将其总结为...

public boolean didWin(int[][] grid, int check, int row, int col) {

    return didWin(grid, check, row, col, 1, 0) ||

                    didWin(grid, check, row, col, -1, 0) ||

                    didWin(grid, check, row, col, 0, 1) ||

                    didWin(grid, check, row, col, 0, -1) ||

                    didWin(grid, check, row, col, 1, 1) ||

                    didWin(grid, check, row, col, -1, -1) ||

                    didWin(grid, check, row, col, -1, 1) ||

                    didWin(grid, check, row, col, 1, -1);

}

因此，使用类似...

int[][] gridTable = new int[ROWS][COLUMNS];

gridTable[ROWS - 1][3] = 1;

gridTable[ROWS - 2][3] = 1;

gridTable[ROWS - 3][3] = 1;

gridTable[ROWS - 4][3] = 1;

System.out.println("Vertical");

System.out.println(didWin(gridTable, 1, ROWS - 1, 3) ? "Win" : "Lose");

System.out.println(didWin(gridTable, 1, ROWS - 4, 3) ? "Win" : "Lose");

gridTable = new int[ROWS][COLUMNS];

gridTable[3][1] = 1;

gridTable[3][2] = 1;

gridTable[3][3] = 1;

gridTable[3][4] = 1;

System.out.println("");

System.out.println("Horizontal");

System.out.println(didWin(gridTable, 1, 3, 1) ? "Win" : "Lose");

System.out.println(didWin(gridTable, 1, 3, 4) ? "Win" : "Lose");

gridTable = new int[ROWS][COLUMNS];

gridTable[0][1] = 1;

gridTable[1][2] = 1;

gridTable[2][3] = 1;

gridTable[3][4] = 1;

System.out.println("");

System.out.println("Diag");

System.out.println(didWin(gridTable, 1, 0, 1) ? "Win" : "Lose");

System.out.println(didWin(gridTable, 1, 3, 4) ? "Win" : "Lose");

哪个打印出类似...

Vertical

Win

Win

Horizontal

Win

Win

Diag

Win

Win

我要补充一点，这种方法仅在您连续提供4个芯片的正确开始时才有效。例如didWin（gridTable，1，3，3）将为水平检查提供false而不是true，因为循环只能检查一个方向。

这样做的目的不是提供“完整的，即装即用的”解决方案，而是提供一个可以开发更广泛的解决方案的概念（我是说，我讨厌人们实际上不得不思考；）。我还基于以下想法设计了解决方案：OP将知道最后一块放置在哪里，即起点；）

通过didWin稍微修改一下方法，就可以从任何点检查n逐个n网格...

public boolean didWin(int[][] grid, int check, int row, int col, int rowDelta, int colDelta) {

    boolean match = false;

    int matches = 0;

    while (row < ROWS && row >= 0 && col < COLUMNS && col >= 0) {

        int test = grid[row][col];

        if (test != check && match) {

            break;

        } else if (test == check) {

            match = true;

            matches++;

        }

        row += rowDelta;

        col += colDelta;

    }

    return matches == 4;

}

所以，我用...

public static final int ROWS = 8;

public static final int COLUMNS = 8;

//...

int[][] gridTable = new int[ROWS][COLUMNS];

gridTable[ROWS - 1][3] = 1;

gridTable[ROWS - 2][3] = 1;

gridTable[ROWS - 3][3] = 1;

gridTable[ROWS - 4][3] = 1;

for (int[] row : gridTable) {

    StringJoiner sj = new StringJoiner("|", "|", "|");

    for (int col : row) {

        sj.add(Integer.toString(col));

    }

    System.out.println(sj);

}

System.out.println(didWin(gridTable, 1, 3, 3));

并能够使其正常工作。有时答案不是一个完整的解决方案，而是将某人带到新地方的想法的种子；）

我将进一步增强功能，包括提供预期的连接件数量，但是我很确定这是我真的不需要演示的增强功能；）