今回はハノイの塔を解くプログラムについてです。


解説動画はこちら

# ハノイの塔を攻略
def hanoi(n, source, target, auxiliary):
    if n == 1:
        print(f"{n}を{source}から{target}に移動")
        return
    hanoi(n-1, source, auxiliary, target)
    print(f"{n}を{source}から{target}に移動")
    hanoi(n-1, auxiliary, target, source)

n = 3
hanoi(n, 'A', 'C', 'B')

ハノイの塔を描画するコード

widgetsを使ってstepごとの画像を描画しています。

# ハノイの塔を描画する
import ipywidgets as widgets
import matplotlib.pyplot as plt
import numpy as np

data,img_data = [],[]

# ディスクの色リスト
colors = ['red', 'green', 'blue', 'purple', 'yellow', 'silver', 'orange', 'pink']

# 棒の位置
positions = {'A': 0, 'B': 1, 'C': 2}

# ハノイの塔を攻略
def hanoi(n, source, target, auxiliary):
    if n == 1:
        data.append([n,source,target])
        return
    hanoi(n-1, source, auxiliary, target)
    data.append([n,source,target])
    hanoi(n-1, auxiliary, target, source)

# ディスクを描画するための関数
def draw_towers(state, step):
    fig, ax = plt.subplots()
    ax.set_xlim(-1, 3)
    ax.set_ylim(0, 5)
    ax.set_xticks([0, 1, 2])
    ax.set_xticklabels(['A', 'B', 'C'])
    ax.set_yticks([])
    for tower in 'ABC':
        for j, disk in enumerate(state[tower]):
            color = colors[disk - 1]
            width = 0.2 * disk
            height = 0.5
            ax.bar(positions[tower], height, bottom=j * height, width=width, color=color, edgecolor='black')
    ax.set_title(f'Step {step}')
    fig.canvas.draw()
    img_data.append(np.array(fig.canvas.renderer.buffer_rgba()))
    plt.close(fig)

# 初期状態
n = 4  # ディスクの数
hanoi(n, 'A', 'C', 'B')
towers = {'A': list(range(n, 0, -1)), 'B': [], 'C': []}
draw_towers(towers, 0)

# 各ステップごとに状態を描画
for step, (disk, source, target) in enumerate(data):
    towers[target].append(towers[source].pop())
    draw_towers(towers, step+1)

# img_data に保存された画像を表示するためのウィジェット
def show_image(step):
    plt.imshow(img_data[step])
    plt.axis('off')
    plt.show()

slider = widgets.IntSlider(value=0, min=0, max=len(img_data)-1, step=1, description='Step:')
widgets.interactive(show_image, step=slider)

タグ ：

#Python

#プログラミング

#パズル

#ハノイの塔

#アルゴリズム

今回は覆面算です

解説動画はこちら



さて覆面算とは、0から9の数字が対応する
文字と数値の変換を行い
何も考えず総当たりでこの計算式が解けるかどうかで
判定してみます。

import itertools
from time import time
tm=time()

d1 = "SEND"
d2 = "MORE"
d3 = "MONEY"

for n in itertools.permutations(range(10) , len({a for a in d1 + d2 + d3})):
    data = dict(zip(sorted({a for a in d1 + d2 + d3}),n))
    if data[d1[0]]*data[d2[0]]*data[d3[0]]!=0:
        a1 = int(''.join([str(data[d]) for d in d1]))
        a2 = int(''.join([str(data[d]) for d in d2]))
        a3 = int(''.join([str(data[d]) for d in d3]))
        if a1+a2 == a3:
            print(data)
            print(a1)
            print(a2)
            print("-------")
            print(a3)
            print()
            break
            
print(time()-tm)

とりあえずは答えが出ましたね。

10個の数字から8個を取り出した
数字の順列は結構な数があります。

このプログラムだと
結構時間かかっちゃう感じなので
少し改良してみましょう。

変数に直接数字を受けたり
文字列に直すのやめたり
少し条件を加えてみましょう。

import itertools
from time import time
tm=time() 

def calc(p,q,r,s,t):
    return p*10000 + q*1000 + r*100 + s*10 + t

"""
  SEND
+MORE
----------
MODEY
"""
for p in itertools.permutations(range(10),8):
    s,e,n,d,m,o,r,y=p
    if s*m!=0 and (d+e==y or d+e==10+y):
        send  = calc(0,s,e,n,d)
        more  = calc(0,m,o,r,e)
        money = calc(m,o,n,e,y)
        if send+more==money:
            print(send)
            print(more)
            print("-------")
            print(money)
            print("")
            break

