Как найти победителя игры в крестики-нолики любого размера?

Это вопрос интервью. "Как бы вы определили, выиграл ли кто-нибудь игру в крестики-нолики на доске любого размера?" Я слышал, что сложность алгоритма была O(1). Имеет ли это смысл? Кто-нибудь может объяснить алгоритм?

Источник

8 ответов

Решение

Ответ прямо на этой странице, но я все равно объясню.

Сложность алгоритма составляет O(1) для определения, выиграет ли данный ход в игре. Это не может быть O(1) в общем, так как вам нужно знать состояние доски, чтобы определить победителя. Тем не менее, вы можете строить это состояние постепенно, так что вы можете определить, выигрывает ли ход в O(1).

Для начала, иметь массив чисел для каждой строки, столбца и диагонали для каждого игрока. На каждом ходу увеличивайте элементы, соответствующие игроку, для строки, столбца и диагонали (ход не обязательно должен быть по диагонали), на которые влияет этот ход. Если счет для этого игрока равен размеру доски, этот игрок выигрывает.

Источник

Самый быстрый способ определения условия выигрыша - отслеживать все строки, столбцы, диагональные и антидиагональные оценки.

Допустим, у вас есть сетка 3х3. Создайте массив партитур размером 2*3+2, который будет содержать баллы следующим образом [row1, row2, row3, col1, col2, col3, diag1, diag2]. Конечно, не забудьте инициализировать его с 0.

Далее после каждого хода вы добавляете +1 для игрока 1 или вычитаете -1 для игрока 2 следующим образом.

оценка [строка] += балл; // где точка либо +1, либо -1

оценка [gridSize + col] += балл;

if (row == col) score [2 * gridSize] += point;

if (gridSize - 1 - col == row) score [2 * gridSize + 1] += point;

Затем все, что вам нужно сделать, это перебрать массив результатов один раз и обнаружить +3 или -3 (GRID_SIZE или -GRID_SIZE).

Я знаю, что код говорит больше, чем слова, так что вот прототип на PHP. Это довольно просто, поэтому я не думаю, что у вас возникнут проблемы с переводом на другие языки.

<?php

class TicTacToe {
    const PLAYER1 = 'X';
    const PLAYER1_POINT = 1;

    const PLAYER2 = 'O';
    const PLAYER2_POINT = -1; // must be the opposite of PLAYER1_POINT

    const BLANK = '';

    /**
    * Level size.
    */
    private $gridSize;

    /** 
    * Level data.
    * Two dimensional array of size GRID_SIZE x GRID_SIZE.
    * Each player move is stored as either 'X' or 'O'
    */
    private $grid;

    /**
    * Score array that tracks score for rows, cols and diagonals.
    * e.g. for 3x3 grid [row1, row2, row3, col1, col2, col3, diag1, diag2]
    */
    private $score;

    /**
    * Avaialable moves count for current game.
    */
    private $movesLeft = 0;

    /**
    * Winner of the game. 
    */
    private $winner = null;

    public function __construct($size = 3) {
        $this->gridSize = $size;
        $this->grid = array();
        for ($i = 0; $i < $this->gridSize; ++$i) {
            $this->grid[$i] = array_fill(0, $this->gridSize, self::BLANK);
        }

        $this->score = array_fill(0, 2*$this->gridSize + 2, 0);
        $this->movesLeft = $this->gridSize * $this->gridSize;
        $this->winner = null;
    }

    public function getWinner() {
        return $this->winner;
    }

    public function displayGrid() {
        $this->display("--------\n");
        for ($row = 0; $row < $this->gridSize; ++$row) {
            for ($col = 0; $col < $this->gridSize; ++$col) {
                if (self::BLANK == $this->grid[$row][$col]) $this->display('  ');
                else $this->display($this->grid[$row][$col].' ');
            }
            $this->display("\n");
        }
        $this->display("--------\n");
    }

    public function play(MoveInput $input) {
        $this->display("NEW GAME\n");
        $nextPlayer = self::PLAYER1;
        $done = false;
        while(!$done) { 
            $move = $input->getNextMove($nextPlayer);
            if (NULL == $move) {
                $this->display("ERROR! NO MORE MOVES\n");
                break;
            }

            $error = false;
            $this->makeMove($move['player'], $move['row'], $move['col'], $error);
            if ($error) {
                $this->display("INVALID MOVE! Please try again.\n");
                continue;
            }
            $nextPlayer = ($nextPlayer == self::PLAYER1) ? self::PLAYER2 : self::PLAYER1;
            $this->displayGrid();
            $done = $this->checkScore();
        }
    }

