# ***そうだナンプレしよう***
この記事は、 **大阪工業大学 Advent Calendar** 2022(https://adventar.org/calendars/7957)の**11日目**の記事です。

::: warning
**前置き長いので遠慮なく読み飛ばしてください。**
:::
はじめまして、ちくわです。
早いもので12月ですねー、月並みなアレですけどもう今年終わりますよ　**\ﾅ､ﾅﾝﾀﾞｯﾃｰ/**
いやー、最近さみぃですね。我が家は親の部屋にしかエアコンがないので夏も冬もやせ我慢の日々を過ごしています。気分は修行僧ですよ……
この時期はお布団君が神アイテムすぎて永遠に二度寝できますね。毎朝僕のことをがっちり掴んで離してくれないのがちと困りものですが、**マイベストフレンド**は彼奴だと思っています。
~~心なしか寝坊（未遂も含む）が増えた気がします、マジで~~

さて、特にネタもなく軽い気持ちで登録してしまったがために12/10現在、何を書こうかなぁと頭をうならせているわけです。自業自得なんですけどね(笑)
その末に絞り出したネタがタイトルにもある通りナンプレです。

僕がナンプレをはじめとするパズルにハマりだしたのは小学生の頃にEテレ（NHK）で夕方放送していた[**ファイ・ブレイン 神のパズル**](https://www6.nhk.or.jp/anime/program/detail.html?i=phibrain)がきっかけですかねー
データ放送でアニメに登場したパズルやそのほかにもたくさんのパズルが遊べて家に帰ってテレビの前に張り付いてた記憶があります。
その結果、自分でナンプレを自作するみたいなこともやったことあります。祖父が数独好きだったので作ったやつを解かせたりとか(笑)

::: success
**その時の純粋無垢なちくわ少年はこうも思ったわけです。一瞬でナンプレがﾊﾞﾊﾞﾊﾞｰｰｯって解けないかなって**
:::
今日はその頃の純粋な少年の願いをかなえたいと思います、もちろんプログラミングの力でね（にちゃあ）

ということで今回は**Python**を使ってナンプレの解答を一瞬で出力するプログラミングをつくっちゃいます、ﾊﾟﾁﾊﾟﾁﾊﾟﾁｰ

---

# そもそもナンプレってなに？
まぁ知らない人多分いないと思います。ですが念のため
ナンバープレース縮めてナンプレ、別名数独といいます。
数独の名前の由来にあるとおり「数字は独身に限る」というのがルールを表しています。
ようするに縦横そして3×3のブロック内に同じ数字がかぶらないように1-9の数字(1-16のものもあったりします)を配置していくゲームです。以外と説明するのむずいのでニコリの[リンク](https://www.nikoli.co.jp/ja/puzzles/sudoku/)貼っときます。（~~はいそこ説明できてないとか言わない~~）

# どうやって解答を得る？
::: danger
**ほんのすこーーーしだけ技術的なこと書いてますが正確だという保証はないので鼻ほじりながら軽く読んでください**
:::
ではどうやって解答を求めましょう？
答えは簡単、**組み合わせを全通り探索してルールに違反しないものが解答です。**
今回は再帰的な関数を用いてしらみつぶしにパターンを探索していく方法で実装しましょう。
再帰的ってなんだって思った方は数列を思い出しましょう。

$$
a_{n}=ka_{n-1}
$$

こんな感じで$a_{n}$を求めようと思ったら$a_{n-1}$が必要で$a_{n-1}$を求めようと思ったら$a_{n-2}$が必要でが無限に続いていきますよね、最終的に$a_1$まで遡れば今度は$a_n$に向かって**元来た道をたどるように値が求まっていきます**。
この一連の流れを再帰的と呼びます（間違っているかもしれないけど）

これをナンプレに用いると左上から試しに数字を入れてルール違反をしていなければ次のマスで同じことを、**間違っていれば1つ手順を戻して別の数字を試す**ということを繰り返すことによって答えを求めることができます。
愚直に次のマス(深さ)に進めることを優先するため**深さ優先探索**と言われたりもしています。
[深さ優先探索のwiki](https://ja.wikipedia.org/wiki/%E6%B7%B1%E3%81%95%E5%84%AA%E5%85%88%E6%8E%A2%E7%B4%A2)

# 実装例
問題は任意で設定できます。（空白を0で記述しています）
どのような順番で関数が呼ばれているかぜひ追ってみてください。

### ソースコード

cnt = 0
input_problem = [
    [0, 0, 1, 0, 0, 3, 9, 6, 0],
    [0, 4, 0, 0, 9, 7, 0, 0, 0],
    [0, 8, 7, 0, 0, 0, 0, 0, 5],
    [0, 0, 0, 0, 0, 9, 3, 4, 0],
    [0, 5, 0, 0, 0, 0, 0, 0, 6],
    [0, 0, 0, 1, 6, 0, 2, 0, 0],
    [0, 0, 0, 6, 0, 0, 0, 0, 9],
    [6, 0, 0, 0, 0, 0, 1, 0, 0],
    [0, 0, 3, 0, 8, 0, 0, 0, 0]]


def keep_violation(grid, y, x, num):
    ck_row = num not in grid[y]
    ck_col = num not in [i[x] for i in grid]
    block_x, block_y = (x//3) * 3, (y//3) * 3
    block = [i[block_x:block_x+3] for i in grid[block_y:block_y+3]]
    ck_block = num not in sum(block, [])
    return (ck_row and ck_col and ck_block)


def find_next(grid):
    for y in range(9):
        for x in range(9):
            if grid[y][x] == 0:
                return y, x
    return -1, -1


def solve(grid, y=0, x=0):
    global cnt
    y, x = find_next(grid)
    if (y == -1 or x == -1):
        return True
    for num in range(1, 10):
        if keep_violation(grid, y, x, num):
            grid[y][x] = num
            if solve(grid, y, x):
                return True
            cnt += 1
            grid[y][x] = 0
    return False


def display(grid):
    for y in range(9):
        for x in range(9):
            print(grid[y][x], end=" ")
            if (x == 2 or x == 5):
                print("|", end=" ")
        print("")
        if (y == 2 or y == 5):
            print("ー－－－－－－－－－－")


solve(input_problem)
display(input_problem)
print("やり直し回数 {0}回".format(cnt))

### 出力結果

5 2 1 | 8 4 3 | 9 6 7 
3 4 6 | 5 9 7 | 8 1 2 
9 8 7 | 2 1 6 | 4 3 5 
ー－－－－－－－－－－
8 6 2 | 7 5 9 | 3 4 1 
1 5 4 | 3 2 8 | 7 9 6 
7 3 9 | 1 6 4 | 2 5 8 
ー－－－－－－－－－－
4 7 8 | 6 3 1 | 5 2 9 
6 9 5 | 4 7 2 | 1 8 3 
2 1 3 | 9 8 5 | 6 7 4 
やり直し回数 258回

---

# おわりに
詳細な解説を書く気がなくなってしまったのでソースコード丸投げになってしまいました、ごめんなさい。
やり直し回数をカウントして出力できるようにしてあるので各自で実行してみるのもいいかもしれません。
**もっと効率のいいアルゴリズム**(ex:井桁理論とか)とかも時間があれば実装してみたいなと思います、ゆくゆくはC言語でかけたら……()

一通り書いた後に見返すとなんとまぁ見事な駄文に仕上がったなと(笑)
次書く機会があったとしたら自他ともに楽しめる文かけるようになりたいですねー、文才ある人はうらやましや。
あとファイブレイン個人的には好きなのでおすすめです。パズルも種類が豊富で楽しいし
~~同時期に放送してたエレメントハンターもぼかぁ大好きでしたよ~~
それではこの辺で終わりたいと思います。最後まで読んでくださった方（いるのかな？）ありがとうございました！それでは～ﾉｼﾉｼ