print(time()-tm)

先ほどと比べると
10分の1くらいの時間で
終わるようになりました。


2問目です。

これはGoogleの入社試験の
問題らしいです。


今度は引き算ですが
やることは一緒ですね。

import itertools
from time import time
tm=time() 

"""
WWWDOT
GOOGLE
-------------
DOTCOM
"""
for p in itertools.permutations(range(10),9):
    W,D,O,T,G,L,E,C,M = p
    if W*G*D==0: continue
    wwwdot = 100000*W+10000*W+1000*W+100*D+10*O+T
    google = 100000*G+10000*O+1000*O+100*G+10*L+E
    dotcom = 100000*D+10000*O+1000*T+100*C+10*O+M
    if wwwdot-google==dotcom:
        print(wwwdot)
        print(google)
        print("-------")
        print(dotcom)
        print()
        break

print(time()-tm)

こいつもまあまあ時間かかっちゃうので
早くなるように改良してみましょう。

こんな感じにしてみました。

import itertools
from time import time
tm=time() 

"""
WWWDOT
GOOGLE
-------------
DOTCOM
"""

for q in itertools.permutations(range(10),3):
    T,E,M = q
    if (T-E==M) or (10+T-E==M):
        for p in itertools.permutations(list(set(range(10)) - set(q)),6):
            W,D,O,G,L,C = p
            if W*G*D==0: continue        
            wwwdot = 100000*W+10000*W+1000*W+100*D+10*O+T
            google = 100000*G+10000*O+1000*O+100*G+10*L+E
            dotcom = 100000*D+10000*O+1000*T+100*C+10*O+M
            if wwwdot - google==dotcom:
                print(wwwdot)
                print(google)
                print("-------")
                print(dotcom)
                print()

print(time()-tm)

1秒切るくらいに早くなりましたね。

注目すべきは1桁目です。
TからEを引いたらMになるはずなので
この3つの数字の関係性を先に計算し
合致するものだけ次に進みます。

残る6個の数字と組み合わせて
計算式を満たせば終了です。

そうすることで、だいぶ計算量が減りますね。

この覆面算パズルは
アルゴリズムを練習するのには
とても良い題材ですね。

色々改良して
早くしてみてください。

それでは。

タグ ：

#プログラミング

#Python

#覆面算

#パズル

#Google

#入社問題

今回はチェスのコマを使ったパズルゲームである
8クイーン問題を解いてみました。

解説動画はこちら



8クイーンをご存じない方のために説明すると
クイーンはチェスのコマで
縦横斜め全てのマスに行く事ができます



このコマを8つ用いて
8x8マスの中にうまく
お互いのクイーンが利かないように
配置出来るかどうかというのが
8クイーンというものになります。

8x8マスなので結構大変ですね


さて解き方を考えてみましょう

愚直に一個一個置いてみて
縦横斜めに置けているかを判定してみれば
行けますかね！！！

for文を用いて全通り試せば行けますね

コードはこんな感じになりました。

sol_num ,count = 0 , 0

def check(i, j, k, l, m, n, o, p):
    return(i!=j) and (i!=k) and (i!=l) and (i!=m) and (i!=n) and (i!=o) and (i!=p) and (j!=k) and (j!=l) and (j!=m) and (j!=n) and (j!=o) and (j!=p) and (k!=l) and (k!=m) and (k!=n) and (k!=o) and (k!=p) and (l!=m) and (l!=n) and (l!=o) and (l!=p) and (m!=n) and (m!=o) and (m!=p) and (n!=o) and (n!=p) and (o!=p) and (abs(i-j)!=1) and (abs(j-k)!=1) and (abs(k-l)!=1) and (abs(l-m)!=1) and (abs(m-n)!=1) and (abs(n-o)!=1) and (abs(o-p)!=1) and (abs(i-k)!=2) and (abs(j-l)!=2) and (abs(k-m)!=2) and (abs(l-n)!=2) and (abs(m-o)!=2) and (abs(n-p)!=2) and (abs(i-l)!=3) and (abs(j-m)!=3) and (abs(k-n)!=3) and (abs(l-o)!=3) and (abs(m-p)!=3) and (abs(i-m)!=4) and (abs(j-n)!=4) and (abs(k-o)!=4) and (abs(l-p)!=4) and (abs(i-n)!=5) and (abs(j-o)!=5) and (abs(k-p)!=5) and (abs(i-o)!=6) and (abs(j-p)!=6) and (abs(i-p)!=7)

