どうもこんにちはRyujiです。
この記事は前回記事の続きです。数独の問題作成部分をpythonで作成します。
Contents
今日実装したところ
前回までで、非同期通信とクライアント間の自動更新が終わりました。
次は問題がないと進まないので、問題を生成するプログラムを作ろうと考えました。
数値や配列の計算が得意と言われているpythonを使用していくことにしました。
pythonは先週DeepLearningの学習で使用しましたが、まだ未経験に毛が生えた程度の知識しかありません。
実装の方針
問題を作るにあたって、以下の順序で進めてまいります。
- 数独のルールに沿った配列を用意する。それを表示できるようにする。
- 各行、各列の和45が崩れない範囲でシャッフルする。
- 数独の問題を解くプログラムを作成する
- 穴を開けていく
- 3のプログラムで解くことができるか確認する。
- 4と5を繰り返し解くことができるならばデータベースに登録する。
今日は1と2の実装を目標にしました。
1.は簡単に、以下にしました。ここからシャッフルしていきます。
[
# 列名 # 行名
# A B C D E F G H I
[1,4,7,2,5,8,3,6,9], # 1
[2,5,8,3,6,9,4,7,1], # 2
[3,6,9,4,7,1,5,8,2], # 3
[4,7,1,5,8,2,6,9,3], # 4
[5,8,2,6,9,3,7,1,4], # 5
[6,9,3,7,1,4,8,2,5], # 6
[7,1,4,8,2,5,9,3,6], # 7
[8,2,5,9,3,6,1,4,7], # 8
[9,3,6,1,4,7,2,5,8] # 9
]
2.についてはシャッフルができるルールが3つあります。
- ABC列ではACBやBCAやBACのように自由に列ごと置き換えることができる。(DEF、GHI、123、456、789も同じ)但し、A列とD列など3ブロックをまたがってシャッフルすることはできない。
- ABC列とDEF列など3行1組ごとシャッフルできる。(123と456等)
- 1〜9の配列の中身の数字はそれぞれ別の数字に置き換えることができる。
このルールに従えば未知の問題の答えが無限に作成できます。
ソースコード
今日頑張って考えながら作ったpythonのソースコードを載せます!デデドン!
※よくわからないと思うし、下でブロックごとに説明を書いたので読み飛ばしてください。
import numpy as np
from enum import Enum
import random
class Sudoku():
SHUFFLE_ABC = 1
SHUFFLE_DEF = 2
SHUFFLE_GHI = 3
SHUFFLE_123 = 4
SHUFFLE_456 = 5
SHUFFLE_789 = 6
SHUFFLE_LINES = 7
SHUFFLE_COLS = 8
SHUFFLE_NUM = 9
def __init__(self, table):
self.table = np.array(table)
def display(self):
print(self.table.shape)
print(self.table)
def check(self):
column_sum = np.array([0] * 9)
for i in range(9):
line_sum = np.array(self.table[i]).sum()
assert line_sum == 45, "not sudoku"
column_sum += np.array(self.table[i])
assert column_sum.all() == np.array([45] * 9).all(), "not sudoku"
def shuffle(self,type):
if type == self.SHUFFLE_ABC:
x = self.table.T
y = x[0:3]
np.random.shuffle(y)
x[0:3] = y
self.table = x.T
elif type == self.SHUFFLE_DEF:
x = self.table.T
y = x[3:6]
np.random.shuffle(y)
x[3:6] = y
self.table = x.T
elif type == self.SHUFFLE_GHI:
x = self.table.T
y = x[6:9]
np.random.shuffle(y)
x[6:9] = y
self.table = x.T
elif type == self.SHUFFLE_123:
x = self.table
y = x[0:3]
np.random.shuffle(y)
x[0:3] = y
self.table = x
elif type == self.SHUFFLE_456:
x = self.table
y = x[3:6]
np.random.shuffle(y)
x[3:6] = y
self.table = x
elif type == self.SHUFFLE_789:
x = self.table
y = x[6:9]
np.random.shuffle(y)
x[6:9] = y
self.table = x
elif type == self.SHUFFLE_LINES:
array = [np.copy(self.table[0:3]),np.copy(self.table[3:6]),np.copy(self.table[6:9])]
random.shuffle(array)
for i in range(3):
self.table[(0+3*i):(3+3*i)] = array[i]
elif type == self.SHUFFLE_COLS:
x = self.table.T
temp = [np.copy(x[0:3]),np.copy(x[3:6]),np.copy(x[6:9])]
random.shuffle(temp)
for i in range(3):
x[(0+3*i):(3+3*i)] = temp[i]
self.table = x.T
elif type == self.SHUFFLE_NUM:
temp = [1,2,3,4,5,6,7,8,9]
random.shuffle(temp)
for i in range(9):
for j in range(9):
data = self.table[i][j]
self.table[i][j] = temp[data - 1]
else:
print("fail")
sudoku = Sudoku([
[1,4,7,2,5,8,3,6,9],
[2,5,8,3,6,9,4,7,1],
[3,6,9,4,7,1,5,8,2],
[4,7,1,5,8,2,6,9,3],
[5,8,2,6,9,3,7,1,4],
[6,9,3,7,1,4,8,2,5],
[7,1,4,8,2,5,9,3,6],
[8,2,5,9,3,6,1,4,7],
[9,3,6,1,4,7,2,5,8]
])
sudoku.display()
sudoku.check()
for i in range(1000):
sudoku.shuffle(random.randint(1,9))
sudoku.display()
ソースコードの説明
import numpy as np
from enum import Enum
import random
ライブラリを読み込んでます。
class Sudoku():
SHUFFLE_ABC = 1
SHUFFLE_DEF = 2
SHUFFLE_GHI = 3
SHUFFLE_123 = 4
SHUFFLE_456 = 5
SHUFFLE_789 = 6
SHUFFLE_LINES = 7
SHUFFLE_COLS = 8
SHUFFLE_NUM = 9
def __init__(self, table):
self.table = np.array(table)
クラスの初期化と、シャッフルの方法を定数を定義しています。
def display(self):
print(self.table.shape)
print(self.table)
tableが数独の9×9の配列を表しています。
def check(self):
column_sum = np.array([0] * 9)
for i in range(9):
line_sum = np.array(self.table[i]).sum()
assert line_sum == 45, "not sudoku"
column_sum += np.array(self.table[i])
assert column_sum.all() == np.array([45] * 9).all(), "not sudoku"
シャッフルしてルールを無視した問題が作成されたら困るので、チェック関数を用意しました。
各行の総和45であること、各列の総和が45であることを確認します。
def shuffle(self,type):
if type == self.SHUFFLE_ABC:
x = self.table.T
y = x[0:3]
np.random.shuffle(y)
x[0:3] = y
self.table = x.T
elif type == self.SHUFFLE_DEF:
x = self.table.T
y = x[3:6]
np.random.shuffle(y)
x[3:6] = y
self.table = x.T
elif type == self.SHUFFLE_GHI:
x = self.table.T
y = x[6:9]
np.random.shuffle(y)
x[6:9] = y
self.table = x.T
elif type == self.SHUFFLE_123:
x = self.table
y = x[0:3]
np.random.shuffle(y)
x[0:3] = y
self.table = x
elif type == self.SHUFFLE_456:
x = self.table
y = x[3:6]
np.random.shuffle(y)
x[3:6] = y
self.table = x
elif type == self.SHUFFLE_789:
x = self.table
y = x[6:9]
np.random.shuffle(y)
x[6:9] = y
self.table = x
elif type == self.SHUFFLE_LINES:
array = [np.copy(self.table[0:3]),np.copy(self.table[3:6]),np.copy(self.table[6:9])]
random.shuffle(array)
for i in range(3):
self.table[(0+3*i):(3+3*i)] = array[i]
elif type == self.SHUFFLE_COLS:
x = self.table.T
temp = [np.copy(x[0:3]),np.copy(x[3:6]),np.copy(x[6:9])]
random.shuffle(temp)
for i in range(3):
x[(0+3*i):(3+3*i)] = temp[i]
self.table = x.T
elif type == self.SHUFFLE_NUM:
temp = [1,2,3,4,5,6,7,8,9]
random.shuffle(temp)
for i in range(9):
for j in range(9):
data = self.table[i][j]
self.table[i][j] = temp[data - 1]
else:
print("fail")
ここが実際にシャッフルしてるところです。ご覧の通り迷走しています。後日リファクタリングします。
一応意図した通りに動作してくれて、以下のようにシャッフルされて動きます。check()関数も実行して、エラーなくできています。
上が元の配列で、下がシャッフル後の配列です。
以下のようにランダムなシャッフル方法を1000回実行しています。
sudoku = Sudoku([
[1,4,7,2,5,8,3,6,9],
[2,5,8,3,6,9,4,7,1],
[3,6,9,4,7,1,5,8,2],
[4,7,1,5,8,2,6,9,3],
[5,8,2,6,9,3,7,1,4],
[6,9,3,7,1,4,8,2,5],
[7,1,4,8,2,5,9,3,6],
[8,2,5,9,3,6,1,4,7],
[9,3,6,1,4,7,2,5,8]
])
sudoku.display()
sudoku.check()
for i in range(1000):
sudoku.shuffle(random.randint(1,9))
sudoku.display()
苦労したところ
いやほとんど苦労しました(汗)
pythonが全くわからないので、都度調べてという感じです。
numpyが最強すぎることは理解できました。
特に難しかったのが、配列の深いコピー、浅いコピーでつまづいたところですね。解決できてよかったです。深いコピー浅いコピーはそれだけで一記事レベルなのでまた後日にします。
まとめと反省
まず変数名が雑すぎますね!普段はこんな名前つけないです!
今日はブログに上げるまで時間がなさすぎたという理由でご勘弁を。
明日は変数名をしっかりしたものに変更して、コメントを入れてわかりやすくするところからですね。
今日も最後まで読んでくれてありがとうございます。
今日で1週間投稿を続けれました!読んでくれてるみなさんのおかげです。
また、記事のアイデアをアドバイスしてくれた同期や先輩の皆さんありがとうございます。
さぁ!明日からも頑張っていきましょうー