この行列パズルを解くより効率的な解法はありますか？

Question

行、列、および対角線の合計が15である3x3行列Mを検索します。条件：1-9のすべての数を使用する必要があります。

は、私は非常に巧妙ではないので、私はちょうどこの強引な方法を試してみました：

def solve_999(): 
    for a in range(1, 10): 
     for b in range(1, 10): 
      for c in range(1, 10): 
       for d in range(1, 10): 
        for e in range(1, 10): 
         for f in range(1, 10): 
          for g in range(1, 10): 
           for h in range(1, 10): 
            for i in range(1, 10): 
             if (a+b+c == d+e+f == g+h+i == a+d+g == b+e+h == c+f+i == a+e+i == c+e+g == 15):           
              if check_unique([a, b, c, d, e, f, g, h, i]): 
               print(a, b, c) 
               print(d, e, f) 
               print(g, h, i) 
               return 


def check_unique(L): 
    d = {1:0, 2:0, 3:0, 4:0, 5:0, 6:0, 7:0, 8:0, 9:0} 
    for letter in L: 
     d[letter] += 1 
     if d[letter] > 1: 
      return False 
    return True 

それは動作しますが、それは非常に効率的ではありません。誰も私がより効率的なソリューションを見つけるのを助けることができますか？

Answer 1

あなたが得られる最大のスピードアップは、すでにユニークなように四角形を生成することになります。これを行う最も簡単な方法はitertools.permutationsです。これはあなたにチェックを減らす9！ == 362880ボードではなく387420489ボード（仕事の約1/1000）であり、それらが一意であることを確認する必要はありません。

from itertools import permutations 
t1=time() 
for board in permutations(list(range(1,10)),9): 
    if sum(board[0:3]) == 15: 
     if sum(board[3:6])== 15: 
      if board[0]+board[3]+board[6]==15: 
       if board[1]+board[4]+board[7]==15: 
        if board[0]+board[4]+board[8]==15: 
         if board[2]+board[4]+board[6]==15: 
          print(board[0:3]) 
          print(board[3:6]) 
          print(board[6:9]) 
          break 

このソリューションの大きな問題点は、私たちが必要以上に多くのケースをチェックしていることです。注目すべきことは、各（a、b、d、e）に対して、c、f、g、h、およびiのそれぞれに最大1つの値が存在することです。つまり、9P4 == 3024の可能性を調べるだけです。これの欠点は、すべての値が一意であるという保証がなくなることです。しかし、このチェックを追加したとしても、よりシンプルなコードに比べてさらに10倍のスピードアップが見られます。時間に

def solve_999(): 
    for a,b,d,e in permutations(range(1,10),4): 
     c = 15 - (a + b) 
     f = 15 - (d + e) 
     g = 15 - (a + d) 
     h = 15 - (b + e) 
     i = 15 - (a + e) 
     if 15 == g+h+i == c+f+i == c+e+g: 
      if len(set([a,b,c,d,e,f,g,h,i]))==9: 
       print(a, b, c) 
       print(d, e, f) 
       print(g, h, i) 
       print() 
       break 

コード：

from timeit import timeitrom itertools import permutations 
def solve_999(): 
    for a,b,d,e in permutations(range(1,10),4): 
     c = 15 - (a + b) 
     f = 15 - (d + e) 
     g = 15 - (a + d) 
     h = 15 - (b + e) 
     i = 15 - (a + e) 
     if 15 == g+h+i == c+f+i == c+e+g: 
      if len(set([a,b,c,d,e,f,g,h,i]))==9: 
       return 
print(timeit(solve_999, number=1000)) 

が2.9秒/ 10000試行の時間を生み出す== 0.00029秒/試みる

Answer 2

あなたが反復処理するitertools.permutationsライブラリを使用することができますすべての可能性はあなたの必要な合計をチェックします。

あなたのコードは入力配列の固定サイズ（この場合は3x3 = 9）で動作しますが、Pythonで補助されたスプライシングを使用して任意の範囲で指定された合計をチェックするように一般化しました。これが機能するには、入力の長さが完全な正方形である必要があることに注意してください。

from itertools import permutations 
from math import sqrt 

def check_magic_square(rangeallowed,sumMS): 
    sidelenght = int(sqrt(len(rangeallowed))) 
    for i in permutations(rangeallowed): 
     # initialize all conditions to be satisfied 
     MSConditionsSatisfied = True 
     # Check for forward diagonal sum 
     if (MSConditionsSatisfied and sum(i[::sidelenght+1]) != sumMS): MSConditionsSatisfied = False 
     # Check for reverse diagonal sum 
     if (MSConditionsSatisfied and sum(i[sidelenght-1:-1:sidelenght-1]) != sumMS): MSConditionsSatisfied = False 
     for j in range(sidelenght): 
      # Check for each column 
      if (MSConditionsSatisfied and sum(i[j::sidelenght]) != sumMS): MSConditionsSatisfied = False 
      # Check for each row 
      if (MSConditionsSatisfied and sum(i[j*sidelenght:(j+1)*sidelenght]) != sumMS): MSConditionsSatisfied = False 
     # if all conditions are satisfied, return the splice reshaped to be a square matrix 
     if MSConditionsSatisfied: return [[i[k*sidelenght + j] for j in range(sidelenght)] for k in range(sidelenght)] 
    return False 

if __name__ == "__main__": 
    print(check_magic_square(range(1,10),15)) 

戻り

[2,7]、[6]、[9]、[5,1]、[4,3]、[8]]私のI5に沿う

時間他のものより短いマシン0.1秒

Answer 3

ビット：

>>> from itertools import permutations 
>>> for a, b, c, d, e, f, g, h, i in permutations(range(1, 10)): 
     if 15 == a+b+c == d+e+f == a+d+g == b+e+h == a+e+i == c+e+g: 
      print(a, b, c) 
      print(d, e, f) 
      print(g, h, i) 
      break 

2 7 6 
9 5 1 
4 3 8 

私のPCで約0.009秒かかります。以下のように測定すると、1000回行うのに約9秒かかります。

from itertools import permutations 
from timeit import timeit 

def solve_999(): 
    for a, b, c, d, e, f, g, h, i in permutations(range(1, 10)): 
     if 15 == a+b+c == d+e+f == a+d+g == b+e+h == a+e+i == c+e+g: 
      return 

print(timeit(solve_999, number=1000)) 

Answer 4

それは簡単です。 3つの数字の合計のうち15を構築する方法がいくつあるか考えてみてください。

1+5+9, 1+6+8, 2+4+9, 2+5+8, 2+6+7, 3+4+8, 3+5+7, 4+5+6 

8つの方法しかないため、各合計は正方形に表示されます。 5は4回表示されるため中央になければなりません。 2,4,6,8は3回表示されているため、角にある必要があります。

ここで、あなたは思考だけで解決策を見つけることができます。