def print_sol(i, j, k, l, m, n, o, p):
    li = [i, j, k, l, m, n, o, p]
    for num in li:
        for a in range(8):
            if a ==num:
                print('Q' , end='\t')
            else:
                print('.' , end='\t')
        print()
    print('\n')

for i in range(8):
    for j in range(8):
        for k in range(8):
            for l in range(8):
                for m in range(8):
                    for n in range(8):
                        for o in range(8):
                            for p in range(8):
                                count+=1
                                if check(i, j, k, l, m, n, o, p):
                                    #print_sol(i, j, k, l, m, n, o, p)
                                    sol_num+=1
print(sol_num , count)

92 16777216

一応答えは出て8x8マスだと
92通り有るようです。


でも8回もfor文を使ったり
判定のところがめちゃくちゃ長かったり
結構酷いプログラムですねえwww

16777216回も判定を行っています
凄い数計算しちゃってますね

もう少し効率の良いものに
直していきましょう

まずfor文は8個も使わなくても
行列の組み合わせを考えれば
効率よく行けますね！！！

Pythonにはitertoolsというライブラリがあり
順列を生成することのできる
permutations というものがあるので
これを使うと8個もfor文を書かなくて済みます

from itertools import permutations

N=8
print(len([combo for combo in permutations(range(N))]))
for combo in permutations(range(N)):
    print(combo)
    break

40320
(0, 1, 2, 3, 4, 5, 6, 7)

順列だと4万通り程度で済むので
だいぶ効率よさそうです

次に判定のところは
2つのクイーン同士の
利きを判定するものにしてみます

# (x1, y1) と (x2, y2) の位置にいるクイーンが互いの効き筋にいるかを判定
def threat(x1, y1, x2, y2):
    return (x1 == x2) or (y1 == y2) or (abs(x1-x2) == abs(y1-y2))

縦横はそれぞれの場所が一緒ならすぐ判定できますね
斜めは縦横が同じ長さなら正方形になるので
その位置の対角線上かどうかが分かります

そういったことで縦横斜めの利きがあるかが
判定できました。

これを使って効率よく書くとこうなりました。

from itertools import permutations

def threat(x1, y1, x2, y2):
    return (x1 == x2) or (y1 == y2) or (abs(x1-x2) == abs(y1-y2))

N,count=8,0
for combo in permutations(range(N)):
    board1 = [(i,c) for i,c in enumerate(combo)]
    board2 = [board1[i+1:] for i,d in enumerate(board1) if i<N-1]
    tmp = 0
    for i,(y1,x1) in enumerate(board1):
        if i==N-1:
            break
        flg=True
        for y2,x2 in board2[i]:
            if y1==y2 and x1==x2:
                continue
            if threat(x1,y1,x2,y2):
                flg=False
        if flg:
            tmp+=1
    if tmp==N-1:
        count+=1
        #for z in board1:
        #    print(' _ ' * z[1] + ' Q ' + ' _ ' * (8-z[1]-1))
        #    print('')
        #break
print(count)

92

一応答えは出ましたね。
だいぶ早く終わるようになりました。

最後にもっと短くて
効率の良いものを見つけました。
それはこちらです。

from itertools import permutations

N,count = 8,0
for combo in permutations(range(N)):
    s1 = set(combo[i]+i for i in range(N))
    s2 = set(combo[i]-i for i in range(N))
    if N==len(s1)==len(s2):
        #print("\n".join(' _ ' * c + ' Q ' + ' _ ' * (N-c-1) for c in combo) + "\n\n")
        count+=1
        #break
print(count)

92

これだと10行程度で終わりますね
自分が見た中でこれが一番
短いかなーと思います。

一応答えは
プリントの部分のコメントアウトすると
こんな感じで出力することもできます。



8クイーンは
色々な人の解法が有って
たくさんコードがありますが

長いよりは短くて分かりやすいのが
いいですよね

もっともっと短く出来る可能性が
有って面白い問題です

誰か1行とかで出来ないかなwww

今回はここまでです
それでは

タグ ：

#Python

#プログラミング

#8クイーン

#チェス

#パズル