Algorithmus zur Bestimmung des Tic Tac Toe Game Over

97

Ich habe ein Tic-Tac-Toe-Spiel in Java geschrieben, und meine derzeitige Methode zur Bestimmung des Spielendes berücksichtigt die folgenden möglichen Szenarien für das Ende des Spiels:

  1. Das Brett ist voll und es wurde noch kein Gewinner bekannt gegeben: Das Spiel ist unentschieden.
  2. Cross hat gewonnen.
  3. Kreis hat gewonnen.

Leider liest es dazu einen vordefinierten Satz dieser Szenarien aus einer Tabelle. Dies ist nicht unbedingt schlecht, wenn man bedenkt, dass sich nur 9 Felder auf einem Brett befinden und der Tisch daher etwas klein ist. Gibt es jedoch eine bessere algorithmische Methode, um festzustellen, ob das Spiel beendet ist? Die Feststellung, ob jemand gewonnen hat oder nicht, ist das Kernstück des Problems, da die Überprüfung, ob 9 Felder voll sind, trivial ist.

Die Tabellenmethode könnte die Lösung sein, aber wenn nicht, was ist das? Was wäre, wenn das Board keine Größe hätte n=9? Was ist, wenn es ein viel größeres Bord ist, sagt ihnen n=16, n=25und so weiter, die Anzahl der hintereinander abgestellte Gegenstände verursacht zu gewinnen zu sein x=4, x=5etc? Ein allgemeiner Algorithmus für alle n = { 9, 16, 25, 36 ... }?

Dreadwail
quelle
Ich addiere meine 2 Cent für alle Antworten: Sie wissen immer, dass Sie mindestens eine Anzahl von Xs oder Os auf dem Brett benötigen, um zu gewinnen (im normalen 3x3-Brett ist es das 3). Sie können also die Anzahl der einzelnen Titel verfolgen und nur dann nach Gewinnen suchen, wenn diese höher sind.
Yuval A.

Antworten:

133

Sie wissen, dass ein Gewinnzug nur stattfinden kann, nachdem X oder O den letzten Zug ausgeführt haben. Sie können also nur Zeilen / Spalten mit optionalem Diagramm durchsuchen, die in diesem Zug enthalten sind, um Ihren Suchraum zu begrenzen, wenn Sie versuchen, ein Gewinnbrett zu bestimmen. Da es in einem Draw-Tic-Tac-Toe-Spiel eine feste Anzahl von Zügen gibt, sobald der letzte Zug ausgeführt wurde, ist es standardmäßig ein Draw-Spiel, wenn es kein Gewinnzug war.

Bearbeiten: Dieser Code ist für ein n mal n Board mit n in einer Reihe zu gewinnen (3x3 Board erfordert 3 in einer Reihe usw.)

Bearbeiten: Code hinzugefügt, um Anti-Diag zu überprüfen. Ich konnte keinen Weg ohne Schleife finden, um festzustellen, ob sich der Punkt auf dem Anti-Diag befand. Deshalb fehlt dieser Schritt

public class TripleT {

    enum State{Blank, X, O};

    int n = 3;
    State[][] board = new State[n][n];
    int moveCount;

    void Move(int x, int y, State s){
        if(board[x][y] == State.Blank){
            board[x][y] = s;
        }
        moveCount++;

        //check end conditions

        //check col
        for(int i = 0; i < n; i++){
            if(board[x][i] != s)
                break;
            if(i == n-1){
                //report win for s
            }
        }

        //check row
        for(int i = 0; i < n; i++){
            if(board[i][y] != s)
                break;
            if(i == n-1){
                //report win for s
            }
        }

        //check diag
        if(x == y){
            //we're on a diagonal
            for(int i = 0; i < n; i++){
                if(board[i][i] != s)
                    break;
                if(i == n-1){
                    //report win for s
                }
            }
        }

        //check anti diag (thanks rampion)
        if(x + y == n - 1){
            for(int i = 0; i < n; i++){
                if(board[i][(n-1)-i] != s)
                    break;
                if(i == n-1){
                    //report win for s
                }
            }
        }

        //check draw
        if(moveCount == (Math.pow(n, 2) - 1)){
            //report draw
        }
    }
}
Hardwareguy
quelle
6
Sie haben vergessen, die Antidiagonale zu überprüfen.
Rampion
1
Bei einem 3x3-Board ist x + y in der Antidiagonale immer gleich 2, in der Mitte und in den Ecken des Boards immer gerade und an anderer Stelle ungerade.
Chris Doggett
5
Ich verstehe den Draw Check am Ende nicht, sollte er nicht 1 subtrahieren?
Inez
4
Es gibt Fälle, in denen ein Spieler im letztmöglichen (9.) Zug gewinnt. In diesem Fall werden sowohl ein Gewinner als auch ein Unentschieden gemeldet ...
Marc
5
@ Roamer-1888 Es geht nicht darum, aus wie vielen Zeilen Ihre Lösung besteht, sondern darum, die zeitliche Komplexität des Algorithmus zu verringern, um nach einem Gewinner zu suchen.
Shady
38

Sie können ein magisches Quadrat verwenden http://mathworld.wolfram.com/MagicSquare.html Wenn eine Zeile, Spalte oder Diag 15 ergibt, hat ein Spieler gewonnen.

adk
quelle
3
Wie überträgt sich das auf das Tic-Tac-Toe-Spiel?
Paul Alexander
Es ist eine nette Information, die ich nicht kannte, also danke ich Ihnen auf jeden Fall für die Information. Wie Paul erwähnte, ist nicht sofort klar, wie dies zur Lösung des vorliegenden Problems beitragen würde, aber es scheint, als würde es Teil einer vollständigeren Lösung sein.
Dreadwail
4
überlagern. 1 für Weiß, 2 für Schwarz und multiplizieren. Wenn etwas zu 15 herauskommt, hat Weiß gewonnen, und wenn es zu 30 herausgekommen ist, hat Schwarz gewonnen.
adk
1
Big O-weise, es ist ziemlich billig, besonders wenn man es mit Hardwareguys zellweiser Überprüfung mischt. Jede Zelle kann sich nur in 4 möglichen Tic-Tac-Toes befinden: zeilenweise, spaltenweise und zwei Diagonalen (Schrägstrich und Backslash). Sobald ein Zug gemacht wurde, müssen Sie höchstens 4 Ergänzungen und Vergleiche vornehmen. Die Antwort von Hardwareguy erfordert im Vergleich dazu 4 (n-1) Prüfungen für jeden Zug.
Rampion
29
Könnten wir das nicht einfach mit 1 und -1 machen und jede Zeile / Spalte / Diag summieren, um zu sehen, ob es n oder -n ist?
Nathan
24

Wie wäre es mit diesem Pseudocode:

Nachdem ein Spieler eine Figur an Position (x, y) abgelegt hat:

col=row=diag=rdiag=0
winner=false
for i=1 to n
  if cell[x,i]=player then col++
  if cell[i,y]=player then row++
  if cell[i,i]=player then diag++
  if cell[i,n-i+1]=player then rdiag++
if row=n or col=n or diag=n or rdiag=n then winner=true

Ich würde ein Array von char [n, n] mit O, X und Leerzeichen verwenden.

  1. einfach.
  2. Eine Schleife.
  3. Fünf einfache Variablen: 4 Ganzzahlen und ein Boolescher Wert.
  4. Skaliert auf jede Größe von n.
  5. Überprüft nur das aktuelle Stück.
  6. Keine Magie. :) :)
