カルテットには、社員同士が交流を深める部活がいくつかあります。バレー部やテニス部といった運動系もあれば、(実際には投資をしない)投資部のようなインドアなものもあります。しかし、人見知りな私は、どの部活にも参加していません(汗) でも、プログラマならプログラミング技術を磨きたい! 部活で! というわけで、自分で「プログラミング部」を作り、中途入社したメンバーを半ば強引に誘って、二人で朝活スタイルの部活としてスタートし活動していました。

プログラミング部の活動は、私がプログラミング問題を選び、二人それぞれ問題を解くコードを書くというものです。ただし、問題を解くことだけをゴールとはせず、プログラマが問題をどのように理解したのか、どのような解き方なのかをコードに表現するという部分を中心に据えて取り組みます。なので、問題を解くコードを完成させるのにかかる時間よりも、コードについて議論し、話の展開に応じてその場でコードを書き換え、また議論するといった時間の方が圧倒的に長いというハードコアな部活です。

プログラミング部でもっともよく議論したポイントを一言でいうと、抽象化です。取り組んでいる問題を字面通りにコードに表現するのではなく、抽象化して捉え直したものを使うことで、コードの役割分担が明確になることがあります。今回は、朝活で取り上げた例を題材にして、問題を抽象化して捉え直す前と後での違いを紹介します。

数独とは

数独(別名ナンプレ、ナンバープレイス)は、魔方陣の一種で、一般的には下のように縦横9×9のマスに、ルールを満たすように1〜9の数字を埋めていくゲームです。すべてのマスに数字が埋まれば完成です。

image

満たさなければならないルールは単純です。

  • そのマスを含む行(横一列)内で、数字の重複がないこと
  • そのマスを含む列(縦一列)内で、数字の重複がないこと
  • 全体を縦横3分割にした9つの領域それぞれで、数字の重複がないこと

初期状態で、ある程度のマスには数字が埋められています。埋められた数字をヒントにしながら、残りの空白のマスの数字をルールに従って埋めていきます。当然ながら、初期状態で空欄が多い(つまりヒントが少ない)ほど解くのが難しくなります。Wikipediaの記述によれば、初期状態でヒントの数が16個以下のものは解法を持ちえないことが証明されているそうです。

数独チェッカー(簡易版)

今回は、数独のすべてのマスに数字を記入し終わった状態が、正解なのか不正解なのかを判定する部分のみを取り上げ、プログラムで実装します。状況を単純にするために、いくつかの不正状態は考慮しないことにします。この数独チェッカー(簡易版)に求められる要件は次のとおりです。

  • 9x9の数独で、すべてのマスに数字が入った状態が正解か不正解かを判定する
  • マスに空欄がある状況は考慮しなくてよい
  • マスには1から9の数字のみが入力される。これ以外の値の入力は考慮しなくてよい

このチェッカーにおけるチェックアルゴリズムの一例は、次のようになります。

  • すべての行について重複がないかチェックを実行し、1つでも重複があれば不正解
  • すべての列について重複がないかチェックを実行し、1つでも重複があれば不正解
  • すべての領域について重複がないかチェックを実行し、1つでも重複があれば不正解
  • 不正解が1つもなければ、正解

愚直に書いたコード

チェックアルゴリズムは単純なので、そのままコードにすることはそれほど難しくありません。行、列、領域ではマスの取り扱い方がやや異なるので、行用のチェック、列用のチェック、領域用のチェックを別々のメソッドで実装することにします。作成した Checker.php は次のようになります。

※チェック部分では、イレギュラーな数値は存在しない前提としています。

// Checker.php
class Checker
{
    public function check(array $data): bool
    {
        if ($this->checkRows($data) === false) return false;
        if ($this->checkColumns($data) === false) return false;
        if ($this->checkRanges($data) === false) return false;

        return true;
    }

    /**
     * すべての行をチェックする
     * @param array $data
     * @return bool
     */
    private function checkRows(array $data): bool
    {
        foreach ($data as $row) {
            if (count(array_unique($row)) !== 9) return false;
        }

        return true;
    }

    /**
     * すべての列をチェックする
     * @param array $data
     * @return bool
     */
    private function checkColumns(array $data): bool
    {
        for ($i = 0; $i < 9; $i++) {
            $colData = [];
            for ($j = 0; $j < 9; $j++) {
                $colData[] = $data[$j][$i];
            }
            if (count(array_unique($colData)) !== 9) return false;
        }

        return true;
    }

