Rings in the Squareの問題をPythonで解いてみた。

Python

　Rings in the Squareの問題をPythonで解いてみました。(^_^;
　点は、p=0〜8の整数値で与えて、p%3でｘ座標、p//3でｙ座標を得ています。

 6---7---8    (0,2)---(1,2)---(2,2)
 |   |   |      |       |       |  
 3---4---5 → (0,1)---(1,1)---(2,1)
 |   |   |      |       |       |  
 0---1---2    (0,0)---(1,0)---(2,0)

　4点が同一円周上にある条件は行列式を使って次の通りです。
\left|\begin{array}{cc}x_0^2+y_0^2&x_0&y_0&1\\x_1^2+y_1^2&x_1&y_1&1\\x_2^2+y_2^2&x_2&y_2&1\\x_3^2+y_3^2&x_3&y_3&1\end{array}\right|=-\left|\begin{array}{cc}x_1^2+y_1^2-(x_0^2+y_0^2)&x_1-x_0&y_1-y_0\\x_2^2+y_2^2-(x_0^2+y_0^2)&x_2-x_0&y_2-y_0\\x_3^2+y_3^2-(x_0^2+y_0^2)&x_3-x_0&y_3-y_0\end{array}\right|=0

※参考URL
●Circumcircle -- from Wolfram MathWorld
●Rings in the Squareの問題をPythonで解いてみた。(2)

● RingsInTheSquare.py

# coding: UTF-8
# RingsInTheSquare.py

import itertools
from time import time

def det3(m):
    r = m[0][0]*m[1][1]*m[2][2]+m[0][1]*m[1][2]*m[2][0]+m[0][2]*m[1][0]*m[2][1]
    r-= m[0][2]*m[1][1]*m[2][0]+m[0][1]*m[1][0]*m[2][2]+m[0][0]*m[1][2]*m[2][1]
    return r

def main():
    tm=time()  # Timer Start

    Points = range(9)
    cnt = 0
    for p in itertools.combinations(Points,4):
        x = [n%3  for n in p]
        y = [n//3 for n in p]
        m = [[x[i]**2+y[i]**2-(x[0]**2+y[0]**2),x[i]-x[0],y[i]-y[0]]
            for i in range(1,3+1)]
        if det3(m)!=0 : continue
        # チェックを潜り抜けたものだけを出力
        cnt+=1
        print("%2d : %s"%(cnt,p))

    tm=time()-tm  # Timer Stop
    print("Runtime : %.3f [sec]"%tm)

if __name__ == '__main__':
    main()

●実行結果

 1 : (0, 1, 3, 4)
 2 : (0, 1, 5, 8)
 3 : (0, 1, 6, 7)
 4 : (0, 2, 3, 5)
 5 : (0, 2, 6, 8)
 6 : (0, 3, 7, 8)
 7 : (1, 2, 3, 6)
 8 : (1, 2, 4, 5)
 9 : (1, 2, 7, 8)
10 : (1, 3, 5, 7)
11 : (2, 5, 6, 7)
12 : (3, 4, 6, 7)
13 : (3, 5, 6, 8)
14 : (4, 5, 7, 8)
Runtime : 0.005 [sec]

※参考図

 6---7---8
 |   |   |
 3---4---5
 |   |   |
 0---1---2

Excel VBAでパズルを解こう

Excel VBAでパズルを解こう