Osama Al-Maadeed
quelle
wenn Zelle [i, n- (i + 1)] = Spieler, dann rdiag ++; - Sieht aus wie mit Klammern wird es richtig sein. Habe ich recht?
Pumych
@Pumych, nein. Wenn i==1und n==3, rdiagmuss überprüft werden (1, 3)und (1, 3-1+1)ist gleich den richtigen Koordinaten, aber (1, 3-(1+1))nein.
KgOfHedgehogs
Er hätte denken können, dass die Zellen nullindexiert waren.
Matias Grioni
Es war nur ein paar Dinge auf meinem Kopf ... es muss während des eigentlichen Schreibens von Code behoben werden :)
Osama Al-Maadeed
21

Dies ähnelt der Antwort von Osama ALASSIRY, tauscht jedoch konstanten Raum und lineare Zeit gegen linearen Raum und konstante Zeit. Das heißt, nach der Initialisierung gibt es keine Schleife.

Initialisieren Sie ein Paar (0,0)für jede Zeile, jede Spalte und die beiden Diagonalen (Diagonale und Antidiagonale). Diese Paare repräsentieren die Ansammlung (sum,sum)der Teile in der entsprechenden Zeile, Spalte oder Diagonale, wobei

Ein Stück von Spieler A hat einen Wert (1,0)
Ein Stück von Spieler B hat den Wert (0,1)

Wenn ein Spieler eine Figur platziert, aktualisieren Sie das entsprechende Zeilen-, Spalten- und Diagonalpaar (falls auf den Diagonalen). Wenn ein neu aktualisiertes Zeilen-, Spalten- oder Diagonalpaar gleich (n,0)oder (0,n)entweder A oder B gewonnen hat.

Asymptotische Analyse:

O (1) Zeit (pro Zug)
O (n) Raum (insgesamt)

Für die Speichernutzung verwenden Sie 4*(n+1)Ganzzahlen.

zwei_Elemente * n_Zeile + zwei_Elemente * n_Spalten +
zwei_Elemente * zwei_Diagonale = 4 * n + 4 ganze Zahlen = 4 (n + 1) ganze Zahlen

Übung: Können Sie sehen, wie Sie in O (1) Zeit pro Zug auf ein Unentschieden testen? In diesem Fall können Sie das Spiel frühzeitig mit einem Unentschieden beenden.

CJ Gaconnet
quelle
1
Ich denke, das ist besser als das von Osama ALASSIRY, da es ungefähr O(sqrt(n))Zeit ist, aber nach jedem Zug gemacht werden muss, wobei n die Größe des Bretts ist. So enden Sie mit O(n^1.5). Für diese Lösung haben Sie O(n)insgesamt Zeit.
Matias Grioni
Eine gute Sichtweise, es ist sinnvoll, sich die tatsächlichen "Lösungen" anzusehen ... für 3x3 hätten Sie nur 8 Paare von "Booleschen Werten" ... Es kann noch platzsparender sein, wenn es jeweils 2 Bits wären ... 16 Bit benötigt und Sie können nur bitweise ODER 1 im richtigen Player nach links an die richtige Stelle verschieben :)
Osama Al-Maadeed
13

Hier ist meine Lösung, die ich für ein Projekt geschrieben habe, an dem ich in Javascript arbeite. Wenn Ihnen die Speicherkosten einiger Arrays nichts ausmachen, ist dies wahrscheinlich die schnellste und einfachste Lösung, die Sie finden werden. Es wird davon ausgegangen, dass Sie die Position des letzten Zuges kennen.

/*
 * Determines if the last move resulted in a win for either player
 * board: is an array representing the board
 * lastMove: is the boardIndex of the last (most recent) move
 *  these are the boardIndexes:
 *
 *   0 | 1 | 2
 *  ---+---+---
 *   3 | 4 | 5
 *  ---+---+---
 *   6 | 7 | 8
 * 
 * returns true if there was a win
 */
var winLines = [
    [[1, 2], [4, 8], [3, 6]],
    [[0, 2], [4, 7]],
    [[0, 1], [4, 6], [5, 8]],
    [[4, 5], [0, 6]],
    [[3, 5], [0, 8], [2, 6], [1, 7]],
    [[3, 4], [2, 8]],
    [[7, 8], [2, 4], [0, 3]],
    [[6, 8], [1, 4]],
    [[6, 7], [0, 4], [2, 5]]
];
function isWinningMove(board, lastMove) {
    var player = board[lastMove];
    for (var i = 0; i < winLines[lastMove].length; i++) {
        var line = winLines[lastMove][i];
        if(player === board[line[0]] && player === board[line[1]]) {
            return true;
        }
    }
    return false;
}
Jack Allan
quelle
2
Dies wäre der Big-Hammer-Ansatz, aber es ist in der Tat eine praktikable Lösung, insbesondere für den Standort als eine von vielen kreativen und funktionierenden Lösungen für dieses Problem. Auch es ist kurz, elegant und sehr gut lesbar - für ein 3x3-Raster (traditionelles Tx3) mag ich diesen Algorithmus.
Nocarrier
Dieser ist super !! Ich fand heraus, dass es einen kleinen Fehler in den Gewinnmustern gibt, bei Besitz 8 sollten die Muster [6,7], [0,4] und [2,5] sein: var winLines = [[[1, 2] , [4, 8], [3, 6]], [[0, 2], [4, 7]], [[0, 1], [4, 6], [5, 8]], [[ 4, 5], [0, 6]], [[3, 5], [0, 8], [2, 6], [1, 7]], [[3, 4], [2, 8] ], [[7, 8], [2, 4], [0, 3]], [[6, 8], [1, 4]], [[6, 7], [ 0 , 4], [ 2, 5]]];
David Ruiz
7

Ich habe das gerade für meine C-Programmierklasse geschrieben.

Ich poste es, weil keines der anderen Beispiele hier mit einem rechteckigen Raster beliebiger Größe und einer beliebigen Anzahl N- in-einer Reihe aufeinanderfolgender Markierungen funktioniert , um zu gewinnen.

Sie finden meinen Algorithmus, so wie er ist, in der checkWinner()Funktion. Es werden keine magischen Zahlen oder irgendetwas Besonderes verwendet, um nach einem Gewinner zu suchen, es werden einfach vier für Schleifen verwendet - Der Code ist gut kommentiert, also werde ich ihn für sich selbst sprechen lassen, denke ich.

// This program will work with any whole number sized rectangular gameBoard.
// It checks for N marks in straight lines (rows, columns, and diagonals).
// It is prettiest when ROWS and COLS are single digit numbers.
// Try altering the constants for ROWS, COLS, and N for great fun!    

// PPDs come first

    #include <stdio.h>
    #define ROWS 9              // The number of rows our gameBoard array will have
    #define COLS 9              // The number of columns of the same - Single digit numbers will be prettier!
    #define N 3                 // This is the number of contiguous marks a player must have to win
    #define INITCHAR ' '        // This changes the character displayed (a ' ' here probably looks the best)
    #define PLAYER1CHAR 'X'     // Some marks are more aesthetically pleasing than others
    #define PLAYER2CHAR 'O'     // Change these lines if you care to experiment with them


// Function prototypes are next

    int playGame    (char gameBoard[ROWS][COLS]);               // This function allows the game to be replayed easily, as desired
    void initBoard  (char gameBoard[ROWS][COLS]);               // Fills the ROWSxCOLS character array with the INITCHAR character
    void printBoard (char gameBoard[ROWS][COLS]);               // Prints out the current board, now with pretty formatting and #s!
    void makeMove   (char gameBoard[ROWS][COLS], int player);   // Prompts for (and validates!) a move and stores it into the array
    int checkWinner (char gameBoard[ROWS][COLS], int player);   // Checks the current state of the board to see if anyone has won

// The starting line
int main (void)
{
    // Inits
    char gameBoard[ROWS][COLS];     // Our gameBoard is declared as a character array, ROWS x COLS in size
    int winner = 0;
    char replay;

    //Code
    do                              // This loop plays through the game until the user elects not to
    {
        winner = playGame(gameBoard);
        printf("\nWould you like to play again? Y for yes, anything else exits: ");

        scanf("%c",&replay);        // I have to use both a scanf() and a getchar() in
        replay = getchar();         // order to clear the input buffer of a newline char
                                    // (http://cboard.cprogramming.com/c-programming/121190-problem-do-while-loop-char.html)

    } while ( replay == 'y' || replay == 'Y' );

    // Housekeeping
    printf("\n");
    return winner;
}


