题目

1. 如图所示的地图着色问题共有多少个解？如果是四色有多少个解？如果只有两色呢？

   

   • 三色

     依据MCV对节点排序，

     	SA	NT	Q	NSW	WA	V	T
     1	$◯$	$\times$	$\times$	$\times$	$\times$	$\times$	$◯$
     2		$◯$	$\times$	$◯$	$\times$	$\times$
     3			$◯$	$\times$	$◯$	$◯$

     $$n=3\times 2\times 3=18$$

   • 四色

     	SA	NT	Q	NSW	WA	V	T
     1	$◯$	$\times$	$\times$	$\times$	$\times$	$\times$	$◯$
     2		$◯$	$\times$	$◯$	$\times$	$\times$
     3			$◯$	$\times$	$◯$	$◯$
     4

     $$n=4\times 3\times 2\times 2\times 2\times 2\times 4=768$$

   • 二色

     	SA	NT	Q	NSW	WA	V	T
     1	$◯$	$\times$	$\times$	$\times$	$\times$	$\times$	$◯$
     2		$◯$	$\times$	$◯$	$\times$	$\times$

     无解

2. 考虑下述的逻辑问题：有5所不同颜色的房子，住着5个来自不同国家的人，每个人都喜欢一种不同牌子的糖果，不同牌子的饮料和不同的宠物。给定下列已知事实，请回答问题“斑马住在哪？哪所房子里的人喜欢喝水？

   · 英国人住在红色房子里。

   · 西班牙人养狗

   · 挪威人住在最左边的第一所房子里

   · 绿房子是象牙色房子的右边邻居

   · 喜欢抽hershey牌巧克力的人住在养狐狸的人的旁边

   · 住在黄色房子里的人喜欢Kit Kats糖果

   · 挪威人住在蓝房子旁边

   · 喜欢smarties糖果的人养了一只蜗牛

   · 喜欢Snickers 糖果的人喝橘汁

   · 乌克兰人喝茶

   · 日本人喜欢Milky Ways糖果

   · 喜欢Kit Kats糖果的人住在养马人的隔壁

   · 住在中间房子里的人喜欢喝牛奶

   · 绿房子的主人喝咖啡

   把这个问题表示成CSP问题，并进行求解。

   • 变量：房屋的序号从左向右排
     V={v1,v2,v3,v4,v5} V=\{v_1,v_2,v_3,v_4,v_5\} V={v1​,v2​,v3​,v4​,v5​}

   • 值域
     D1={red, green, ivory, yellow, blue}D2={British, Spanish,Norway, Ukraine, Japanese}D3={hershey, kit kats, smarties, snickers, milky ways}D4={orange, tea, milk, coffee, water}D5={dog, fox, snail, horse, zebra} D_1=\{red, \ green,\ ivory,\ yellow,\ blue\} \\ D_2=\{British,\ Spanish, Norway,\ Ukraine,\ Japanese\} \\ D_3=\{hershey,\ kit\ kats,\ smarties,\ snickers,\ milky\ ways\} \\ D_4=\{orange,\ tea,\ milk,\ coffee,\ water\} \\ D_5=\{dog,\ fox,\ snail,\ horse,\ zebra\} D1​={red, green, ivory, yellow, blue}D2​={British, Spanish,Norway, Ukraine, Japanese}D3​={hershey, kit kats, smarties, snickers, milky ways}D4​={orange, tea, milk, coffee, water}D5​={dog, fox, snail, horse, zebra}

   • 约束条件

     $a=b$：$a,b$在同一个房间里

     $a<b$：$a$在$b$左邻的房间里

     $a>b$：$a$在$b$右邻的房间里

     $a\in v_i$：$a$在房间$v_i$里

     $$\begin{array}{rl}& British=red\\ & Spanish=dog\\ & Norway\in v_1\\ & green>ivory\\ & hershey<fox||hershey>fox\\ & yellow=kitkats\\ & Norway<blue||Norway>blue\\ & smarties=snail\\ & snickers=orange\\ & Ukraine=tea\\ & milkyways=Japanese\\ & kitkats<horse||kitkats>horse\\ & milk\in v_3\\ & green=coffee\end{array}$$

   推理如下

   	$v_1$	$v_2$	$v_3$	$v_4$	$v_5$
   red	$\times$	$\times$	3	$\times$	$\times$
   green	$\times$	$\times$	$\times$	$\times$	5
   ivory	$\times$	$\times$	$\times$	4	$\times$
   yellow	1	$\times$	$\times$	$\times$	$\times$
   blue	$\times$	2	$\times$	$\times$	$\times$
   British	$\times$	$\times$	3	$\times$	$\times$
   Spanish	$\times$	$\times$	$\times$	4	$\times$
   Norway	1	$\times$	$\times$	$\times$	$\times$
   Ukraine	$\times$	2	$\times$	$\times$	$\times$
   Japanese	$\times$	$\times$	$\times$	$\times$	5
   hershey	$\times$	2	$\times$	$\times$	$\times$
   kit kats	1	$\times$	$\times$	$\times$	$\times$
   smarties	$\times$	$\times$	3	$\times$	$\times$
   snickers	$\times$	$\times$	$\times$	4	$\times$
   milky ways	$\times$	$\times$	$\times$	$\times$	5
   orange	$\times$	$\times$	$\times$	4	$\times$
   tea	$\times$	2	$\times$	$\times$	$\times$
   milk	$\times$	$\times$	3	$\times$	$\times$
   coffee	$\times$	$\times$	$\times$	$\times$	5
   water	1	$\times$	$\times$	$\times$	$\times$
   dog	$\times$	$\times$	$\times$	4	$\times$
   fox	1	$\times$	$\times$	$\times$	$\times$
   snail	$\times$	$\times$	3	$\times$	$\times$
   horse	$\times$	2	$\times$	$\times$	$\times$
   zebra	$\times$	$\times$	$\times$	$\times$	5

   最终结果为

   $V$	$D_1$	$D_2$	$D_3$	$D_4$	$D_5$
   1	yellow	Norway	kit kats	water	fox
   2	blue	Ukraine	hershey	tea	horse
   3	red	British	smarties	milk	snail
   4	ivory	Spanish	snickers	orange	dog
   5	green	Japanese	milky ways	coffee	zebra

   斑马住在最右边的绿房子里，最左边的乌克兰人喜欢喝水。

| 4 | ivory | Spanish | snickers | orange | dog |
| 5 | green | Japanese | milky ways | coffee | zebra |

斑马住在最右边的绿房子里，最左边的乌克兰人喜欢喝水。