连接4检查获胜算法

Question

我知道有很多关于连接4检查获胜的问题.问题是大多数其他算法使我的程序有运行时错误,因为它们试图访问我的数组之外的索引.我的算法是这样的:

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 grid

int player = gridTable[rowNum][colNum]; //player ID
int count=0;

// Horizontal check
for (int i=0;i<maxCol;i++)
{
    if (gridTable[rowNum][i]==player)
        count++;
    else
        count=0;

    if (count>=4)
        return 1;
}
//Vertical check
for (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 diagonally
for(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 diagonally
for(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 diagonally
for(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是检查获胜的变量,如果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 delta(运动方向).您可以将其汇总为一个方法......

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));

并能够让它工作.有时候答案不是一个完整的解决方案,而是一个将某人带到一个新地方的想法的种子;)

我进一步增强将包括提供预期连体件的数量,但我很确定这是一个我真的不需要演示的增强;)