int playGame(char gameBoard[ROWS][COLS])
{
    int turn = 0, player = 0, winner = 0, i = 0;

    initBoard(gameBoard);

    do
    {
        turn++;                                 // Every time this loop executes, a unique turn is about to be made
        player = (turn+1)%2+1;                  // This mod function alternates the player variable between 1 & 2 each turn
        makeMove(gameBoard,player);
        printBoard(gameBoard);
        winner = checkWinner(gameBoard,player);

        if (winner != 0)
        {
            printBoard(gameBoard);

            for (i=0;i<19-2*ROWS;i++)           // Formatting - works with the default shell height on my machine
                printf("\n");                   // Hopefully I can replace these with something that clears the screen for me

            printf("\n\nCongratulations Player %i, you've won with %i in a row!\n\n",winner,N);
            return winner;
        }

    } while ( turn < ROWS*COLS );                           // Once ROWS*COLS turns have elapsed

    printf("\n\nGame Over!\n\nThere was no Winner :-(\n");  // The board is full and the game is over
    return winner;
}


void initBoard (char gameBoard[ROWS][COLS])
{
    int row = 0, col = 0;

    for (row=0;row<ROWS;row++)
    {
        for (col=0;col<COLS;col++)
        {
            gameBoard[row][col] = INITCHAR;     // Fill the gameBoard with INITCHAR characters
        }
    }

    printBoard(gameBoard);                      // Having this here prints out the board before
    return;                             // the playGame function asks for the first move
}


void printBoard (char gameBoard[ROWS][COLS])    // There is a ton of formatting in here
{                                               // That I don't feel like commenting :P
    int row = 0, col = 0, i=0;                  // It took a while to fine tune
                                                // But now the output is something like:
    printf("\n");                               // 
                                                //    1   2   3
    for (row=0;row<ROWS;row++)                  // 1    |   |
    {                                           //   -----------
        if (row == 0)                           // 2    |   |
        {                                       //   -----------
            printf("  ");                       // 3    |   |

            for (i=0;i<COLS;i++)
            {
                printf(" %i  ",i+1);
            }

            printf("\n\n");
        }

        for (col=0;col<COLS;col++)
        {
            if (col==0)
                printf("%i ",row+1);

            printf(" %c ",gameBoard[row][col]);

            if (col<COLS-1)
                printf("|");
        }

        printf("\n");

        if (row < ROWS-1)
        {
            for(i=0;i<COLS-1;i++)
            {
                if(i==0)
                    printf("  ----");
                else
                    printf("----");
            }

            printf("---\n");
        }
    }

    return;
}


void makeMove (char gameBoard[ROWS][COLS],int player)
{
    int row = 0, col = 0, i=0;
    char currentChar;

    if (player == 1)                    // This gets the correct player's mark
        currentChar = PLAYER1CHAR;
    else
        currentChar = PLAYER2CHAR;

    for (i=0;i<21-2*ROWS;i++)           // Newline formatting again :-(
        printf("\n");

    printf("\nPlayer %i, please enter the column of your move: ",player);
    scanf("%i",&col);
    printf("Please enter the row of your move: ");
    scanf("%i",&row);

    row--;                              // These lines translate the user's rows and columns numbering
    col--;                              // (starting with 1) to the computer's (starting with 0)

    while(gameBoard[row][col] != INITCHAR || row > ROWS-1 || col > COLS-1)  // We are not using a do... while because
    {                                                                       // I wanted the prompt to change
        printBoard(gameBoard);
        for (i=0;i<20-2*ROWS;i++)
            printf("\n");
        printf("\nPlayer %i, please enter a valid move! Column first, then row.\n",player);
        scanf("%i %i",&col,&row);

        row--;                          // See above ^^^
        col--;
    }

    gameBoard[row][col] = currentChar;  // Finally, we store the correct mark into the given location
    return;                             // And pop back out of this function
}


int checkWinner(char gameBoard[ROWS][COLS], int player)     // I've commented the last (and the hardest, for me anyway)
{                                                           // check, which checks for backwards diagonal runs below >>>
    int row = 0, col = 0, i = 0;
    char currentChar;

    if (player == 1)
        currentChar = PLAYER1CHAR;
    else
        currentChar = PLAYER2CHAR;

    for ( row = 0; row < ROWS; row++)                       // This first for loop checks every row
    {
        for ( col = 0; col < (COLS-(N-1)); col++)           // And all columns until N away from the end
        {
            while (gameBoard[row][col] == currentChar)      // For consecutive rows of the current player's mark
            {
                col++;
                i++;
                if (i == N)
                {
                    return player;
                }
            }
            i = 0;
        }
    }

    for ( col = 0; col < COLS; col++)                       // This one checks for columns of consecutive marks
    {
        for ( row = 0; row < (ROWS-(N-1)); row++)
        {
            while (gameBoard[row][col] == currentChar)
            {
                row++;
                i++;
                if (i == N)
                {
                    return player;
                }
            }
            i = 0;
        }
    }

    for ( col = 0; col < (COLS - (N-1)); col++)             // This one checks for "forwards" diagonal runs
    {
        for ( row = 0; row < (ROWS-(N-1)); row++)
        {
            while (gameBoard[row][col] == currentChar)
            {
                row++;
                col++;
                i++;
                if (i == N)
                {
                    return player;
                }
            }
            i = 0;
        }
    }
                                                        // Finally, the backwards diagonals:
    for ( col = COLS-1; col > 0+(N-2); col--)           // Start from the last column and go until N columns from the first
    {                                                   // The math seems strange here but the numbers work out when you trace them
        for ( row = 0; row < (ROWS-(N-1)); row++)       // Start from the first row and go until N rows from the last
        {
            while (gameBoard[row][col] == currentChar)  // If the current player's character is there
            {
                row++;                                  // Go down a row
                col--;                                  // And back a column
                i++;                                    // The i variable tracks how many consecutive marks have been found
                if (i == N)                             // Once i == N
                {
                    return player;                      // Return the current player number to the
                }                                       // winnner variable in the playGame function
            }                                           // If it breaks out of the while loop, there weren't N consecutive marks
            i = 0;                                      // So make i = 0 again
        }                                               // And go back into the for loop, incrementing the row to check from
    }

    return 0;                                           // If we got to here, no winner has been detected,
}                                                       // so we pop back up into the playGame function

// The end!

// Well, almost.

// Eventually I hope to get this thing going
// with a dynamically sized array. I'll make
// the CONSTANTS into variables in an initGame
// function and allow the user to define them.
mattR
quelle
Sehr hilfreich. Ich habe versucht, etwas Effizienteres zu finden. Wenn Sie beispielsweise N = COL = ROW kennen, können Sie dies auf etwas viel Einfacheres reduzieren, aber ich habe nichts Effizienteres für eine beliebige Boardgröße und N.
Hassan
6

Wenn die Tafel n × n ist, gibt es n Zeilen, n Spalten und 2 Diagonalen. Überprüfen Sie jedes dieser Elemente auf All-X oder All-O, um einen Gewinner zu finden.

Wenn es nur x < n aufeinanderfolgende Quadrate braucht , um zu gewinnen, ist es etwas komplizierter. Die naheliegendste Lösung besteht darin, jedes x × x- Quadrat auf einen Gewinner zu überprüfen . Hier ist ein Code, der das demonstriert.

(Habe ich nicht getestet tatsächlich diesen * hust *, aber es ist die Kompilierung auf dem ersten Versuch, yay me!)

public class TicTacToe
{
    public enum Square { X, O, NONE }

