基礎編:再帰処理II

#自己紹介
初めまして。
本誌を訪問頂き有難うございます。
趣味で python を始めた中年おじさんです。
基礎から始めたくて記事を書き始めた今日この頃です。
本誌は基礎編 第五弾です。

[**第一弾 基礎編:木構造の全探索(DFS/BFS)**](https://qiita.com/AKpirion/items/9a223254d628a5afca70)
[**第二弾 基礎編:二分探索**](https://qiita.com/AKpirion/items/c70c55554ec187d2bf7e)
[**第三弾 基礎編:再帰処理**](https://qiita.com/AKpirion/items/6a390e86ff8bd22aa5e8)
[**第四弾 基礎編:キューとスタック**](https://qiita.com/AKpirion/items/a5e137ac861939cb94e8)

全部わからなくてもいい。
気が向いたときに改めて向き合えば良いと思っているので
ゆるーく、やっていきます。

#学習目標
今回は [**Leetcode:Recursion II**](https://leetcode.com/explore/learn/card/recursion-ii/) の理解を目標とします。
どのように理解するかは、以下のアプローチで進めます。

`テンプレートの暗記` =>
`記述の理解(イメージ作成)` => 
`自分なりのアプローチで再検証` => 
`理解の穴を埋める`

試行錯誤を繰り返すことで理解が深まり、思考力が養われると思います。

#例題 & 解説 [Marge Sort](https://leetcode.com/explore/learn/card/recursion-ii/470/divide-and-conquer/2868/)

leetcode 先生による講義を拝読しました。[**D & C introduction**](https://leetcode.com/explore/learn/card/recursion-ii/470/divide-and-conquer/2897/)から
divide & conguer(分割と攻略)という考え方を賜りました。

以下にあるように、入力したデータを再帰処理で分割していき、
分割後の要素数を n < 2 になるまで繰り返して Divid(分割)します。
分割したデータを使って conquer (攻略)していき、分割したデータを元の要素数に戻していきます。 
<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/737344/8645a86e-2474-2ed3-1f11-77b2f368e061.png"width=50%>
この考え方は marge sort に、そのまま適用することができます。
<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/737344/132f5c3b-df23-7b29-f4f7-52e9c719c5b1.png"width=50%>
>`step1:divide`
図にある 8 個の要素 n = 1 になるまで分割します、ちょうど青四角の部分です。

>`step2:conquer`
図には書いていませんが、青四角が 8 個あり、それぞれ 1 vs 5, 3 vs 2, 8 vs 7, 6 vs 4 の
どちらが大きいかを比較する作業を行っています。

>`step3:marge`
step2 で、それぞれ どちらが大きいか確認したら、昇順に marge していきます。
step3 の紫枠で囲まれている領域内の緑四角がそれに当たります。

step 3 には実はもう少し補足が必要な部分があります。
そう、緑の四角から、白の四角になる過程です。
要素数 2 の緑の四角を 2 つ使って、昇順に並べ替えて要素数 4 の塊に戻す作業を行います。 
この作業は、以下にあるように白四角(要素数 4) x2 を使って赤四角(要素数 8) に戻す作業と
同じ要領で行います。
<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/737344/4d7ab823-59e4-c9dc-2d8d-b2ce803b9f7f.gif"width=60%>
動作をイメージして書いてみると筆者の環境だと以下のコードでパスしました。

```margeSort.py
class Solution:
    def sortArray(self, nums: List[int]) -> List[int]:
        if len(nums) <= 1:
            return nums
        
        cptr = len(nums)//2
        left = self.sortArray(nums[:cptr])#再帰処理で要素数を 1 以下にする
        right= self.sortArray(nums[cptr:])#再帰処理で要素数を 1 以下にする
        
        def helper(left,right):
            #融合が進んだ後に以下の while 分で一つずつ
            #比較して融合させるので left ,right の要素をカウントする引数が必要
            lcnt = rcnt = 0 
            ans = []        
            while lcnt < len(left) and rcnt < len(right):
                if left[lcnt] < right[rcnt]:
                    ans.append(left[lcnt])
                    lcnt += 1
                else:
                    ans.append(right[rcnt])
                    rcnt += 1
            #余った要素を足し合わせる
            #=>以下いずれかが空になっているはずだが空を足しても出力としては変わらない
            ans += left[lcnt:]
            ans += right[rcnt:]
            return ans
        
        return helper(left,right)# 細切れの要素たちを融合させる
```

前述のコードは top down でアプローチしていることが分かります。
では bottom up もあるのではないでしょうか？はい、あります。
<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/737344/d8b35b6a-8159-9db6-15b5-81caa8279ee4.png"width=60%>

```margeSort.py
def margeSort(a):
    if len(a) <= 1:
        return a
    # margeSort で要素数 1 になるまで分割したら marge!
    return marge(margeSort(a[:len(a)//2]),margeSort(a[len(a)//2:]))

def marge(l,r):
    #後述している marge(l[1:],r[::]) or marge(l[::],r[1:])で l or r が len() = 0
    #の時に l + r で返せば切り抜けられる
    if len(l) == 0 or len(r)==0:
        return l+r
    elif l[0] < r[0]:# l[0] が先頭なら残りは l[1:] と r[::] の融合を再度図る
        return [l[0]] + marge(l[1:],r[::])
    else:            # r[0] が先頭なら残りは l[::] と r[1:] の融合を再度図る
        return [r[0]] + marge(l[::],r[1:])
    
#test input data
nums = [6,5,7,2,5,3,8,1]
print(margeSort(nums))
```

#演習 [Validate Binary Search Tree](https://leetcode.com/problems/validate-binary-search-tree/)
与えられた木が二分探索木かどうかを確認してください。
二分探索木の判断は以下の項目に着目して判断してください。
・ノードの値 > 左ノードの値
・ノードの値 < 右ノードの値
・左/右ノードの部分木も二分探索木であること

```answer_image.py
#Example 1:
Input: root = [2,1,3]
Output: true
#Example 2:
Input: root = [5,1,4,null,null,3,6]
Output: false
#Explanation: The root node's value is 5 but its right child's value is 4.
```
##解説
過去に以下の記事で演習7として本件を解いています。
[**基礎編:木構造の全探索(DFS/BFS)**](https://qiita.com/drafts/9a223254d628a5afca70/edit)
これは独断と偏見が大部分を占めた解説になっていますので、
今回は前述にある Divide & Conquer を意識して考察していきたいと思います。
まずはBST の復習です。

>与えられた二分木が二分探索木(BST)と判断するためには
以下の条件を満たす必要があります。
1.左側の部分木には、現在のノード値よりも全て小さい値を持つ
2.右側の部分木には、現在のノード値よりも全て大きい値を持つ
3.左右の部分木内も、前述の項目に該当している必要がある

留意すべきは、基本的には BST の問題は再帰処理で対応し、特に本件では
各ノードまで分割し、結合し、二分探索木であることを確認するので
自然と Divide & Conquer の手法を取り入れる必要があるということです。

以下に二分探索木の例を添付します。
<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/737344/c847a12a-6759-b9bf-0a45-5f2392a380f3.png"width=60%>
>**基本的なアプローチ**
>1.Divide
　ツリーを2つの部分木に分割 (**左**部分木 :青、**右**部分木 :緑)
>2.Conquer
　各サブツリーが実際に二分探索木であることを再帰的に検証
>3.Combine
　ステップ2の結果から、左右の部分木が両方とも有効なBSTである場合にのみ、true を return 

前述の 2 では再帰処理で leaf まで辿り着く、もしくは leaf まで進んだつもりが何もなかった場合を
判定し、Yes であれば True を返します。ただし、これだけでは不足していますので、
リマインドですが、以下についても検討する必要があります。
>1.左側の部分木には、現在のノード値よりも全て小さい値を持つ
2.右側の部分木には、現在のノード値よりも全て大きい値を持つ
3.左右の部分木内も、前述の項目に該当している必要がある

```isValidBST.py
class Solution:
    def isValidBST(self, root: TreeNode) -> bool:

        def helper(root):
            #leaf の left or right node に辿り着いた場合
            if not root:return True

            #以下の二分探索木の確認で No が出た場合,return False
            if not helper(root.left):
                return False

            #left.val から見た root.val =>二分探索木の確認
            #root.val から見た right.val=>二分探索木の確認
            if self.prev >= root.val:
                return False
            self.prev = root.val #prev の更新
            return helper(root.right)#left 確認後に right を確認
            
        self.prev = -float("inf")
        return helper(root)
```
![ValidateBST_case2.gif](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/737344/f4cdb581-ea65-c641-64b6-297965099492.gif)

#演習 [Search a 2D Matrix II](https://leetcode.com/explore/learn/card/recursion-ii/470/divide-and-conquer/2872/)
m x n 行列から target を効率的に探し出すアルゴを考えてみてください。
行列には以下の特徴があります。
1.各行は左から右に向かって昇順に整理されている
2.各列は上から下に向かって昇順に整理されている

**Example1**
<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/737344/9441905a-0635-016f-ce65-7c7304f03705.jpeg"width=30%>

```answer_image1.py
Input: matrix = [[1,4,7,11,15],[2,5,8,12,19],[3,6,9,16,22],[10,13,14,17,24],[18,21,23,26,30]], target = 5
Output: true
```

**Example2**
<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/737344/cb47091f-5787-6d1c-6fc5-90a862c5982e.jpeg"width=30%>

```answer_image1.py
Input: matrix = [[1,4,7,11,15],[2,5,8,12,19],[3,6,9,16,22],[10,13,14,17,24],[18,21,23,26,30]], target = 20
Output: false
```

##解説
[**D&C Template**](https://leetcode.com/explore/learn/card/recursion-ii/470/divide-and-conquer/2869/) に記載されている説明を理解しながら考察していきたいと思います。
色々な解放がありますが、今回の行列の仕様では Divide & Conquer する手法が適用できます。
具体的なアプローチは以下になります。

>1.Divide: 行列を 4 分割
2.Conquer: 再帰処理で分割した行列から要求値を探索
3.Combine:いずれかの分割した行列で要求値を見つけたら、探索をやめてスグに要求値を return

上記は大枠であり、実際は 2 の中で分割処理を再帰で進めていき、
base case として答えに辿り着くか、答えが無いかの何れかになります。
ただ、全ての行列を見る必要があるでしょうか。

`前述の 1 で分割した行列の左上にある最小値、
右下にある最大値が target のレンジでなければ探索する必要はないです。`

よって、2の工程で更に 4 分割した時には前述にあるように最小値/最大値を確認して
どの分割した行列を見ればよいのかを判断していけばよいのです。

```search2Dmatrix.py
class Solution:
    def searchMatrix(self,matrix,target):
        if not matrix:
            return False
        
        def search_rec(left,up,right,down):
            if left > right or up > down:
                return False
            elif target < matrix[up][left] or target > matrix[down][right]:
                return False
            mid = (left+right)//2
            row = up
            while row <= down and matrix[row][mid] <= target:
                if matrix[row][mid] == target:
                    return True
                row += 1
                #print(right)
            return search_rec(left,row,mid-1,down) or \
                   search_rec(mid+1,up,right,row-1)
        
        return search_rec(0,0,len(matrix[0])-1,len(matrix)-1)


#  ↓left       ↓right
#  [...........] ← up
#  [...........]
#  [...........]
#  [...........]
#  [...........] ← down

matrix = [[1,4,7,11,15],[2,5,8,12,19],[3,6,9,16,22],[10,13,14,17,24],[18,21,23,26,30]]
target = 24

S = Solution()
print(S.searchMatrix(matrix,target))
```

Example にあるように target = 5 を探してみましょう。
![Search2dMatrixII.gif](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/737344/d2d38db3-2700-9aeb-0675-9082992aca30.gif)
あれ？4 分割していない(笑)
別パターンも見てみましょう。
Example2 にあるように**20**を探してみます。
![Search2dMatrixII_case2.gif](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/737344/ed0b1ae4-0b28-fd58-7e49-c5490bebe8e8.gif)
あれ?左半分を確認した結果、最終的に return False or False となっています。
もう右半分は??
はい、大丈夫です。コードを追っかけるのに必死になって
忘れていますが、全体像を整理してみましょう。
![over_view.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/737344/2e42ad2d-44cf-7541-0aab-a0e8aa5931e0.png)
はい、ツリー構造のように探索しているのですが、
上図で追いかけていたのは以下、赤枠の部分のイメージです。
![over_view_c.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/737344/cc02f398-2363-a20b-6ab4-452409d84999.png)
はい、まだ確認していない個所が右側の探索になります。
冒頭にある 4 分割は、いったいどこに行ったのでしょう。。(笑)
また気が向いたときに再チャレンジしていきたいと思います。

#演習 [N-Queens](https://leetcode.com/explore/learn/card/recursion-ii/472/backtracking/2804/)
n-queens パズル問題は、女王様が互いにケンカしないように
n x n のチェスボードにどのように配置するかを検討する問題です。
整数 n を渡しますので、個別の解の数を返す必要してください。

**Example 1**:
<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/737344/85cf7a2a-768c-d53f-552f-046580365876.jpeg"width=30%>
>Input: n = 4
>Output: 2
>Explanation: There are two distinct solutions to the 4-queens puzzle as shown.

**Example 2**:
>Input: n = 1
>Output: 1

[補足]
Queen の動きが良く分からないため、確認しました。
以下にあるように結構万能に動けるので互いの移動範囲に
入らないような配置の組み合わせを求められているようです。
<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/737344/8e9f3a40-8d19-60ab-0594-8a4aafbc4972.jpeg"width=50%>


##解説
Queen は四方八方に配置ができます。上下、左右だけではなく、対角線上も移動が可能です。
それぞれが可動範囲に重ならないように配置するなんて、なんて無茶なんだ(心の声)
しかし、一旦、対角線の事は忘れます。

とりあえず上下左右だけで考えてみます。
今までの条件だけで考えると例えば 1行目に 1 つ配置したら、
1行目には、これ以上 Queen を配置することは出来ません。
っということは、`各行に配置できる Queen は MAX 1 個`ってことになります。

では対角線はどうしましょう。
例えば以下の行列で row, col を各要素で足したり引いたりします。
その値を行列にメモしていきます。

次に、その計算結果が共通となる要素を線でつなぐと、どうでしょう対角線になります。
各値を hill,dales と名付け、これらが深さを持つ配列となれば、対角線の使用、未使用を管理できます。
<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/737344/f3657e5c-24ec-2a68-03cd-aadb9c2be137.png"width=60%>
`どうやら対角線も管理できる`ようです。

ここまでをイメージして以下の回答が、どの部分に該当しているか
コメントを入れてみました。

```nQueensII.py
class solution:
    def toalQueens(n):
        #行、対角線上に Queen が無ければ return Ture
        def is_not_under_attack(row,col):
            return not (rows[col] or hills[row-col] or bales[row+col])   
        #Queen を配置した場合、各配列に 1 を格納
        def add_queen(row,col):
            rows[col] = 1
            hills[row-col] = 1
            bales[row+col] = 1
        #Queen を外す場合、各配列に 0 を格納            
        def remove_queen(row,col):
            rows[col] = 0
            hills[row-col] = 0
            bales[row+col] = 0
            
        def backtrack(row=0,count=0):
            for col in range(n):
                if is_not_under_attack(row,col):
                    add_queen(row,col)
                    if row+1 == n:
                        print("in")
                        count += 1
                    else:
                        count = backtrack(row+1,count)
                    remove_queen(row,col)
            return count
            
            
        rows = [0]*n      #point1:1行における Queen は 1 つだけ。列まで管理不要
        hills = [0]*(2*n-1)#point2:対角線を定義
        bales = [0]*(2*n-1)#point2:対角線を定義
        
        return backtrack()
```

素朴な疑問が出てきますが列(col)はどうするのでしょうか？

実は、その疑問こそが次の backtrack へと続いていきます。
例えば row=0 の時、col は 0,1,2,3 と 4 つ選択肢があります。
backtrack では、上下左右、対角線をチェックして、問題ない場合は
col = 0 の場合、col = 1 の場合、、、っというように Queen を配置して
都度、行動範囲が Queen 間で重ならないかチェックします。
試してダメであれば、戻って、次を試す。。まさしく backtrackですね。

また`大事なポイントですが、全行に 1 つずつ置けた場合のみ
Queen の配置の組み合わせとして 1 つカウントすることが出来ます。`
では、row,col = 0,0 に Queen を配置した場合、
どのような動きをするのか GIF で追いかけてみましょう。
![nQueens.gif](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/737344/e9d297ad-e191-cd0d-ca51-bfd136f008b6.gif)
ここまでが Queen の初期配置を row,col = 0,0 とした場合の動きです。
次は row,col = 0,1 です。どこまで丁寧にまとめるかは検討中ですが、
なんとか答えを出すまでを GIF に出来ればいいかな～(たぶんやらない。。)。

因みに上下左右に Queen が重なるかをチェックする記述は
`def is_not_under_attack(row,col):` にある `rows[col]` で判断しています。
素朴になんでコレだけで？！と思われる方も居るかもしれません。
そもそも、今回のコードは row を 1 ずつインクリメントして進んでいきます。
また Queen は 1行に 1つしか置けません。よって、行は管理しなくて良いです。
![image1.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/737344/61449fea-be81-8e9f-96ba-c0e80c942938.png)
つまり、過去どの列に Queen を配置していたかだけを管理すれば上下左右をチェックしていることになります。
っということで以下のように列を管理する印があるとどうでしょうか。
![image2.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/737344/224bfb12-70d2-ebec-ff6e-e21dbce5c4fa.png)
row = 0 の時、列を管理している配列が[0,0,0,0]である場合、[0,0] に Queen を配置したとします。
配置出来たら、[0,0,0,0] を [1,0,0,0] にアップデートします。
row = 1 の時、[1,0,0,0]を見ると1列目には Queen が居るので、[1,0] に Queen は配置できません。
[1,1],[1,2],[1,3]にある空欄のいずれかに配置することができます。
よって、`row[col]` っというシンプルな記述で列を管理するだけで上下左右を管理したことになるのです。

#演習 [Robot Room Cleaner](https://leetcode.com/explore/learn/card/recursion-ii/472/backtracking/2794/)
格子状にデザインされた部屋にお掃除ロボットを置いてみました。各セルは通路として通れたり、
障害物があって通れなかったりします。お掃除ロボットは全身、左折、右折など 4 つの API を与えます。
右折 or 左折は 90度の旋回になります。
もし、ブロックされたセルに動こうとすると、
バンパーのセンサーが障害物を検知し、現状のセルに留まろうとします。
以下の 4つの API を使って、部屋全体を掃除するアルゴリズムをデザインしてください。

```API.py
interface Robot {
  # returns true if next cell is open and robot moves into the cell.
  # returns false if next cell is obstacle and robot stays on the current cell.
  boolean move();

  # Robot will stay on the same cell after calling turnLeft/turnRight.
  # Each turn will be 90 degrees.
  void turnLeft();
  void turnRight();

  # Clean the current cell.
  void clean();
}
```

```answer_image.py
#Example:
Input:
room = [
  [1,1,1,1,1,0,1,1],
  [1,1,1,1,1,0,1,1],
  [1,0,1,1,1,1,1,1],
  [0,0,0,1,0,0,0,0],
  [1,1,1,1,1,1,1,1]
],
row = 1,
col = 3

#Explanation:
#All grids in the room are marked by either 0 or 1.
#0 means the cell is blocked, while 1 means the cell is accessible.
#The robot initially starts at the position of row=1, col=3.
#From the top left corner, its position is one row below and three columns right.
```

メモ:
1.入力には初期化された部屋とロボットの初期位置が与えられます。"blindgolded"で問題を解いてください。
つまり、ロボットの初期位置、部屋の構成を知らない状態で 4つの API を使ってロボットを制御してください。
2.ロボットの初期位置はブロックされたセルではなく、必ず何処かの通路に配置されます。
3.ロボットの向いている初期の方向は上向きです。
4.すべての通り道は一本に繋がっています。1と記載された全てのセルにアクセスすることが出来ます。
5.部屋は四方を壁で囲まれています。

##解説
まずはイメージを作っていきたいと思います。
以下にあるように格子状の空間をロボットが進んでいきます。
赤ドットがロボットを指しており、通過した場所は足跡マークで印をつけて進みます。
<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/737344/633c6498-10e9-a7ca-4a7d-a97626979cfa.png"width=60%>
ポイントを箇条書きにしていきます。
・ロボットの各工程は再帰処理で対応する
・進行方向のセルが既に掃除されているか、障害物であるかを逐次確認する
・進行方向が決まったら、そのセルに印を付ける
・立ち戻れるようにマークは消していく
・backtrack の再帰処理により一つずつ掃除していきます。
また四方が障害物、掃除済みの印で囲まれることでトリガーが掛かります。
backtrack が終了したら開始地点に戻ることで全てのセルを最低 1 回通過したことになります。

```cleenRoom.py
class Solution():       
    def cleanRoom(self, robot):
        def go_back():
            robot.turnRight()
            robot.turnRight()
            robot.move()
            robot.turnRight()
            robot.turnRight()
            
        def backtrack(cell = (0, 0), d = 0):
            visited.add(cell)
            robot.clean()
            # going clockwise : 0: 'up', 1: 'right', 2: 'down', 3: 'left'
            for i in range(4):
                new_d = (d + i) % 4
                new_cell = (cell[0] + directions[new_d][0], \
                            cell[1] + directions[new_d][1])
                print(new_cell)
                
                if not new_cell in visited and robot.move():
                    backtrack(new_cell, new_d)
                    go_back()
                # turn the robot following chosen direction : clockwise
                robot.turnRight()
    
        # going clockwise : 0: 'up', 1: 'right', 2: 'down', 3: 'left'
        directions = [(-1, 0), (0, 1), (1, 0), (0, -1)]
        visited = set()
        backtrack()
```

まずは例題にあるようにスタートして動かした場合、
一回目の障害物検知と、右旋回までを見ていこうと思います。
![cleanRoom_Case1.gif](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/737344/da8afb22-0c1b-a521-4475-981f6e94894a.gif)
GIF の最後のページで記載したコメントをリマインドします。
for 文は進行方向を表していますので、
もし障害物を検知したり、一度通った道は、無理に進まず、右旋回します。
i = 0 で行うのはココまでです。i = 1 になれば、進行方向 right において
進むかどうかを判断します。
この調子でいくと左端の隅でハマります。イメージは以下です。
<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/737344/633c6498-10e9-a7ca-4a7d-a97626979cfa.png"width=60%>
どのような挙動になるかを GIF で追いかけてみます。
![cleanRoom_Case2.gif](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/737344/1798c1dd-46cc-f047-0735-2dcef2ec129d.gif)
一個戻ることが出来ました。あとは for 分で方向を回して (-2,0)に向かおうと思います。
それが以下になります。
![cleanRoom_Case3.gif](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/737344/f80a8335-94c6-87b5-7346-e3faf0bcc5bc.gif)
どんどん戻っていきましょう。
![cleanRoom_Case4.gif](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/737344/02dcb127-364b-9d43-c982-7826cf80df45.gif)

#演習 [Sudoku Solver](https://leetcode.com/explore/learn/card/recursion-ii/472/backtracking/2796/)
空のセルを埋めるて Sudoku パズルで解くプログラムを書いてください。 
sudoku の解放は以下の点を全て満たす必要があります。

・1〜9の数字は、各行に1回だけ出現する必要があります。
・1〜9の数字は、各列に1回だけ出現する必要があります。
・1〜9の数字は、グリッドの9つの3x3サブボックスのそれぞれで1回だけ出現する必要があります。 
・'.' は空のセルを意味します。
**Example**
![250px-Sudoku-by-L2G-20050714.svg.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/737344/64391b61-a232-9862-b8f5-1dce79d18d06.png)

```answer_image.py
Input: board = [
["5","3",".",".","7",".",".",".","."],
["6",".",".","1","9","5",".",".","."],
[".","9","8",".",".",".",".","6","."],
["8",".",".",".","6",".",".",".","3"],
["4",".",".","8",".","3",".",".","1"],
["7",".",".",".","2",".",".",".","6"],
[".","6",".",".",".",".","2","8","."],
[".",".",".","4","1","9",".",".","5"],
[".",".",".",".","8",".",".","7","9"]
]

Output: [
["5","3","4","6","7","8","9","1","2"],
["6","7","2","1","9","5","3","4","8"],
["1","9","8","3","4","2","5","6","7"],
["8","5","9","7","6","1","4","2","3"],
["4","2","6","8","5","3","7","9","1"],
["7","1","3","9","2","4","8","5","6"],
["9","6","1","5","3","7","2","8","4"],
["2","8","7","4","1","9","6","3","5"],
["3","4","5","2","8","6","1","7","9"]
]
#Explanation: 
#The input board is shown above and the only valid solution is shown below:
```
**answer_image**
![250px-Sudoku-by-L2G-20050714_solution.svg.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/737344/4cfe29a5-6f47-789d-7b7b-e104951a07f4.png)

制約:
・board.length == 9
・board[i].length == 9
・board[i][j] は数字 or '.'(空欄).
・答えが必ずあることが保障されています。

##解説



---

すいません。
時間をかけて増やしていきます(^0^)/

分かったつもりでも、自分で組み直すと
足りないところが見えたりして、楽しいですね(^ - ^)9。