生成AIも進展してプログラミングもできるようになったので、今までのように補助的な使用をしないで Python3 プログラムそのものを作成してもらいました。
今回は Google Gemini を利用して、数独のプログラム作成依頼でプロンプトはこのようになりました。
「python3で数独を解くプログラムを作成したい。動作するコンピュータが遅いのでなるべく高速になるように作成したい。問題はプログラムの入力ではなく、問題の１行を表す要素数９個のリストを９個使用する。以下に、問題の例を示す。
# Set Puzzle
R1 = [3, 0, 0, 7, 4, 0, 5, 2, 0]
R2 = [0, 2, 8, 9, 0, 0, 0, 0, 0]
R3 = [0, 4, 5, 0, 0, 0, 9, 0, 3]
R4 = [4, 5, 0, 6, 0, 7, 0, 0, 9]
R5 = [9, 0, 0, 0, 2, 3, 0, 0, 1]
R6 = [0, 0, 0, 8, 5, 9, 3, 4, 7]
R7 = [5, 0, 9, 0, 0, 2, 8, 0, 4]
R8 = [1, 0, 0, 0, 0, 8, 0, 0, 0]
R9 = [0, 0, 2, 3, 9, 4, 1, 0, 5]
」
Gemini の回答は以下の通りです。
ここから＝＝＝＝＝＝
数独ソルバーを高速化するために、いくつかの最適化手法を取り入れたPython3プログラムを提案します。
**1. 問題の表現**
与えられた問題を効率的に処理するために、NumPy配列を使用します。NumPyは、数値計算に特化したライブラリであり、高速な配列操作を提供します。
```python
import numpy as np
puzzle = np.array([
[3, 0, 0, 7, 4, 0, 5, 2, 0],
[0, 2, 8, 9, 0, 0, 0, 0, 0],
[0, 4, 5, 0, 0, 0, 9, 0, 3],
[4, 5, 0, 6, 0, 7, 0, 0, 9],
[9, 0, 0, 0, 2, 3, 0, 0, 1],
[0, 0, 0, 8, 5, 9, 3, 4, 7],
[5, 0, 9, 0, 0, 2, 8, 0, 4],
[1, 0, 0, 0, 0, 8, 0, 0, 0],
[0, 0, 2, 3, 9, 4, 1, 0, 5]
])
```
**2. 制約条件のチェック**
各セルに数字を配置する際に、行、列、3x3ブロックの制約条件を満たしているかを効率的にチェックする関数を実装します。
```python
def is_valid(puzzle, row, col, num):
# 行のチェック
if num in puzzle[row]:
return False
# 列のチェック
if num in puzzle[:, col]:
return False
# 3x3ブロックのチェック
start_row, start_col = 3 * (row // 3), 3 * (col // 3)
if num in puzzle[start_row:start_row + 3, start_col:start_col + 3]:
return False
return True
```
**3. 再帰的なバックトラッキング**
数独を解くために、再帰的なバックトラッキングアルゴリズムを使用します。
```python
def solve_sudoku(puzzle):
for row in range(9):
for col in range(9):
if puzzle[row, col] == 0:
for num in range(1, 10):
if is_valid(puzzle, row, col, num):
puzzle[row, col] = num
if solve_sudoku(puzzle):
return True
else:
puzzle[row, col] = 0
return False
return True
```
**4. 実行と結果の表示**
数独ソルバーを実行し、結果を表示します。
```python
if solve_sudoku(puzzle):
print(puzzle)
else:
print("解が見つかりませんでした。")
**高速化のポイント**
* **NumPyの活用:** NumPy配列を使用することで、高速な配列操作が可能になります。
* **制約条件の効率的なチェック:** 制約条件を効率的にチェックすることで、無駄な探索を減らします。
* **バックトラッキングの最適化:** バックトラッキングアルゴリズムを最適化することで、探索時間を短縮します。
（以下省略）
＝＝＝＝＝＝ここまで
入門者にとって、かなり洗練されたプログラムが提示されました。
・ 配列を扱うために NumPy を使い、 array() で ndarray オブジェクトを生成する。
・ 条件判定に、 if num in ndarryaオブジェクトから抽出したもの を使う。
・ 再帰的呼び出し（バックトラッキングアルゴリズムと説明されている）で数値を埋めていく。
このプログラムは１つ解が見つかったら終了するので、以前作成したプログラムを解が見つかったら exit()で終了するようにして実際に実行してみました。
前のプログラム：
real 0m40.165s
user 0m40.147s
sys 0m0.017s
Geminiが提示したプログラム：
real 0m0.446s
user 0m0.637s
sys 0m0.042s
数独プログラムなので至るところで作成されて公開されているので生成AIが高速化されたプログラムを教えてくれると思いましたが、ここまで高速だったとは「衝撃的」です。
入門者は、すでに行ったように作成を少し助けてもらう事やdocstring などを生成してもらう場合に限定して生成AIを使ったほうが良さそうですね。
今回の場合のように全面的にプログラム作成に使ってしまった場合は、その動きを正しく理解する必要があると思いました。
というわけで、入門者として生成されたプログラムの説明を試みました。
まず、問題を２次元配列として考えるために NumPy を利用していますね。その、array()で生成されるndarrayオブジェクトにより、
・ 配列の行は、puzzle[row] 。
・ 配列の列は、puzzle[ : ,col] 。
・ ３行３列の部分配列の取り出しは、puzzle[row:row+3 , ocl:col+3 ] 。
で得られます。
これによって、is_valid()関数の判定で、
if num in puzzle[....]: が使えるようになり、行、列、3x3ブロックのなかに数値 num があるかどうかの判定ができるので分かりやすくなりますね。
ちなみに、3*(row//3) は切り捨て割り算なので、rowが 0~2 なら 0, 3~5 なら 3, 6-8 なら 6 となり数独のブロックに使えます。
入門者にとって難しいのは、「バックトラッキング」 solve_sudoku(puzzle) です。
まず、大切なのは Pytnon の関数の引数は「参照渡し」であることです。
そのため、puzzle のある要素 puzzle[row,col] の値が 0 の時、
puzzle[row,col] = num のように値を代入したり、
その値代入が条件を満たさなかった場合に、
puzzle[row,col] = 0 のように値の代入をキャンセルしてもとの値 0 に戻すことができるわけですね。
外側のfor ループでrow（行） が 0から8まで、2番目のfor ループでcol（列） が 0から8まで繰り返して、
puzzle[row,col]の値が 0 でなければなにもしないで次に行き、
0 の場合は、
３番目のfor ループで num に 1から9まで値をpuzzle[row,col]に入れて、その時点で条件がクリア (is_valid()がTrue) できているときに、
puzzle[row,col]にnumを代入して、再帰的に solve_sudoku(puzzle) を呼び出すと、
今度は前に見つかった値が0の場所に仮の値が入っているので、次に値が0になるところまでrow、col を進めて、
同じ事を繰り返すわけです。
最後まで仮の値に矛盾がなければ True で帰って、穴埋め完了になり、矛盾が生まれたら値を 0 に戻して、次の num を試すのですね。
一見、外側の row ループや、2番目の col ループで繰り返すみたいに見えますが、
値をどんどん入れて行ったときに再帰的に呼び出した solve_sudoku() の中で、
すでに値が設定された要素をスキップして、次の値が0の要素を探すためのループと解釈できそうです。
0の所に値をどんどん入れて行って最後のsolve_sudoku() 呼び出しのとき値がすべて 0 でないので最後の行で True で帰るので、
次々に solve_sudoku()が True で帰って 9 行目の return Trueで終了するようです。
最後から２行目の return False は、解が無い場合の保険ですね。
設定する値は必ず 1~9 の中にある（Trueで帰る）前提でプログラムが作られているようです。
初心者なので、再帰的呼び出しが多くなりすぎるので動かないのではと思ってしまいそうなのと、このようなプログラムを作るとかなりの頻度でバグが発生しそうで、しかもバグが発生した場合に修正に困難が予想されるのでこのようなプログラムに辿り着ける可能性はほぼないような気がしました。
気になるのは、どうしてこのように高速になったのかです。
・ solve_sudoku() のアルゴリズム
・ NumPy の ndarray オブジェクトの使用
が考えられます。
そこで、次回 NumPy を使わない場合を試してみることにします。
今回は Google Gemini を利用して、数独のプログラム作成依頼でプロンプトはこのようになりました。
「python3で数独を解くプログラムを作成したい。動作するコンピュータが遅いのでなるべく高速になるように作成したい。問題はプログラムの入力ではなく、問題の１行を表す要素数９個のリストを９個使用する。以下に、問題の例を示す。
# Set Puzzle
R1 = [3, 0, 0, 7, 4, 0, 5, 2, 0]
R2 = [0, 2, 8, 9, 0, 0, 0, 0, 0]
R3 = [0, 4, 5, 0, 0, 0, 9, 0, 3]
R4 = [4, 5, 0, 6, 0, 7, 0, 0, 9]
R5 = [9, 0, 0, 0, 2, 3, 0, 0, 1]
R6 = [0, 0, 0, 8, 5, 9, 3, 4, 7]
R7 = [5, 0, 9, 0, 0, 2, 8, 0, 4]
R8 = [1, 0, 0, 0, 0, 8, 0, 0, 0]
R9 = [0, 0, 2, 3, 9, 4, 1, 0, 5]
」
Gemini の回答は以下の通りです。
ここから＝＝＝＝＝＝
数独ソルバーを高速化するために、いくつかの最適化手法を取り入れたPython3プログラムを提案します。
**1. 問題の表現**
与えられた問題を効率的に処理するために、NumPy配列を使用します。NumPyは、数値計算に特化したライブラリであり、高速な配列操作を提供します。
```python
import numpy as np
puzzle = np.array([
[3, 0, 0, 7, 4, 0, 5, 2, 0],
[0, 2, 8, 9, 0, 0, 0, 0, 0],
[0, 4, 5, 0, 0, 0, 9, 0, 3],
[4, 5, 0, 6, 0, 7, 0, 0, 9],
[9, 0, 0, 0, 2, 3, 0, 0, 1],
[0, 0, 0, 8, 5, 9, 3, 4, 7],
[5, 0, 9, 0, 0, 2, 8, 0, 4],
[1, 0, 0, 0, 0, 8, 0, 0, 0],
[0, 0, 2, 3, 9, 4, 1, 0, 5]
])
```
**2. 制約条件のチェック**
各セルに数字を配置する際に、行、列、3x3ブロックの制約条件を満たしているかを効率的にチェックする関数を実装します。
```python
def is_valid(puzzle, row, col, num):
# 行のチェック
if num in puzzle[row]:
return False
# 列のチェック
if num in puzzle[:, col]:
return False
# 3x3ブロックのチェック
start_row, start_col = 3 * (row // 3), 3 * (col // 3)
if num in puzzle[start_row:start_row + 3, start_col:start_col + 3]:
return False
return True
```
**3. 再帰的なバックトラッキング**
数独を解くために、再帰的なバックトラッキングアルゴリズムを使用します。
```python
def solve_sudoku(puzzle):
for row in range(9):
for col in range(9):
if puzzle[row, col] == 0:
for num in range(1, 10):
if is_valid(puzzle, row, col, num):
puzzle[row, col] = num
if solve_sudoku(puzzle):
return True
else:
puzzle[row, col] = 0
return False
return True
```
**4. 実行と結果の表示**
数独ソルバーを実行し、結果を表示します。
```python
if solve_sudoku(puzzle):
print(puzzle)
else:
print("解が見つかりませんでした。")
**高速化のポイント**
* **NumPyの活用:** NumPy配列を使用することで、高速な配列操作が可能になります。
* **制約条件の効率的なチェック:** 制約条件を効率的にチェックすることで、無駄な探索を減らします。
* **バックトラッキングの最適化:** バックトラッキングアルゴリズムを最適化することで、探索時間を短縮します。
（以下省略）
＝＝＝＝＝＝ここまで
入門者にとって、かなり洗練されたプログラムが提示されました。
・ 配列を扱うために NumPy を使い、 array() で ndarray オブジェクトを生成する。
・ 条件判定に、 if num in ndarryaオブジェクトから抽出したもの を使う。
・ 再帰的呼び出し（バックトラッキングアルゴリズムと説明されている）で数値を埋めていく。
このプログラムは１つ解が見つかったら終了するので、以前作成したプログラムを解が見つかったら exit()で終了するようにして実際に実行してみました。
前のプログラム：
real 0m40.165s
user 0m40.147s
sys 0m0.017s
Geminiが提示したプログラム：
real 0m0.446s
user 0m0.637s
sys 0m0.042s
数独プログラムなので至るところで作成されて公開されているので生成AIが高速化されたプログラムを教えてくれると思いましたが、ここまで高速だったとは「衝撃的」です。
入門者は、すでに行ったように作成を少し助けてもらう事やdocstring などを生成してもらう場合に限定して生成AIを使ったほうが良さそうですね。
今回の場合のように全面的にプログラム作成に使ってしまった場合は、その動きを正しく理解する必要があると思いました。
というわけで、入門者として生成されたプログラムの説明を試みました。
まず、問題を２次元配列として考えるために NumPy を利用していますね。その、array()で生成されるndarrayオブジェクトにより、
・ 配列の行は、puzzle[row] 。
・ 配列の列は、puzzle[ : ,col] 。
・ ３行３列の部分配列の取り出しは、puzzle[row:row+3 , ocl:col+3 ] 。
で得られます。
これによって、is_valid()関数の判定で、
if num in puzzle[....]: が使えるようになり、行、列、3x3ブロックのなかに数値 num があるかどうかの判定ができるので分かりやすくなりますね。
ちなみに、3*(row//3) は切り捨て割り算なので、rowが 0~2 なら 0, 3~5 なら 3, 6-8 なら 6 となり数独のブロックに使えます。
入門者にとって難しいのは、「バックトラッキング」 solve_sudoku(puzzle) です。
まず、大切なのは Pytnon の関数の引数は「参照渡し」であることです。
そのため、puzzle のある要素 puzzle[row,col] の値が 0 の時、
puzzle[row,col] = num のように値を代入したり、
その値代入が条件を満たさなかった場合に、
puzzle[row,col] = 0 のように値の代入をキャンセルしてもとの値 0 に戻すことができるわけですね。
外側のfor ループでrow（行） が 0から8まで、2番目のfor ループでcol（列） が 0から8まで繰り返して、
puzzle[row,col]の値が 0 でなければなにもしないで次に行き、
0 の場合は、
３番目のfor ループで num に 1から9まで値をpuzzle[row,col]に入れて、その時点で条件がクリア (is_valid()がTrue) できているときに、
puzzle[row,col]にnumを代入して、再帰的に solve_sudoku(puzzle) を呼び出すと、
今度は前に見つかった値が0の場所に仮の値が入っているので、次に値が0になるところまでrow、col を進めて、
同じ事を繰り返すわけです。
最後まで仮の値に矛盾がなければ True で帰って、穴埋め完了になり、矛盾が生まれたら値を 0 に戻して、次の num を試すのですね。
一見、外側の row ループや、2番目の col ループで繰り返すみたいに見えますが、
値をどんどん入れて行ったときに再帰的に呼び出した solve_sudoku() の中で、
すでに値が設定された要素をスキップして、次の値が0の要素を探すためのループと解釈できそうです。
0の所に値をどんどん入れて行って最後のsolve_sudoku() 呼び出しのとき値がすべて 0 でないので最後の行で True で帰るので、
次々に solve_sudoku()が True で帰って 9 行目の return Trueで終了するようです。
最後から２行目の return False は、解が無い場合の保険ですね。
設定する値は必ず 1~9 の中にある（Trueで帰る）前提でプログラムが作られているようです。
初心者なので、再帰的呼び出しが多くなりすぎるので動かないのではと思ってしまいそうなのと、このようなプログラムを作るとかなりの頻度でバグが発生しそうで、しかもバグが発生した場合に修正に困難が予想されるのでこのようなプログラムに辿り着ける可能性はほぼないような気がしました。
気になるのは、どうしてこのように高速になったのかです。
・ solve_sudoku() のアルゴリズム
・ NumPy の ndarray オブジェクトの使用
が考えられます。
そこで、次回 NumPy を使わない場合を試してみることにします。
トータル