    /**
     * Returns the winning player, or NONE if the game has
     * finished without a winner, or null if the game is unfinished.
     */
    public Square findWinner(Square[][] board, int lengthToWin) {
        // Check each lengthToWin x lengthToWin board for a winner.    
        for (int top = 0; top <= board.length - lengthToWin; ++top) {
            int bottom = top + lengthToWin - 1;

            for (int left = 0; left <= board.length - lengthToWin; ++left) {
                int right = left + lengthToWin - 1;

                // Check each row.
                nextRow: for (int row = top; row <= bottom; ++row) {
                    if (board[row][left] == Square.NONE) {
                        continue;
                    }

                    for (int col = left; col <= right; ++col) {
                        if (board[row][col] != board[row][left]) {
                            continue nextRow;
                        }
                    }

                    return board[row][left];
                }

                // Check each column.
                nextCol: for (int col = left; col <= right; ++col) {
                    if (board[top][col] == Square.NONE) {
                        continue;
                    }

                    for (int row = top; row <= bottom; ++row) {
                        if (board[row][col] != board[top][col]) {
                            continue nextCol;
                        }
                    }

                    return board[top][col];
                }

                // Check top-left to bottom-right diagonal.
                diag1: if (board[top][left] != Square.NONE) {
                    for (int i = 1; i < lengthToWin; ++i) {
                        if (board[top+i][left+i] != board[top][left]) {
                            break diag1;
                        }
                    }

                    return board[top][left];
                }

                // Check top-right to bottom-left diagonal.
                diag2: if (board[top][right] != Square.NONE) {
                    for (int i = 1; i < lengthToWin; ++i) {
                        if (board[top+i][right-i] != board[top][right]) {
                            break diag2;
                        }
                    }

                    return board[top][right];
                }
            }
        }

        // Check for a completely full board.
        boolean isFull = true;

        full: for (int row = 0; row < board.length; ++row) {
            for (int col = 0; col < board.length; ++col) {
                if (board[row][col] == Square.NONE) {
                    isFull = false;
                    break full;
                }
            }
        }

        // The board is full.
        if (isFull) {
            return Square.NONE;
        }
        // The board is not full and we didn't find a solution.
        else {
            return null;
        }
    }
}
John Kugelman
quelle
Ich verstehe was du meinst. In einem traditionellen n = x-Spiel würde es (n * n * 2) Gesamtantworten geben. Dies würde jedoch nicht funktionieren, wenn x (die Anzahl der zum Gewinnen erforderlichen aufeinanderfolgenden Spiele) kleiner als n wäre. Es ist eine gute Lösung, ich mag es besser als die Tabelle für seine Erweiterbarkeit.
Dreadwail
Ich habe die Möglichkeit von x <n im ursprünglichen Beitrag nicht erwähnt, daher ist Ihre Antwort immer noch genau richtig.
Dreadwail
4

Ich kenne Java nicht so gut, aber ich kenne C, also habe ich die magische Quadratidee von adk ausprobiert (zusammen mit der Suchbeschränkung von Hardwareguy ).

// tic-tac-toe.c
// to compile:
//  % gcc -o tic-tac-toe tic-tac-toe.c
// to run:
//  % ./tic-tac-toe
#include <stdio.h>

// the two types of marks available
typedef enum { Empty=2, X=0, O=1, NumMarks=2 } Mark;
char const MarkToChar[] = "XO ";

// a structure to hold the sums of each kind of mark
typedef struct { unsigned char of[NumMarks]; } Sum;

// a cell in the board, which has a particular value
#define MAGIC_NUMBER 15
typedef struct {
  Mark mark;
  unsigned char const value;
  size_t const num_sums;
  Sum * const sums[4];
} Cell;

#define NUM_ROWS 3
#define NUM_COLS 3

// create a sum for each possible tic-tac-toe
Sum row[NUM_ROWS] = {0};
Sum col[NUM_COLS] = {0};
Sum nw_diag = {0};
Sum ne_diag = {0};

// initialize the board values so any row, column, or diagonal adds to
// MAGIC_NUMBER, and so they each record their sums in the proper rows, columns,
// and diagonals
Cell board[NUM_ROWS][NUM_COLS] = { 
  { 
    { Empty, 8, 3, { &row[0], &col[0], &nw_diag } },
    { Empty, 1, 2, { &row[0], &col[1] } },
    { Empty, 6, 3, { &row[0], &col[2], &ne_diag } },
  },
  { 
    { Empty, 3, 2, { &row[1], &col[0] } },
    { Empty, 5, 4, { &row[1], &col[1], &nw_diag, &ne_diag } },
    { Empty, 7, 2, { &row[1], &col[2] } },
  },
  { 
    { Empty, 4, 3, { &row[2], &col[0], &ne_diag } },
    { Empty, 9, 2, { &row[2], &col[1] } },
    { Empty, 2, 3, { &row[2], &col[2], &nw_diag } },
  }
};

// print the board
void show_board(void)
{
  size_t r, c;
  for (r = 0; r < NUM_ROWS; r++) 
  {
    if (r > 0) { printf("---+---+---\n"); }
    for (c = 0; c < NUM_COLS; c++) 
    {
      if (c > 0) { printf("|"); }
      printf(" %c ", MarkToChar[board[r][c].mark]);
    }
    printf("\n");
  }
}


// run the game, asking the player for inputs for each side
int main(int argc, char * argv[])
{
  size_t m;
  show_board();
  printf("Enter moves as \"<row> <col>\" (no quotes, zero indexed)\n");
  for( m = 0; m < NUM_ROWS * NUM_COLS; m++ )
  {
    Mark const mark = (Mark) (m % NumMarks);
    size_t c, r;

    // read the player's move
    do
    {
      printf("%c's move: ", MarkToChar[mark]);
      fflush(stdout);
      scanf("%d %d", &r, &c);
      if (r >= NUM_ROWS || c >= NUM_COLS)
      {
        printf("illegal move (off the board), try again\n");
      }
      else if (board[r][c].mark != Empty)
      {
        printf("illegal move (already taken), try again\n");
      }
      else
      {
        break;
      }
    }
    while (1);

    {
      Cell * const cell = &(board[r][c]);
      size_t s;

      // update the board state
      cell->mark = mark;
      show_board();

      // check for tic-tac-toe
      for (s = 0; s < cell->num_sums; s++)
      {
        cell->sums[s]->of[mark] += cell->value;
        if (cell->sums[s]->of[mark] == MAGIC_NUMBER)
        {
          printf("tic-tac-toe! %c wins!\n", MarkToChar[mark]);
          goto done;
        }
      }
    }
  }
  printf("stalemate... nobody wins :(\n");
done:
  return 0;
}

Es kompiliert und testet gut.

% gcc -o tic-tac-toe tic-tac-toe.c
% ./tic-tac-toe
     | |
  --- + --- + ---
     | |
  --- + --- + ---
     | |
  Züge eingeben als "" (keine Anführungszeichen, null indiziert)
  Xs Zug: 1 2
     | |
  --- + --- + ---
     | | X.
  --- + --- + ---
     | |
  O's Zug: 1 2
  illegaler Umzug (bereits unternommen), versuchen Sie es erneut
  O's Zug: 3 3
  illegaler Zug (vom Brett), versuchen Sie es erneut
  O's Zug: 2 2
     | |
  --- + --- + ---
     | | X.
  --- + --- + ---
     | | Ö
  Xs Zug: 1 0
     | |
  --- + --- + ---
   X | | X.
  --- + --- + ---
     | | Ö
  O's Zug: 1 1
     | |
  --- + --- + ---
   X | O | X.
  --- + --- + ---
     | | Ö
  Xs Zug: 0 0
   X | |
  --- + --- + ---
   X | O | X.
  --- + --- + ---
     | | Ö
  O's Zug: 2 0
   X | |
  --- + --- + ---
   X | O | X.
  --- + --- + ---
   O | | Ö
  Xs Zug: 2 1
   X | |
  --- + --- + ---
   X | O | X.
  --- + --- + ---
   O | X | Ö
  O's Zug: 0 2
   X | | Ö
  --- + --- + ---
   X | O | X.
  --- + --- + ---
   O | X | Ö
  Tic-Tac-Toe! O gewinnt!