    private function makeMove($player, $row, $col, &$error) {
        $error = false;
        if (!$this->isValidMove($row, $col) || self::BLANK != $this->grid[$row][$col]) {
            $error = true;
            return;
        }

        $this->grid[$row][$col] = $player;
        --$this->movesLeft;

        $point = 0;
        if (self::PLAYER1 == $player) $point = self::PLAYER1_POINT;
        if (self::PLAYER2 == $player) $point = self::PLAYER2_POINT;

        $this->score[$row] += $point;
        $this->score[$this->gridSize + $col] += $point;
        if ($row == $col) $this->score[2*$this->gridSize] += $point;
        if ($this->gridSize - 1 - $col == $row) $this->score[2*$this->gridSize + 1] += $point;
    }

    private function checkScore() {
        if (0 == $this->movesLeft) {
            $this->display("game is a DRAW\n");
            return true;
        }

        for ($i = 0; $i < count($this->score); ++$i) {
            if ($this->player1TargetScore() == $this->score[$i]) {
                $this->display("player 1 WIN\n");
                $this->winner = self::PLAYER1;
                return true;
            }

            if ($this->player2TargetScore() == $this->score[$i]) {
                $this->display("player 2 WIN\n");
                $this->winner = self::PLAYER2;
                return true;
            }
        }

        return false;
    }

    private function isValidMove($row, $col) {
        return (0 <= $row && $row < $this->gridSize) &&
                (0 <= $col && $col < $this->gridSize);
    }

    private function player1TargetScore() {
        return $this->gridSize * self::PLAYER1_POINT;
    }

    private function player2TargetScore() {
        return $this->gridSize * self::PLAYER2_POINT;
    }

    private function display($string) {
        echo $string;
    }
}

interface MoveInput {
    public function getNextMove($player);
}

class QueuedMoveInput implements MoveInput {
    private $moves;

    public function __construct($movesArray) {
        $this->moves = $movesArray;
    }

    public function getNextMove($player) {
        return array_shift($this->moves);
    }
}

class InteractiveMoveInput implements MoveInput {
    public function getNextMove($player) {
        while(true) {
            echo "Please enter next move for player $player: [row,col] ";
            $line = trim(fgets(STDIN));
            list($row, $col) = sscanf($line, "%D,%D");
            if (is_numeric($row) && is_numeric($col)) {
                return array('player' => $player, 'row' => $row, 'col' => $col);
            }
        }
    }
}

// helpers
function p1($row, $col) {
    return array('player' => TicTacToe::PLAYER1, 'row' => $row, 'col' => $col);
}

function p2($row, $col) {
    return array('player' => TicTacToe::PLAYER2, 'row' => $row, 'col' => $col);
}

// TESTING!!!!! ;]

// GAME 1 - testing diagonal (0,0) -> (2,2) win condition
$game = new TicTacToe();
$moves = new QueuedMoveInput(array(p1(1,1), p2(0,1), p1(2,0), p2(0,2), p1(0,0), p2(1,0), p1(2,2), p2(2,1)));
$game->play($moves);
assert($game->getWinner() == TicTacToe::PLAYER1);

// GAME 2 - using invalid move, testing straight line (0,0) -> (0,2) win condition
$game = new TicTacToe();
$moves = new QueuedMoveInput(array(p1(1,1), p2(1,1), p2(2,0), p1(2,1), p2(0,1), p1(2,2), p2(0,0), p1(1,0), p2(0,2)));
$game->play($moves);
assert($game->getWinner() == TicTacToe::PLAYER2);

// GAME 3 - testing draw condition
$game = new TicTacToe();
$moves = new QueuedMoveInput(array(p1(1,1), p2(2, 2), p1(1,2), p2(1,0), p1(2,0), p2(0,2), p1(0,1), p2(2,1), p1(0,0)));
$game->play($moves);
assert($game->getWinner() == NULL);

