乙Py先生のプログラミング教室
初学者のためのプログラミング学習サイト

パズル

2つのバケツを使って水の量を測るっていう
古典的なパズル問題ありますよね

今回はそれをプログラムで解いてみました。

解説動画はこちら



二つのバケツで指定の水量を測るやつ

問題

5リットル入るバケツと3リットル入るバケツがある
この2つだけを使って4リットルの水を測りたい
どうすれば良いでしょうか

ヒント : 水は捨てたり移動したりして良い





プログラムでの解法

幅優先探索(breadth-first search, BFS)を
用いて手順の探索を行っていきます。

バケツをA, B、測りたい水量をXとし
A,Bの水量を記録していきます

途中、以下の6つの状態でうまく切り替えて手順を記録し
どこかが水量Xになったら終了になります。

1. Aを満たす
2. Bを満たす
3. Aを空にする
4. Bを空にする
5. AからBに移す
6. BからAに移す

プログラム上ではキューというデータ構造のものを使って
手順を記録していく形になります。


手順を解くコード


手順を算出するコードは次のようになります。

from collections import deque
from math import gcd

# 幅優先探索(breadth-first search, BFS)を用いて手順の探索を行う
def min_steps_to_measure(A, B, X):
    # 目標の水量がAとBの最大公約数で割り切れない場合は終了
    if X > max(A, B) or X % gcd(A, B) != 0:
        return []

    # キューとSETと状態の親を初期化
    queue, visited, parent = deque(), set(), {}

    # 初期状態をキューに追加
    queue.append((0, 0))  # (容器Aの水量, 容器Bの水量)
    parent[(0, 0)] = None  # 初期状態の親はNone

    while queue:
        a, b = queue.popleft()

        # 目標の水量に達した場合
        if a == X or b == X:
            # 結果を表示
            steps = []
            while (a, b) is not None:
                steps.append((a, b))
                # 親が存在する場合のみアンパック
                if parent[(a, b)] is not None:
                    a, b = parent[(a, b)]
                else:
                    break
            steps.reverse()
            return steps

        # 訪れた状態を記録
        if (a, b) in visited:
            continue
        visited.add((a, b))

        # 次の状態をキューに追加
        # 1. 容器Aを満たす
        if (A, b) not in visited:
            queue.append((A, b))
            parent[(A, b)] = (a, b)
        # 2. 容器Bを満たす
        if (a, B) not in visited:
            queue.append((a, B))
            parent[(a, B)] = (a, b)
        # 3. 容器Aを空にする
        if (0, b) not in visited:
            queue.append((0, b))
            parent[(0, b)] = (a, b)
        # 4. 容器Bを空にする
        if (a, 0) not in visited:
            queue.append((a, 0))
            parent[(a, 0)] = (a, b)
        # 5. 容器Aから容器Bに移す
        transfer_to_B = min(a, B - b)
        if (a - transfer_to_B, b + transfer_to_B) not in visited:
            queue.append((a - transfer_to_B, b + transfer_to_B))
            parent[(a - transfer_to_B, b + transfer_to_B)] = (a, b)
        # 6. 容器Bから容器Aに移す
        transfer_to_A = min(b, A - a)
        if (a + transfer_to_A, b - transfer_to_A) not in visited:
            queue.append((a + transfer_to_A, b - transfer_to_A))
            parent[(a + transfer_to_A, b - transfer_to_A)] = (a, b)

    return []  # 目標の水量を測ることができない場合





早速実行して見てみましょう。

バケツA,Bの値と
ターゲットの水量Xを指定すると
その手順が表示されます。

# 容器の容量と目標の水量を指定
A = 5  # 容器Aの容量
B = 3  # 容器Bの容量
X = 4  # 測りたい水量

# 最小手数を計算
steps = min_steps_to_measure(A, B, X)

# 結果を表示
if steps:
    print("途中の過程:")
    for step in steps:
        print(f"容器A: {step[0]}L, 容器B: {step[1]}L")
else:
    print("目標の水量を測ることができませんでした。")

途中の過程:
容器A: 0L, 容器B: 0L
容器A: 5L, 容器B: 0L
容器A: 2L, 容器B: 3L
容器A: 2L, 容器B: 0L
容器A: 0L, 容器B: 2L
容器A: 5L, 容器B: 2L
容器A: 4L, 容器B: 3L



このように探索の結果が表示されます。

文字だけだと分かりづらいので
描画してみることにしましょう。



手順を描画するコード

ipywidgetsでスライダーを作り
stepを可変で描画できます。

A,B,Xを色々な設定に変えて
色々遊んでみてください。

import matplotlib.pyplot as plt
import matplotlib.patches as patches
import numpy as np
import ipywidgets as widgets
from IPython.display import display
%matplotlib inline

A = 5  # 容器Aの容量
B = 3  # 容器Bの容量
X = 4  # 測りたい水量

