Это вопрос . "Как бы вы определили, выиграл ли кто-нибудь игру тик-так-паук на доске любого размера?" Я слышал, что сложность алгоритма была O (1). Имеет ли это смысл? Может ли кто-нибудь объяснить алгоритм?
Как найти победителя тик-таковой игры любого размера?
Ответ 1
Ответ на этой странице прав, но я все равно объясню.
Сложность алгоритма - O (1) для определения того, будет ли данный ход побеждать в игре. Это не может быть O (1) вообще, так как вам нужно знать состояние совета, чтобы определить победителя. Тем не менее, вы можете построить это состояние постепенно, чтобы вы могли определить, выигрывает ли движение в O (1).
Для начала создайте массив чисел для каждой строки, столбца и диагонали для каждого игрока. На каждом шаге приращивайте элементы, соответствующие игроку для строки, столбца и диагонали (движение может не обязательно находиться на диагонали), на которое влияет этот ход. Если счетчик для этого игрока равен размерности доски, этот игрок выигрывает.
Ответ 2
Самый быстрый способ обнаружения условия выигрыша - отслеживать все строки, столбцы, диагональные и антидиагональные оценки.
Скажем, у вас есть сетка 3x3. Создайте массив баллов размером 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());
Надеюсь, что это поможет;]
Ответ 3
Эта проблема и множество связанных проблем могут быть решены в O (1) раз, если предположить, что по крайней мере 
существуют и предполагается, что таблица поиска может быть предварительно вычислена. Это решение не требует предварительного отслеживания состояния, как описывают другие ответы, а часть времени выполнения алгоритма не требует суммирования столбцов или строк, как описывают другие ответы.
Рассматривайте состояние n * n-board как единственное целое B. Для этого представляйте одну ячейку c в позиции (x, y) как целое число, где 
= 0 указывает O, = 1 указывает X и = 2 указывает пустую ячейку.
Затем представляем каждый квадрат 
как:
Затем представляем все состояние платы B как:
Предполагая, что вы представили свою доску таким образом, вы можете посмотреть позицию B памяти в предварительно вычисленной таблице, которая описывает ответ на заданный вопрос.
Кодировка, которую я предоставил, может представлять собой любую конфигурацию n * n tic-tac-toe board compact, включая позиции, которые не могут быть достигнуты при нормальной игре. Тем не менее, вы можете использовать любой уникальный способ кодирования платы, какой вам нравится, например строки или массивы, если вы интерпретируете представление платы как длинное уникальное целое число, индексируясь в таблицу предварительно вычисленных решений. Я предоставил одну такую идеальную хеш-функцию здесь, но многие другие существуют.
Представленное представление платы также допускает гоночные помехи, когда игроку предоставляется произвольное количество бесплатных начальных ходов.
Интересно, что если у вас достаточно памяти, вы также можете в этот момент найти ответы на такие вопросы, как: выиграть или проиграть текущую игру с отличной игрой, какой ход идеален с позиции, и если игра является гарантированный выигрыш или проигрыш, сколько максимальных ходов существует для победы или потери. Этот метод используется, что важно, в компьютерных шахматах; таблица поиска, которую все используют, называется таблицей Налимова.
Обобщение tic-tac-toe на любой размер платы, где игрок, получивший k камней в ряду побед, называется m, n, k game, и есть много интересных доказательств об этом типе игры.
ТЛ: др; если вы собираетесь записывать скорость, почти невозможно обыграть таблицу с низким поиском.
Ответ 4
Мне просто задали этот вопрос в интервью по программированию. "Учитывая плату tic-tac-toe, как проверить ход, это был победный шаг в ПОСТОЯННОЕ время"
мне потребовалось более 20 минут, но я ДУМАЛ смог найти ответ и решить его в O (1)
Итак, скажите, пусть начнется с простой 3-х на 3-х тик-таковой доской, поместите номер, соответствующий каждому блоку на доске 123 456 789
Итак, мой ответ на вопрос довольно прост, HASH все выигрышные комбинации в таблицу хэша, такие как 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)
Ответ 5
Я написал сообщение в блоге для этого вопроса.
Суть в том, что вы отслеживаете, сколько X было размещено в каждой строке/столбцах + 2 диагоналей по мере продвижения игры.
Затем каждый раз, когда игрок заканчивает свою очередь, вы проверяете, содержит ли строка и столбец последней установленной координаты N число X. Если это так, то игрок выиграл.
Ответ 6
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]--;
}
}