How to find the winner of a tic-tac-toe game of any size?_问答_开发者

This is an interview question. "How would you determine if someone has won a game of tic-tac-toe on a board of any size?" I heard the algorithm complexity wa开发者_开发知识库s O(1). Does it make sense ? Can anybody explain the algorithm ?

The answer is right on that page, but I'll explain it anyway.

The algorithm's complexity is O(1) for determining if a given move will win the game. It cannot be O(1) in general since you need to know the state of the board to determine a winner. However, you can build that state incrementally such that you can determine whether a move wins in O(1).

To start, have an array of numbers for each row, column, and diagonal for each player. On each move, increment the elements corresponding to the player for the row, column, and diagonal (the move may not necessarily be on a diagonal) influenced by that move. If the count for that player is equal to the dimension of the board, that player wins.

Fastest way of detecting win condition is to keep track of all rows, cols, diagonal and anti-diagonal scores.

Let's say you have 3x3 grid. Create score array of size 2*3+2 that will hold scores as following [row1, row2, row3, col1, col2, col3, diag1, diag2]. Of course don't forget to initialize it with 0.

Next after every move you add +1 for player 1 or subtract -1 for player 2 as following.

score[row] += point; // where point is either +1 or -1

score[gridSize + col] += point;

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

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

Then all you have to do is iterate over score array once and detect +3 or -3 (GRID_SIZE or -GRID_SIZE).

I know code tells more then words so here is a prototype in PHP. It's pretty straight forward so I don't think you'll have problems translating it into other lang.

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

Hope that helps ;]

This problem, and a bunch of related problems, may be solved in O(1) time, assuming that at least