- はじめに
Ｃマガ電脳クラブ 1991年4月号（参考文献(1)），7月号（参考文献(2)）にクイズ「2枚のカードの間には」が掲載されている（図1）。本報告では、数独の解法（参考文献(3)）などで活用されている「再帰呼び出しプログラム」を使用しクイズを解いてみたので紹介する。
図1 クイズ「2枚のカードの間には」 - 問題設定
1)「再帰呼び出し」を使用して一つの解を得るプログラムの作成
2)1)を用いて, 重複した解を削除した全ての解を得るプログラムの作成
3)解析システム
RaspberryPi4＋Python
3.「再帰呼び出し」を使用して一つの解を得るプログラムの作成
3.1 プログラム
プログラムは下記の通り.
# 規則に合った初期値を設定
Table=[1,0,1,0,0,0,0,0,0,0,0,0,0,0]
#Table=[3,5,0,0,3,0,0,5,0,0,0,0,0,0]
#Table=[4,1,0,1,0,4,0,0,0,0,0,0,0,0]
#Table=[1,4,1,0,0,0,4,0,0,0,0,0,0,0]
import csv, copy, pprint
backtracks = 0
# 空のマス番号の検出
def find_next_cell(grid):
for x in range(14):
if grid[x] == 0:
# 0 の座標を返す
return x
# すべてのマスに数字が入っている状態
return -1
# 2枚のカードは希望する位置に入れるか?
def is_valid(grid, x, value):
# print(grid, x, value)
is_row = value not in grid
if grid[x]==0: is_space_1=True
else: is_space_1=False
if x+value+1 < 14 and grid[x+value+1]==0: is_space_2=True
else: is_space_2=False
if x+value+1 > 13: is_max=False
else: is_max=True
# print(is_row, is_max)
return all([is_row, is_space_1, is_space_2, is_max])
# 再帰呼び出しプロゴラム
def solve_Card(grid, x=0):
x = find_next_cell(grid)
# 終了判定
if x == -1:
return True
# 入力
for value in range(1, 8):
if is_valid(grid, x, value):
grid[x] = value
grid[x+value+1] = value
# 次へ
if solve_Card(grid, x):
return True
grid[x] = 0
grid[x+value+1] = 0
return False
print(solve_Card(Table))
pprint.pprint(Table)
3.2 計算例
初期配列として下記を設定すると
Table=[1,0,1,0,0,0,0,0,0,0,0,0,0,0]
出力は下記となる.
[1,4,1,5,6,7,4,2,3,5,2,6,3,7]
ここでの注意点は上記解は唯一のものではなく一番初めに見つかったものであるということである.次章では網羅的に初期値を入力し規則に合ったものを選択するようにしている.
4.重複した解を削除した全ての解を得るプログラムの作成
4.1 プログラム
プログラムは下記の通り.
import numpy as np
list = np.zeros((50, 14))
Table=[0,0,0,0,0,0,0,0,0,0,0,0,0,0]
Table1=[0,0,0,0,0,0,0,0,0,0,0,0,0,0]
Table2=[0,0,0,0,0,0,0,0,0,0,0,0,0,0]
import csv, copy, pprint
backtracks = 0
＃ 3章と同じ
def find_next_cell(grid):
for x in range(14):
if grid[x] == 0:
# 0 の座標を返す
return x
# すべてのマスに数字が入っている状態
return -1
def is_valid(grid, x, value):
# 行のチェック
# print(grid, x, value)
is_row = value not in grid
if grid[x]==0: is_space_1=True
else: is_space_1=False
if x+value+1 < 14 and grid[x+value+1]==0: is_space_2=True
else: is_space_2=False
if x+value+1 > 13: is_max=False
else: is_max=True
# 有効チェック
# print(is_row, is_max)
return all([is_row, is_space_1, is_space_2, is_max])
def solve_Card(grid, x=0):
x = find_next_cell(grid)
# 終了判定
if x == -1:
return True
# 入力
for value in range(1, 8):
if is_valid(grid, x, value):
grid[x] = value
grid[x+value+1] = value
# 次へ
if solve_Card(grid, x):
return True
grid[x] = 0
grid[x+value+1] = 0
return False
# 4種類8枚のカードを網羅的に配置し解が得られるかをチェック
ans=0
for i1 in range(7):
for i2 in range(7):
for i3 in range(7):
for i4 in range(7):
for i in range(14):
Table[i]=0
Table[0]=i1+1
Table[i1+2]=i1+1
if i1!=i2:
Table[1]=i2+1
Table[i2+3]=i2+1
if i3!=i1 and i3!=i2 and Table[2]==0 and Table[i3+4]==0:
Table[2]=i3+1
Table[i3+4]=i3+1
if i4!=i1 and i4!=i2 and i4!=i3 and Table[3]==0 and Table[i4+5]==0:
Table[3]=i4+1
Table[i4+5]=i4+1
if solve_Card(Table):
# 左右反転も含め同一解のチェック
check=0
for k in range(ans):
for i in range(14):
Table1[i]=Table[i]
Table2[i]=int(list[k,13-i])
if Table1==Table2:
# print(Table1)
check=check+1
for k in range(ans):
for i in range(14):
Table1[i]=Table[i]
Table2[i]=int(list[k,i])
if Table1==Table2:
# print(Table1)
check=check+1
if check==0:
print("No=",ans+1," ",Table)
for j in range(14):
list[ans,j]=Table[j]
ans=ans+1
#print(list)
4.2 計算結果
Ｃマガ電脳クラブ 1991年7月号の解答と同じ下記26種類の解が得られた.
No= 1 [1, 4, 1, 5, 6, 7, 4, 2, 3, 5, 2, 6, 3, 7]
No= 2 [1, 7, 1, 2, 5, 6, 2, 3, 4, 7, 5, 3, 6, 4]
No= 3 [1, 6, 1, 3, 5, 7, 4, 3, 6, 2, 5, 4, 2, 7]
No= 4 [1, 5, 1, 4, 6, 7, 3, 5, 4, 2, 3, 6, 2, 7]
No= 5 [1, 4, 1, 6, 7, 3, 4, 5, 2, 3, 6, 2, 7, 5]
No= 6 [1, 5, 1, 7, 3, 4, 6, 5, 3, 2, 4, 7, 2, 6]
No= 7 [1, 5, 1, 6, 3, 7, 4, 5, 3, 2, 6, 4, 2, 7]
No= 8 [1, 6, 1, 7, 2, 4, 5, 2, 6, 3, 4, 7, 5, 3]
No= 9 [2, 3, 6, 2, 7, 3, 4, 5, 1, 6, 1, 4, 7, 5]
No= 10 [2, 6, 3, 2, 5, 7, 3, 4, 6, 1, 5, 1, 4, 7]
No= 11 [2, 7, 4, 2, 3, 5, 6, 4, 3, 7, 1, 5, 1, 6]
No= 12 [2, 3, 7, 2, 6, 3, 5, 1, 4, 1, 7, 6, 5, 4]
No= 13 [2, 4, 7, 2, 3, 6, 4, 5, 3, 1, 7, 1, 6, 5]
No= 14 [2, 5, 6, 2, 3, 7, 4, 5, 3, 6, 1, 4, 1, 7]
No= 15 [2, 6, 7, 2, 1, 5, 1, 4, 6, 3, 7, 5, 4, 3]
No= 16 [3, 5, 7, 2, 3, 6, 2, 5, 4, 1, 7, 1, 6, 4]
No= 17 [3, 7, 4, 6, 3, 2, 5, 4, 2, 7, 6, 1, 5, 1]
No= 18 [3, 6, 7, 1, 3, 1, 4, 5, 6, 2, 7, 4, 2, 5]
No= 19 [3, 4, 6, 7, 3, 2, 4, 5, 2, 6, 1, 7, 1, 5]
No= 20 [4, 1, 6, 1, 7, 4, 3, 5, 2, 6, 3, 2, 7, 5]
No= 21 [4, 1, 7, 1, 6, 4, 2, 5, 3, 2, 7, 6, 3, 5]
No= 22 [4, 6, 1, 7, 1, 4, 3, 5, 6, 2, 3, 7, 2, 5]
No= 23 [5, 2, 4, 6, 2, 7, 5, 4, 3, 1, 6, 1, 3, 7]
No= 24 [5, 2, 6, 4, 2, 7, 5, 3, 4, 6, 1, 3, 1, 7]
No= 25 [5, 3, 6, 4, 7, 3, 5, 2, 4, 6, 2, 1, 7, 1]
No= 26 [5, 7, 1, 4, 1, 6, 5, 3, 4, 7, 2, 3, 6, 2]
- おわりに
再帰呼び出しプログラムの使用は初めてであったが何とか解くことが出来た.
参考文献
(1) Ｃマガ電脳クラブ 1991年4月号（問題）
(2) Ｃマガ電脳クラブ 1991年7月号（解答）
(3) 数独はPythonで考えて解く話