首页 > 其他 > 详细

棋盘染色法(双色染色法)

时间:2020-01-03 22:07:52      阅读:165      评论:0      收藏:0      [点我收藏+]

  棋盘染色法是一类借助国际象棋棋盘通过染色解决组合问题的解题方法, 

 

  双色染色法

技术分享图片  技术分享图片

 

一个5*5的棋盘,可以上下左右移动,问从图中的黑色格子出发,能否走遍所有格子并且不重复走一个格子.

技术分享图片

 

因为是黑色格子为起点, 你模拟一下 会发现无论怎么走 都会是 黑白黑白 交替, 而 5*5 总共 25格子  12黑格子  13 白格子,  起点为黑色  黑-> - > ->  如果终点为黑格的话  黑色格子需要比白色格子多一个 矛盾故不可, 如果终点为白格的话, 黑->白 ……-> 黑-> 白 黑格数量等于白格 矛盾故不可, 综上, 无解

 

 一个8*8的格子纸, 去掉对角两格,能否用1*2的方块来覆盖它, 问题的本质是1*2的方块的覆盖, 这说明问题和奇偶性有关,我们染色成国际象棋以后, 发现不管不管怎么放  1*2方块都会遮住一个黑色一个白色块,所以如果我们数一下黑白格子的数量,就会发现 黑格比白格少两个, 故不可.

技术分享图片

可以扩展到1*n   多色染色法

加上空间三维染色法,

图着色问题, 用尽可能少的颜色给图着色,

 

棋盘染色法(双色染色法)

原文:https://www.cnblogs.com/163467wyj/p/12142953.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!