% ./tic-tac-toe
     | |
  --- + --- + ---
     | |
  --- + --- + ---
     | |
  Züge eingeben als "" (keine Anführungszeichen, null indiziert)
  Xs Zug: 0 0
   X | |
  --- + --- + ---
     | |
  --- + --- + ---
     | |
  O's Zug: 0 1
   X | O |
  --- + --- + ---
     | |
  --- + --- + ---
     | |
  Xs Zug: 0 2
   X | O | X.
  --- + --- + ---
     | |
  --- + --- + ---
     | |
  O's Zug: 1 0
   X | O | X.
  --- + --- + ---
   O | |
  --- + --- + ---
     | |
  Xs Zug: 1 1
   X | O | X.
  --- + --- + ---
   O | X |
  --- + --- + ---
     | |
  O's Zug: 2 0
   X | O | X.
  --- + --- + ---
   O | X |
  --- + --- + ---
   O | |
  Xs Zug: 2 1
   X | O | X.
  --- + --- + ---
   O | X |
  --- + --- + ---
   O | X |
  O's Zug: 2 2
   X | O | X.
  --- + --- + ---
   O | X |
  --- + --- + ---
   O | X | Ö
  Xs Zug: 1 2
   X | O | X.
  --- + --- + ---
   O | X | X.
  --- + --- + ---
   O | X | Ö
  Patt ... niemand gewinnt :(
%.

Das hat Spaß gemacht, danke!

Wenn Sie darüber nachdenken, brauchen Sie kein magisches Quadrat, nur eine Zählung für jede Zeile / Spalte / Diagonale. Dies ist etwas einfacher als das Verallgemeinern eines magischen Quadrats auf n× nMatrizen, da Sie nur bis zählen müssen n.

Rampion
quelle
3

Die gleiche Frage wurde mir in einem meiner Interviews gestellt. Meine Gedanken: Initialisieren Sie die Matrix mit 0. Behalten Sie 3 Arrays 1) sum_row (Größe n) 2) sum_column (Größe n) 3) diagonal (Größe 2)

Für jede Bewegung um (X) dekrementieren Sie den Feldwert um 1 und für jede Bewegung um (0) erhöhen Sie ihn um 1. Zu jedem Zeitpunkt, wenn die Zeile / Spalte / Diagonale, die in der aktuellen Bewegung geändert wurde, entweder -3 oder + summiert 3 bedeutet, dass jemand das Spiel gewonnen hat. Für eine Auslosung können wir den obigen Ansatz verwenden, um die moveCount-Variable beizubehalten.

Glaubst du, mir fehlt etwas?

Bearbeiten: Gleiches kann für die nxn-Matrix verwendet werden. Die Summe sollte gerade +3 oder -3 sein.

Piyush Beli
quelle
2

eine Methode ohne Schleife, um festzustellen, ob sich der Punkt auf dem Anti-Diag befand:

`if (x + y == n - 1)`
Jeff
quelle
2

Ich bin spät dran, aber ich wollte auf einen Vorteil hinweisen, den ich bei der Verwendung eines magischen Quadrats festgestellt habe , nämlich dass es verwendet werden kann, um einen Verweis auf das Quadrat zu erhalten, das den Gewinn oder Verlust in der nächsten Runde verursachen würde, anstatt wird nur verwendet, um zu berechnen, wann ein Spiel vorbei ist.

Nimm dieses magische Quadrat:

4 9 2
3 5 7
8 1 6

Richten Sie zunächst ein scoresArray ein, das bei jeder Verschiebung erhöht wird. Siehe diese Antwort für Details. Wenn wir nun illegal zweimal hintereinander X bei [0,0] und [0,1] spielen, scoressieht das Array folgendermaßen aus:

[7, 0, 0, 4, 3, 0, 4, 0];

Und das Board sieht so aus:

X . .
X . .
. . .

Dann müssen wir nur noch Folgendes tun, um einen Hinweis darauf zu erhalten, auf welchem ​​Quadrat wir gewinnen / blockieren sollen:

get_winning_move = function() {
  for (var i = 0, i < scores.length; i++) {
    // keep track of the number of times pieces were added to the row
    // subtract when the opposite team adds a piece
    if (scores[i].inc === 2) {
      return 15 - state[i].val; // 8
    }
  }
}

In der Realität erfordert die Implementierung einige zusätzliche Tricks, wie den Umgang mit nummerierten Schlüsseln (in JavaScript), aber ich fand es ziemlich einfach und genoss die Freizeitmathematik.

gwg
quelle
1

Ich habe einige Optimierungen in den Zeilen-, Spalten- und Diagonalprüfungen vorgenommen. Es wird hauptsächlich in der ersten verschachtelten Schleife entschieden, ob eine bestimmte Spalte oder Diagonale überprüft werden muss. So vermeiden wir die Überprüfung von Spalten oder Diagonalen, was Zeit spart. Dies hat große Auswirkungen, wenn die Platinengröße größer ist und eine erhebliche Anzahl der Zellen nicht gefüllt ist.

Hier ist der Java-Code dafür.

    int gameState(int values[][], int boardSz) {


    boolean colCheckNotRequired[] = new boolean[boardSz];//default is false
    boolean diag1CheckNotRequired = false;
    boolean diag2CheckNotRequired = false;
    boolean allFilled = true;


    int x_count = 0;
    int o_count = 0;
    /* Check rows */
    for (int i = 0; i < boardSz; i++) {
        x_count = o_count = 0;
        for (int j = 0; j < boardSz; j++) {
            if(values[i][j] == x_val)x_count++;
            if(values[i][j] == o_val)o_count++;
            if(values[i][j] == 0)
            {
                colCheckNotRequired[j] = true;
                if(i==j)diag1CheckNotRequired = true;
                if(i + j == boardSz - 1)diag2CheckNotRequired = true;
                allFilled = false;
                //No need check further
                break;
            }
        }
        if(x_count == boardSz)return X_WIN;
        if(o_count == boardSz)return O_WIN;         
    }


    /* check cols */
    for (int i = 0; i < boardSz; i++) {
        x_count = o_count = 0;
        if(colCheckNotRequired[i] == false)
        {
            for (int j = 0; j < boardSz; j++) {
                if(values[j][i] == x_val)x_count++;
                if(values[j][i] == o_val)o_count++;
                //No need check further
                if(values[i][j] == 0)break;
            }
            if(x_count == boardSz)return X_WIN;
            if(o_count == boardSz)return O_WIN;
        }
    }

    x_count = o_count = 0;
    /* check diagonal 1 */
    if(diag1CheckNotRequired == false)
    {
        for (int i = 0; i < boardSz; i++) {
            if(values[i][i] == x_val)x_count++;
            if(values[i][i] == o_val)o_count++;
            if(values[i][i] == 0)break;
        }
        if(x_count == boardSz)return X_WIN;
        if(o_count == boardSz)return O_WIN;
    }

    x_count = o_count = 0;
    /* check diagonal 2 */
    if( diag2CheckNotRequired == false)
    {
        for (int i = boardSz - 1,j = 0; i >= 0 && j < boardSz; i--,j++) {
            if(values[j][i] == x_val)x_count++;
            if(values[j][i] == o_val)o_count++;
            if(values[j][i] == 0)break;
        }
        if(x_count == boardSz)return X_WIN;
        if(o_count == boardSz)return O_WIN;
        x_count = o_count = 0;
    }

    if( allFilled == true)
    {
        for (int i = 0; i < boardSz; i++) {
            for (int j = 0; j < boardSz; j++) {
                if (values[i][j] == 0) {
                    allFilled = false;
                    break;
                }
            }

            if (allFilled == false) {
                break;
            }
        }
    }

    if (allFilled)
        return DRAW;

    return INPROGRESS;
}
sanjiv
quelle
1