// GAME 4 - testing diagonal (2,0) -> (0,2) win condition
$game = new TicTacToe();
$moves = new QueuedMoveInput(array(p1(2,0), p2(1, 2), p1(0,2), p2(2,2), p1(0,1), p2(0,0), p1(1,1)));
$game->play($moves);
assert($game->getWinner() == TicTacToe::PLAYER1);

// GAME 5 - testing straight line (0,0) -> (2,0) win condition
$game = new TicTacToe();
$moves = new QueuedMoveInput(array(p2(1,1), p1(0,0), p2(0,2), p1(2,0), p2(2,1), p1(1,0)));
$game->play($moves);
assert($game->getWinner() == TicTacToe::PLAYER1);

// GAME 6 - 5x5 grid, testing diagonal (0,0) -> (4,4) win condition
$game = new TicTacToe(5);
$moves = new QueuedMoveInput(array(p1(1,1), p2(0,1), p1(2,0), p2(0,2), p1(0,0), p2(1,0), p1(2,2), p2(4,2), p1(3,3), p2(4,3), p1(4,4)));
$game->play($moves);
assert($game->getWinner() == TicTacToe::PLAYER1);

// GAME 7 - Interactive game.
$game = new TicTacToe();
$game->play(new InteractiveMoveInput());

Надеюсь, это поможет;]

Источник