steps = min_steps_to_measure(A, B, X)

# 描画関数
def draw_graph(step):
    a_value = steps[step][0]
    b_value = steps[step][1]
    a_frame_height = A - a_value
    b_frame_height = B - b_value

    # 描画
    fig, ax = plt.subplots(figsize=(8, 4))
    ax.bar(0, a_value, width=0.4, label='Container A Volume (L)', color='blue', linewidth=2, edgecolor='black')
    rect_a = patches.Rectangle((-0.2, a_value), 0.4, a_frame_height, linewidth=2, edgecolor='black', facecolor='none')
    ax.add_patch(rect_a)
    ax.text(0, max(A,B)+1, str(a_value), ha='center', va='bottom', fontsize=12, color='green')
    ax.bar(1, b_value, width=0.4, label='Container B Volume (L)', color='red', linewidth=2, edgecolor='black')
    rect_b = patches.Rectangle((0.8, b_value), 0.4, b_frame_height, linewidth=2, edgecolor='black', facecolor='none')
    ax.add_patch(rect_b)
    ax.text(1, max(A,B)+1, str(b_value), ha='center', va='bottom', fontsize=12, color='green')

    # タイトルとラベルの設定
    ax.set_title(f'Container A : {A} and B: {B} Target Volume : {X} with Frames step : {step}')
    ax.set_xlabel('Containers')
    ax.set_ylabel('Volume (L)')
    ax.set_xticks([0, 1])
    ax.set_xticklabels(['Container A', 'Container B'])
    ax.set_ylim(0, max(A,B)+3)
    plt.show()

# スライダーの作成
step_slider = widgets.IntSlider(value=0, min=0, max=len(steps)-1, step=1, description='Step:')
interactive_plot = widgets.interactive(draw_graph, step=step_slider)
display(interactive_plot)
step06


今回は2つのバケツを使って水量を測るやつを
プログラムにしてみました。

動画ではもう少し手順のかかるやつもやっているので
興味がある場合は見てみてください。

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


 

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


解説動画はこちら



ハノイの塔(Tower of Hanoi)とは

古来からあるパズルゲーム



以下のルールに従って
すべての円盤を右端の杭に移動させられれば完成です。

・3本の杭と、大きさの異なる複数の円盤から構成
・初期配置は左端の杭に昇順で積み重ねられている
・1回に1枚ずつ移動させるられるが
 小さいものの上に大きな円盤を乗せることはできない


ハノイの塔は
「再帰的な方法」で解くことができる古典的な問題です。

ディスクの数 n、出発点の棒 source
目的地の棒 target、および補助の棒 auxiliaryとします。

基底条件として、ディスクが1枚だけの場合は
sourceからtargetに直接移動
それ以外の場合は、再帰的に以下のステップを実行:

n-1枚のディスクをsourceからauxiliaryに移動
残りの1枚のディスクをsourceからtargetに移動
n-1枚のディスクをauxiliaryからtargetに移動

配置するディスクの数 n を変更することで
他のケースも同様に解くことができます。



ハノイの塔を解くコード

# ハノイの塔を攻略
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')
1をAからCに移動
2をAからBに移動
1をCからBに移動
3をAからCに移動
1をBからAに移動
2をBからCに移動
1をAからCに移動



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

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)
スクリーンショット 2024-08-31 12.59.50


終わりに

インドの巨大な寺院の話が元ネタのようです。

天地創造の時に神が64枚の純金の円盤を重ねて置いた
司祭たちはそこで、昼夜を通して円盤を別の柱に移し替えている
全ての円盤の移し替えが終わったときに
世界は崩壊し終焉を迎える・・・



ハノイの塔のstep数は 2のディスクの枚数乗 -1 なので
2 ** 64 -1 stepかかります。

すっごい回数
おじさん達が移し替えてると思うと
大変だなーと思う今日この頃です。

それでは。


今回は覆面算です

解説動画はこちら



さて覆面算とは、0から9の数字が対応する
別の記号に置き換えられた計算式を与えられて
どの記号が何の数字に対応しているかを推理して
完全な計算式を導き出すパズルのことです。

 
   A B C
+ A C B
————
   C B A

A=4,B=5,C=9


ルール
同じ文字には同じ数字
違う文字には違う数字が入る(0-9 , 最多で10種類)
一番左側の文字は0にはならない

これを解くプログラムを考えてみましょう。

1問目は

    S E N D
+   M O R E
------------------------
  M O N E Y


文字と数値の変換を行い
何も考えず総当たりでこの計算式が解けるかどうかで
判定してみます。
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)

{'D': 7, 'E': 5, 'M': 1, 'N': 6, 'O': 0, 'R': 8, 'S': 9, 'Y': 2}
9567
1085
-------
10652

