举例:棋盘的覆盖问题 国际象棋棋盘8×8方格 ■多米诺骨牌可覆盖相邻的两个方格 ■问题:32张牌能否恰好覆盖整个棋盘? 构造一些"完美覆盖"容易 计算出有多少"完美覆盖"不易(24×9012=12988816) 若考虑mxm的棋盘 是否存在完美覆盖?(对应于分子物理的二聚物问 题) ■若棋盘去掉两个对角(剩62个方格 ■是否存在完美覆盖? ■证明:31 Black white not=32Back+30whte 200399 Dept of couputer ciena and ngineering, Shanghai iaotong University 举例:幻方问题 ■最古老、最流行的游戏 ■1,2,3灬n2个数排成nxn方阵 每行、每列、以及对角线上元素和为定数s 是否存在? nn=3,n=4「816 163213 510118 357 96712 492 415141 200399 Dept of computer Science and Engineering, Shanghai fiaotong Univrsity4 2003-9-9 Dept of Computer Science and Engineering， Shanghai Jiaotong University 7 举例：棋盘的覆盖问题 „ 国际象棋棋盘8x8方格 „ 多米诺骨牌可覆盖相邻的两个方格 „ 问题：32张牌能否恰好覆盖整个棋盘？ „ 构造一些“完美覆盖”容易 „ 计算出有多少“完美覆盖”不易（24x9012=12988816） „ 若考虑m x n的棋盘 „ 是否存在完美覆盖？（对应于分子物理的二聚物问 题） „ 若棋盘去掉两个对角（剩62个方格） „ 是否存在完美覆盖? „ 证明：31Black|white not= 32Black + 30white 2003-9-9 Dept of Computer Science and Engineering， Shanghai Jiaotong University 8 举例：幻方问题 „ 最古老、最流行的游戏 „ 1,2,3,…,n2个数排成nxn方阵 „ 每行、每列、以及对角线上元素和为定数s „ 是否存在？ „ n=3, n=4