【プログラミング】業務的思考と学問的思考【数独】

こんにちは。ディマージシェアの技術担当です。
今回は数独を解くプログラムを作成し、業務的な考え方と、学問的な考え方を対比してみたいと思います。

数独

　数独は有名なペンシルパズルの1つです。詳細はgoogleで調べてください。ゲームとして手軽に楽しめる数独ですが、学問的には充足可能性問題（SAT）に分類され、SATは今でも盛んに研究が行われています。

　市販されているゲームとしての数独は人間が解くことができるように調整されています。人間が解くには難易度が高すぎる問題でも、コンピュータならば解くことができます。
　難易度の高い数独の問題を解くプログラムを作ろうと考えた際、業務的な考え方、コーディングと、学問的な考え方を紹介したいと思います。学問的なコーディングに関してはgoogleで論文を探した方が良いコンテンツがあるのでここでは割愛します。

業務的な考え方、コーディング

　業務的な考え方は、第一に理解のしやすさが来ます。コンピュータは単純なことを何回も繰り返すことが得意です。なので、計算の効率を考えたときに、多少非効率的でもその方法で課題が解決できるのであれば、業務的には問題ありません。

　例えば数独では、人間が解くときは何かしらのテクニックを用いることがほとんどです。「数独、解き方」のようなワードで検索すると出てくる手法です。しかし、これらはどれも、プログラムとして実装しようと思うと簡単とは言えないものが多いです。先述したように、コンピュータは単純なことの繰り返しが得意なので、左上のマスから手あたり次第試す、ということが試せます。とりあえずこの方法で実装してみます。言語はPHPを採用してみました。

<?php

$sudoku = [
 [0,0,0,1,0,0,0,0,4],
 [0,7,9,0,0,0,3,0,2],
 [0,0,0,7,9,0,0,8,1],
 [5,0,0,8,0,6,4,3,9],
 [9,3,7,4,5,0,8,2,6],
 [0,0,0,0,3,0,0,1,0],
 [2,9,4,3,1,8,0,5,0],
 [0,5,1,6,4,7,2,0,8],
 [7,6,0,9,2,5,0,0,0]
];

function print_sudoku($sudoku) {
 for ($i = 0; $i < 9; ++$i) {
   for ($j = 0; $j < 9; ++$j) {
     echo ($sudoku[$i][$j] !== 0 ? $sudoku[$i][$j] : ' ') . ',';
   }
   echo "\n";
 }
}

function solve($sudoku) {
 /* 空きマスを選ぶ */
 if(blank($sudoku, $tate, $yoko)) {
   for($n = 1; $n <= 9; ++ $n) {
     /* 空きマスにnを入れることがルール違反でない */
     if(is_valid_move($sudoku, $tate, $yoko, $n)) {
       $sudoku[$tate][$yoko] = $n;/* マスを埋める */
       solve($sudoku);
       $sudoku[$tate][$yoko] = 0;/* 手を戻す */
     }
   }
 } else { /* 空きマスがない（解けている） */
   print_sudoku($sudoku);
 }
}

/* 適当な空きマスを探す */
function blank($sudoku, & $tate, & $yoko) {
 for($i = 0; $i < 9; ++ $i) {
   for($j = 0; $j < 9; ++ $j) {
     if($sudoku[$i][$j] === 0) {
       $tate = $i;
       $yoko = $j;
       return true;
     }
   }
 }
 return false;
}

/* 指定位置に値nを入れる事が可能か */
function is_valid_move($sudoku, $tate, $yoko, $n) {
 if($sudoku[$tate][$yoko] !== 0) {
   return false;//すでに値が入っている
 }
 for($i = 0; $i < 9; ++ $i) {
   if($sudoku[$tate][$i] === $n || $sudoku[$i][$yoko] === $n) {
     return false;//同じ行，または列に該当する数字がある
   }
 }
 $is = (int)($tate / 3) * 3;
 $js = (int)($yoko / 3) * 3;
 for($i = $is; $i < $is + 3; ++ $i) {
   for($j = $js; $j < $js + 3; ++ $j) {
     if($sudoku[$i][$j] === $n) {
       return false;//同じブロックに該当する数字がある
     }
   }
 }
 return true;
}

solve($sudoku);

　コードとしてはこれだけです。印刷してもA4の用紙2枚に収まる規模です。実際にこのコードは実行時間も一瞬で数独の答えが得られます。特に人間が解ける程度の難易度の数独であれば、このコードで十分です。

　このように、単純なロジック、少ないコード、時間さえかければ必ず解ける（理屈上は）ようなコードに落とすのが業務的な考え方、コーディングになります。
　競技プログラミングで例えると、3段階のうち2段階目くらいの難易度です。3段階目はきちんとアルゴリズムを組まないと戦えません。

学問的な考え方

　数独を解くプログラムを一度でも作成したことがある方は、先に紹介したコードでは、ちょっと難しい問題を与えるだけで現実的な実行時間で解けないことはご存じだと思います。例えば人間が解くときに用いる各種テクニックをソースコードに反映すれば、数千倍以上の性能向上が実現できます。しかし、コードの量が嵩み、かつデバッグの困難性も上がります。業務で性能の向上が求められているならば必要経費ですが、業務上の性能要件を満たしているときにこちらの方向へコストを割くことはできません。

　数独を解くプログラムの学問的な最適解は、世に出回っているSATソルバーを用いる方法です。SATソルバーはとても高度に計算量を減らす工夫がされています。誤解を生みそうな表現になりますが、SATソルバーに使われているテクニックのうち、数独に転用可能でかつ人間が理解できる程度の工夫が、数独を解くテクニックとして広く認知されています。言い換えれば、どんなに頑張って数独を解くテクニックを充実させたソルバーを実装しても、SATソルバーの性能には全く歯が立ちません。

まとめ

　業務的な考え方、コーディングと、学問的な考え方を紹介しました。本記事では、かなり極端な対極的な例を紹介しました。実際の業務では、双方の考え方をバランス良く検討し、丁度良い落としどころを見つけることが大切です。
　また、業務的な考え方の視野だけでは「不可能でしょ」という問題も、学問的な考え方に精通している人からすれば「やり方を間違えなければ大丈夫」といったように、人によって問題の見え方は違います。もし、チームで何らかの課題に取り組む場合は、誰がどの分野に強いかを把握し、上手くコントロールするのが成功のコツです。