Ich mag diesen Algorithmus, da er eine 1x9 vs 3x3 Darstellung des Boards verwendet.

private int[] board = new int[9];
private static final int[] START = new int[] { 0, 3, 6, 0, 1, 2, 0, 2 };
private static final int[] INCR  = new int[] { 1, 1, 1, 3, 3, 3, 4, 2 };
private static int SIZE = 3;
/**
 * Determines if there is a winner in tic-tac-toe board.
 * @return {@code 0} for draw, {@code 1} for 'X', {@code -1} for 'Y'
 */
public int hasWinner() {
    for (int i = 0; i < START.length; i++) {
        int sum = 0;
        for (int j = 0; j < SIZE; j++) {
            sum += board[START[i] + j * INCR[i]];
        }
        if (Math.abs(sum) == SIZE) {
            return sum / SIZE;
        }
    }
    return 0;
}
Scott Duchin
quelle
1
Ich mag diesen Ansatz am meisten. Es hätte geholfen, wenn Sie erklärt hätten, was "Start" und "Inkr" bedeuten. (Es ist eine Möglichkeit, alle "Zeilen" als
Startindex
Bitte fügen Sie weitere Erklärungen hinzu. Wie sind Sie auf diesen Code gekommen?
Farzan
0

Eine weitere Option: Generieren Sie Ihre Tabelle mit Code. Bis zur Symmetrie gibt es nur drei Möglichkeiten, um zu gewinnen: Kantenreihe, mittlere Reihe oder Diagonale. Nehmen Sie diese drei und drehen Sie sie auf jede mögliche Weise:

def spin(g): return set([g, turn(g), turn(turn(g)), turn(turn(turn(g)))])
def turn(g): return tuple(tuple(g[y][x] for y in (0,1,2)) for x in (2,1,0))

X,s = 'X.'
XXX = X, X, X
sss = s, s, s

ways_to_win = (  spin((XXX, sss, sss))
               | spin((sss, XXX, sss))
               | spin(((X,s,s),
                       (s,X,s),
                       (s,s,X))))

Diese Symmetrien können in Ihrem Spielcode mehr Verwendung finden: Wenn Sie zu einem Brett gelangen, von dem Sie bereits eine gedrehte Version gesehen haben, können Sie einfach den zwischengespeicherten Wert oder den zwischengespeicherten besten Zug von diesem nehmen (und ihn zurückdrehen). Dies ist normalerweise viel schneller als die Auswertung des Spielunterbaums.

(Das Umdrehen nach links und rechts kann auf die gleiche Weise helfen. Dies wurde hier nicht benötigt, da die Rotationsmenge der Gewinnmuster spiegelsymmetrisch ist.)

Darius Bacon
quelle
0

Hier ist eine Lösung, die ich mir ausgedacht habe: Sie speichert die Symbole als Zeichen und verwendet den int-Wert des Zeichens, um herauszufinden, ob X oder O gewonnen hat (siehe Code des Schiedsrichters).

public class TicTacToe {
    public static final char BLANK = '\u0000';
    private final char[][] board;
    private int moveCount;
    private Referee referee;

    public TicTacToe(int gridSize) {
        if (gridSize < 3)
            throw new IllegalArgumentException("TicTacToe board size has to be minimum 3x3 grid");
        board = new char[gridSize][gridSize];
        referee = new Referee(gridSize);
    }

    public char[][] displayBoard() {
        return board.clone();
    }

    public String move(int x, int y) {
        if (board[x][y] != BLANK)
            return "(" + x + "," + y + ") is already occupied";
        board[x][y] = whoseTurn();
        return referee.isGameOver(x, y, board[x][y], ++moveCount);
    }

    private char whoseTurn() {
        return moveCount % 2 == 0 ? 'X' : 'O';
    }

    private class Referee {
        private static final int NO_OF_DIAGONALS = 2;
        private static final int MINOR = 1;
        private static final int PRINCIPAL = 0;
        private final int gridSize;
        private final int[] rowTotal;
        private final int[] colTotal;
        private final int[] diagonalTotal;

        private Referee(int size) {
            gridSize = size;
            rowTotal = new int[size];
            colTotal = new int[size];
            diagonalTotal = new int[NO_OF_DIAGONALS];
        }

        private String isGameOver(int x, int y, char symbol, int moveCount) {
            if (isWinningMove(x, y, symbol))
                return symbol + " won the game!";
            if (isBoardCompletelyFilled(moveCount))
                return "Its a Draw!";
            return "continue";
        }

        private boolean isBoardCompletelyFilled(int moveCount) {
            return moveCount == gridSize * gridSize;
        }

        private boolean isWinningMove(int x, int y, char symbol) {
            if (isPrincipalDiagonal(x, y) && allSymbolsMatch(symbol, diagonalTotal, PRINCIPAL))
                return true;
            if (isMinorDiagonal(x, y) && allSymbolsMatch(symbol, diagonalTotal, MINOR))
                return true;
            return allSymbolsMatch(symbol, rowTotal, x) || allSymbolsMatch(symbol, colTotal, y);
        }

        private boolean allSymbolsMatch(char symbol, int[] total, int index) {
            total[index] += symbol;
            return total[index] / gridSize == symbol;
        }

        private boolean isPrincipalDiagonal(int x, int y) {
            return x == y;
        }

        private boolean isMinorDiagonal(int x, int y) {
            return x + y == gridSize - 1;
        }
    }
}

Auch hier sind meine Unit-Tests, um zu überprüfen, ob es tatsächlich funktioniert

import static com.agilefaqs.tdd.demo.TicTacToe.BLANK;
import static org.junit.Assert.assertArrayEquals;
import static org.junit.Assert.assertEquals;

import org.junit.Test;

public class TicTacToeTest {
    private TicTacToe game = new TicTacToe(3);

    @Test
    public void allCellsAreEmptyInANewGame() {
        assertBoardIs(new char[][] { { BLANK, BLANK, BLANK },
                { BLANK, BLANK, BLANK },
                { BLANK, BLANK, BLANK } });
    }

    @Test(expected = IllegalArgumentException.class)
    public void boardHasToBeMinimum3x3Grid() {
        new TicTacToe(2);
    }

    @Test
    public void firstPlayersMoveMarks_X_OnTheBoard() {
        assertEquals("continue", game.move(1, 1));
        assertBoardIs(new char[][] { { BLANK, BLANK, BLANK },
                { BLANK, 'X', BLANK },
                { BLANK, BLANK, BLANK } });
    }

    @Test
    public void secondPlayersMoveMarks_O_OnTheBoard() {
        game.move(1, 1);
        assertEquals("continue", game.move(2, 2));
        assertBoardIs(new char[][] { { BLANK, BLANK, BLANK },
                { BLANK, 'X', BLANK },
                { BLANK, BLANK, 'O' } });
    }

    @Test
    public void playerCanOnlyMoveToAnEmptyCell() {
        game.move(1, 1);
        assertEquals("(1,1) is already occupied", game.move(1, 1));
    }

    @Test
    public void firstPlayerWithAllSymbolsInOneRowWins() {
        game.move(0, 0);
        game.move(1, 0);
        game.move(0, 1);
        game.move(2, 1);
        assertEquals("X won the game!", game.move(0, 2));
    }

    @Test
    public void firstPlayerWithAllSymbolsInOneColumnWins() {
        game.move(1, 1);
        game.move(0, 0);
        game.move(2, 1);
        game.move(1, 0);
        game.move(2, 2);
        assertEquals("O won the game!", game.move(2, 0));
    }

    @Test
    public void firstPlayerWithAllSymbolsInPrincipalDiagonalWins() {
        game.move(0, 0);
        game.move(1, 0);
        game.move(1, 1);
        game.move(2, 1);
        assertEquals("X won the game!", game.move(2, 2));
    }

    @Test
    public void firstPlayerWithAllSymbolsInMinorDiagonalWins() {
        game.move(0, 2);
        game.move(1, 0);
        game.move(1, 1);
        game.move(2, 1);
        assertEquals("X won the game!", game.move(2, 0));
    }

    @Test
    public void whenAllCellsAreFilledTheGameIsADraw() {
        game.move(0, 2);
        game.move(1, 1);
        game.move(1, 0);
        game.move(2, 1);
        game.move(2, 2);
        game.move(0, 0);
        game.move(0, 1);
        game.move(1, 2);
        assertEquals("Its a Draw!", game.move(2, 0));
    }

    private void assertBoardIs(char[][] expectedBoard) {
        assertArrayEquals(expectedBoard, game.displayBoard());
    }
}

Vollständige Lösung: https://github.com/nashjain/tictactoe/tree/master/java

Naresh Jain
quelle
0

Wie wäre es mit einem folgenden Ansatz für 9 Slots? Deklarieren Sie 9 ganzzahlige Variablen für eine 3x3-Matrix (a1, a2 .... a9), wobei a1, a2, a3 Zeile-1 darstellen und a1, a4, a7 Spalte-1 bilden würden (Sie haben die Idee). Verwenden Sie '1', um Spieler-1 anzuzeigen, und '2', um Spieler-2 anzuzeigen.

Es gibt 8 mögliche Gewinnkombinationen: Win-1: a1 + a2 + a3 (Antwort könnte 3 oder 6 sein, je nachdem welcher Spieler gewonnen hat) Win-2: a4 + a5 + a6 Win-3: a7 + a8 + a9 Win-4 : a1 + a4 + a7 .... Win-7: a1 + a5 + a9 Win-8: a3 + a5 + a7

Jetzt wissen wir, dass wenn Spieler 1 a1 kreuzt, wir die Summe von 3 Variablen neu bewerten müssen: Win-1, Win-4 und Win-7. Welches 'Win-?' Variablen erreicht 3 oder 6 zuerst gewinnt das Spiel. Wenn die Variable Win-1 zuerst 6 erreicht, gewinnt Spieler-2.

Ich verstehe, dass diese Lösung nicht einfach skalierbar ist.

user3071398
quelle
0

Dies ist eine sehr einfache Möglichkeit, dies zu überprüfen.

    public class Game() { 

    Game player1 = new Game('x');
    Game player2 = new Game('o');

    char piece;

    Game(char piece) {
       this.piece = piece;
    }

public void checkWin(Game player) {

    // check horizontal win
    for (int i = 0; i <= 6; i += 3) {

        if (board[i] == player.piece &&
                board[i + 1] == player.piece &&
                board[i + 2] == player.piece)
            endGame(player);
    }

    // check vertical win
    for (int i = 0; i <= 2; i++) {

        if (board[i] == player.piece &&
                board[i + 3] == player.piece &&
                board[i + 6] == player.piece)
            endGame(player);
    }

    // check diagonal win
    if ((board[0] == player.piece &&
            board[4] == player.piece &&
            board[8] == player.piece) ||
            board[2] == player.piece &&
            board[4] == player.piece &&
            board[6] == player.piece)
        endGame(player);
    }

}}

