## 1. Coloring

A map visible as the following figure , Each area in the picture represents a province , Now please use red （1）、 LAN （2）、 yellow （3）、 green （4） Four colors, color the provinces , Ask each province to use one color , And the colors of any two neighboring provinces cannot be the same , Please give a color scheme that meets the conditions .

## Test question code

``````# Project name ：
# Project brief introduction ：
# do     person ：key
# Development time ：2020/12/21 21:06

''' Of Graphs m The coloring problem '''

#  Graph with adjacency table
n = 5  #  Number of nodes
count = 0 #  Number of schemes
a, b, c, d, e = range(n)  #  The name of the node
graph = [
{

b, c, d},
{

a, c, d, e},
{

a, b, d},
{

a, b, c, e},
{

b, d}
]

m = 4  # m Color
Color = [' red ',' blue ',' yellow ',' green ']

x = [0] * n  #  A solution （n Meta array , Fixed length ） Be careful ： Explain x The subscript of is a,b,c,d,e!!!
X = []  #  A set of solutions

#  Collision detection
def conflict(k):
global n, graph, x

#  Find out the k Adjacent nodes that have been colored in front of nodes
nodes = [node for node in range(k) if node in graph[k]]
if x[k] in [x[node] for node in nodes]:  #  There are already adjacent nodes painted this color
return True

return False  #  No conflict

#  Of Graphs m To color （ Complete solution ）
def dfs(k):  #  arrive （ Explain x Of ） The first k Nodes
global n, m, graph, x, X, count

if k == n:  #  The length of the solution exceeds
print(x)
count+=1
# return
# X.append(x[:])
else:
for color in range(m):  #  Traversal node k Can be painted color number of （ The state space ）, It's all the same
x[k] = Color[color]
if not conflict(k):  #  prune
dfs(k + 1)

#  test
dfs(a)  #  From the node a Start
print(' Altogether {} Kind of plan '.format(count))
``````
###### —— Dream around the border city , The heart flies home building ——

https://cdmana.com/2020/12/20201224100744076s.html

Scroll to Top