    /**
     * すべての領域をチェックする
     * @param array $data
     * @return bool
     */
    private function checkRanges(array $data): bool
    {
        for ($i = 0; $i < 9; $i++) {
            $checkData = [];
            for ($j = 0; $j < 3; $j++) {
                for ($k = 0; $k < 3; $k++) {
                    $row = (int)($i / 3) * 3 + $j;
                    $col = ($i % 3) * 3 + $k;
                    $checkData[] = $data[$row][$col];
                }

            }
            if (count(array_unique($checkData)) !== 9) return false;
        }

        return true;
    }
}

最初の状態のクラス図 最初の状態のクラス図

ここまでの段階で、コードにどのような問題があるのかを考えるのは難しいかもしれません。以降ではまず抽象化などによって問題を捉え直し、その結果を使ってコードを書き直します。そこまで考えを進めてから振り返ることで、コードの問題が浮かび上がります。

問題を捉え直す

最初のコードは極端に愚直に書いたものでした。そこにはただ1つの Checker というオブジェクトがあり、checkRows() checkColumns() checkRanges() というプライベートメソッドを使ってチェックを実現しているということしか表現されていません。整理の糸口をつかむために、まずは数独の世界に登場する他の要素もオブジェクトに加えてみましょう。そうすることで、自然と問題を細かく見ていくことになり分析が進む、というのが典型的なオブジェクト指向のアプローチです。

オブジェクトを使う

この記事の最初に載せた数独のビジュアルイメージからは、まず次の2つがオブジェクトの候補になりそうです。

  • Cell (セル:1つのマス)
  • CellMatrix (セルのマトリックス。数独の全体。)

次に、チェックアルゴリズムの記述では、行や列、領域といった言葉が登場していますので、これらもオブジェクト候補として検討に加えましょう。

  • Row (行:セルマトリックスにおける、横一列のセルの集まり)
  • Column (列:セルマトリックスにおける、縦一列のセルの集まり)
  • Range (領域:セルマトリックスを縦横3分割にした、個々の正方形部分)

これらのオブジェクトの名前を使って、チェックアルゴリズムを表現しなおしてみましょう。

  • すべての Row について Cell の値に重複がないかチェックを実行し、1つでも重複があれば false
  • すべての Column について Cell の値に重複がないかチェックを実行し、1つでも重複があれば false
  • すべての Range について Cell の値に重複がないかチェックを実行し、1つでも重複があれば false
  • 不正解が1つもなければ、true

CellMatrix が現れていませんが、チェックアルゴリズムを実行する前提として数独のデータが存在していなくてはならないため、これもオブジェクトとして妥当なものとします。 これらのオブジェクトを使って書き直したコードは特に載せませんが、チェックアルゴリズムの表現方法は最初のものとほとんど同じになりそうですよね。もう少し上手い表現方法はないでしょうか?

バリエーションのある部分から抽象化を検討する

問題やコードでバリエーションのある部分を上手く扱うことは、コード設計の重要な関心事の一つです。今回の問題では、どのあたりにバリエーションがありそうでしょうか?

チェックアルゴリズム内にあらわれる「行のチェック」「列のチェック」「領域のチェック」の部分に何かありそうですね。この3つのチェック処理で、具体的には何が異なっているのかを考えてみましょう。どのチェックでも、9つのマスを対象にし、9つのマスに入っている数字に重複がないということをチェックしています。これらは、3つのチェック処理の共通性です。逆に異なっているのは何でしょうか? 答えは、チェック処理の「対象とするデータ範囲の形状」です。これが、チェック処理における可変性です。

チェックアルゴリズムの共通性と可変性 共通性と可変性

この共通性を軸として抽象化を検討していきます。しかし、現段階ではまだ、この抽象を具体的にどのように扱うのかは定まっていません。実装イメージを持ちながら、順に検討していきましょう。

数学的な抽象を使う道

チェック対象とするデータのバリエーションである行、列、領域ですが、数学的に言えば、「行」と「列」のいずれも「領域」とみなすことができます。「行」は「縦が1マス、横が9マスの領域」であり、「列」は「縦が9マス、横が1マスの領域」だからです。この見方を採用すると、行や列という特化した表現は捨てて領域という表現に一本化できます。すると、チェック処理からバリエーションを取り除くことができそうですね。

この抽象を採用すると、Checker クラスのコードはどうなるでしょうか。チェック対象のデータは、「領域」という概念に一本化されます。Checker クラスにあるチェック用プライベートメソッドは checkRanges() だけが残ることになります。コード量が減って一見良さそうです。 しかし、checkRanges() メソッドのコードがチェック処理として本質的なのかどうか、疑問が残らないでしょうか。

データ抽象を使う道