Lusion
quelle
0

Wenn Sie beispielsweise das Grenzfeld 5 * 5 haben, habe ich die nächste Überprüfungsmethode verwendet:

public static boolean checkWin(char symb) {
  int SIZE = 5;

        for (int i = 0; i < SIZE-1; i++) {
            for (int j = 0; j <SIZE-1 ; j++) {
                //vertical checking
            if (map[0][j] == symb && map[1][j] == symb && map[2][j] == symb && map[3][j] == symb && map[4][j] == symb) return true;      // j=0
            }
            //horisontal checking
            if(map[i][0] == symb && map[i][1] == symb && map[i][2] == symb && map[i][3] == symb && map[i][4] == symb) return true;  // i=0
        }
        //diagonal checking (5*5)
        if (map[0][0] == symb && map[1][1] == symb && map[2][2] == symb && map[3][3] == symb && map[4][4] == symb) return true;
        if (map[4][0] == symb && map[3][1] == symb && map[2][2] == symb && map[1][3] == symb && map[0][4] == symb) return true;

        return false; 
        }

Ich denke, es ist klarer, aber wahrscheinlich nicht der optimalste Weg.

Aleksei Moshkov
quelle
0

Hier ist meine Lösung mit einem zweidimensionalen Array:

private static final int dimension = 3;
private static final int[][] board = new int[dimension][dimension];
private static final int xwins = dimension * 1;
private static final int owins = dimension * -1;

public static void main(String[] args) {
    Scanner scanner = new Scanner(System.in);
    int count = 0;
    boolean keepPlaying = true;
    boolean xsTurn = true;
    while (keepPlaying) {
        xsTurn = (count % 2 == 0);
        System.out.print("Enter i-j in the format:");
        if (xsTurn) {
            System.out.println(" X plays: ");
        } else {
            System.out.println(" O plays: ");
        }
        String result = null;
        while (result == null) {
            result = parseInput(scanner, xsTurn);
        }
        String[] xy = result.split(",");
        int x = Integer.parseInt(xy[0]);
        int y = Integer.parseInt(xy[1]);
        keepPlaying = makeMove(xsTurn, x, y);
        count++;
    }
    if (xsTurn) {
        System.out.print("X");
    } else {
        System.out.print("O");
    }
    System.out.println(" WON");
    printArrayBoard(board);
}

private static String parseInput(Scanner scanner, boolean xsTurn) {
    String line = scanner.nextLine();
    String[] values = line.split("-");
    int x = Integer.parseInt(values[0]);
    int y = Integer.parseInt(values[1]);
    boolean alreadyPlayed = alreadyPlayed(x, y);
    String result = null;
    if (alreadyPlayed) {
        System.out.println("Already played in this x-y. Retry");
    } else {
        result = "" + x + "," + y;
    }
    return result;
}

private static boolean alreadyPlayed(int x, int y) {
    System.out.println("x-y: " + x + "-" + y + " board[x][y]: " + board[x][y]);
    if (board[x][y] != 0) {
        return true;
    }
    return false;
}

private static void printArrayBoard(int[][] board) {
    for (int i = 0; i < dimension; i++) {
        int[] height = board[i];
        for (int j = 0; j < dimension; j++) {
            System.out.print(height[j] + " ");
        }
        System.out.println();
    }
}

private static boolean makeMove(boolean xo, int x, int y) {
    if (xo) {
        board[x][y] = 1;
    } else {
        board[x][y] = -1;
    }
    boolean didWin = checkBoard();
    if (didWin) {
        System.out.println("keep playing");
    }
    return didWin;
}

private static boolean checkBoard() {
    //check horizontal
    int[] horizontalTotal = new int[dimension];
    for (int i = 0; i < dimension; i++) {
        int[] height = board[i];
        int total = 0;
        for (int j = 0; j < dimension; j++) {
            total += height[j];
        }
        horizontalTotal[i] = total;
    }
    for (int a = 0; a < horizontalTotal.length; a++) {
        if (horizontalTotal[a] == xwins || horizontalTotal[a] == owins) {
            System.out.println("horizontal");
            return false;
        }
    }
    //check vertical
    int[] verticalTotal = new int[dimension];

    for (int j = 0; j < dimension; j++) {
        int total = 0;
        for (int i = 0; i < dimension; i++) {
            total += board[i][j];
        }
        verticalTotal[j] = total;
    }
    for (int a = 0; a < verticalTotal.length; a++) {
        if (verticalTotal[a] == xwins || verticalTotal[a] == owins) {
            System.out.println("vertical");
            return false;
        }
    }
    //check diagonal
    int total1 = 0;
    int total2 = 0;
    for (int i = 0; i < dimension; i++) {
        for (int j = 0; j < dimension; j++) {
            if (i == j) {
                total1 += board[i][j];
            }
            if (i == (dimension - 1 - j)) {
                total2 += board[i][j];
            }
        }
    }
    if (total1 == xwins || total1 == owins) {
        System.out.println("diagonal 1");
        return false;
    }
    if (total2 == xwins || total2 == owins) {
        System.out.println("diagonal 2");
        return false;
    }
    return true;
}
user3743369
quelle
0

