解説

本問で扱っているパズルは、"数独"や"ナンプレ(ナンバープレース)"と呼ばれるものです。もし文章だけではルールがわかりにくい場合は、実際にプレイしてみるとイメージしやすいでしょう。

解説の便宜上、図5のプログラムに行番号を振っておきます。〔アについて〕
空欄にはif文の条件式が入ります。6行目のコメントに「//対象のマスが空白でない場合」とあるので、これを表現できるような条件式を考えます。

〔盤面の表現〕を読むと、9×9の盤面は全81個から成る1次元配列 board で表現され、空白の場合は要素に0を格納するとあります。表1の solve(x) の説明に「盤面を表す board[] の添字xを引数とする」とあるため、関数 solve 内において現在対象となっているマスはxであり、それに対応する配列 board 上の要素は board[x] で参照することができます。

対象のマスが空白でないときに条件式がtrueを返すようにしたいので、適切な条件式はboard[x]が0でないとなります。

∴ア＝board[x]が0でない

〔イについて〕
空欄は関数 solve の引数です。7行目のコメントに「//次の探索」とあるように、対象のマスが空白でない場合には、空白のマスが見つかるまで探索対象を次のマスに移す操作を行うことになります。したがって、[イ]に入るのは次に探索するマスの添字となります。

〔パズルを解く手順〕(1)に「マスは左端から順に右方向に探索し，右端に達したら一行下がり，左端から順に探索する」とあることから、次に探索するマスとは、探索しているマスの右隣、右端を探索している場合は一行下の左端となります。図3が示すとおり盤面の情報は一次元配列の board に格納されていて、xの次のマスは単純にx＋1となっています。

したがって、関数 solve の引数として指定するのはx＋1となります。

∴イ＝x＋1

〔ウについて〕
空欄にはif文の条件式が入ります。[ウ]がある10行目にはコメントがないので、分岐後の処理から条件式を推測します。

分岐後の処理を見ると、11行目で添字xのマスに数字を入れ、直後の12行目では次のマスの探索を行っています。ここで〔パズルを解く手順〕の内容と照らし合わせると、この「数字を入れた後に次のマスを探索する」に該当する手順は(4-1)とわかります。これより、[ウ]には手順(4-1)の実行条件、すなわち「数字を入れたときに、その状態がパズルのルールにのっとっている」を満たす場合にtrueとなる条件式が入ると判断できます。

ここで、パズルのルールは本文中で「盤面の横1行，縦1列，及び太線で固まれた3×3の枠内の全てにおいて，1～9の数字が一つずつ入る(＝数字の重複がない)」と説明されています。このルールをチェックする処理は1行で書き表せないほど複雑ですが、表1を見ると、以下の3つを全部まとめて呼び出す関数 check_ok が用意されていることがわかります。

• 横1行の重複チェックを行う関数 row_ok
• 縦1行の重複チェックを行う関数 colmun_ok
• 3×3の枠内の重複チェックを行う関数 frame_ok

これを利用すれば対象のマスの重複チェックを1行で記述できます。

関数 check_ok(n, x) の説明には「横1行・縦1列・3×3の枠内それぞれで重複が"ない"場合にtrueを返す」とあるので、関数 check_ok がtrueを返せば「パズルのルールにのっとっている」という条件を満たすことになります。引数nはチェック対象の数字なので現在マスに入れようとしている数字を保持するループ変数のn、引数xはチェック対象マスの添字なので現在対象となっているマスに対象となっているマスの添字を保持するxを指定します。したがって、[ウ]に当ては条件式はcheck_ok(n, x)がtrueと等しいとなります。

∴ウ＝check_ok(n, x)がtrueと等しい

〔エについて〕
空欄に入るのは、board[x]（探索対象のマス）に代入する値です。[エ]が含まれる行のコメントには「//再帰から戻った場合のマスの初期化」とあります。

関数 solve は再帰構造になっていて、10行目のif文がtrueとなった場合には対象のマスに数字を入れて次のマスの探索に移ります。その後、次のマスに何らかの数字が入ればさらに次のマスの探索に移りますが、何の数字も入らない場合には関数 solve は何もせずに呼出し元に帰る（再帰から戻る）ことになります。したがって、solve の次に位置する13行目の処理は、次のマスに何の数字も入らなかったときに行われる処理ということになります。

今そのマスに入れいている数字では次のマスに入る数字がないので、先ほど board[x] に入れた数字を初期化する必要があります。仮の数字が入ったままだと重複チェックが正しく動作しないためです。マスの初期状態は空白、空白は0で表すので、board[x] に代入すべきは0が適切です。

∴エ＝0

解説

解説の便宜上、図6のプログラムに行番号を振っておきます。〔オについて〕
対象のマスを示す添字xから、その行の左端のマスを示す添字を求める式が入ります。
行の左端マスの添字は、上から順に0,9,18,…,72と9の倍数になっており、具体的には、xと左端のマスの添字は以下のように対応しています。

• 0～8の場合 → 0
• 9～17の場合 → 9
• …
• 72～80の場合 → 72

これを一般化すると、左端のマスを示す添字は x÷9 の商を求めそれに9を乗じた数と等しくなっています。表1には除算の商部分を求める関数 div が用意されているので、div(x, 9)*9とすれば、行の左端にあたるマスの添字を求めることができます。

xからxを9で割った余りを引いても求められるので、x－mod(x, 9)も解答として可です。

∴オ＝div(x, 9)*9

