アルゴリズムを解く５

3 * 3の9 * 9マスからなる正方形の盤面のアルゴリズム

いくつからのますに数字が入れられている上たから数字の入っていない各ますに、１〜９のうちどれか一つの数字を入れていく。

パズルを解く手順

（１）盤面の左上端から探索を開始する。ますは左端から順に右方向に探索し、右端に達したら1行下り、左端から順に探索する

（２）空白のマスを見つける

（３）(2)で見つけた空白のますに、１〜９の数字を順番に入れる

（４）数字を入れた時に、その状態がパズルのルールに則っているかどうかをチェックする

ルールに則っている場合は(2)に進んで次の空白のマスを見つける
ルールに則っていない場合は、(3)に戻って次の数字を入れる。この時も、入れる数字がない場合には、マスを空白を戻して一つ前に数字を入れたマスに戻り、(3)から再開する

（５）最後のマスまで数字が入り、空白のマスがなくなったら、それが回答となる。

盤面の表現

9*9の盤面を81個の要素を持つ一次元配列boardで表現する。
添字は０から始まる。

ルールのチェック方法

3 * 3の枠内の左上端のマスを特定し、行、列、枠内のマスに既に格納されている数字と、入れた数字がそれぞれ重複していないことを確認する。このチェックを"重複チェック"という。

解放のプログラム

メインプログラム

function main()
    board[]を初期化する
    solve(0) # 盤面を表すboard[]の添字xを引数とする
endfunction

関数solveのプログラム