今回のチェック処理で必要としている本質的なデータを考えてみます。数独のチェックに必要なのは、「9つのマスに1から9の数字が重複なく入っている」ということだけです。9つのマスの並びが行であっても列であっても領域であっても、このチェック内容を表現した文章はそのまま適用できます。つまり、チェック処理はマスの形状に依存しないということです。そうすると、チェック処理には「9つのマス(並び方は関係ない)」だけが渡されれば十分ですね。

このように、扱っているデータから、今着目している部分以外を取り除き、必要な部分に絞って取り扱う技法をデータ抽象と呼びます。

「並び方に依存しない9つのマス」を扱うために、次のような CellCollection クラスを用意します。実装を簡単にするために、LaravelのCollectionクラスを継承しています。

// CellCollection.php
use Tightenco\Collect\Support\Collection;

class CellCollection extends Collection
{
}

問題に表れる行、列、領域である Row Column Range は、基本的にはセルの集まりでもある(Row is a CellCollection)ため、CellCollection を継承するようにしておきます。

// Row.php
class Row extends CellCollection
{
}

アプリケーションのどこかで、盤面である CellMatrix から、行に対応する Row、列に対応する Column、領域に対応する Range が切り出されるものとします(後述)。 この3種類はどれも CellCollection を継承しています。Checker のチェックアルゴリズムが対象領域の形状に依存しないよう、CellMatrix だけを使って書き直してみます。

// Checker.php
class Checker
{
    /**
     * @var array|CellCollection[]
     */
    private $targets = [];

    /**
     * @param CellCollection $range
     * @return $this
     */
    public function addTarget(CellCollection $range)
    {
        $this->targets[] = $range;

        return $this;
    }

    /**
     * @return bool
     */
    public function check(): bool
    {
        foreach ($this->targets as $target) {
            if ($this->checkOneTarget($target) === false) return false;
        }

        return true;
    }

    /**
     * @param CellCollection $cellCollection
     * @return bool
     */
    private function checkOneTarget(CellCollection $cellCollection): bool
    {
        return $cellCollection->map(function($item, $key) {
            return $item->getNumber();
        })->unique()->count() === 9;
    }
}

最後に、CellMatrixChecker を構成するコードを App.php に記述します。数独の盤面の構造を表す CellMatrix の構造、および、Checker でチェックする行、列、領域の構造はアプリケーションのライフサイクルの中で変わることはないため、App.phpのコンストラクタに記述しています。

// App.php
class App
{
    /**
     * @var CellMatrix
     */
    private $cellMatrix;

    /**
     * @var Checker
     */
    private $checker;

    public function __construct()
    {
        $this->cellMatrix = new CellMatrix();
        $this->checker = new Checker();

        for ($i = 0; $i < 9; $i++) {
            // 行
            $row = $this->cellMatrix->getRow($i);
            $this->checker->addTarget($row);

            // 列
            $column = $this->cellMatrix->getColumn($i);
            $this->checker->addTarget($column);

            // 領域
            $left = (int)($i / 3) * 3;
            $top = ($i % 3) * 3;
            $range = $this->cellMatrix->getRange($left, $top, $left + 2, $top + 2);
            $this->checker->addTarget($range);
        }
    }
    // ...

これで一通りの修正が完了しました。修正前と修正後の Checker を比べてみてください。修正前のコードにどのような問題があったのかも浮かび上がっています。

  • 複数のチェックメソッドに重複して記述されていたチェック処理 → 一本化された
  • 行や列、領域といった詳細な事情(=対象となるセル群の形状に関する情報) → チェック処理から切り離された

修正後のクラス図 修正後のクラス図

CellCollection は、今回の問題空間におけるデータ抽象です。データ抽象を導入したことで、盤面の構造に関心のあるコードと、正解かどうかのチェックに関心のあるコードの接点が小さくなりました(情報隠蔽)。

  • 盤面の構造に関心のあるコード
    • Cell
    • CellMatrix
    • (CellCollection)
    • Row
    • Column
    • Range
  • 正解かどうかのチェックに関心のあるコード
    • CellCollection
    • Checker

おわりに

抽象化というのは、コード内で抽象クラスやインターフェイスを使うことだけを指すのではありません。問題の捉え方そのものに抽象化を使うことが本質です。そしてこのようにして見出した本質的な構造は、ある状況における問題の形態(Form)であり、それこそがソフトウェアの骨格を作るアーキテクチャとなっていくものだと思います。

そんなアーキテクチャを、たとえ小さな箇所においてでも見つけられることが、ソフトウェア設計の楽しさですよね。

参考:ジェームス・O・コプリン著『新装版 マルチパラダイムデザイン』