〔カについて〕
表1より、関数 row_ok は横1行の重複チェックを行う関数で、数字の重複がある場合にはfalseを返すことがわかります。動作としては、for文でiを1ずつ増やすことで行の左端から1マスずつチェックしていき、nと同じ数があった場合には"重複あり"と判定しています。if文が真のときにはfalseを返しているので、空欄に入るのは、nと同じ数字が見つかったときにtrueとなる条件式です。

行の左端を示すマスは変数 row_top を用いて board[row_top]、左端から1つ右のマスは board[row_top＋1]、その1つ右のマスは board[row_top＋2] というように表せるので、for文中で現在重複チェックしているマスは board[row_top+i] と表すことができます。

board[row_top＋i] にnが格納されている場合には"重複あり"ということになるので、条件式としてはboard[row_top＋i]がnと等しいが適切です。

∴カ＝board[row_top＋i]がnと等しい

〔キについて〕
対象のマスを示す添字xより、その列の上端のマスを示す添字を求める式が入ります。具体的には、xと上端のマスの添字は以下のように対応しています。

• 0,9,18,27,…,72の場合 → 0
• 1,10,19,28,…,73の場合 → 1
• …
• 8,17,26,35,…,80の場合 → 8

これを一般化すると、上端のマスを示す添字は x÷9 の余りと等しくなっています。表1には除算の剰余を求める関数 mod が用意されているので、mod(x, 9)とすれば、列の上端にあたるマスの添字が求められます。

∴キ＝mod(x, 9)、別解：x－div(x, 9)*9

〔クについて〕
表1より、関数 colmun_ok は縦1列の重複チェックを行う関数で、数字の重複がある場合にはfalseを返すことがわかります。関数 row_ok と同様にループ変数 i を使って縦1列をチェックしていき、値の重複があればfalseを返す仕様です。

添字の値は行が1つ下になるたびに9増えるので、列の上端を示すマスは変数 column_top を用いて board[column_top]、上端から1つ下のマスは board[column_top＋9]、その1つ下のマスは board[row_top＋18] ということになります。＋9、＋18の部分をiを使って表現すると「9*i」となるので、for文中で現在重複チェックしているマスは board[column_top＋i*9] と表すことができます。

board[column_top＋i*9] にnが格納されている場合には"重複あり"ということになるので、条件式としてはboard[column_top＋i*9]がnと等しいが適切です。

∴ク＝board[column_top＋9*i]がnと等しい

〔ケについて〕
対象のマスを示す添字xより、その枠内の左上端のマスを示す添字を求める式が入ります。

関数 frame_ok の2行目には既にxから mod(x, 3) を引く式が記されているので、 まずはこの処理の意味について考えます。
チェック対象の添字xから mod(x, 3) を引いた値は、チェック対象のマスが、

• 1,4,7列目にある場合は、対象のマス自身の添字
• 2,5,8列目にある場合は、対象の1つ左のマスの添字
• 3,6,9列目にある場合は、対象の2つ左のマスの添字

になります。引いた後の添字は「行の位置は変わらず、列は3×3の枠内の左端の位置」になっているので、列位置を左端に揃えるという役割を持っています。

したがって、[ケ]には「列の位置を変えずに、行を3×3の枠内の上端の位置」にするために引くべき値を入れればよいです。具体的には、チェック対象のマスが、

• 1,4,7行目にある場合は、そのまま（0を引く）
• 2,5,8行目にある場合は、9を引く
• 3,6,9行目にある場合は、18を引く

ことで、行が3×3の枠内の上端の位置に揃います。問題は2,5,8→9、3,6,9→18という関係を式でどのように表現するかです。

上記の「引くべき値」は、1,2,3行目の場合には div(x, 9)*9 で求められますが、4～9行目の場合はこれでは不適切です。ここで、4～6行目では「div(x, 9)*9」と「引くべき値」の差が27、7～9行目では「div(x, 9)*9」と「引くべき値」の差が54になっているので、「div(x, 9)*9」を27で割った剰余を使う、すなわち「mod(div(x, 9)*9, 27)」が引くべき値を求める式ということになります。以上より、答えはmod(div(x, 9)*9, 27)です。

∴ケ＝mod(div(x, 9)*9, 27)

※別解が多数考えられるため、別の解答が正しいか確かめたい場合はプログラムや表計算ソフト等で確認してみてください。
<別解例>
mod(div(x, 9), 3)*9
div(mod(x, 27), 9)*9
div(x, 9)*9 - div(x, 27)*27 等

解説

データ構造Zの更新処理では、マスに数字を入れたときにそのマスに関連するマスの数字の要素を0にすることはできますが、逆に0を1に戻すことはできません。つまり、マスに数字を入れた場合、データ構造Zの内容は不可逆となってしまうということがポイントです。

入れる数字がなくマスを空白にして前に戻る場合、そのマスに数字を入れる前の状態のデータ構造Zが必要になりますが、次のマスの処理で更新されているデータ構造Zは巻き戻し不可なので使うことはできません（データ構造は大域変数）。また、データ構造Zを巻き戻すには盤面に対して戻った都度重複チェックを行う必要があり、本文で記されている「重複チェックの実行回数を少なくする」という方針に適しません。これを回避するために、数字を入れて次のマスの探索に移る前に、数字を入れる前のデータ構造Zを関数内の一時変数として保持しておく必要があります。

数字を入れる前にデータ構造Zを退避しておき、マスを空白にして一つ前に戻った後に退避したデータ構造Zを取り出せば適切に処理を進めることができます。したがって、[処理A]はデータ構造Zを退避する、[処理B]は退避したデータ構造Zを取り出すとなります。

∴処理A＝データ構造Zを退避する
　処理B＝退避したデータ構造Zを取り出す