function solve(x) 
    if (xがMAX_BOARD-1より大きい) # 引数がboard[]の最後の添字ならば
        print_board() # board[]の内容を出力する
        exit() # メインプログラムを終了
    else # 最後の添字でなければ
        if(<ア>) # 空白でなければ
            solve(<イ>）# 次の要素に対してパズルを解くためのsolve処理を行う
        else # 空白であれば
            for(nを1から9まで１ずつ増やす）# １から９を入れていく
                if (<ウ>) # チェックでOKならば
                    board[x]←n # board[x]に格納している
                    solve(<イ>) # 次の要素に対してパズルを解くためのsolve処理を行う
                    board[x]←<エ> # 空白にする
                endif
            endfor
        endif
    endif
endfunction

if(<ア>)

board[]の添え字が最後尾ではない場合の処理内容
最初の空白のマスを見つける処理をしているのでそれをすると思う。

空白の場合は０を格納する

board[x]が０と等しい

書き間違えた
board[x]が０と等しくない

solve(<イ>）

次の要素を調べるので
x+1

if (<ウ>)

row_ok(n,x)とcolumn_ok(n,x)とframe(n,x)が共にtrueならば

間違えた
check_okがソースコードに書かれていなかったのを怠った。
説明文を見れば確認コードを全て呼び出す関数なので
check_ok(n,x)がtrueと等しい

board[x]←<エ>

マスを空白に戻して一つ目に数字を入れたますに戻り

0

重複チェックを行うプログラムの一部

funtion row_ok(n,x) # nはチェック対象の数字, xはチェック対象のマスをを示す添字
    row_top ← <オ> # 数字を入れようとするますが含まれる横1行の左端のマスを示す添字
    for(iを0から8まで一つずつ増やす）
        if(<カ>) # 下の行を見るとfalseと書いてあるのでこの分岐は重複がある場合の条件
            return false
        endif
    endfor
    return true
endfunction

function column_ok(n,x)
    column_top ← <キ>
    for(iを0から8まで一つずつ増やす)
        if(<ク>)
            return false
        endif
    endfor
    return true
endfunction

function frame_ok(n, x)
    frame_top ← x - <ケ> - mod(x,3)
    for (iを0から2まで1ずつ増やす)
        for (jを0から2まで1ずつ増やす)
            if(board[frame_top + 9 * i + j]がnと等しい)
                return false
            endif
        endfor
    endfor
    return true
endfunction

row_top ← <オ>

横1行の重複チェックを行う関数

任意の行の左端の要素を取得するためには常に左端の要素に対応する数式を使う
添字を求められているからxはチェック対象のマスをを示す添字を使う
数式を想像しながらトレースする
9*div(x,9)

if(<カ>)

横1行の重複チェックを行う関数

要素の値に重複があった場合の条件なのでnはチェック対象の数字を使う
横1行内の重複の見分け方はどうすればいいか？
iを0から8まで一つずつ増やすと1行上の条件式に書かれているのでiを使う
nがboard[row_top+i]と等しい

column_top ← <キ>

colunm_top:縦1行の上端のマスを示す添字を格納する
任意の要素の添字から任意の要素の左端の添字を引けばいい
9*div(x,9)-x

書き間違えた
x-9*div(x,9)

if(<ク>)

縦1行の重複チェックを行う関数
9*div(i,9)で縦方向に進めるそれにcolumn_topを使って横方向に移動することができる
9*div(i,9)+column_top

間違えた
board[9*i+column_top]がnと等しい
改めて考えれば9*iするべきだった。

frame_top ← x - <ケ> - mod(x,3)

3 * 3の枠内の重複チェックを行う関数
mod(x,3)はトレースしてみると上に移動するための差分になる
なので横の移動する差分を見つければいいと思う。それが左端の要素の添字
9*div(x,9)
90,91,9*2にすれば引くことができる

わからなかった。
mod(div(x,9),3)*9
もっとトレースすればなぁ

(2)空白のマスを見つける

(3)データ構造Zを参照し、（２）で見つけた空白のマスに入れることができる数字のリストを取得し、リストの数字を順番に入れる。
(3-1)入れる数字がある場合、処理Aを行った後、マスに数字を入れる。その後、データ構造Zの更新処理を行い、(2)に進んで次の空白のマスを見つける
(3-2)入れる数字がない場合、ますの空白に戻し、処理Bを行った後、一つ前に数字を入れたマスに戻り、戻ったマスで取得したリストの次の数字から再開する。

(4)最後のマスまで数字が入り、空白のマスがなくなったら、それが解答となる

処理Aの内容

• 入れる数字があれば処理Aを行う
• マスに数字を入れる

マスに数字を入れる前に処理Aを行っているのでマスに入れる処理を探る。
最初の処理に対して新たに初期化処理を追加し、処理内容が変化した。

追加前

(2)　空白のマスを見つける
(3)　(2)で見つけた空白のマスに、1~9の数字を順番に入れる。
(4)　数字を入れた時に、そのお状態がパズルのルールにのっとっているかどうかをチェックする
　　(4-1)　ルールに則っている場合は、(2)に進んで次の空白マスを見つける。
　　(4-2)　ルールに則っていない場合は、(3)に戻って次の数字を入れる。この時、入れる数字がない場合には、マスに空白に戻して一つ前に数字を入れたマスに戻り、(3)から再会する。
(5)　最後のマスまで数字が入り、空白のマスがなくなったら、それが解答となる。

追加後

(2)　空白のマスを見つける。
(3)　データ構造Zを参照し、（２）で見つけた空白のマスに入れることができる数字のリストを取得し、リストの数字を順番に入れる。
　　(3-1)　入れる数字がある場合、処理Aを行った後、マスに数字を入れる。その後、データ構造Zの更新処理を行い、(2)に進んで次の空白のマスを見つける
　　(3-2)　入れる数字がない場合、ますの空白に戻し、処理Bを行った後、一つ前に数字を入れたマスに戻り、戻ったマスで取得したリストの次の数字から再開する
(4)　最後のマスまで数字が入り、空白のマスがなくなったら、それが解答となる。

データ構造Zとは

盤面のマスの数*9の要素を持ち、添字xは０から、添字nは１から始まる2次元配列とする。Z[x][n]は、ゲームのルールに則ってboard[x]に数字を入れることができる場合は要素に１を、できない場合は要素に０を格納する。

感想

最後の問題を解けなかったが理解したい。
とんでもなく間違った。
解説を読んでも理解できなかった。しかし
データ構造Zに対する理解度が低いことが分かった。

解説

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

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

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

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

再度データ構造Zを理解する

解法のプログラムは深さ優先探索であり，探索の範囲が広くなるほど，再帰呼出しの回数が指数関数的に増加し，重複チェックの実行回数も増加する。
　そこで，重複チェックの実行回数を少なくするために，各マスに入れることができる数字を保持するためのデータ構造Zを考える。データ構造Zは盤面のマスの数×9の要素をもち，添字xは0から，添字nは1から始まる2次元配列とする。Z[x][n]は，ゲームのルールにのっとってboard[x]に数字nを入れることができる場合は要素に1を，できない場合は要素に0を格納する。データ構造Zの初期化処理と更新処理を表2のように定義した。
　なお，データ構造Zは大域変数として導入する。

• 重複チェックの実行回数を少なくするために使う
• 各マスに入れることができる数字を保持する
• データ構造Zの構造は2次元配列
• 数字nを入れることができる場合は要素に1
• 数字nを入れることができない場合は要素に0を格納する

処理化処理

空白のマスに入れることができない数字は、データ構造Zの該当する数字の要素に0を設定するそれ以外の要素には１を設定する。

更新処理

データ構造Zの該当する数字を０に更新する