本履歴

購入した古本の履歴と時々プログラミング

数学パズル本に敢てプログラムで挑戦(8)

マーチン・ガードナーサム・ロイド本の続き

69. The Canals on Mars

火星で発見された水路を通って各町を必ず一回回ってスタート地点に戻ってくる問題。火星の半球面全体に水路を張るのはすごい技術というか無駄な気がするけど、まあプログラム的にはハミルトン閉路を求めるものですね。各都市には文字が振られていて、正解路は何か意味を持つとのこと。これはチェックが大変だと思ったら、正解は実質一通りしかなかった。

通常ハミルトンがあるかは解けないですが、今回は辺の数が少ないので幅優先で探索したらさくっと解答が出ました。いつもこのくらいだと嬉しいんですが。実行時間がコーディング時間より長くなると悲しいよね。まあ、グラフの構造を入力するのが一番大変かな。 くだらないのが、本によると多くの読者(数千人)が”THERE IS NO POSSIBLE WAY”(そんな道存在しないよ)と言ってきたとのこと。ナンジャと思ったらそれが正解メッセージでしたとさ。本当にくだらない。

cities="THYAWNREIOIELPESSBOS".chars.to_a
edges=[
    [1,2],
    [0,5,9,10,11],
    [0,3,4,8,17],
    [2,4],
    [2,3,7,12,14],
    [1,9,13,16,18,19],
    [10,11,14],
    [4,10,12],
    [2,15,17],
    [1,5,13],
    [1,6,7,11,14,16],#10
    [1,6,10],
    [4,7,17],
    [5,9,18],
    [4,6,10],
    [8,17,19],
    [5,10,17],
    [2,8,12,15,16,19],
    [5,13,19],
    [5,15,17,18]
]

n=cities.size
ans=[]
s=s_bit=0
q=[]
init_state=[[s],s_bit]
q.push init_state
g_bit=(?1*n).to_i(2)

until q.empty?
    state=q.shift
    seq,bit=state
    u=seq.last
    if bit==g_bit
        ans << seq if u==s #hamiltonian cycle path
        next
    end
    edges[u].each{|v|
        if bit[v]==0
            next_state=[seq.dup << v, bit+(1<<v)]
            q.push next_state
        end
    }
end

puts ans.size
ans.each{|seq|puts seq[0..-2].map{|i|cities[i]}.join} #=> THEREISNOPOSSIBLEWAY

f:id:uru:20170430162424j:plain