<?php

class BacktrackAlgorithm
{

    public function backtrack($target, $last = null)
    {
        $this->printLine($target);
        $blank = array_search("blank", $target);
        if (!$this->checkIsValid($target)) {
            if ($last === "white") {
                for ($i = count($target); $i >= 1; $i--) {
                    if (!in_array($target[$i],array("blank","white"))) {
                        $target[$blank] = "black";
                        $target[$i] = "blank";
                        return $this->backtrack($target, "black");
                    }
                }
            } else {
                for ($i = 1; $i <= count($target); $i++) {
                    if (!in_array($target[$i],array("blank","black"))) {
                        $target[$blank] = "white";
                        $target[$i] = "blank";
                        return $this->backtrack($target, "white");
                    }
                }
            }
        }
    }

    public function checkIsValid($target)
    {
        return (bool) !in_array("white", array_slice($target,0,3)) && !in_array("blank", array_slice($target, 0, 3));
    }

    public function printLine($target)
    {
        echo "<tr>";
        foreach ($target AS $value) :
            echo "<td class=\"{$value}\">{$value}</td>";
        endforeach;
        echo "</tr>";
    }

}
?>
<style>
    td { width: 50px; height: 50px; border: 1px solid black; text-align: center; }
    .white { background: white; }
    .black { background: black; }
    .blank { background: brown; }
</style>
<table>
<?php
$backtrack = new BacktrackAlgorithm();
$backtrack->backtrack(array(1 => 'white','white','white','blank','black','black','black'));
?>
</table>
<?php