例のアレ

gistfile1.php

<?php

foreach (range(1, 10) as $n) {
	echo "calculating $n connection...\n";
	$c = new Connection($n, $n === 1 ? null : $c);
	echo 'got answer. connection patterns: ', count($c->answers), "\n";
}

class Connection {

	public $n;

	public $answers = [];
	public $answerHashes = [];

	public function __construct($n, Connection $prevConnection = null) {
		if ($prevConnection) {
			$this->prevConnection = $prevConnection;
		} elseif ($n !== 1) {
			$this->prevConnection = new self($n - 1);
		}

		$this->n = $n;
		$this->resolve();
	}

	public function resolve() {
		if ($this->n === 1) {
			$this->answers = [
				[
					[
						1
					],
				],
			];
		} else {
			foreach ($this->prevConnection->answers as $answer) {
				foreach ($answer as $i => $row) {
					foreach ($row as $j => $exists) {
						if (!isset($answer[$i + 1][$j])) {
							$a = $answer;
							$a[$i + 1][$j] = 1;
							$this->addAnswer($a);
						}

						if (!isset($answer[$i][$j + 1])) {
							$a = $answer;
							$a[$i][$j + 1] = 1;
							$this->addAnswer($a);
						}

						if ($i === 0) {
							$a = $answer;
							$a[$i - 1][$j] = 1;
							$b = $this->shift($a, 1, 0);
							$this->addAnswer($b);
						}

						if ($i === 1) {
							if (!isset($answer[$i - 1][$j])) {
								$a = $answer;
								$a[$i - 1][$j] = 1;
								$this->addAnswer($a);
							}
						}

						if ($j !== 0) {
							if (!isset($answer[$i][$j - 1])) {
								$a = $answer;
								$a[$i][$j - 1] = 1;
								$this->addAnswer($a);
							}
						}
					}
				}
			}
		}
	}

	public function addAnswer($a) {
		$hash = $this->hash($a);
		if (!isset($this->answerHashes[$hash])) {
			$this->answers[] = $a;
			$this->answerHashes[$hash] = true;
		}
	}

	public function hash($answer) {
		$hash = 'a';
		for ($i = 0; $i <= $this->n - 1; $i++) {
			for ($j = 0; $j <= $this->n - 1; $j++) {
				$hash .= isset($answer[$i][$j]) ? '0' : '1';
			}
		}

		return $hash;
	}

	public function shift($answer, $di, $dj) {
		$result = [];
		foreach ($answer as $i => $row) {
			foreach ($row as $j => $exists) {
				$result[$i + $di][$j + $dj] = 1;
			}
		}
		return $result;
	}

	public function dump($answers = null) {
		if ($answers === null) {
			$answers = $this->answers;
		}

		$n = 0;
		foreach ($answers as $answer) {
			$n++;
			echo "answer$n:\n";
			// print_r($answer);
			for ($j = $this->n; $j >=0; $j--) {
				for ($i = 0; $i <= $this->n; $i++) {
					echo isset($answer[$i][$j]) ? '.' : ' ';
				}
				echo "\n";
			}
		}
	}

}