Konstante Zeitlösung, läuft in O (8).

Speichern Sie den Status der Karte als Binärzahl. Das kleinste Bit (2 ^ 0) ist die obere linke Reihe der Platine. Dann geht es nach rechts, dann nach unten.

IE

+ ----------------- +
| 2 ^ 0 | 2 ^ 1 | 2 ^ 2 |
| ----------------- |
| 2 ^ 3 | 2 ^ 4 | 2 ^ 5 |
| ----------------- |
| 2 ^ 6 | 2 ^ 7 | 2 ^ 8 |
+ ----------------- +

Jeder Spieler hat seine eigene Binärzahl, um den Zustand darzustellen (weil Tic-Tac-Toe) 3 Zustände hat (X, O & leer), so dass eine einzelne Binärzahl nicht funktioniert, um den Zustand des Bretts für mehrere Spieler darzustellen.

Zum Beispiel ein Board wie:

+ ----------- +
| X | O | X |
| ----------- |
| O | X | |
| ----------- |
| | O | |
+ ----------- +

   0 1 2 3 4 5 6 7 8
X: 1 0 1 0 1 0 0 0 0
O: 0 1 0 1 0 0 0 1 0

Beachten Sie, dass die Bits für Spieler X von den Bits für Spieler O getrennt sind. Dies ist offensichtlich, da X kein Stück dort platzieren kann, wo O ein Stück hat, und umgekehrt.

Um zu überprüfen, ob ein Spieler gewonnen hat, müssen wir alle von diesem Spieler abgedeckten Positionen mit einer Position vergleichen, von der wir wissen, dass es sich um eine Gewinnposition handelt. In diesem Fall wäre der einfachste Weg, dies zu tun, das UND-Gating der Spielerposition und der Gewinnposition und das Überprüfen, ob beide gleich sind.

boolean isWinner(short X) {
    for (int i = 0; i < 8; i++)
        if ((X & winCombinations[i]) == winCombinations[i])
            return true;
    return false;
}

z.B.

X: 111001010
W: 111000000 // Gewinnposition, alle gleich in der ersten Reihe.
------------
&: 111000000

Hinweis: X & W = WX befindet sich also in einem Gewinnzustand.

Dies ist eine Lösung mit konstanter Zeit, die nur von der Anzahl der Gewinnpositionen abhängt, da das Anwenden des UND-Gatters eine Operation mit konstanter Zeit ist und die Anzahl der Gewinnpositionen endlich ist.

Es vereinfacht auch die Aufgabe, alle gültigen Kartenzustände aufzulisten, wobei nur alle Zahlen durch 9 Bits darstellbar sind. Aber natürlich benötigen Sie eine zusätzliche Bedingung, um sicherzustellen, dass eine Nummer ein gültiger Board-Status ist (z. B. 0b111111111eine gültige 9-Bit-Nummer, aber kein gültiger Board-Status, da X gerade alle Runden gemacht hat).

Die Anzahl der möglichen Gewinnpositionen kann im laufenden Betrieb generiert werden, aber hier sind sie trotzdem.

short[] winCombinations = new short[] {
  // each row
  0b000000111,
  0b000111000,
  0b111000000,
  // each column
  0b100100100,
  0b010010010,
  0b001001001,
  // each diagonal
  0b100010001,
  0b001010100
};

Um alle Kartenpositionen aufzulisten, können Sie die folgende Schleife ausführen. Obwohl ich es einer anderen Person überlassen werde, zu bestimmen, ob eine Nummer ein gültiger Board-Status ist.

HINWEIS: (2 ** 9 - 1) = (2 ** 8) + (2 ** 7) + (2 ** 6) + ... (2 ** 1) + (2 ** 0)

for (short X = 0; X < (Math.pow(2,9) - 1); X++)
   System.out.println(isWinner(X));
alexsalo
quelle
Bitte fügen Sie eine weitere Beschreibung hinzu und ändern Sie den Code, damit die Frage von OP genau beantwortet wird.
Farzan
0

Ich bin mir nicht sicher, ob dieser Ansatz noch veröffentlicht wurde. Dies sollte für jedes m * n-Brett funktionieren und ein Spieler soll die aufeinanderfolgende Position " wonPos " besetzen . Die Idee basiert auf dem laufenden Fenster.

private boolean validateWinner(int x, int y, int player) {
    //same col
    int low = x-winnerPos-1;
    int high = low;
    while(high <= x+winnerPos-1) {
        if(isValidPos(high, y) && isFilledPos(high, y, player)) {
            high++;
            if(high - low == winnerPos) {
                return true;
            }
        } else {
            low = high + 1;
            high = low;
        }
    }

    //same row
    low = y-winnerPos-1;
    high = low;
    while(high <= y+winnerPos-1) {
        if(isValidPos(x, high) && isFilledPos(x, high, player)) {
            high++;
            if(high - low == winnerPos) {
                return true;
            }
        } else {
            low = high + 1;
            high = low;
        }
    }
    if(high - low == winnerPos) {
        return true;
    }

    //diagonal 1
    int lowY = y-winnerPos-1;
    int highY = lowY;
    int lowX = x-winnerPos-1;
    int highX = lowX;
    while(highX <= x+winnerPos-1 && highY <= y+winnerPos-1) {
        if(isValidPos(highX, highY) && isFilledPos(highX, highY, player)) {
            highX++;
            highY++;
            if(highX - lowX == winnerPos) {
                return true;
            }
        } else {
            lowX = highX + 1;
            lowY = highY + 1;
            highX = lowX;
            highY = lowY;
        }
    }

    //diagonal 2
    lowY = y+winnerPos-1;
    highY = lowY;
    lowX = x-winnerPos+1;
    highX = lowX;
    while(highX <= x+winnerPos-1 && highY <= y+winnerPos-1) {
        if(isValidPos(highX, highY) && isFilledPos(highX, highY, player)) {
            highX++;
            highY--;
            if(highX - lowX == winnerPos) {
                return true;
            }
        } else {
            lowX = highX + 1;
            lowY = highY + 1;
            highX = lowX;
            highY = lowY;
        }
    }
    if(highX - lowX == winnerPos) {
        return true;
    }
    return false;
}

private boolean isValidPos(int x, int y) {
    return x >= 0 && x < row && y >= 0 && y< col;
}
public boolean isFilledPos(int x, int y, int p) throws IndexOutOfBoundsException {
    return arena[x][y] == p;
}
Adler
quelle
-2

Ich habe dafür einmal im Rahmen eines Wissenschaftsprojekts einen Algorithmus entwickelt.

Grundsätzlich teilen Sie das Brett rekursiv in eine Reihe überlappender 2x2-Rechtecke auf und testen die verschiedenen möglichen Kombinationen, um auf einem 2x2-Quadrat zu gewinnen.

Es ist langsam, hat aber den Vorteil, dass es auf einer Karte jeder Größe mit ziemlich linearen Speicheranforderungen funktioniert.

Ich wünschte, ich könnte meine Implementierung finden

bgw
quelle
Eine Rekursion zum Testen des Finishs ist nicht erforderlich.
Gabriel Llamas