如何找到任何规模的井字游戏的赢家？
这是一个面试问题."你如何确定是否有人在任何规模的棋盘上赢得了一场井字游戏？" 我听说算法复杂度为O(1).是否有意义 ？任何人都可以解释算法吗？
MSN*_*MSN 35
答案就在那个页面上,但无论如何我都会解释.
算法的复杂度为O(1),用于确定给定的移动是否会赢得游戏.它通常不能是O(1)因为您需要知道董事会的状态以确定胜利者.但是,您可以逐步构建该状态,以便确定移动是否在O(1)中获胜.
首先,为每个玩家的每一行,每列和每个对角线设置一个数字数组.在每次移动中,增加与该移动影响的行,列和对角线(移动可能不一定在对角线上)的玩家对应的元素.如果该玩家的计数等于棋盘的尺寸,则该玩家获胜.
- 能用小例解释一下这个!你的陈述不明确!! 请. (6认同)
- 如果您对保存少量空间感兴趣,则无需为每个播放器设置阵列."X"的增量,"O"的减量.检查消极和积极的"N"以确定获胜者. (4认同)
小智 19
检测获胜条件的最快方法是跟踪所有行,列,对角线和反对角线得分.
假设你有3x3网格.创建大小为2*3 + 2的分数数组,其中包含以下分数[row1,row2,row3,col1,col2,col3,diag1,diag2].当然不要忘记用0初始化它.
每次移动后,您为玩家1添加+1,或者为玩家2减去-1,如下所示.
得分[row] + = point; //其中point为+1或-1
得分[gridSize + col] + = point;
if(row == col)得分[2*gridSize] + = point;
if(gridSize - 1 - col == row)得分[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)时间内解决,假设至少是这样 
存在区域并假设可以预先计算查找表.正如其他答案所描述的那样,该解决方案不需要先前的状态跟踪,并且算法的运行时部分不需要对列或行进行求和.
将n*n板状态视为单个整数B.为此,将位置(x,y)处的单个单元c表示为整数,其中 
= 0表示O, = 1表示X,和 = 2表示空单元格.
接下来,代表每个方块 
如:
然后,将整个董事会状态B表示为:
假设您已经如此代表您的董事会,您可以在预先计算的表格中查看记忆位置B,该表格描述了给出的问题的答案.
我提供的编码可以紧凑地表示任何n*n tic-tac-toe板配置,包括在正常播放中无法到达的位置.但是,您可以使用任何您喜欢的独特电路板编码方法,例如字符串或数组,只要您将电路板表示解释为一个长的,唯一的整数,索引到预先计算的解决方案表中.我在这里提供了一个这样完美的哈希函数,但是存在许多其他函数.
提供的这种委员会代表也允许玩家获得任意数量的免费初始移动的类似障碍.
有趣的是,如果你有足够的记忆力,你也可以在这一点上查找问题的答案,例如当前游戏是否以完美游戏获胜或失败,哪个移动是理想的位置,如果游戏是保证获胜或损失,赢或输有多少次最大变动.重要的是,这种技术用于计算机国际象棋; 每个人使用的查找表称为Nalimov表库.
将tic-tac-toe推广到任何规模的棋盘,其中连续获得k石的玩家获胜,被称为m,n,k游戏,并且有许多关于这种类型游戏的有趣证据.
TL:博士; 如果你想要一个速度记录,几乎不可能击败低位查找表.