15パズルとMathematica

(1)

Ᏹ㒔ᐑ኱Ꮫᩍ⫱Ꮫ㒊 ᩍ⫱ᐇ㊶⥲ྜࢭࣥࢱ࣮⣖せ ➨ ྕ ᖺ ᭶ ᪥

㻝㻡䝟䝈䝹䛸㻹㼍㼠㼔㼑㼙㼍㼠㼕㼏㼍

䈂 బ⸨ ⚞ᏹ _{࣭㛗⦖ ┤ᓫ} Ᏹ㒔ᐑ኱Ꮫᩍ⫱Ꮫ㒊 ྡྂᒇ኱Ꮫ⌮Ꮫ◊✲⛉ ᴫせ ࣃࢬࣝࡢ᏶ᡂྍ⬟ᛶࡢุᐃ࠾ࡼࡧゎࢆồࡵࡿᡭ⥆ࡁࢆᩘᘧฎ⌮ࢯࣇࢺ 0DWKHPDWLFD ࢆ⏝࠸࡚グ㏙ࡋࡓࠋ ࣃࢬࣝࢆ⨨᥮⩌࡜ࡋ࡚ゎ㔘ࡋࣉࣟࢢ࣒ࣛࡢືసࢆ♧ࡍࡇ࡜ࡣࠊᏛ⏕࡟࡜ࡗ࡚㔞ᏊຊᏛ࡟࠾ࡅࡿ⩌ㄽࡢ┤ឤⓗ ⌮ゎ࡟኱࠸࡟ᙺ࡟❧ࡘࡶࡢ࡜⪃࠼ࡿࠋ ࣮࣮࢟࣡ࢻ ᩘ⌮ࣔࢹࣝࠊᩍᮦ㛤Ⓨࠊ᝟ሗฎ⌮ᩍ⫱ࠊ ࣃࢬࣝࠊ⨨᥮ࠊᩘᘧฎ⌮ 㸯㸬ࡣࡌࡵ࡟ ࣃࢬࣝࡣ࠿ࡽ ࡢ␒ྕࡢ௜࠸ࡓ ಶࡢࢱ ࢖ࣝࢆ[ࡢ᱁Ꮚ࡟ᩜࡁワࡵࡓࡶࡢ࡛ ಶࡢ࣐ ࢫ┠ࡀ✵࠸࡚࠸ࡿࠋ✵࠸ࡓ࣐ࢫ┠ࣈࣛࣥࢡࢆ฼⏝ ࡋ࡚ࢱ࢖ࣝࢆࢫࣛ࢖ࢻࡉࡏࠊ௵ពࡢ㓄⨨࠿ࡽฟⓎࡋ ࡚ᅗ D࡟♧ࡍ᏶ᡂᙧࡢ㓄⨨࡟ᥞ࠼ࡿࢤ࣮࣒࡛࠶ࡿࠋ ᅗ Eࡣ࡜ ࢆ஺᥮ࡋࡓࠕ ࣃࢬࣝࠖ࡜࿧ ࡤࢀࠊᅗ Dࡢ㓄⨨࡟┤ࡍࡇ࡜ࡀ࡛ࡁ࡞࠸ࠋṔྐⓗ ࡟ࡣࢧ࣒࣭ࣟ࢖ࢻࡀࡇࡢࠕ୙ྍ⬟ࣃࢬࣝࠖ ࡢ≉チࢆ⏦ㄳࡋࡓࡇ࡜࡛᭷ྡ࡟࡞ࡗࡓࠋ ࣃࢬࣝ࡟㛵ࡋ࡚ᩘᏛㄽᩥࡀⓎ⾲ࡉࢀ࡚࠸ࡿࠋ>@ ᩘᏛⓗゎㄝࡣḟ࡟ヲࡋ࠸ࠋ ࠕ⩌ㄽࡢ࿡ࢃ࠸ࠖ>@ ࠕ:ROIUDP0DWK:RUOG3X]]OHࠖ>@ ๓⪅ࡣᩘᏛࡢᢳ㇟ᴫᛕࡢ⌮ゎࢆຓࡅࡿࡓࡵ࡟ࠊィ ⟬ᶵ௦ᩘࢯࣇࢺ࢙࢘࢔6$*(ࢆ⏝࠸ࡓᩍᮦࡀྲྀࡾධ ࢀࡽࢀ࡚࠸ࡿࠋᚋ⪅ࡣ࢙࢘ࣈࡢᩘᏛ㎡඾࡛࠶ࡾࠊᩘ ᘧฎ⌮ࢯࣇࢺ࢙࢘࢔0DWKHPDWLFDࡢ౛㢟ࡀ♧ࡉࢀ ࡚࠸ࡿࠋࡇࢀࡽ࡟࡞ࡽࡗ࡚⨨᥮ࡸ⨨᥮⩌ࡢ⌮ゎࢆ῝ ࡵࡿࡓࡵ0DWKHPDWLFDࢆ౑ࡗ࡚ᐇ㦂ࢆ⾜ࡗࡓࠋ ࣃࢬࣝ࡜⨨᥮ࢆ 0DWKHPDWLFD ࢆ౑ࡗ࡚⾲⌧ࡋࡓᚋࠊ ࣃࢬࣝࡢ᏶ᡂྍ⬟ᛶࡢุᐃ᪉ἲ࡜ࣃࢬࣝࢆゎࡃࣉࣟ ࢢ࣒ࣛ࡟ࡘ࠸࡚㏙࡭ࡿࠋ௨ୗ࡛ࡣ 0DWKHPDWLFDࡢ㛵 ᩘࢆ᫂☜࡟ࡍࡿࡓࡵ࡟ᮏᩥ࡜␗࡞ࡿᏐయࢆ౑࠺ࡇ࡜ ࡟ࡍࡿࠋ

͊Yoshihiro Sato㸨_{, Naotaka Naganawa}㸨㸨_: 15 Puzzle and Mathematica

_{Faculty of Education, Utsunomiya University} _{Graduate School of Science, Nagoya University}

ᅗ D᏶ᡂᙧࡢ㓄⨨ ᅗ Eࠕ ࣃࢬࣝࠖ 㸰㸬0DWKHPDWLFD࡟ࡼࡿ ࣃࢬࣝࡢ㓄⨨ࡢ⾲⌧ 0DWKHPDWLFDࡣᩘᘧฎ⌮ࡀ࡛ࡁࡿ࢖ࣥࢱ࣮ࣉࣜࢱ ᆺࡢࢯࣇࢺ࢙࢘࢔࡛࠶ࡿࠋ⡆༢࡞ὀពⅬࢆ♧ࡍࠋ ࣭⤌ࡳ㎸ࡳ㛵ᩘࡢ㛵ᩘྡࡣ኱ᩥᏐ࡛ࡣࡌࡲࡾᘬᩘࢆ ♧ࡍࡓࡵ࡟ゅᣓᘼࢆ౑⏝ࡍࡿࠋ ࣭࣮ࣘࢨ࣮ࡀᐃ⩏ࡍࡿ㛵ᩘྡࡣ⤌ࡳ㎸ࡳ㛵ᩘ࡜༊ู ࡍࡿࡓࡵᑠᩥᏐ࡛ࡣࡌࡵࡿࠋ ࣭ࢹ࣮ࢱࡣࣜࢫࢺ࡛⾲⌧ࡉࢀࡿࠋせ⣲ࡢ㞟ࡲࡾࢆἼ ᣓᘼ࡛ᣓࡗ࡚ࣜࢫࢺ࡜ࡍࡿࠋ ࣭࣋ࢡࢺࣝࢆࣜࢫࢺ࡛ࠊ⾜ิࢆࣜࢫࢺࡢࣜࢫࢺ࡛⾲ ⌧ࡍࡿࠋ 0DWKHPDWLFD ࡛ࡣ ࣃࢬࣝࡢ㓄⨨ࢆ⾜ิ࡛⾲ࡍࡇ ࡜ࡀ࡛ࡁࡿࠋᅗ Dࡢ᏶ᡂᙧࡢ㓄⨨ࡣ௨ୗ࡟࡞ࡿࠋ ⤌ࡳ㎸ࡳ㛵ᩘ _Rangeࢆ౑ࡗ࡚ࣜࢫࢺࢆసࡿࠋ list0 = Range[16] э{1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16} ࣜࢫࢺࡢせ⣲ࢆ ಶࡎࡘࡲ࡜ࡵ࡚⾜ิࢆ⾲⌧ࡍࡿࠋ m0 = Partition[list0,4] э{{1,2,3,4},{5,6,7,8},{9,10,11,12}, {13,14,15,16}} 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 1 2 3 4 5 6 7 8 9 10 11 12 13 15 14 宇都宮大学教育学部　教育実践総合センター紀要　第35号　2012年 7 月 1 日 † Yoshihiro Sato*, Naotaka Naganawa**: 15 Puzzle and Mathematica * Faculty of Education, Utsunomiya University ** Graduate School of Science, Nagoya University

15 パズルと Mathematica

†

佐藤　禎宏

＊

_{・長縄　直崇}

＊＊

宇都宮大学教育学部

＊　

名古屋大学理学研究科

＊＊

(2)

ࢆ✵ⓑ࡛⨨ࡁ᥮࠼࡚ࣃࢬࣝࡢ㓄⨨ࢆ⾲⌧ࡍࡿࠋ MatrixForm[ mat0 = m0 /. {16 -> " "} ] 㸱㸬 ࣃࢬࣝ࡜⨨᥮ ✵࠸ࡓ࣐ࢫ┠࡟⾲グୖ ࡜␒ྕࢆ௜ࡅࡿࡇ࡜࡟ ࡼࡾࠊ ࣃࢬࣝࡢ㓄⨨ࢆ㞟ྜ^`ࡢ ⨨᥮࡛⾲⌧ࡍࡿࡇ࡜ࡀ࡛ࡁࡿࠋ0DWKHPDWLFD࡟ ࡣ⨨᥮ࢆ⾲⌧ࡍࡿ⾲グ࡜ࡋ࡚ࠕ⨨᥮ࡢࣜࢫࢺࠖ⾲グ࡜ࠕᕠᅇ⨨᥮ࠖ⾲グࡀ࠶ࡿࠋᅗ ࡢ㓄⨨ࢆ⾜ิ ࡛⾲⌧ࡋࡑࡢᵓ㐀ࢆᾘࡋ࡚సࡗࡓࣜࢫࢺࡣࠕ⨨᥮ ࡢࣜࢫࢺࠖ࡟࡞ࡗ࡚࠸ࡿࠋ ᅗ 㓄⨨ࡢ౛ 㻌 ᅗ 㻞㻌䛾㓄⨨䜢⾜ิ䛷⾲⌧䛧䝸䝇䝖䜢స䜛䚹㻌 MatrixForm[ m2 = {{1,2,3,4},{5,6,7,8},{9,10,11,16}, {13,14,15,12}}]㻌㻌㻌㻌 list2 = Flatten[m2] э{1,2,3,4,5,6,7,8,9,10,11,16,13,14,15,12} 㻌㛵ᩘ㻌_{PermutationCycles}㻌䜢౑䛖䛣䛸䛻䜘䜚䛂⨨᥮ 䛾䝸䝇䝖䛃䛛䜙䛂ᕠᅇ⨨᥮䛃䜢ồ䜑䜛䛣䛸䛜䛷䛝䜛䚹⤖ᯝ 䛿㻝㻞㻌䛸㻝㻢㻌䛸䛾ᕠᅇ⨨᥮䛻䛺䜛䚹ᕠᅇ⨨᥮䛾⾲グ䛻䛿㻌Cycles㻌䛜᫂♧䛥䜜䜛䚹㻌 cycles = PermutationCycles[list2] эCycles[{{12,16}}] 㻌䛂⨨᥮䛾䝸䝇䝖䛃䛻ᑐ䛧䛶⨨᥮䛾₇⟬䜢⾜䛖㛵ᩘ䛿 PermutationReplace䛷䛒䜛䚹㻌 ồ䜑䛯_cycles䜢᏶ᡂ ᙧ䛾䛂⨨᥮䛾䝸䝇䝖䛃䛻₇⟬䛥䛫䛯⤖ᯝ䛿 list2䛻䛺䜛䛣䛸䜢☜ㄆ䛩䜛䚹ᅗ 㻞㻌䛾㓄⨨䛿௨ୗ䛷䛒䜛䚹㻌 PermutationReplace[Range[16],cycles] 㻌㻌㻌㻌㻌䋻{1,2,3,4,5,6,7,8,9,10,11,16,13,14,15,12}㻌 list2 == PermutationReplace[Range[16], 㻌㻌㻌㻌㻌㻌㻌㻌_cycles] эTrue 㻌㻌 ㄽ⌮ⓗ䛻┿䛺䛾䛷➼䛧䛔䚹㻌㻌㸲㸬᏶ᡂྍ⬟ᛶࡢุᐃ᪉ἲ 㻌㻭㻚㻲㻚㻭㼞㼏㼔㼑㼞㻌 ࡢㄽᩥ㼇㻝㼉㻌 ࡟᭩࠸࡚࠶ࡿุᐃἲ࡟ࡘ࠸ ࡚㏙࡭ࡿࠋ㓄⨨ࢆ௨ୗ࡟㏙࡭ࡿࠕ㓄఩ࠖ㻌㻔㻯㼛㼚㼒㼕㼓㼡㼞㼍㼠㼕㼛㼚㻕 ࡟ኚ᥮ࡍࡿࡇ࡜࡟ࡼࡾࠊࣈࣛࣥࢡࢆື࠿ࡍࡇ࡜ࡣ㓄 ఩ࡢ⨨᥮࡟ᑐᛂࡍࡿࠋࡇࡢ⨨᥮ࢆ⏕ᡂඖ࡜ࡍࡿ⨨᥮ ⩌ࡣ 㻝㻡 ḟࡢ஺௦⩌㻌㻭㻝㻡㻌 ࡟࡞ࡿࠋᚑࡗ࡚᏶ᡂ㓄⨨ࡢ 㓄఩࠿ࡽ㛤ጞࡢ㓄఩࡬ࡢ⨨᥮ࡀഅ⨨᥮࡞ࡽࡤ᏶ᡂྍ ⬟࡜ุᐃ࡛ࡁࡿࠋ㻌㻌 ᅗ 㻟㻌 ◚⥺࡜ᩘᏐࡣࢭࣝࡢ㡰ᗎࢆ♧ࡍࠋࡇࢀ࡛ࠕ㓄఩ࠖ ࢆᐃ⩏ࡍࡿࠋ㻌㻌㻔㻝㻕㻌㓄఩㻌㻔㻯㼛㼚㼒㼕㼓㼡㼞㼍㼠㼕㼛㼚㻕㻌㻌㻠㻌㼤㻌㻠㻌 ࡢࡦ࡜ࡘࡢ࣐ࢫ┠ࢆࢭࣝ࡜࿧ࡧࠊᅗ 㻟 ࡟♧ࡍ ࡼ࠺࡟ࢭࣝ࡟⺬≧ࡢ㡰ᗎ࡛␒ྕࢆࡘࡅࡿࠋࢭࣝࡢ␒ ྕ㡰࡟୪ࢇࡔ㐨➽࡟ࣈࣛࣥࢡࢆື࠿ࡍሙྜ࡟ࡣࠊࢱ ࢖ࣝࡢࢭࣝࡢ␒ྕࡢ㡰ᗎࡣኚࢃࡽ࡞࠸ࠋᚑࡗ࡚⺬≧ ࡢ㡰ᗎ࡟ࣈࣛࣥࢡࢆ⛣ືࡋࡓ࡜ࡁ࡟ᚓࡽࢀࡿ㓄⨨ࡣ ྠ್㛵ಀ࡟࠶ࡿࠋࡇࡢྠ್㢮ࢆࠕ㓄఩ࠖ࡜࿧ࡧࠊ㻝㻢 ✀㢮ࡢ㓄⨨ࢆྵࢇ࡛࠸ࡿࠋ㻌㻌㻌 ࣈࣛࣥࢡࡢ఩⨨࡟㛵㐃ࡋࠊ௨ୗࡢ஧ࡘࡢつ๎࡟ᚑ ࡗ࡚ࢭࣝ␒ྕ࠿ࡽࠕࢫࣟࢵࢺ␒ྕࠖࢆᐃ⩏ࡍࡿࠋ㻔㻝㸧 ࢱ࢖ࣝࡢࢭࣝ␒ྕࡀࣈࣛࣥࢡࡢࢭࣝ␒ྕࡼࡾᑠࡉ࠸ ሙྜ࡟ࡣࠊࡑࡢࢭࣝ␒ྕࢆࢫࣟࢵࢺ␒ྕ࡜ࡍࡿࠋ㻔㻞㻕 ࡑࡢ௚ࡢሙྜ࡟ࡣࢭࣝ␒ྕ࠿ࡽ㸯ࢆᘬ࠸ࡓࡶࡢࢆࢫ ࣟࢵࢺ␒ྕ࡜ࡍࡿࠋ㻌 ␒ྕ㻌㼕㻌 ࡢࢱ࢖ࣝࡢࢫࣟࢵࢺ␒ ྕࢆ㻌㼍㻌㼕㻌 ࡜ࡋ࡚㓄఩ࢆ㻌㼇㼍㻌㻝㻘㻌㻚㻚㻚㻌㻘㻌㼍㻝㻡㼉㻌 ࡜⾲グࡍࡿࠋ㻌㻌 ࣈࣛࣥࢡࢆື࠿ࡍࡇ࡜ࡣࢱ࢖ࣝࡢࢫࣟࢵࢺ␒ྕࢆ ኚ໬ࡉࡏࡿࡇ࡜࡟ᑐᛂࡍࡿࠋࡓ࡜࠼ࡤᅗ 㻠㼎 ࡢሙྜࠊ ࢭࣝ 㻝㻜 ࡟࠶ࡿࣈࣛࣥࢡࢆࢭࣝ 㻝㻡 ࡟⛣ືࡍࡿ࡜ࠊࢭ ࣝ 㻝㻡㻌㻔ࢫࣟࢵࢺ 㻝㻠㻕࡟࠶ࡗࡓࢱ࢖ࣝࡣࢭࣝ 㻝㻜㻔ࢫࣟࢵ ࢺ 㻝㻜㻕ࡢ఩⨨࡟࡞ࡿࠋࡲࡓࠊ㻝㻝 ␒࠿ࡽ 㻝㻠 ␒ࡢࢭࣝ࡟ ࠶ࡗࡓࢱ࢖ࣝࡢࢫࣟࢵࢺ␒ྕࡣࡑࢀࡒࢀ㸯ࡔࡅቑ࠼ 1 2 3 4 5 6 7 8 9 10 11 13 14 15 12 1 2 3 4 8 7 6 5 9 10 11 12 16 15 14 13

(3)

ࡿࠋࡋࡓࡀࡗ࡚ࢭࣝ 㻝㻜 ࡟࠶ࡿࣈࣛࣥࢡࢆࢭࣝ 㻝㻡 ࡟ ⛣ືࡍࡿࡇ࡜ࡣ㓄఩ࡢ⨨᥮㻌ı= (10,11,12,13,14) 㻌 ࡟ᑐᛂࡍࡿࠋ㻌㻌㻌㻌㻌㻌㻌㻌㻌㻌㻌 ᅗ 㻠㼍㻌㻌㻌㻌㻌㻌㻌㻌 ᅗ 㻠㼎㻌 ᅗ 㻠㼍㻌 ࡣ᏶ᡂᙧࡢ㓄⨨࡛࠶ࡾࠊ㓄఩ࡣ㻌㻵㻌㻩㻌㼇㻝㻘㻞㻘㻟㻘㻠㻘㻤㻘㻣㻘㻢㻘㻡㻘㻥㻘㻝㻜㻘㻝㻝㻘㻝㻞㻘㻝㻡㻘㻝㻠㻘㻝㻟㼉㻌 ࡟࡞ࡿࠋ㻌 ᅗ 㻠㼎㻌 ࡢ㓄఩ࡣ㻌㻌㻯㻌㻩㻌㼇㻝㻘㻞㻘㻟㻘㻠㻘㻤㻘㻣㻘㻢㻘㻡㻘㻝㻠㻘㻝㻞㻘㻌㻝㻟㻘㻝㻜㻘㻝㻡㻘㻝㻝㻘㻥㼉㻌 ࡛࠶ࡿࠋ㻌㻌 ᅗ 㻠 ࡢ㓄⨨࡟ࡘ࠸࡚☜ㄆࢆ⾜࠺ࠋ⾜ิࡢ఩⨨࡜ࢭࣝ ␒ྕࡢᑐᛂつ๎ࢆ⏝࠸࡚㓄⨨࠿ࡽ㓄఩࡟ኚ᥮ࡍࡿ㛵 ᩘ㻌_pl2Cf㻌 ࢆసࡿࠋ㻔㻌㻭㼜㼜㼑㼚㼐㼕㼤㻌㻝㻔㻝㻕㻌㻕㻌㻌 ࡇࢀࢆ౑ࡗ࡚ ᅗ 㻠㼍㻌 ࡢ㓄఩ࢆồࡵࡿࠋ㻌 (placement0 = Partition[Range[16], 4] /. {16 -> " "}) // MatrixForm 㻌 initialCf = pl2Cf[placement0] э{1,2,3,4,8,7,6,5,9,10,11,12,15,14,13} 㻌 ᅗ 㻠㹠㻌 ࡢ㓄఩ࢆồࡵࡿࠋ㻌 (placement1={{1,2,3,4},{5,6,7,8}, {15," ",12,14},{13,9,11,10}}) // MatrixForm 㻌 startCf = pl2Cf[placement1] э_{{1,2,3,4,8,7,6,5,14,12,13,10,15,11,9}} 㻌㻔㻞㻕㻌㓄఩ࡢ⨨᥮࡜അወᛶ㻌 ⨨᥮ࢆồࡵࡿ㛵ᩘfindPermutationReplaceࢆᐃ ⩏ࡋࠊồࡵࡓᕠᅇ⨨᥮ࡢഅወࢆุᐃࡍࡿ㛵ᩘ㻌 permutationSignatureࢆ 㻭㼜㼜㼑㼚㼐㼕㼤㻌㻝㻔㻞㻕㻌 ࡟♧ࡍࠋ ࡇ ࢀ ࢆ ౑ ࡗ ࡚ ᏶ ᡂྍ ⬟ ᛶࢆ ㄪ ࡭ ࡿ ࠋ ඛ ࡟ồ ࡵ ࡓ initialCf࡜_startCfࡢ㓄఩ࢆ౑ࡗ࡚ᕠᅇ⨨᥮ࢆồ ࡵࡿࠋ㻌 cycles1 = findPermutationReplace[initialCf, startCf] эCycles[{{9,14,11,13},{10,12}}] ᕠᅇ⨨᥮ࡢഅወࢆㄪ࡭ࡿࠋ㻌 permutationSignature[cycles1] э㻝㻌 അወᛶࢆㄪ࡭ࡓ⤖ᯝࡣ 㻝 ࡞ࡢ࡛അ⨨᥮࡛࠶ࡿࠋࡋࡓ ࡀࡗ࡚ࠊ᏶ᡂྍ⬟࡛࠶ࡿࠋ㻌㻌 ࠕ㻝㻠㻙㻝㻡 ࣃࢬࣝࠖࡢ㓄⨨㻔ᅗ 㻝㼎㻕㻌 ࡟ࡘ࠸࡚ㄪ࡭ࡿࠋࡇ ࢀࡣ᏶ᡂ㓄⨨ࡢ 㻝㻠㻌 ࡜ 㻝㻡㻌 ࢆ⨨᥮ࡋࡓ㓄⨨࡛࠶ࡿࠋ㻌 placement2 = {{1,2,3,4},{5,6,7,8}, {9,10,11,12},{13,15,14," "}};㻌 startCf2 = pl2Cf[placement2] э_{{1,2,3,4,8,7,6,5,9,10,11,12,15,13,14}} cycles2 = findPermutationReplace[initialCf, startCf2] эCycles[{{13,14}}] permutationSignature[cycles2] э㻙㻝㻌 ⤖ᯝࡣ㻌㻙㻝㻌 ࡞ࡢ࡛ወ⨨᥮࡛࠶ࡿࠋࡋࡓࡀࡗ࡚ࠊ᏶ᡂ ୙ྍ⬟࡛࠶ࡿࠋ㻌㻌⾜ิ࡛⾲ࡋࡓ㓄⨨ࢆᘬᩘ࡜ࡋ࡚౑࠼ࡿ᏶ᡂྍ⬟ᛶࢆ ุᐃࡍࡿ㛵ᩘ࡜ࡋ࡚㻌_parityQ㻌 ࢆ㻌㻭㼜㼜㼑㼚㼐㼕㼤㻌㻝㻔㻞㻕㻌 ࡟ ♧ࡍࠋ parityQ[placement0, placement2] э㻙㻝㻌㻌㻔㻟㻕㻌 ஺௦⩌࡟ࡘ࠸࡚㻌 ࢭࣝ 㼕㻌 ࠿ࡽࢭࣝ 㼖㻌 ࡟ࣈࣛࣥࢡࢆ⛣ືࡋ࡚ᚓࡽࢀࡿ ⨨᥮ࢆ㻌_ı_i,j㻌 ࡜⾲グࡍࡿ࡜ࠊ_ı_i,i+1, i = 1,..., 15㻌 ࡣ㓄఩ࢆኚ࠼࡞࠸⨨᥮࡛࠶ࡾࠊࡲࡓ_ı_j,i_ı_i,j-1㻌_࡛ ࠶ࡿࠋࡑࡢ௚࡟㻌㻥 ಶࡢ⨨᥮㻌_ı_1,8 _ı_2,7 _ı_3,6 _, ı5,12 , ı6,11ı7,10 ı9,16 ı10,15 ı11,14ࡀ࠶ ࡿࠋㄽᩥ㼇㻝㼉㻌 ࡟ࡣ 㻥 ಶࡢ⨨᥮ࡢᕠᅇ⨨᥮ࡀ᫂グࡉࢀ ࡚࠾ࡾࠊࡇࢀࡽࡢ⨨᥮ࢆ⏕ᡂඖ࡜ࡍࡿ⨨᥮⩌ࡣ 㻝㻡 ḟࡢ஺௦⩌ 㻭㻌㻝㻡࡟࡞ࡿࡇ࡜ࢆド᫂ࡋ࡚࠸ࡿࠋ㻌㻹㼍㼠㼔㼑㼙㼍㼠㼕㼏㼍㻌 ࡟ࡣ⏕ᡂඖ࠿ࡽ⨨᥮⩌ࢆసࡿ㛵ᩘ࡜ ࡋ࡚_{PermutationGroup} ࡀ࠶ࡾࠊ㻝㻡 ḟࡢ஺௦⩌ࢆ సࡿ㛵ᩘ࡜ࡋ࡚ _{AlternatingGroup[15]}㻌 ࡀ࠶ࡿࡢ ࡛ࡇࡢド᫂ࡢ☜ㄆࢆ⾜࠺ࠋ㻌 ࡣࡌࡵ࡟ࠊᅗ 㻠㼎 ࢆཧ⪃࡟ࡋ࡚ࢭࣝ 㻝㻜 ࡟࠶ࡿࣈࣛ ࣥࢡࢆࢭࣝ 㻝㻡 ࡟⛣ືࡍࡿࡇ࡜ࡣ㓄఩ࡢ⨨᥮㻌 ı10,15= (10,11,12,13,14) ࡟ᑐᛂࡍࡿࡇ࡜ࢆ☜࠿ 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 1 2 3 4 8 7 6 5 9 10 11 12 16 15 14 13 1 2 3 4 5 6 7 8 15 12 14 13 9 11 10 1 2 3 4 8 7 6 5 9 10 11 12 16 15 14 13

(4)

ࡵࡿࠋࣈࣛࣥࢡࡀࢭࣝ 㻝㻜 ࡟࠶ࡿ㓄఩ࡣ᪤࡟ồࡵࡓ㻌 startCf࡛࠶ࡿࠋࡲࡓࠊࢭࣝ 㻝㻡 ࡟ࣈࣛࣥࢡࢆ⛣ື ࡋࡓ㓄఩ࡣ௨ୗ࡟࡞ࡿࠋ㻌 pl2 = {{1,2,3,4},{5,6,7,8},{15,9,12,14}, {13, " ",11,10}}; cf2 = pl2Cf[pl2] э{1,2,3,4,8,7,6,5,10,13,14,11,15,12,9} ᚑࡗ࡚ࠊ ı10,15=findPermutationReplace[startCf, cf2] э_{Cycles[{{10,11,12,13,14}}]} ྠᵝ࡟ࡋ࡚ồࡵࡓ⤖ᯝࡣḟ࡟࡞ࡿࠋ㻌 ı1,8 = Cycles[{{1, 2, 3, 4, 5, 6, 7}}]; ı2,7 = Cycles[{{2, 3, 4, 5, 6}}]; ı3,6 = Cycles[{{3, 4, 5}}]; ı5,12= Cycles[{{5, 6, 7, 8, 9, 10, 11}}]; ı6,11 = Cycles[{{6, 7, 8, 9, 10}}]; ı7,10 = Cycles[{{7, 8, 9}}]; ı9,16 = Cycles[{{9, 10, 11, 12, 13, 14, 15}}]; ı11,14 = Cycles[{{11, 12, 13}}]; ⏕ᡂඖ࠿ࡽసࡗࡓ⩌ࡀ 㻝㻡 ḟࡢ஺௦⩌㻌㻭㻝㻡࡟࡞ࡿࡇ ࡜ࢆ௨ୗࡢࡼ࠺࡟☜ㄆ࡛ࡁࡿࠋ㻌 list = ^ı1,8ı2,7ı3,6, ı5,12 ı6,11, ı7,10, ı9,16 , ı10,15ı11,14}; PermutationGroup[list] == AlternatingGroup[15] эTrue 㻌 ࣃࢬࣝࡢつ๎࡟ᚑࡗࡓ㓄⨨ࡢᩘࡣ఩ᩘ 㻝㻡 ࡢ஺௦⩌㻌㻭㻝㻡㻌 ࡢඖ࡟ᑐᛂࡋ࡚ 㻝㻡㻍㻛㻞 ಶ࡛࠶ࡿࠋ⩌ࡢඖࡢᩘࢆ ồࡵࡿ㛵ᩘ㻌_GroupOrderࢆ౑ࡗ࡚☜ㄆ࡛ࡁࡿࠋ㻌 GroupOrder[AlternatingGroup[15]]== 15!/2 эTrue 㻌㸳㸬 ࣃࢬࣝࢆゎࡃࣉࣟࢢ࣒ࣛ 㻌㻤 ࣃࢬࣝࢆゎࡃ 㻹㼍㼠㼔㼑㼙㼍㼠㼕㼏㼍㻌 ࡢࣉࣟࢢ࣒ࣛࡀࠕᛂ⏝ 㻹㼍㼠㼔㼑㼙㼍㼠㼕㼏㼍ࠖ㼇㻡㼉㻌 ࡟㍕ࡗ࡚࠸ࡿࠋࡇࢀࡣ 㻝㻡 ࣃࢬࣝ࡟ ࡶ ౑ ࠺ ࡇ ࡜ ࡀ ࡛ ࡁࡿ ࠋ ࡇࡢ ࣉ ࣟ ࢢ ࣛ ࣒ ࡢ඲ య ࢆ㻌㻭㼜㼜㼑㼚㼐㼕㼤㻌㻞㻌 ࡟♧ࡍࠋ㻌 ࣃࢬࣝࢆゎࡃࡓࡵࡢ㐨ල࡜ࡋ࡚ḟࡢ㛵ᩘࢆసࡿᚲせ ࡀ࠶ࡿࠋࣉࣟࢢ࣒ࣛࡢ᰾ᚰࡣḟࡢ㡯┠ 㻟 ࡢᐇ⿦࡟࠶ ࡿࠋ㻌㻝㻚ࣈࣛࣥࢡࡢྍ⬟࡞⛣ືࢆồࡵࡿ㛵ᩘ㸸㻌_moves㻌㻞㻚ࣈࣛࣥࢡࡢ⛣ື࡟ࡼࡿ᪂ࡓ࡞㓄⨨ࢆసࡿ㛵ᩘ㸸㻌㻌㻌㻌㻌㻌㻌㻌㻌㻌㻌㻌㻌㻌㻌㻌㻌㻌㻌_effectmove㻌㻟㻚௵ពࡢ㓄⨨࠿ࡽ᏶ᡂᙧࡢ㓄⨨ࡲ࡛ࡢ㏆ࡉࢆ⾲ࡍ㔞㻌 ࢆồࡵࡿ㛵ᩘ㸸㻌_{manhattandistance}㻌㻠㻚⛣ືࡢ㐃㙐ࢆ᥈⣴ࡍࡿ㛵ᩘ㸸_iterate㻌㻌 ࣃࢬࣝࡢ᏶ᡂᙧࡢ㓄⨨㸦ᅗ 㻝㼍㸧ࢆḟࡢ⾜ิ࡛⾲⌧ࡍ ࡿࠋ㻌 (desired=Partition[Range[16]/.{16->" "},4]) // MatrixForm 㻌㻌㻔㻝㻕ࣈࣛࣥࢡࡢྍ⬟࡞⛣ືࢆồࡵࡿ㛵ᩘ㸸 _moves 㻔㻌㻭㼜㼜㼑㼚㼐㼕㼤㻌㻞㻔㻝㻕㻌㻕㻌 ࣈࣛࣥࢡࡀ 㻝 ิ࡟࠶ࡿ࡞ࡽࡤᕥ㻔_{Left㻕࡟⛣ື࡛ࡁ} ࡞࠸ࡋࠊ㻠 ิ࡞ࡽࡤྑ㻔_{Right㻕㻌 ࡟⛣ື࡛ࡁ࡞࠸ࠋྠ} ᵝ࡞つ๎࡟ࡋࡓࡀࡗ࡚௵ពࡢ఩⨨࡟࠶ࡿࣈࣛࣥࢡ࡟ チ ࡉ ࢀ ࡿ ⛣ ື ࢆ Ỵ ࡵ ࡿ 㛵 ᩘ ࡀ _{moves ࡛ ࠶ ࡿ}ࠋ㻌㻌 desired㻌 ࡢࣈࣛࣥࢡࡢྍ⬟࡞⛣ືࡣ㻌Up㻌 ࡜㻌Left㻌 ࡛࠶ࡿࠋ㻌 moves[desired] э{"Up", "Left"} 㻌㻔㻞㻕㻌 ࣈࣛࣥࢡࡢ⛣ື࡟ࡼࡿ᪂ࡓ࡞㓄⨨ࢆసࡿ㛵ᩘ㸸 effectmove 㻔㻌㻭㼜㼜㼑㼚㼐㼕㼤㻌㻞㻔㻞㻕㻌㻕㻌 ⛣ືLeft㻌 ౑ࡗ࡚᪂ࡓ࡞㓄⨨ࢆసࡿࠋ㻌

effectmove[desired, "Left"] // MatrixForm

㻌

⧞ࡾ㏉ࡋ⛣ືࡉࡏࡓᚋࡢ㓄⨨ࡣ௨ୗ࡟࡞ࡿࠋ㻌 (firstmove =

effectmove[desired, "Left", "Left", "Up", "Up"]) // MatrixForm 㻌㻌㻔㻟㻕㻌㏆ࡉࡢホ౯㛵ᩘ㸸࣐ࣥࣁࢵࢱࣥ㊥㞳ࢆồࡵࡿ㛵ᩘ㸸㻌 manhattandistance 㻔㻌㻭㼜㼜㼑㼚㼐㼕㼤㻌㻞㻔㻟㻕㻌㻕㻌 ⌧ᅾࡢ㓄⨨࠿ࡽ᏶ᡂᙧࡢ㓄⨨ࡲ࡛ࡢ㏆ࡉࢆ⾲ࡍ㔞 ࡜ࡋ࡚࣐ࣥࣁࢵࢱࣥ㊥㞳ࢆ౑⏝ࡍࡿࠋ㓄⨨_desired ࡛ࡣࠊࢱ࢖ࣝ 㻢 ࡣ㻌㻞⾜㻞 ิࡢ఩⨨࡟࠶ࡾࠊ_firstmove

(5)

ࡢ㓄⨨࡛ࡣ 㻟⾜㻞 ิ࡟࠶ࡿࠋࡑࡢ⾜ࡢᕪࡢ⤯ᑐ್࡜ ิࡢᕪࡢ⤯ᑐ್ࡢ࿴ࢆ࡜ࡾ㻌㻝㻌 ࡜࡞ࡿࠋ㻌㻝 ࠿ࡽ 㻝㻡㻌 ࡢࢱ࢖ࣝ࡜ࣈࣛࣥࢡࡢࡑࢀࡒࢀ࡟ࡘ࠸ ࡚ồࡵࡓ್ࢆຍ࠼ࡓࡶࡢࡀ࣐ࣥࣁࢵࢱࣥ㊥㞳࡟࡞ࡿࠋ㻌 ࡋࡓࡀࡗ࡚ィ⟬⤖ᯝࡣ 㻤㻌 ࡜࡞ࡿࠋ㻌 manhattandistance[desired, firstmove] э㻤㻌㻌㻔㻠㻕㻌 ⛣ືࡢ㐃㙐ࢆ᥈⣴ࡍࡿᮌࡢ⏕ᡂ㻌 ᭱ึࡢ㓄⨨ࢆ㻌P0㻌 ࡜ࡍࡿࠋ㛵ᩘ _moves ࢆ౑ࡗ࡚ ྍ⬟࡞ࣈࣛࣥࢡࡢ⛣ື㻌 m1, m2㻌 ࢆ᥈ࡍࡇ࡜ࡀ࡛ࡁ ࡿࠋࡑࢀࡒࢀࡢ⛣ື㻌 ࡟ࡼࡗ࡚సࡽࢀࡿ㓄⨨㻌_{P1, P2}㻌 ࡣ㛵ᩘ effectmove㻌 ࡟ࡼࡗ࡚ồࡵࡿࡇ࡜ࡀ࡛ࡁࡿࠋ P0㻌 ࢆᮌࡢ࣮ࣝࢺ࡜ࡋࠊ⛣ື㻌m1, m2 ࢆᯞ࡜ࡋࠊ᪂ ࡓ࡟సࡽࢀࡓ㓄⨨ࢆࣀ࣮ࢻ࡜ࡍࡿᮌࡢᵓ㐀ࢆᅗ 㻢 ࡟ ♧ࡍࠋ⟅࠼ࢆぢࡘࡅࡿ࡟ࡣࡇࢀࡽࡢࣀ࣮ࢻࡀ᏶ᡂᙧ ࡢ㓄⨨࡜ྠࡌ࠿ࠊ࡝ࢀࡔࡅ㏆࠸࠿ࢆㄪ࡭ࡿᚲせࡀ࠶ ࡿࠋࡇࢀࢆホ౯ࡍࡿ㛵ᩘࡀ࣐ࣥࣁࢵࢱࣥ㊥㞳࡛࠶ࡿࠋ ࡇࡇ࡛ࡑࢀࡒࢀࡢ⛣ື࡟࣐ࣥࣁࢵࢱࣥ㊥㞳ࢆྵࡵࡓ ࣜࢫࢺࢆసࡿ㛵ᩘ࡜ࡋ࡚listscores ࢆᐃ⩏ࡍࡿࠋ㻌㻔㻌㻭㼜㼜㼑㼚㼐㼕㼤㻌㻞㻔㻠㻕㻌㻕㻌㻌㻌㻌 ᅗ 㻢㻌㻌 ⛣ືࡢ㐃㙐ࢆ᥈⣴ࡍࡿᮌ㻌㻌㻌㓄⨨㻌P1, P2㻌 ࡟⟅࠼ࡀ࠶ࢀࡤ᏶஢࡟࡞ࡿࠋ⟅࠼ࡀ ࡞࠿ࡗࡓሙྜࠊࡑࢀࡒࢀࡢ㓄⨨ࡘ࠸࡚⛣ືࢆ⧞ࡾ㏉ ࡍࡇ࡜࡟ࡼࡗ࡚⟅࠼ࢆぢࡘࡅࡿࡇ࡜ࡀྍ⬟࡛࠶ࡿࠋ ࡋ࠿ࡋ࡞ࡀࡽグ㘓ᐜ㔞ࡢไ㝈࠿ࡽᅔ㞴ࡀ⏕ࡌࡿࠋゎ Ỵ᪉ἲࡢ㸯ࡘ࡜ࡋ࡚ࠊ࣐ࣥࣁࢵࢱࣥ㊥㞳ࡀ᭱ࡶᑠࡉ ࠸ࣀ࣮ࢻ࡟ࡘ࠸࡚ඃඛⓗ࡟⛣ືࡢ᥈⣴ࢆ⧞ࡾ㏉ࡍ᪉ ἲࢆ᥇⏝ࡍࡿࠋ㊥㞳ࡀ➼ࡋ࠸࡜ࡁࡣࡑࡢ୰࠿ࡽࣛࣥ ࢲ࣒࡟㑅ࡧฟࡍࡇ࡜࡟ࡍࡿࠋ㻌 ᅗ 㻢㻌 ࡟♧ࡍP0 ࠿ࡽP1࡜P2 ࡬ࡢ⛣ື㻌m1࡜m2㻌 ࡣ㛵ᩘ _{listscores[P0]}㻌 ࢆ౑ࡗ࡚࣐ࣥࣁࢵࢱࣥ㊥㞳 ࢆ ྵ ࡵ ࡓ ᙧ ࡛ ồ ࡵ ࡿ ࡇ ࡜ ࡀ ࡛ ࡁ ࡿ ࠋ ࡇ ࢀ ࢆ㻌 firstmoves ={{a,m1},{b,m2}}㻌 ࡜ࡍࡿࠋἼᣓᘼࡣ ࣜࢫࢺࢆ⾲ࡋࠊ࣐ࣥࣁࢵࢱࣥ㊥㞳㻌a㻌 ࡜ b㻌 ࡣ㻌a < b㻌 ࡢ㛵ಀ࡟࠶ࡿࡶࡢ࡜ࡍࡿࠋᅗ࡛ࡣ㊥㞳ࡀᑠࡉ࠸㡰࡟ ᕥ࠿ࡽྑ࡟ᥥ࠸࡚࠸ࡿࠋ㻌 firstmoves㻌 ࢆධຊ࡜ࡋ࡚㻌P11࡜P12㻌 ࡬ࡢ⛣ືࢆ ồࡵࡿ㛵ᩘ㻌_{iterate[P0,firstmoves]} ࡣ㻌 secondmoves={{c,m1,m11},{d,m1,m12},{b,m2}}, c < d < b ࢆฟຊࡍࡿࠋ᭦࡟ secondmoves㻌 ࢆධຊ ࡜ ࡋ࡚ 㻌P111㻌 ࡜ P112㻌 ࡬ ࡢ⛣ື thirdmoves ࢆ iterate[P0,secondmoves]㻌 ࡛సࡿࡇ࡜ࡀ࡛ࡁࡿࠋ ࡇࢀࢆ⧞ࡾ㏉ࡋ࡚⟅ࢆぢࡘࡅࡿࡇ࡜ࡀྍ⬟࡜࡞ࡿࠋ㻌㻌 ࡇࡢ᥈⣴࡟࠾࠸࡚↓ព࿡࡞⛣ືࠊࡍ࡞ࢃࡕྑ࡟⛣ ືࡋࡓᚋᕥ࡟⛣ືࡍࡿࡇ࡜ࡸࠊୖ࡟⛣ືࡋࡓᚋ࡟ୗ ࡬ࡢ⛣ືࢆྲྀࡾ㝖ࡃࡓࡵ_worthwhile㻌㛵ᩘࢆ౑ࡗ࡚ ࠸ࡿࠋࡲࡓࠊ࣐ࣥࣁࢵࢱࣥ㊥㞳ࡀᑠࡉ࠸⛣ືࢆඃඛ ࡋ࡚᥈⣴ࡍࡿࡀࠊ⛣ືิࡢ᥈⣴ࢆㄪᩚࡍࡿࡓࡵࡢ㛵 ᩘ _bestscore㻌 ࡶ౑ࡗ࡚࠸ࡿࠋ㻔㻌㻭㼜㼜㼑㼚㼐㼕㼤㻌㻞㻔㻠㻕㻌㻕㻌 ᭱⤊ⓗ࡟⛣ືࡢ᥈⣴ࢆ⧞ࡾ㏉ࡋ࡚⟅ࢆぢࡘࡅࡿ㛵 ᩘࡀ㻌try㻌 ࡛࠶ࡿࠋ☜ㄆࡢࡓࡵᐇ⾜⤖ᯝࢆ♧ࡍࠋ㻌 start = effectmove[desired, "Left", "Up",

"Left"]; result = try[start, 10]

The following solution was found э{0, "Right", "Down", "Right"}㻌

࣐ࣥࣁࢵࢱࣥ㊥㞳ࡀ㻌㻜㻌 ࡢ⛣ືࡢᡭ㡰ࡀồࡵࡽࡓࠋ㻌 ☜ㄆࡢࡓࡵ㓄⨨ࢆ⾲♧ࡍࡿࠋᡭ㡰࡟ᚑࡗࡓࣈࣛࣥࢡ ࡢ⛣ືࡢᵝᏊࡀぢ࡚ྲྀࢀࡿࠋ㻌

puzseq = FoldList[effectmove[#1, #2] &, start, Rest[result]]; viewlolol[puzseq]㻌㻌㻌 ࣉࣟࢢ࣒ࣛࡢ᳨ウ㻝㻡 ࣃࢬࣝࡢ௵ពࡢ㓄⨨ࡣࡘࡂࡢࡼ࠺࡟஘ᩘࢆ౑ࡗ ࡚సࡿࡇ࡜ࡀ࡛ࡁࡿࠋ㻌 Partition[RandomSample[Range[16]] /. {16 -> " "}, 4]; ஘ᩘ࡛సࡗࡓ㓄⨨ࡢ౛ࢆ♧ࡍࠋ㻌㻌 P0 P1 P2 P11 P12 P111 P112 m1 m2 m11 m12 m111 m112 firstmoves secondmoves thirdmoves

(6)

ࡇࡢ㓄⨨ࡢ᏶ᡂྍ⬟ᛶࢆㄪ࡭ࡿࠋ㻌 parityQ[desired, realstart] э₁㻌 അ࡞ࡢ࡛᏶ᡂྍ⬟࡞㓄⨨࡛࠶ࡿࠋᕠᅇ⨨᥮ࡣḟ࡟ ࡞ࡿࠋ㻌 list1= Flatten[realstart /. {" " -> 16}]; list2= Flatten[desired /. {" " -> 16}]; perm1=findPermutationReplace[list1, list2] э Cycles[{{1,15,8,10,16,11,9,6,5,14,2,12,3, 7,4}}] ⡆༢࡞㓄⨨࡟ࡘ࠸࡚ࡣ㛵ᩘ _try࡛⛣ືࡢṇゎᡭ㡰 ࢆồࡵࡿࡇ࡜ࡀ࡛ࡁࡿࠋࡋ࠿ࡋ࡞ࡀࡽࡇࡢ㓄⨨ࡣ⟅ ࠼ࡀồࡲࡽ࡞࠸౛࡛࠶ࡗࡓࠋ㻌 try[realstart, 1000]

Solution not found, best sequence was э_{{28, "Right", "Up", … , "Up", "Up"}}

ṇゎᡭ㡰ࡀồࡲࡽ࡞࠸⌮⏤ࡣグ᠈ᐜ㔞ࡢไ⣙࡛ࡣ ࡞ࡃ⛣ືࡢ㐃㙐ࢆ᥈⣴ࡍࡿ᪉ἲ࡟࠶ࡾࠊᨵⰋࡢవᆅ ࡀ࠶ࡿࡇ࡜ࢆ♧ࡋ࡚࠸ࡿࠋ㻌㻌㻔㻢㻕ࣉࣟࢢ࣒ࣛࡢᨵⰋ㻌 ḟࡢࡼ࠺࡞ᨵⰋࢆຍ࠼ࡿࡇ࡜࡛ṇゎᡭ㡰ࢆồࡵࡿ ࡇ࡜ࡀ࡛ࡁࡓࠋ㻌㻝㻕ࢱ࢖ࣝ 㻝 ࢆᥞ࠼ࡿࡇ࡜࠿ࡽࡣࡌࡵࠊḟ࡟ 㻝㻘㻞 ࢆᥞ ࠼ࡉࡽ࡟ 㻝㻘㻞㻘㻟 ࡜⧞ࡾ㏉ࡋ࡚඲࡚ࢆᥞ࠼ࡿࠋ㻌㻞㻕㸯⾜┠ࡢࢱ࢖ࣝ 㻝㻘㻞㻘㻟㻘㻠 ࡀᥞࡗࡓᚋࡣࠊࣈࣛࣥࢡࡢ ⛣ືࢆ 㻞㻘㻟㻘㻠⾜࡟ไ㝈ࡍࡿࠋࡇࢀࡣ⛣ືࡢ⮬⏤ᗘࢆ ᑠࡉࡃࡍࡿࡓࡵ⟅ࢆồࡵ᫆ࡃࡍࡿຠᯝࡀ኱ࡁ࠸ࠋ㻌㻟㻕㻞⾜┠ࡢࢱ࢖ࣝ 㻡㻘㻢㻘㻣㻘㻤㻌 ࢆᥞ࠼ࡿ᫬࡟ࡣࣈࣛࣥࢡࡢ ⛣ືࢆ 㻞㻘㻟㻘㻠⾜࡟ไ㝈ࡋࠊࡑࡢᚋ 㻞㻘㻌㻟⾜࡟⤠ࡾ㎸ࡴࠋ㻌㻠㻕㻝 ࠿ࡽ 㻝㻞㻌 ࡲ࡛ࡢࢱ࢖ࣝࡀᥞࡗࡓᚋࡣࠊࣈࣛࣥࢡࡢ ⛣ືࢆ 㻟㻘㻠⾜࡟ไ㝈ࡍࡿࠋ㻌㻌 ௨ୖࡢᨵⰋࢆຍ࠼ࡿࡓࡵ࡟ࡣ㻌_moves㻌㛵ᩘ࡜࣐ࣥࣁ ࢵࢱࣥ㊥㞳ࢆィ⟬ࡍࡿ㛵ᩘ࡟ಟṇࢆຍ࠼ࡿᚲせࡀ࠶ ࡿࠋࡇࡢᨵⰋࢆຍ࠼ࡿࡇ࡜࡛」㞧࡟࡞ࡿࡀ᪂ࡋ࠸㛵 ᩘ㻌_newtryN㻌 ࡢసᡂ࡟ᡂຌࡋࡓࠋ㻌㻌 result = newtryN[realstart] 㼀㼔㼑㻌㼒㼛㼘㼘㼛㼣㼕㼚㼓㻌㼟㼛㼘㼡㼠㼕㼛㼚㻌㼣㼍㼟㻌㼒㼛㼡㼚㼐㻚㻌

э{0, "Down", "Left", "Up", ... , "Right", "Right"}

Length[Rest[result]] э㻝㻜㻜㻌 ṇゎࡢᡭ㡰ࡣ 㻝㻜㻜 ᡭࡢ⛣ືࡢิ࡛࠶ࡗࡓࠋࡇࡢ⤖ ᯝࡀඛ࡟ồࡵࡓᕠᅇ⨨᥮_perm1࡜୍⮴ࡍࡿ࠿☜ㄆࢆ ⾜࠺ࠋ⛣ືᡭ㡰ࢆ㛵ᩘ㻌_{puzseq2cycles} ࢆ౑ࡗ࡚ᕠ ᅇ⨨᥮࡟ኚ᥮ࡋࠊ㻝㻜㻜 ಶࡢ⨨᥮ࡢ✚ࢆồࡵࡿࠋ㻌㻔㻌㻭㼜㼜㼑㼚㼐㼕㼤㻌㻞㻌㻔㻡㻕㻌㻕

puzseq= FoldList[effectmove[#1, #2] &,

_{realstart, Rest[result]];} cyclesSet = puzseq2cycles[puzseq]; perm2=PermutationProduct @@ cyclesSet э Cycles[{{1,15,8,10,16,11,9,6,5,14,2,12,3, 7,4}}] perm2 == perm1 эTrue ᚑࡗ࡚஧ࡘࡢ᪉ἲ࡛ồࡵࡓᕠᅇ⨨᥮ࡣ୍⮴ࡍࡿࠋ㻌㻌㸴㸬ࡲ࡜ࡵ࡜௒ᚋࡢㄢ㢟 ᢳ㇟ⓗ࡞ᩘᏛⓗᴫᛕ࡛࠶ࡿ⩌ㄽࡢᐇ౛ࡢࡦ࡜ࡘ࡜ ࡋ࡚ࠊ㻝㻡 ࣃࢬࣝࡢ᏶ᡂྍ⬟ᛶࡢุᐃࢆ 㻹㼍㼠㼔㼑㼙㼍㼠㼕㼏㼍 ࢆ฼⏝ࡋ࡚ㄽࡌࡓࠋḟ࡟ࣃࢬࣝࢆゎࡃࣉࣟࢢ࣒ࣛࢆ ㄝ᫂ࡋᨵⰋ᪉ἲࢆ♧ࡋࡓࠋ㻌㻌 ⨨᥮ࡢ௚࡟ࢢࣛࣇ⌮ㄽࡢぢᆅ࠿ࡽ 㻝㻡 ࣃࢬࣝࢆㄽࡌ ࡓᩘᏛㄽᩥ㼇㻞㼉ࡀ࠶ࡿࠋ㻹㼍㼠㼔㼑㼙㼍㼠㼕㼏㼍㻌 ࡟ࡣࢢࣛࣇ࡟㛵 ࡍࡿ㛵ᩘࡀ⏝ពࡉࢀ࡚࠸ࡿࡢ࡛ࡇࡢᶵ⬟ࢆᛂ⏝ࡋࡓ ⌮ゎ࡜☜ㄆࢆ⾜࠸ࡓ࠸ࠋ㻌 ࡲࡓࠊᏛ⏕ᐇ⩦➼࡟௒ᅇసᡂࡋࡓࣉࣟࢢ࣒ࣛࢆ⏝ ࠸ࠊ㔞ᏊຊᏛ࡟࠾ࡅࡿ⩌ㄽ࡞࡝ࡢᢳ㇟ᴫᛕࡢ⌮ゎࢆ ຓࡅࡿྍ⬟ᛶࢆ᥈ࡿࡇ࡜ࡣ௒ᚋࡢㄢ㢟࡛࠶ࡿࠋ 㻌 ཧ⪃ᩥ⊩㻌㻝㻕㻭㼞㼏㼔㼑㼞㻘㻭㻚㻲㻚䇿㻭㻌㻹㼛㼐㼑㼞㼚㻌㼀㼞㼑㼍㼠㼙㼑㼚㼠㻌㼛㼒㻌㼠㼔㼑㻌㻝㻡㻌㻼㼡㼦㼦㼘㼑㻚䇿㻌㻭㼙㼑㼞㻚㻌㻹㼍㼠㼔㻚㻹㼛㼚㼠㼔㼘㼥㻌㻝㻜㻢㻘㻣㻥㻟㻙㻣㻥㻥㻘㻝㻥㻥㻥㻌㻞㻕㼃㼕㼘㼟㼛㼚㻘㻾㻚㻹㻚㻌䇾㻳㼞㼍㼜㼔㻌㻼㼡㼦㼦㼘㼑㼟㻘㻌㻴㼛㼙㼛㼠㼛㼜㼥㻘㻌㼍㼚㼐㻌㼠㼔㼑㻌㻭㼘㼠㼑㼞㼚㼍㼠㼕㼚㼓㻌㻳㼞㼛㼡㼜㻚䇿㻌㻶㻚㻌㻯㼛㼙㼎㼕㼚㻚㻌㼀㼔㻚㻌㻿㼑㼞㻚㻮㻌㻝㻢㻘㻌㻤㻢㻙㻥㻢㻘㻝㻥㻣㻠㻌㻟㻕㻰㻚㻶㼛㼥㼚㼑㼞㻌䇾㻭㼐㼢㼑㼚㼠㼡㼞㼑㻌㼕㼚㻌㼓㼞㼛㼡㼜㻌㼠㼔㼑㼛㼞㼥䇿㻌㻞㼚㼐_{㻌㼑㼐㻘㻌㻞㻜㻜㻤㻌} ࠕ⩌ㄽࡢ࿡ࢃ࠸ࠖᕝ㎶἞அヂ㻌㻠㻕㼃㼛㼘㼒㼞㼍㼙㻌㻹㼍㼠㼔㼣㼛㼞㼘㼐㻘㻌䇾㻝㻡㻌㻼㼡㼦㼦㼘㼑䇿㻌㻘㻌 KWWSPDWKZRUOGZROIUDPFRP3X]]OHKWPO :76KDZDQG-7LJJ͆$SSOLHG0DWKHPDWLFD͇ ࠕᛂ⏝ 0DWKHPDWLFDࠖᑠ㔝㝧Ꮚヂ

(7)

Appendix1

(1) 㓄఩ (Configuration)

pl2Cf#mat_List? MatrixQ' : Module#rule, cellconf, blank,

rule 1, 1 1, 1, 2 2, 1, 3 3, 1, 4 4, 2, 1 8, 2, 2 7, 2, 3 6, 2, 4 5, 3, 1 9, 3, 2 10, 3, 3 11, 3, 4 12, 4, 1 16, 4, 2 15, 4, 3 14, 4, 4 13;

cellconf +Position#mat, Ó' & s Range#15'/ s. rule; blank Position#mat, Ó' &" " s. rule;

If#Ó ! blank, Ó 1, Ó' & s cellconf'

(2) 㓄఩ࡢ⨨᥮࡜അወᛶ

findPermutationReplace#lst1_, lst2_' :

Map#lst1##Ó'' &, FindPermutation#lst2, lst1', 3' permutationSignature#perm_?PermutationCyclesQ' :

Apply#Times, +1/^+Length s First#perm' 1/' parityQ#x_List? MatrixQ, y_List? MatrixQ' :

permutationSignature#findPermutationReplace#pl2Cf#x', pl2Cf#y'''

Appendix2 15ࣃࢬࣝࢆゎࡃࣉࣟࢢ࣒ࣛ [ 5 ]

viewlolol#a_List' : Map#MatrixForm#Ó, TableSpacing 1, 1' &, a'; desired Partition# Range#16' s. 16 " ", 4';

(1) ࣈࣛࣥࢡࡢ఩⨨࠿ࡽྍ⬟࡞ ⛣ື ࢆồࡵࡿ㛵ᩘ㸸moves

moves#current_? MatrixQ' : Module#answer, xdim, ydim, place, xpos, ypos, answer "Up", "Down", "Left", "Right";

ydim Length#current'; xdim Length#current##1'''; place Position#current, " "'; xpos place##1, 2'';

ypos place##1, 1'';

If#xpos m xdim, answer Drop#answer, 4''; If#xpos m 1, answer Drop#answer, 3''; If#ypos m ydim, answer Drop#answer, 2''; If#ypos m 1, answer Drop#answer, 1''; answer'

(2) ࣈࣛࣥࢡࡢ⛣ື࡟ࡼࡿ᪂ࡓ࡞㓄⨨ࢆసࡿ㛵ᩘ㸸effectmove

effectmove#a___, b___, " ", c_, d___, e___, "Right"' : a, b, c, " ", d, e effectmove#a___, b___, c_, " ", d___, e___, "Left"' : a, b, " ", c, d, e effectmove#a_, "Up"' : Transpose#effectmove#Transpose#a', "Left"''

effectmove#a_, "Down"' : Transpose#effectmove#Transpose#a', "Right"'' effectmove#a_List, b_String, c__String' : effectmove#effectmove#a, b', c'

(8)

(3) ㏆ࡉࡢホ౯㛵ᩘ㸸࣐ࣥࣁࢵࢱࣥ㊥㞳ࢆồࡵࡿ㛵ᩘ : manhattandistance

manhattandistance::incompat "Manhattan distance can only be computed for matrices with tha same dimension"; manhattandistance#x_List, y_List' :

Module#temp, If#Dimensions#x' Dimensions#y', Message#manhattandistance::incompat', temp Map#Flatten#Position#y, Ó'' &, x, 2';

temp temp Map#Flatten#Position#x, Ó'' &, x, 2'; temp Total#Flatten#Abs#temp'''''

(4) ⛣ືࡢ㐃㙐ࢆ᥈⣴ࡍࡿᮌࡢ⏕ᡂ

listscores#x_' : Module#makemoves, ans, makemoves Map#effectmove#x, Ó' &, moves#x'';

ans Flatten#Map#manhattandistance#Ó##1'', desired' &, makemoves''; Transpose#ans, moves#x'''

worthwhile#x___, "Right", "Left"' : False; worthwhile#x___, "Left", "Right"' : False; worthwhile#x___, "Up", "Down"' : False; worthwhile#x___, "Down", "Up"' : False; worthwhile#x___' : True

bestscore#x_List, y_List, delta_: 0.2' :

If#x##1'' y##1'' delta +Length#Rest#y'' Length#Rest#x''/, True, False' iterate#start_, x_, y__, z___' : Module#endnode, newnodes, newseq,

endnode effectmove#start, y'; newnodes listscores#endnode';

newseq Map#Join#First#Ó', y, Rest#Ó'' &, newnodes'; Sort#Join#Select#newseq, worthwhile', z', bestscore''; try#start_, n_' : Module#temp, count, count 0;

temp listscores#start';

While#temp##1, 1'' ! 0 && count n, temp iterate#start, temp'; count count 1';

If#count m n && temp##1, 1'' 0, Print#"Solution not found, best sequence was"', Print#"The following solution was found"'';

temp##1'''

(5) ࣉࣟࢢ࣒ࣛࡢᨵⰋ

findPermutationReplace#lst1_, lst2_' :

Map#lst1##Ó'' &, FindPermutation#lst2, lst1', 3' toList#mat_' : Flatten#mat' s. " " 16

puzseq2cycles#puzseq_' : MapThread#findPermutationReplace#toList#Ó1', toList#Ó2'' &, Most#puzseq', Rest#puzseq''