n queens problem | eight queens puzzle | recursive | مسئله ۸ وزیر | بازگشتی

n_queens_problem_recursive.php

<?php
/**
  * @author Arman Hosseini <[email protected]>
  */
?>
<style type="text/css">
    * {
        margin: 0;
        padding: 0;
    }
    body {
        background: white;
        text-align: center;
        margin: 10px;
    }
    .chess {
        display: inline-block;
        border: 1px #000 solid;
    }
    .chess ul {
        position: relative;
    }
    .chess ul li {
        width: 50px;
        height: 50px;
        align-items: center;
        display: inline-grid;
    }
    .witeStep {
        background-color: #FFF;
    }
    .brownStep {
        background-color: #a7937a;
    }
</style>
<?php
class Chess {
    const MINISTER = 1;

    private $map = [];
    private $end = false;

    public function __construct($n = 8)
    {
        for ($i = 0; $i < $n; $i++) {
            for ($j = 0; $j < $n; $j++) {
                $this->map[$i][$j] = '-';
            }
        }
    }

    public function draw()
    {
        echo "<div class='chess'>";
        foreach ($this->map as $rowNumber => $row) {
            echo "<ul>";
            foreach ($row as $colNumber => $colValue) {
                printf("<li class='%s'>%s</li>", $this->getStepCSSClass($rowNumber+$colNumber), $colValue);
            }
            echo "</ul>";
        }
        echo "</div>";

        return $this;
    }

    private function getStepCSSClass($step)
    {
        return $step % 2 == 0 ? 'whiteStep' : 'brownStep';
    }

    private function getNumberOfRowsOrCols()
    {
        return count($this->map);
    }

    public function solve($row = 0)
    {
        if ( $row > $this->getNumberOfRowsOrCols()-1 )
            $this->end = true;
        else {
            for ( $col = 0; $col < $this->getNumberOfRowsOrCols(); $col++ ) {
                if ( $this->canPlacedIn($row, $col) ) {
                    $this->cleanPlacesInRow($row);
                    $this->place($row, $col);
                    $this->solve($row + 1);
                }
            }

            // Clean columns and backtrack
            $this->cleanPlacesInRow($row);
        }

        return;
    }

    private function canPlacedIn($row, $col)
    {
        if ( $this->end ) {
            return false;
        }

        for ($i = $row-1; $i >= 0; $i--) {
            if ( in_array(self::MINISTER, [@$this->map[$i][$col-($row-$i)], @$this->map[$i][$col], @$this->map[$i][$col+($row-$i)]]) )
                return false;
        }

        return true;
    }

    private function cleanPlacesInRow($row)
    {
        if ( $this->end ) {
            return false;
        }

        for ($col = 0; $col < $this->getNumberOfRowsOrCols(); $col++) {
            $this->map[$row][$col] = '-';
        }

        return true;
    }

    private function place($row, $col)
    {
        if ( !$this->end )
            $this->map[$row][$col] = self::MINISTER;
    }
}

$chess = new Chess();
$chess->solve();
$chess->draw();