Pythonでいろいろやってみる

Pythonを使った画像処理や機械学習などの簡単なプログラムを載せています。

賢くなるパズル(KENKEN)を解く

賢くなるパズル(KENKEN)は数字を使ったパズルの一種です。
例えば下図のような4x4のマトリックスにルールに従って1,2,3,4いずれかの数字を当てはめます。

f:id:T_A_T:20210419180023j:plain

数字を入れる際のルールは次の2つです。
①縦横に同じ数字を入れない
②太線で囲われた枠の数字をあらかじめ描かれた加減乗除の記号で計算した結果が、あらかじめ描かれた数字になる

上の図の左上のように2つの枠が太線で囲われていて、あらかじめ左上に「1-」と書かれている場合には「2つの数字を引いた結果が1となる」という意味で、例えば2と1、4と3などが入ります。数字の順番は問われません(1,2でも良い)。

フリー百科事典『ウィキペディア(Wikipedia)』>>賢くなるパズル

2004年に数学教師の宮本哲也さんが考案しその後、世界中で親しまれるようになりました。ニューヨークタイムズにも掲載されており、上の例はTHE NEW YORK TIMES INTERNATIONAL EDITION, MARCH 19, 2021に掲載されたものを使わせていただきました。

具体的には
(1)1,2,3,4の4つの数字の順列を生成しリスト化する (2)各行(横向き)に順列リストから一つずつ要素を取り出し当てはめる
(3)各列(縦向き)の数字が重複していないかチェックする
(4)すべての太枠内の計算結果をチェックする
という順序で上図のパズルを解きます。

環境
  • windows10 home
  • Anaconda 3/ jupyter notebook 5.6.0
  • Python 3.7.0
コード

順列の生成には標準モジュールのitertoolsを用いています。itertools.permutationsにより重複の無いすべての組み合わせが生成されます。

import itertools

numbers = [i+1 for i in range(4)]  # 1,2,3,4 の数列生成

# 1,2,3,4 による順列を生成しリストpermutationに格納
permutation = []
for i in itertools.permutations(numbers):
    permutation.append(i)
               
for i in permutation:
    for j in  permutation:
        for k in  permutation:
            for l in  permutation:
                matrix = [] 
                matrix.append(i)
                matrix.append(j)
                matrix.append(k)
                matrix.append(l)
                
                check = 0
                
                # matrixからcolumn(縦の列)を抽出しnumbersの要素と比較
                # 一致しない場合(数字の重複がある場合)はcheckを1に
                for m in range(length):    
                    column = [matrix[n][m] for n in range(4)]    
                    if set(column) != set(numbers):
                        check = 1
                        
                if check == 0:
                # 各演算条件のチェック
                    if abs(matrix[0][0]-matrix[0][1]) != 1:
                        check = 1
                    if abs(matrix[1][0]-matrix[1][1]) != 2:
                        check = 1
                    if matrix[2][0] != 4:
                        check = 1
                    if abs(matrix[3][0]-matrix[3][1]) != 2:
                        check = 1
                    if matrix[0][2]+matrix[0][3]+matrix[1][2] != 9:
                        check = 1
                    if matrix[2][1]+matrix[2][2]+matrix[3][2] != 6:
                        check = 1
                    if abs(matrix[1][3]-matrix[2][3]) != 1:
                        check = 1
                    if matrix[3][3] != 1:
                        check = 1
                            
                if check == 0:
                    print(matrix)
実行結果

答えが出力されます。

[(3, 2, 1, 4), (1, 3, 4, 2), (4, 1, 2, 3), (2, 4, 3, 1)]

図示すると以下のようになります。
f:id:T_A_T:20210419181702j:plain

以下のサイトを参考にさせていただきました

Python >> itertools --- 効率的なループ実行のためのイテレータ生成関数
Pythonの文法メモ >> 【標準ライブラリ】itertoolsによる順列・組合せの作成

ブログランキングに参加しています

にほんブログ村 IT技術ブログへ
にほんブログ村