結論から言うと351市+問題市5市です。
考え方としては次の通り。
※隣接には架橋隣接、点隣接、離島隣接すべて含みます。また境界未確定についても、
市町村隣接関係一覧で微妙隣接として隣接扱いされているものに関しては、隣接とみなしています。
1.以下の24市については、隣接市がないので必ず想定解になります。
釧路、帯広、留萌、稚内、紋別、根室、八戸、三沢、むつ、久慈、白河、かほく、下田、御坊、室戸、対馬、壱岐、五島、西之表、奄美、石垣、名護、宮古島、南城
2.須賀川については、非該当市の郡山にしか隣接していないため、必ず想定解になります。
3.以下の6ペアについては、ペアのうちどちらかが想定解となります。
函館・北斗、北見・網走、士別・名寄、小田原・南足柄、輪島・珠洲、沖縄・うるま
4.伊勢・鳥羽・志摩の3市については、この中の1市が想定解になります。
5.徳島・小松島・阿南の3市については、最大を取るには徳島、阿南の2市を選択しなければなりません。
6.尾鷲・熊野・新宮・田辺の4市は、「尾鷲、新宮」、「尾鷲、田辺」、「熊野、田辺」のいずれかが想定解になります。
7.那覇・宜野湾・浦添・糸満・豊見城の5市については、最大を取るには、那覇、宜野湾、糸満の3市を選択しなければなりません。
※ここまでで39市
8.1.~7.を除くと、以下の6グループに分かれます。
A.北海道グループ(旭川市~室蘭市の23市)
B.宮城山形グループ(仙台市周辺と山形県内陸部の15市)
C.静岡グループ(静岡市と浜松市に挟まれた9市)
D.愛媛高知グループ(伊予市~土佐清水市の8市)
E.宮崎鹿児島グループ(宮崎県南部と鹿児島県の26市)
F.それ以外(青森県~宮崎県までの646市)
これらのグループについて、「以下の2条件で想定解、非想定解を確定→これらをグループから除外」を繰り返し解を絞っていきます。
条件1:グループ内で1市にしか隣接していない市は想定解。
条件2:グループ内で2市に隣接している市で、その隣接している市同士も隣接しており、それらの隣接市数が3以上の場合、「2市に隣接している市」は想定解。
A.~E.についてはこれらの2条件だけで解が特定できて、例えば一例ですが、
A(11市):小樽、旭川、室蘭、夕張、苫小牧、美唄、江別、滝川、歌志内、富良野、恵庭
B(7市):塩竈、岩沼、富谷、寒河江、上山、長井、東根
C(4市):磐田、焼津、掛川、牧之原
D(4市):宇和島、八幡浜、伊予、土佐清水
E(12市):人吉、水俣、日南、小林、西都、鹿屋、枕崎、阿久根、指宿、日置、志布志、姶良
が想定解となります。
※ここまでで77市
Fについてはこの2条件だけでは解ききれませんが、人が試行錯誤で解けるレベルにまでは細切れにできます。
Fにこの2条件を適用し、想定解、非想定解を除外すると、次の4つのグループが残ります。
F1:倉敷、浅口、笠岡、井原、総社の5市
F2:甲府、北杜、甲斐、韮崎、中央、南アルプスの6市
F3:いなべ、四日市、鈴鹿、亀山、伊賀、名張、甲賀、東近江、近江八幡、野洲、湖南、宇陀、桜井、橿原、御所、大和高田、葛城、香芝、柏原、八尾、藤井寺、羽曳野、松原の23市
F4:茨城県、栃木県を中心とした48市
F1はループになっているだけなので、5市のうち隣接しない2市が想定解です
F2は「甲府、韮崎」、「甲府、南アルプス」、「北杜、中央」、「韮崎、中央」、「甲斐、中央」のいずれかの選択肢しかありません。
F3はたとえば亀山と甲賀に着目すると、
「亀山が想定解の場合、隣接する甲賀は非想定解」
「亀山が非想定解の場合、鈴鹿、四日市、甲賀に条件2が適用できるようになって、鈴鹿が想定解、四日市、甲賀が非想定解」
が導け、甲賀は必ず非想定解であることがわかります。F3はここからドミノ倒し的に解が決まっていきます。
F4も同様の試行錯誤を繰り返すことで解が決まっていき、最終的に以下のような結果例が得られます。
F(274市):弘前、黒石、五所川原、十和田、宮古、北上、陸前高田、釜石、二戸、滝沢、角田、登米、東松島、秋田、能代、横手、男鹿、にかほ、米沢、酒田、新庄、田村、南相馬、伊達(福島)、本宮、日立、結城、下妻、北茨城、取手、牛久、ひたちなか、潮来、常陸大宮、坂東、かすみがうら、桜川、鉾田、鹿沼、那須塩原、さくら、下野、桐生、館林、渋川、藤岡、富岡、熊谷、本庄、狭山、羽生、上尾、越谷、蕨、志木、和光、北本、八潮、坂戸、幸手、ふじみ野、白岡、銚子、館山、茂原、東金、習志野、勝浦、流山、鎌ケ谷、富津、浦安、四街道、袖ケ浦、印西、富里、匝瑳、三鷹、青梅、町田、日野、国分寺、福生、狛江、東大和、清瀬、稲城、西東京、茅ヶ崎、逗子、三浦、秦野、座間、綾瀬、柏崎、新発田、小千谷、加茂、見附、村上、燕、糸魚川、南魚沼、滑川、黒部、小矢部、射水、七尾、羽咋、能美、野々市、敦賀、小浜、勝山、鯖江、あわら、富士吉田、北杜、上野原、甲州、中央、諏訪、須坂、小諸、駒ヶ根、中野、塩尻、千曲、安曇野、美濃、羽島、恵那、美濃加茂、土岐、各務原、山県、瑞穂、飛騨、下呂、熱海、三島、御殿場、湖西、伊豆、春日井、津島、碧南、蒲郡、常滑、新城、東海、知立、尾張旭、岩倉、豊明、日進、田原、清須、弥富、松阪、鈴鹿、いなべ、伊賀、近江八幡、草津、湖南、米原、舞鶴、宇治、向日、八幡、京丹後、南丹、木津川、岸和田、池田、吹田、泉大津、高槻、守口、泉佐野、松原、大東、柏原、交野、大阪狭山、阪南、尼崎、明石、芦屋、赤穂、宝塚、三木、高砂、加西、養父、丹波、南あわじ、淡路、たつの、大和郡山、橿原、葛城、宇陀、海南、橋本、鳥取、倉吉、浜田、大田、雲南、倉敷、笠岡、新見、瀬戸内、赤磐、美作、広島、竹原、尾道、三次、大竹、江田島、下関、宇部、萩、防府、下松、柳井、吉野川、高松、丸亀、東かがわ、三豊、松山、西条、四国中央、安芸、南国、土佐、大牟田、直方、田川、柳川、八女、行橋、豊前、中間、小郡、春日、宗像、太宰府、古賀、朝倉、糸島、武雄、鹿島、小城、神埼、島原、諫早、平戸、西海、八代、玉名、宇土、上天草、阿蘇、合志、別府、津久見、豊後高田、豊後大野、延岡
※合計351市
最小についても頑張って求めようとしましたが、いいロジックが思いつきませんでした。
8.のE.までは人力で解けても、8.のF.は人力では無理です。
最小選択の場合、必ず選択される市を特定できる条件、なにかないものだろうか。