6.051903963088989

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

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)
9567
1085
-------
10652

0.5969181060791016

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


2問目です。

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

  WWWDOT
ー GOOGLE
-----------------------
  DOTCOM

今度は引き算ですが
やることは一緒ですね。
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)
777589
188103
-------
589486

2.180610179901123


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

こんな感じにしてみました。
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)

777589
188103
-------
589486

777589
188106
-------
589483

0.25487303733825684


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

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

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

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

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

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

それでは。




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

解説動画はこちら



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


このコマを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行程度で終わりますね
自分が見た中でこれが一番
短いかなーと思います。

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

Q  _  _  _  _  _  _  _ 
 _  _  _  _  Q  _  _  _ 
 _  _  _  _  _  _  _  Q 
 _  _  _  _  _  Q  _  _ 
 _  _  Q  _  _  _  _  _ 
 _  _  _  _  _  _  Q  _ 
 _  Q  _  _  _  _  _  _ 
 _  _  _  Q  _  _  _  _ 


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

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

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

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

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

今回は数独をプログラムで解いてみます。

解説動画はこちら



さて数独のルールですが
9x9のマスがあり初期配置で数値が置かれている。

空いているマスに1〜9のいずれかの数字を入れる。

縦・横の各列及び
太線で囲まれた3×3のブロック内に
同じ数字が複数入ってはいけない。
download

コレをプログラムで解いていきましょう。

考え方としては

事前:用意された数値埋めて
空白マスを0として埋めたリスト型を用意する

(1) 左上から右下へと順に0を調べていく
(2) 0があれば、その時点で配置可能な数字を調べる
(3) 配置可能な数字を仮に配置して、次のマスを調べていく
(4) もし配置がうまくいかなければ(3)に戻る
(5) 最後のマスに到達するまで、(2)以降の処理を繰り返す
(6) 最後に到達したら結果を出力する

こんな感じです。

プログラムの実装を考えてみましょう。

考えたく無い方はこちらが
実装例になります。
# 行、列、ブロックのチェック
def is_valid(grid, y, x, val):
    if val in grid[y]:
        return False 
    if val in [i[x] for i in grid]:
        return False
    # NxNブロックの判定
    t_x, t_y = (x//N) * N, (y//N) * N
    block = [i[t_x:t_x + N] for i in grid[t_y:t_y + N]]
    if val in sum(block, []):
        return False
    return True

# 0の座標を返す
def find_next(grid):
    for y in range(N*N):
        for x in range(N*N):
            if grid[y][x] == 0:
                return x , y
    return -1, -1

# 数独を解く
def solve(grid, y=0, x=0):
    x , y = find_next(grid)
    if -1==x or -1==y:
        return True
    for val in range(1, N*N+1):
        if is_valid(grid, y, x, val):
            grid[y][x] = val
            if solve(grid, y, x):
                return True
            grid[y][x] = 0
    return False

# ブロックの大きさ
N=3
# 初期配列
input_num = [
[5, 8, 7, 2, 0, 0, 0, 0, 1],
[9, 0, 0, 0, 0, 0, 4, 0, 0],
[0, 0, 0, 1, 8, 0, 6, 0, 0],
[0, 0, 0, 0, 0, 4, 7, 2, 0],
[0, 5, 0, 8, 7, 0, 0, 4, 0],
[0, 0, 2, 0, 0, 0, 0, 0, 0],
[0, 4, 0, 0, 0, 3, 0, 0, 0],
[0, 0, 0, 0, 0, 7, 2, 9, 3],
[0, 2, 1, 0, 0, 0, 0, 0, 0]]

solve(input_num)
for row in input_num:
    print(' , '.join([str(i) for i  in row]))
5 , 8 , 7 , 2 , 4 , 6 , 9 , 3 , 1
9 , 1 , 6 , 7 , 3 , 5 , 4 , 8 , 2
2 , 3 , 4 , 1 , 8 , 9 , 6 , 5 , 7
1 , 9 , 8 , 3 , 6 , 4 , 7 , 2 , 5
6 , 5 , 3 , 8 , 7 , 2 , 1 , 4 , 9
4 , 7 , 2 , 9 , 5 , 1 , 3 , 6 , 8
7 , 4 , 9 , 5 , 2 , 3 , 8 , 1 , 6
8 , 6 , 5 , 4 , 1 , 7 , 2 , 9 , 3
3 , 2 , 1 , 6 , 9 , 8 , 5 , 7 , 4

一応この実装では
9x9以上の数独にも対応してますが
16x16以上は時間がかかるので
試してませんwww

数独は色々な実装を考えることができ
解き方は1つでは無いかと思います。

もっと効率の良い
実装をすれば16x16の数独なども
素早く解けるのでは無いかと思います。

こういったパズルゲームを
解くのは面白いですよね

今日はコレまでです
それでは。

このページのトップヘ