Created
October 28, 2018 16:12
-
-
Save eduidl/79f09f316ff12939ef18909a231bb5b9 to your computer and use it in GitHub Desktop.
東京都市区町村の４色塗り分け問題
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| import pulp | |
| COLORS = ['R', 'G', 'B', 'Y'] | |
| AREAS = [ | |
| 'Adachi', 'Arakawa', 'Bunkyo', 'Chiyoda', 'Chuo', 'Edogawa', | |
| 'Itabashi', 'Katsushika', 'Kita', 'Koto', 'Meguro', 'Minato', | |
| 'Nakano', 'Nerima', 'Ota', 'Setagaya', 'Shibuya', 'Shinagawa', | |
| 'Shinjuku', 'Suginami', 'Sumida', 'Taito', 'Toshima', | |
| 'Akishima', 'Akiruno', 'Chofu', 'Fuchu', 'Fussa', 'Hachioji', | |
| 'Hamura', 'Higashikurume', 'Higashimurayama', 'Higashiyamato', | |
| 'Hino', 'Inagi', 'Kiyose', 'Kodaira', 'Koganei', 'Kokubunji', | |
| 'Komae', 'Kunitachi', 'Machida', 'Mitaka', 'Musashimurayama', | |
| 'Musashino', 'Nishitokyo', 'Ome', 'Tachikawa', 'Tama', | |
| 'Hinode', 'Mizuho', 'Okutama', 'Hinohara' | |
| ] | |
| NEIGHBORINGS = [ | |
| [0, 1], [0, 7], [0, 8], [0, 20], [1, 2], [1, 8], [1, 20], [1, 21], | |
| [2, 3], [2, 8], [2, 18], [2, 21], [2, 22], [3, 4], [3, 11], [3, 18], | |
| [3, 21], [4, 9], [4, 11], [4, 20], [4, 21], [5, 7], [5, 9], [5, 20], | |
| [6, 8], [6, 13], [6, 22], [7, 20], [8, 22], [9, 11], [9, 14], [9, 17], | |
| [9, 20], [10, 14], [10, 15], [10, 16], [10, 17], [11, 16], [11, 17], | |
| [11, 18], [12, 13], [12, 16], [12, 18], [12, 19], [12, 22], [13, 19], | |
| [13, 22], [13, 44], [13, 45], [14, 15], [14, 17], [15, 16], [15, 19], | |
| [15, 25], [15, 39], [15, 42], [16, 17], [16, 18], [16, 19], [18, 22], | |
| [19 ,42], [19, 44], [20, 21], [23, 27], [23, 28], [23, 33], [23, 47], | |
| [24, 27], [24, 28], [24, 29], [24, 46], [24, 49], [24, 51], [24, 52], | |
| [25, 26], [25, 34], [25, 37], [25, 39], [25, 42], [26, 33], [26, 34], | |
| [26, 37], [26, 38], [26, 40], [26, 48], [27, 28], [27, 29], [27, 43], | |
| [27, 47], [27, 50], [28, 33], [28, 41], [28, 48], [28, 52], [29, 46], | |
| [29, 50], [30, 31], [30, 35], [30, 36], [30, 45], [31, 32], [31, 35], | |
| [31, 36], [32, 36], [32, 43], [32, 47], [33, 40], [33, 47], [33, 48], | |
| [34, 48], [36, 37], [36, 38], [36, 45], [36, 47], [37, 38], [37, 42], | |
| [37, 44], [37, 45], [38, 40], [38, 47], [40, 47], [41, 48], [42, 44], | |
| [43, 47], [43, 50], [44, 45], [46, 49], [46, 50], [46, 51], [51, 52] | |
| ] | |
| def main(): | |
| problem = pulp.LpProblem('Four Colors', pulp.LpMinimize) | |
| var = { | |
| area: pulp.LpVariable.dicts(area, COLORS, cat = pulp.LpBinary) | |
| for area in AREAS | |
| } | |
| for area in AREAS: | |
| problem += sum(var[area].values()) == 1 | |
| for pair in NEIGHBORINGS: | |
| for color in COLORS: | |
| problem += var[AREAS[pair[0]]][color] + var[AREAS[pair[1]]][color] <= 1 | |
| result = problem.solve() | |
| if pulp.LpStatus[result] != 'Optimal': | |
| print('解なし') | |
| return | |
| output = { color: [] for color in COLORS } | |
| for area, v in var.items(): | |
| for color, flg in v.items(): | |
| if flg.value() == 1: | |
| output[color].append(area) | |
| break | |
| print(output) | |
| if __name__ == '__main__': main() |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment