pythonで数独の問題を作る方法!
おはようございます、にわこまです。今回はpythonを使って数独（ナンプレ）を生成するプログラムを作ってみました。
pythonで何か作りたい人や数独（ナンプレ）に興味がある人におすすめです。
何か不明な点やご指摘があればご連絡ください！
スポンサードサーチ
数独（ナンプレ）を作る方法！
今回はpythonを使って数独（ナンプレ）を生成するプログラムを作ってみました。
しかし、プログラムが長すぎるのでプログラムは他のページに全て載せてあります。 ここから移動してください。
（注釈）このページでは、数独を作るアルゴリズムやプログラム内で定義した関数について説明していきたいと思います。
プログラムを作るにあたって、数独のアルゴリズムを考えるのが1番難しかったです。今回のプログラムも完璧ではありません。
1回の実行で数独の問題は出力されますが、プログラム内で完成するまで繰りかえしています。
正直、作るだけならランダムに数字を選んで代入していけばいつかは完成しますが、完成するまでにかなり時間がかかります。
私のプログラムでは、なるべく1回の実行で数独の問題を生成出来るように工夫しています。
（注釈）今回の説明にあたって3×3のマスをボックスと呼ぶことにします。
アルゴリズム
数独のルールは
・空いているマスに数字を代入する
・代入した数字が縦、横、ボックス内で重なってはいけない
というものです。
ゆえに、「縦、横、ボックス内で重ならない」というのは必須になります。 私が考えたアルゴリズムは以下のようになります。
・空欄があるか確認する
・空欄であるマスからランダムにマスを選ぶ
・選んだマスに代入可能な数字を選出する
・選出された数字からランダムに代入する
これを繰り返す。このように、アルゴリズムを言葉で表すと簡単のように見えます。しかし、コードを実際に書いて動かしてみると、うまくいかないことが多かったです。
細かいプログラムについてはコードのところで説明します。
スポンサードサーチ
コード
実際に書いたコードについて詳しく説明していきます。
(1)空欄のマスがあるか確認する関数
def zero_count(num_81):
for i in range(0, 9):
for j in range(0, 9):
n = num_81[(i, j)]
if(n == 0):
return True
else:
pass
# 0が「num_81」に１つも入ってないときはFalseを返す
return Falseこの関数では、引数に9×9の行列をもらいます。num_81という9×9の行列に0（空欄）があるかないか確かめる関数です。返却値はTrueまたはFalseです。 num_81を最初から最後まで1つずづ確認して、0が代入されていればFalseを返します。全てのマスに0以外の数字が代入されていればTrueを返します。
(2)縦、横、ボックスにおいて数字が重なっていないか確認する関数
# 横軸に同じ数字が入っていないか確認する関数
def row_check(number, x, y):
# 縦軸に同じ数字が入っていないか確認する関数
def col_check(number, x, y):
# 3×3のボックスの中に同じ数字が入っていないことを確認する
def box_check(number, x, y):この関数では、引数に座標とその座標に代入する数字をもらいます。縦においてはｙを固定して、横においてはｘを固定して確認します。ボックスにおいては、オフセットを利用して確認します。返却値はTrueまたはFalseです。
(3)縦、横、ボックスにおいて重なりがない数字のリストを返却する関数
# 指定された座標から横軸に格納可能な数字のリストを返す
def row_num_list(x, y):
# 指定された座標から縦軸に格納可能な数字のリストを返す
def col_num_list(x, y):
# 指定された座標に対応する3*3boxの中に格納可能な数字のリストを返す
def box_num_list(x, y):この関数では、引数に座標をもらいます。縦、横、ボックスにおいてそのマス以外で、0以外の数字を関数内で定義してあるリストから削除します。また、そのリストを返却します。返却値はリストです。
(4)あるマスに代入可能な数字が1つであるときその数字を返す関数
# 横軸において指定されたマスに代入可能な数字が1つのときその数字を返す関数
def ok_row_num(x, y):
# 縦軸において指定されたマスに代入可能な数字が1つのときその数字を返す関数
def ok_col_num(x, y):
# boxにおいて指定されたマスに代入可能な数字が1つのときその数字を返す関数
def ok_box_num(x, y):この関数では、引数に座標をもらいます。縦、横、ボックスにおいて指定されたマスに、唯一代入可能な数字を返却します。唯一代入可能な数字がないときは0を返却します。
下の図を用いて例を説明します。
上の図の緑色のマスには「4, 6, 7, 8」の数字が代入される可能性があります。しかし、横軸に置いて緑色のマス以外に「7」は代入することが出来ません。ゆえに、緑色のマスには「7」しか代入出来ないことになります。
このような場合に使われる関数です。
(5) (3)と(4)を使いあるマスにおいて代入可能な数字を1つ返却する関数
# (3)と(4)を呼び出し数字を1つ返却する関数
def ok_num(x, y):この関数では、引数に座標をもらいます。(3)から得られたリストの和集合を作ります。その和集合に、(4)で得られた数字が含まれているか確認します。含まれていればその数字を返却し、含まれていなければ和集合からランダムに返却します。
(6)あるマスにおいて指定された数字が他のマスで唯一の数字になっていないか確認する関数
# 横軸において,指定された数字が他のマスで唯一の数字になっていないか確認する
def row_only_check(number, x, y):
# 縦軸において,指定された数字が他のマスで唯一の数字になっていないか確認する
def col_only_check(number, x, y):
# 3*3のボックス内において,指定された数字が他のマスで唯一の数字になっていないか確認する
def box_only_check(number, x, y):この関数では、引数に座標とその座標に代入する数字をもらいます。引数の座標以外の縦、横、ボックスのマスで、引数の数字が唯一の数字になっていないか確認する関数です。返却値はTrueまたはFalseです。
下の図を用いて例を説明します。
上の図の緑色のマスには「5, 6, 7, 8, 9」の数字が代入される可能性があります。このときに「7」が選ばれた場合、3×3のボックスにおいて「2の上のマス」には「7」しか代入されないため、緑色のマスでは「7」を選ぶことが出来ません。これをTrueまたはFalseで返却します。
このような場合に使われる関数です。
(7)ボックスに数字が重ならないように代入する関数です。
# 左上の3*3マスと真ん中の3*3マスと右下の3*3マスに
# ランダムに数字を代入する
# place = 0 or 3 or 6
def rand_insert(place, emp, num_81_list):この関数では、引数に左上のボックス、真ん中のボックス、右下のボックスを指定する数字と空欄のマスの座標が入っているリストと9×9の行列をもらいます。
数独を作るにあたって1マス1マスランダムに数字を埋めていくと、かなり時間がかかります。ある程度、他のマスを気にせず数字を代入出来ないか考えました。その結果、左上、真ん中、右下は互いに影響を受けないので、そのボックス限定で数字を代入することが出来る関数を作りました。返却値は空欄可能なマスのリストです。
下の図のように、先に数字を代入してから、具体的に数字を代入するアルゴリズムを実行します。
(8) (2)と(6)をまとめた関数
# check_list True or False
def check_list(n, x, y):
rc_TF = row_check(n, x, y)
cc_TF = col_check(n, x, y)
bc_TF = box_check(n, x, y)
roc_TF = row_only_check(n, x, y);
coc_TF = col_only_check(n, x, y);
boc_TF = box_only_check(n, x, y);
if( (rc_TF == True) and (cc_TF == True) and (bc_TF == True) and (roc_TF == True) and (coc_TF == True) and (boc_TF == True)):
return True
return Falseこの関数では、引数に座標とその座標に代入する数字をもらいます。(2)と(6)のTrueまたはFalseをまとめています。1つでもFalseがあればFalseを返却します。全てTrueである場合のみTrueを返却します。
実行部分であるwhile文のなかで、6つも書くと汚く見えたのでまとめました。この関数はあまり重要ではありません。この関数で呼び出している(2)と(6)の関数を理解していれば問題ありません。
(9)あるマスに代入可能な数字が1つの場合その数字を代入する関数
# 横において各マスに格納可能な数字のリスト作成する
# 既に格納されている場合は空値を返す
# リストを足して数字が1回しか出てこなかったらその数字を代入する
def row_only_set(emp, num_81):
# 縦において各マスに格納可能な数字のリスト作成する
# 既に格納されている場合は空値を返す
# リストを足して数字が1回しか出てこなかったらその数字を代入する
def col_only_set(emp, num_81):
# 3*3boxにおいて各マスに格納可能な数字のリスト作成する
# 既に格納されている場合は空値を返す
# リストを足して数字が1回しか出てこなかったらその数字を代入する
def box_only_set(emp, num_81):この関数では、引数に空欄のマスの座標が入っているリストと9×9の行列をもらいます。縦、横、ボックスにおいて、空欄のマスに代入可能な数字が1つの場合はその数字を代入する関数です。返却値は空欄のマスの座標が入っているリストです。
下の図を使て例を説明します。
上の図の緑色のマスには、左から「5, 6, 7, 8」「5, 6, 8」「5, 6, 8」「5, 6, 8」の数字が代入できる可能性があります。このとき、「7」だけが唯一1回しか現れていません。ゆえに、「7」が1回だけ現れた1番左の緑色のマスに「7」を代入します。
このような場合に使われます。
(10) (9)をまとめた関数
def all_num_set(emp, num_81):
while(True):
row_emp = row_only_set(emp, num_81)
col_emp = col_only_set(emp, num_81)
box_emp = box_only_set(emp, num_81)
if( row_emp == col_emp == box_emp ):
break
return empこの関数では、引数に空欄のマスの座標が入っているリストと9×9の行列をもらいます。(9)の関数を繰り返し、(9)の3つ関数が全て同じ返却値であるとき繰り返しを終了し、空欄のマスの座標が入っているリストを返却します。
「(9)の3つ関数が全て同じ返却値であるとき」は、その3つの関数で代入可能な数字が1つであるマスがなかったことを意味します。
(11)9×9の行列をコマンドプロンプトに見やすくするための関数
def table_print(list):この関数では、引数に9×9の行列をもらいます。その行列をコマンドプロンプト上で見やすくするための関数です。9×9の行列にしか対応していません。
ただ単に、9×9の行列をコマンドプロンプトに表示すると上図のようになります。
table_print()関数を使えば先ほどよりは見やすく表示することが出来ます。
具体的な実行部分について説明します
while(len(emp) > 0):
c = 0
emp = rand_insert(0, emp, num_81)
emp = rand_insert(3, emp, num_81)
emp = rand_insert(6, emp, num_81)
while(c < 81):
c = c + 1
zc_TF = zero_count(num_81)
emp_l = len(emp)
if( (zc_TF == True) and (emp_l >= 0) ):
emp = all_num_set(emp, num_81)
emp_l = len(emp)
if(emp_l == 0):
break
r = random.randint(0, emp_l - 1)
x, y = emp[r]
n = ok_num(x, y)
if(n != 0):
num_81[emp[r]] = n
cl_TF = check_list(n, x, y)
if( (cl_TF == True) ):
emp.pop(r)
else:
num_81[emp[r]] = 0
pass
else:
break
else:
break
if(len(emp) == 0):
break
# 再定義
num_81 = np.zeros((9,9), dtype=int)
emp = []
for i in range(0, 9):
for j in range(0, 9):
emp.append((i, j))外側のwhile文は空欄のマスがなくなるまで繰り返すように設定してあります。内側のwhile文は数独を作るプログラムです。
まず、内側のwhile文に入る前に「rand_insert()」によって、左上、真ん中、右下のボックスに数字を代入します。その後、内側のwhile文の中で「all_num_set()」やランダムに数字を代入することを繰り返します。「空欄のマスがなくなる」または「矛盾が生じて数字を代入することが出来なくなる」まで繰り返します。
使い方
こちらのページにプログラムがあります。
pythonのプログラムを任意の名前で保存して下さい。名前は何でも問題ありません。
また、style.cssとprint.cssのファイルを同じフォルダに保存して下さい。このとき「.css」のファイルは名前を変えずに保存して下さい。
保存が終わったらコマンドプロンプトを起動してくださいwindowsでは左下の検索ボックスに「cmd」といれて、エンターを押していただければ起動します。
次に、保存したフォルダまで移動します。「cd 保存場所」で移動します。保存場所には絶対パスまたは、相対パスを入れて移動してください。
次に、「python ファイル名.py」または「python3 ファイル名.py」と打ち込み、エンターを押してください。以下のようなものが画面に出力されれば、正しく動作しています。
正しく動作がすると同じフォルダに「sudoku.html」というファイルが出来ます。これをダブルクリックするとブラウザに数独の問題が表示されます。これをプリントアウトしていただくことで実際に問題を解くことが出来ます。
何か不明な点があればtwitterやメールでご連絡ください。
スポンサードサーチ
まとめ
今回はpythonを使って数独（ナンプレ）を生成するプログラムを作ってみました。作るのに1か月くらいかかりました。
ゲームなどのルールがあるプログラムを作成することはかなり難しいと感じました。ゲームのルールだけではなく、例外が発生しないように制御したり、正しく選んだり、出力したり、実際に考えてコードを書いてみないと分からないことばかりでした。
ゲーム関係のプログラムを将来書いてみたいと考えている人は、こういうのを作ってみると良いかもしれません。
今回は「数独を生成するプログラム」でしたが、「数独を解くプログラム」や「数独の初期値の数はどこまで減らして良いのか」などを発信していきたいと思います。
スポンサードサーチ
