gistfile1.php

<?php

interface Mikado
{
    public function searchFreeStick();
    public function removeStick($i);
}

class MikadoCollectionQueue implements Mikado
{
    /**
     * @var SplFixedArray
     */
    private $coverage;
    
    /**
     * @var SplQueue
     */
    private $queue;
    
    public function __construct($n, array $puzzle)
    {
        $this->coverage = new SplFixedArray($n + 1);
        for ($i = 0; $i <= $n; $i++) {
            $this->coverage[$i] = new ArrayObject();
        }
        
        for ($j = 0; $j < count($puzzle); $j++) {
            $this->coverage[$puzzle[$j][0]][$puzzle[$j][1]] = true;
        }
        
        $this->queue = new SplQueue();
        for ($i = 1; $i <= $n; $i++) {
            $this->enqueueIfNotBlocked($i);
        }
    }
    
    public function searchFreeStick() 
    {
        return $this->queue->dequeue();
    }

    public function removeStick($i)
    {
        for ($j = 1; $j < count($this->coverage); $j++) {
            if (isset($this->coverage[$j]) && isset($this->coverage[$j][$i])) {
                unset($this->coverage[$j][$i]);
            
                $this->enqueueIfNotBlocked($j);
            }
        }
    }

    protected function enqueueIfNotBlocked($i)
    {
        if (count($this->coverage[$i]) === 0) {
            $this->queue->enqueue($i);
        }
    }
}

$n = 7;
$mikado = new MikadoCollectionQueue(
    $n, 
    array(
        array(1, 6),
        array(2, 1),
        array(2, 4),
        array(2, 6),
        array(2, 7),
        
        array(3, 1),
        array(3, 2),
        array(3, 4),
        array(3, 7),
        array(4, 1),
        array(4, 6),
        array(5, 1),
        array(5, 2),
        array(5, 3),
        
        array(5, 4),
        array(5, 6),
        array(5, 7),
        array(7, 1),
        array(7, 4),
        array(7, 6)
    )
);

for ($i = 1; $i <= $n; $i++) {
    $stick = $mikado->searchFreeStick();
    echo "\n\nfree stick: {$stick}";
    
    $mikado->removeStick($stick);
}