Queens [problem]

queens.php

<?php

class Queens
{
    /**
     * Board size
     * @var integer
     */
    protected $boardSize;

    /**
     * Queens positions
     * @var SplStack
     */
    protected $queensPositions;

    /**
     * Found positions
     * @var integer
     */
    protected $foundPositions = 0;

    /**
     * Min board size
     */
    CONST MIN_BOARD_SIZE = 4;

    /**
     * Class constructor
     * 
     * @param integer $boardSize
     */
    public function __construct($boardSize)
    {
        if ($boardSize < self::MIN_BOARD_SIZE) {
            throw new Exception('Min board size is '  . self::MIN_BOARD_SIZE);
        }

        $this->boardSize = $boardSize - 1;
        $this->queensPositions = new SplStack();
    }

    /**
     * Get a last queen position
     * 
     * @return array|boolean
     *      integer row
     *      integer column
     */
    protected function getLastQueenPosition()
    {
        $lastQueen = $this->queensPositions->top();
        $this->queensPositions->pop();

        if ($lastQueen['column'] + 1 <= $this->boardSize) {
            return array(
                'row' => $lastQueen['row'],
                'column' => $lastQueen['column'] + 1
            );
        }

        // get a prev queen position
        if($this->queensPositions->isEmpty()) {
            return false;
        }

        $prevQueen = $this->queensPositions->top();
        $this->queensPositions->pop();    

        return array(
            'row' => $prevQueen['row'],
            'column' => $prevQueen['column'] + 1
        );
    }

    /**
     * Check is position free
     * 
     * @param integer $row
     * @param integer $column
     * @return boolean
     */
    protected function isPositionFree($row, $column)
    {
        $left  = $row - $column;
        $right = $row + $column;

        if (!$this->queensPositions->isEmpty()) {
            foreach($this->queensPositions as $position) {
                if ($position['row'] == $row 
                        || $position['column'] == $column 
                        || $position['left'] == $left 
                        || $position['right'] == $right) {

                    return false;
                }
            }
        }

        // remember the current position
        $this->queensPositions->push(array(
            'row' => $row,
            'column' => $column,
            'left' => $left,
            'right' => $right
        ));

        return true;
    }

    /**
     * Get all posible queens positions
     * 
     * @return integer
     */
    public function getAllPosiblePositions()
    {
        // start position
        $row    = 0;
        $column = 0;

        while (true) {
            // we have found a free position
            if ($this->isPositionFree($row, $column)) {                
                // count the position
                if ($row == $this->boardSize) {
                    $this->foundPositions++;
                }

                // we have reached the end of board
                if ($row == $this->boardSize) {
                    // get the last queen position
                    if (false === ($position = $this->getLastQueenPosition())) {
                        break;
                    }

                    $row = $position['row'];
                    $column = $position['column'];
                    continue;
                }

                $row++; // get a next row
                $column = 0;
                continue;
            }

            // we have reached the end of columns and not found any free position
            if ($column == $this->boardSize) {
                // get the last queen position
                if (false === ($position = $this->getLastQueenPosition())) {
                    break;
                }

                $row = $position['row'];
                $column = $position['column'];
                continue;
            }

            $column++;
        };

        return $this->foundPositions;
    }
}


// unit tests

$tests = array(
    array(
        'expected' => 2,
        'board_size' => 4
    ),
    array(
        'expected' => 10,
        'board_size' => 5
    ),
    array(
        'expected' => 4,
        'board_size' => 6
    ),
    array(
        'expected' => 40,
        'board_size' => 7
    ),
    array(
        'expected' => 92,
        'board_size' => 8
    ),
    array(
        'expected' => 352,
        'board_size' => 9
    ),
    array(
        'expected' => 724,
        'board_size' => 10
    )
);

foreach($tests as $index => $test) {
	$timeStart = microtime(true);

    $queens = new Queens($test['board_size']);
    $foundPositions = $queens->getAllPosiblePositions();

    $timeEnd = microtime(true);
    $executionTime = ($timeEnd - $timeStart);

    $result = $test['expected'] == $foundPositions
        ? 'Test case ' . $index . ' successfully passed'
        : 'Test case ' . $index . ' failed, you expected ' . $test['expected'] . ', but result is ' . $foundPositions;

    echo $result . '<br>';
    echo '<b>Total Execution Time:</b> ' . $executionTime . '<br><hr />';
}

echo '<b>memory usage:</b> ' . ( memory_get_usage() / 1024 / 1024);