Эта проблема и куча связанных с ней проблем могут быть решены за O(1) раз, при условии, что по крайней мере 3 ^ (п ^ 2 области памяти существуют и при условии, что таблица поиска может быть предварительно вычислена. Это решение не требует предыдущего отслеживания состояния, как описывают другие ответы, а часть времени выполнения алгоритма не требует суммирования столбцов или строк, как описывают другие ответы.

Рассматривайте состояние платы n * n как одно целое число B. Для этого представьте одну ячейку c в позиции (x,y) как целое число, где с (х, у = 0 обозначает O, с (х, у = 1 обозначает X, и с (х, у = 2 указывает на пустую ячейку.

Далее представьте каждый квадрат S (x,y): 1 <= x <= n, 1 <= y <= n здесь как:

S (x,y) = c (x,y) точка 3 ^ (n (x-1) + (y-1

Затем представьте все состояние платы B как:

Предполагая, что вы таким образом представляли свою доску, вы можете посмотреть на позицию памяти B в предварительно вычисленной таблице, которая описывает ответ на заданный вопрос.

Кодировка, которую я предоставил, может компактно представлять любую n * n конфигурацию платы крестики-нолики, включая позиции, которые не могут быть достигнуты при нормальной игре. Однако вы можете использовать любой уникальный метод кодирования платы, например, строки или массивы, если вы интерпретируете представление платы как длинное уникальное целое число, индексирующееся в таблице предварительно вычисленных решений. Я предоставил одну такую идеальную хеш-функцию, но существует множество других.

Это представленное на доске представление также разрешает подобные гандикапы, когда игроку предоставляется произвольное количество бесплатных начальных ходов.

Интересно, что если у вас достаточно памяти, вы также можете на этом этапе искать ответы на такие вопросы, как: выиграна или проиграна текущая игра с идеальной игрой, какой ход идеален с позиции, и если игра является гарантированным выигрышем или потеря, сколько максимальных ходов существует для победы или поражения. Эта техника, главное, используется в компьютерных шахматах; таблица поиска, которую все используют, называется таблицей Налимова.

Обобщение крестики-нолики на доске любого размера, где игрок, который получает k камней подряд, выигрывает, называется игрой m, n, k, и есть много интересных доказательств об этом типе игры.

ТЛ: д-р; Если вы хотите получить рекорд скорости, почти невозможно победить скромную таблицу поиска.

Источник

Мне только что задали этот вопрос в интервью по программированию. "Учитывая доску в крестики-нолики, как проверить ход был выигрышный ход в ПОСТОЯННОМ времени"

это заняло у меня более 20 минут, но я думаю, что смог найти ответ и решить его в O(1)

Скажем так, давайте начнем с простой крестообразной доски 3 на 3, поместим число, соответствующее каждому блоку на доске 123 456 789

Итак, мой ответ на этот вопрос довольно прост: хешируйте все выигрышные комбинации в хэш-таблицу, такую ​​как 123, 456, 789, 159 и т. Д.

Имейте два списка чисел, чтобы отследить движение отдельного игрока

Алг описан ниже

    So when player_1 puts a X on a square, he will get the corresponding
    number into his number list
    When player_2 puts a O on a square, he will also get the corresponding
    number into his number list.
    At the end of every round, look through the Hash table to see if any 
    of the two players have the winning combination

Так что я думаю, что это O(1)

Источник

Я написал сообщение в блоге на этот вопрос.

Суть в том, что по ходу игры вы отслеживаете, сколько X было размещено в каждой строке / столбцах + 2 диагонали.

Затем каждый раз, когда игрок заканчивает свой ход, вы проверяете, содержат ли строка и столбец последней размещенной координаты N число X. Если это так, то игрок выиграл.

Источник 
class Solution {
    public String tictactoe(int[][] moves) {

        boolean startValidating = false;
        int[][] matrix = new int[3][3]; //if you want to try for 4 by 4 change to [4][5]
        for (int i = 0; i < moves.length; i++) {
            if (i > (matrix.length - 2) * 2 + 1) { //start validating only after after 5th move in 3x3, since no way there is a possibility to win, this improve efficiency by unnecessary validation untile first 4 moves
                startValidating = true;
            }
            if (i % 2 == 0) { //even case 1st candidate starts
                matrix[moves[i][0]][moves[i][1]] = 'x';
                if (startValidating) {
                    if (checkAllRowSame(matrix) || checkAllColumnSame(matrix) || checkAllDiagonalSame(matrix))
                        //check all row, all column, all diagonal tic tac toe possibility win for first candidate A
                        return Character.toString('A');
                }
            } else { //odd case second candidate starts
                matrix[moves[i][0]][moves[i][1]] = '0';
                if (startValidating) {
                    if (checkAllRowSame(matrix) || checkAllColumnSame(matrix) || checkAllDiagonalSame(matrix))
                        //check all row, all column, all diagonal tic tac toe possibility win for first candidate B
                        return Character.toString('B');
                }
            }
        }
        if (moves.length == matrix.length * matrix.length) //if all the moves completed, there is no one win, it becomes draw
            return "Draw";


        return "Pending"; //if less number of moves, unable to decide winner 


    }

    private static boolean checkAllRowSame(int[][] matrix) {
        for (int i = 0; i < matrix.length; i++) {
            boolean flag = true;
            for (int j = 0; j < matrix.length - 1; j++) {
                if ((!(matrix[i][j] == 0 || matrix[i][j + 1] == 0)) && flag) { //skip if any one of them is not filled
                    flag = flag && (matrix[i][j] == matrix[i][j + 1]); // set to false in case of not equal, proceed to next row validation by skipping remaining items in the row
                } else {
                    flag = false;
                    break;
                }
            }
            if (flag)
                return true;

        }
        return false;
    }

    private static boolean checkAllColumnSame(int[][] matrix) {
        for (int i = 0; i < matrix.length; i++) {
            boolean flag = true;
            for (int j = 0; j < matrix.length - 1; j++) {
                if ((!(matrix[j][i] == 0 || matrix[j + 1][i] == 0)) && flag) { //skip if any one of them is not filled
                    flag = flag && (matrix[j][i] == matrix[j + 1][i]); // set to false in case of not equal, proceed to next col validation by skipping remaining items in the col
                } else {
                    flag = false;
                    break;
                }
            }
            if (flag)
                return true;

        }
        return false;

    }

    private static boolean checkAllDiagonalSame(int[][] matrix) {
        boolean flag = true;
        for (int i = 0; i < matrix.length - 1; i++) {
            if ((!(matrix[i][i] == 0 || matrix[i + 1][i + 1] == 0)) && flag) { //skip if any one of them is not filled
                flag = flag && (matrix[i][i] == matrix[i + 1][i + 1]); // set to false in case of not equal, proceed to right to left diagonal in the below for loop
            } else {
                flag = false;
                break;
            }
            if (!flag)
                break;
        }
        if (flag)
            return true;
        flag = true;
        for (int i = 0, j = matrix.length - 1; i < matrix.length - 1 && j > 0; i++, j--) {
            if ((!(matrix[i][j] == 0 || matrix[i + 1][j - 1] == 0)) && flag) {
                flag = flag && (matrix[i][j] == matrix[i + 1][j - 1]);
            } else {
                flag = false;
                break;
            }
            if (!flag)
                break;
        }
        if (flag)
            return true;


        return flag;
    }
}
Источник

решить n * n крестики-нолики, тест на победителя.

комбинация n * 2 + 2 для победы в любой игре, где x или o должны быть n подряд

Мы знаем, что если игрок выберет любой квадрат по краю или диагонали, у него есть шанс на победу тремя способами, если (n нечетно, средний будет иметь 5 вариантов (самая высокая вероятность), остальные два квадрата имеют два способа выигрыша.

**Чтобы игрок выиграл, он должен выбрать хотя бы одну позицию по диагонали (это дает нам только (n2+2) из ​​n^2 возможных результатов. Давайте запишем (n2+2)

В отдельном выигрышном листе

Скажем, x сначала выберите первую строку, o выберите первую строку, n будет записано в выигрышном листе

Первая строка (сторона, вниз, диагональ) Сторона означает (первая строка первая, первая строка вторая… .. до первой строки n-й прямоугольник) Вниз означает (первая строка первая, вторая строка сначала… до n-й строки первая строка) Диагональные средние (первая строка первая, вторая строка вторая… до n-й строки n-й)

x….o (теперь вы можете игнорировать эту строку со следующего раунда, поскольку для выигрыша x или y требуется n последовательных x или o)

Икс

Икс

Второй ряд (сбоку, вниз)

Сторона означает (вторая строка первая, вторая строка вторая… .. ко второй строке n-й прямоугольник) Вниз означает (первая строка вторая, вторая строка вторая… до n-й строки второй)

.

.

Третий ряд (сбоку, вниз)

.

.

N-я строка (сторона, вверх) Вверх (n-я строка n-я, n-я-1-я строка ... n-я первая строка)

.

о

Первая n-я строка (диагональ) Это (первая n-я строка, вторая n-я строка-1… первая n-я строка)

о

Второй раунд, если x выберите вторую строку, а 0 выберите вторую строку, третью,

Первый ряд (сбоку, вниз, по диагонали)

x….o

Икс

Икс

Второй ряд (сбоку, вниз)

.ox (теперь вы можете игнорировать эту строку со следующего раунда)

.

Третий ряд (сбоку, вниз).

.

N-й ряд (сбоку, вверх)

.

… ..О

N-я строка первая (по диагонали)

… ..О

Повторите раунд (выигрывает тот, кто первым заполнит указанную выше строку), т.е. (первая строка (сторона), нам не нужно проверять это со второго раунда, так как в нем есть как x, так и o.

Источник 
    class TicTacToe
{

    //http://basicalgos.blogspot.com/#!/2012/03/13-test-winning-condition-of-tic-tac.html
    //No time for test case

    int[,] board = null;

    int diag = 0;
    int antiDiag = 0;
    int[] rows = null;
    int[] cols = null;


    int diagonalLen = 0;

    public TicTacToe(int rowLen, int colLen)
    {
        board = new int[rowLen, colLen];

        rows = new int[rowLen];
        cols = new int[colLen];

        if (rowLen == colLen)
            diag = (int)(rowLen * Math.Sqrt(2));//Square formula
        else
            diagonalLen = (int)Math.Sqrt(Math.Pow(rowLen, 2) + Math.Pow(colLen, 2));//rectangle formula

    }

    public bool hasWon(int rowIdx, int colIdx, int player)
    {
        if (player == 1)
        {
            rows[rowIdx]++;
            cols[colIdx]++;

            if (rowIdx == colIdx) diag++;
            if (rowIdx + colIdx == rows.Length - 1) antiDiag++;//This is IMPORTANT finding.............

        }
        else
        {
            rows[rowIdx]--;
            cols[colIdx]--;

            if (rowIdx == colIdx) diag--;
            if (rowIdx + colIdx == rows.Length - 1) antiDiag--;
        }

        return diag == diagonalLen || rows[rowIdx] == rows.Length || cols[colIdx] == cols.Length || antiDiag == diagonalLen;
    }

    public void markOnBoard(int row, int col, int player)
    {
        if (player == 1)
            board[row, col]++;
        else
            board[row, col]--;
    }
}
Источник
Другие вопросы по тегам