Функция проверки диагонали TicTacToe

Question

Функция проверки диагонали TicTacToe

class Board
{
const MARK_0 = 0;
const MARK_X = 1;

/** @var int */
private $sizeX;

/** @var int */
private $sizeY;

/** @var int */
private $requiredMarks;

/** @var array */
private $map = [];

/**
* @param int $sizeX
* @param int $sizeY
*/
public function __construct (int $sizeX = 3, int $sizeY = 3)
{
$this->sizeX = $sizeX;
$this->sizeY = $sizeY;

$this->requiredMarks = $sizeX;
}

/**
* @return int
*/
public function getSizeX() : int
{
return $this->sizeX;
}

/**
* @return int
*/
public function getSizeY() : int
{
return $this->sizeY;
}

/**
* @return int
*/
public function getRequiredMarks() : int
{
return $this->requiredMarks;
}

/**
* @param int $count
*/
public function setRequiredMarks (int $count) : void
{
$this->requiredMarks = $count;
}

/**
* @param int $x
* @param int $y
* @param int $mark
*/
public function setMark (int $x, int $y, int $mark) : void
{
$this->map[$x][$y] = $mark;
}

/**
* @param int $x
* @param int $y
*
* @return int|null
*/
public function getMark (int $x, int $y) : ?int
{
return $this->map[$x][$y] ?? null;
}

/**
* @return int|null
*/
public function checkWin() : ?int
{
foreach([self::MARK_0, self::MARK_X] as $mark)
{
if(/* $this->checkLanes($mark) ||  */ $this->checkDiagonals($mark))
{
return $mark;
}
}

return null;
}

/**
* @param int $mark
*
* @return bool
*/
private function checkDiagonals (int $mark) : bool
{
$sizeX = $this->getSizeX();
$sizeY = $this->getSizeY();

$required = $this->getRequiredMarks();

$size = max($sizeX, $sizeY);

for($k = $required - $size; $k <= ($size - $required); $k++)
{
$score1 = 0;
$score2 = 0;

$startI = max(0, $k);
$endI = min($size, $size + $k);

for($i = $startI; $i < $endI; $i++)
{
if($this->getMark($i, $k + $i) === $mark)
{
if(++$score1 >= $required)
{
return true;
}
}
else
{
$score1 = 0;
}

if($this->getMark($i, $size - 1 + $k - $i) === $mark)
{
if(++$score2 >= $required)
{
return true;
}
}
else
{
$score2 = 0;
}
}
}

return false;
}
}

$b = new Board (4, 4);
$b->setRequiredMarks(3);

$b->setMark(0, 1, Board::MARK_X);
$b->setMark(1, 2, Board::MARK_X);
$b->setMark(2, 3, Board::MARK_X);

$winner = $b->checkWin();

if($winner === null)
{
$winner = "nobody";
}
elseif($winner === Board::MARK_X)
{
$winner = "X";
}
else
{
$winner = "0";
}

var_dump($winner);

Как исправить функцию «checkDiagonals», чтобы обработка диагонали как в Фото произошло правильно и вернул правильный результат?

Если сделать проверку по диагонали, как в Фото, это работает правильно.

Я не могу придумать алгоритм проверки диагоналей, поэтому я взял его отсюда: https://stackoverflow.com/a/34257658/10261980

Прокомментированная функция «checkLanes» работает правильно, поэтому она скрыта от кода.

0

php tic-tac-toe

Решение

Другие решения

Других решений пока нет …

Источник

Accepted Answer

Вот координаты диагоналей, которые проверяет ваш алгоритм:

x: 0, y: -1
x: 1, y: 0
x: 2, y: 1

x: 0, y: 0
x: 1, y: 1
x: 2, y: 2
x: 3, y: 3

x: 1, y: 2
x: 2, y: 3
x: 3, y: 4

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

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

1...  .1..  ....  ....  ...1  ..1.  ....  ....
.2..  ..2.  1...  .1..  ..2.  .2..  ...1  ..1.
..3.  ...3  .2..  ..2.  .3..  3...  ..2.  .2..
....  ....  ..3.  ...3  ....  ....  .3..  3...

Это три вложенных цикла: строки, столбцы и диагонали:

Цикл строки начинается с 0 и продолжается до $sizeY - $requiredMarks,
Первый цикл столбца начинается с 0 и продолжается до $sizeX - $requiredMarks проверка диагоналей слева направо.
Второй цикл столбца запускается из $sizeX - $requiredMarks + 1 в $sizeX проверка справа налево диагоналей.
Самая внутренняя диагональная петля начинается с 0 и продолжается до $requiredMarks,

Индексирование в ячейку выглядит следующим образом: row: ($row + $diag), столбец: ($col + $diag * $xDirection), $xDirection множитель (либо 1 или же -1) позволяет функции проверки диагонали двигаться в любом направлении (влево или вправо).

Вот код, который делает это:

private function checkDiagonals(int $mark) : bool {
$required = $this->getRequiredMarks();

for ($row = 0; $row <= $this->getSizeY() - $required; $row++) {
for ($col = 0; $col <= $this->getSizeX() - $required; $col++) {
if ($this->checkDiagonal($mark, $row, $col, 1)) {
return true;
}
}

for ($col = $this->getSizeX() - $required + 1; $col < $this->getSizeX(); $col++) {
if ($this->checkDiagonal($mark, $row, $col, -1)) {
return true;
}
}
}

return false;
}

private function checkDiagonal(int $mark, int $row, int $col, int $xDir) : bool {
for ($i = 0; $i < $this->getRequiredMarks(); $i++) {
if ($this->getMark($col + $i * $xDir, $row++) !== $mark) {
return false;
}
}

return true;
}

Вот диагонали, которые он проверяет:

x: 0, y: 0
x: 1, y: 1
x: 2, y: 2

x: 1, y: 0
x: 2, y: 1
x: 3, y: 2

x: 2, y: 0
x: 1, y: 1
x: 0, y: 2

x: 3, y: 0
x: 2, y: 1
x: 1, y: 2

x: 0, y: 1
x: 1, y: 2
x: 2, y: 3

x: 1, y: 1
x: 2, y: 2
x: 3, y: 3

x: 2, y: 1
x: 1, y: 2
x: 0, y: 3

x: 3, y: 1
x: 2, y: 2
x: 1, y: 3

Это не очень эффективно, потому что включает в себя посещение квадратов несколько раз, но это должно по крайней мере заставить вас работать. Если скорость важна, подумайте об использовании bitboards который может проверить всю доску с помощью нескольких операций, но требует некоторой корректировки вашего подхода. Более простой рефакторинг — отслеживать последний ход игрока и проверять только возможные выигрыши с этой клетки.

Вот РЕПЛ тестировать.

0