许友军，刘若男，萧 焯

(南华大学 数理学院，湖南 衡阳，421001)

2017-07-28

湖南省自然基金项目(2015JJ2127)；中国国家自然基金项目(11126170)；湖南省普通高等学校教育教学改革项目(JG2014B048)；南华大学创新平台项目(5-2011-XQD-008)

许友军(1976-)，男，湖南永兴人，教授，博士，硕士生导师，从事偏微分方程、分布参数系统、数学建模与优化研究；E-mail1102568593@qq.com

1672-7010(2017)05-0008-06

棋盘设计五子连珠求解

许友军，刘若男，萧 焯

(南华大学 数理学院，湖南 衡阳，421001)

求解棋盘中满足五子不相连的情况下需取出的最少棋子数,采用回溯法和递归的思想，从特殊到一般、二维到三维，先得出6×7、13×17棋盘至少需要抽出8、44个棋子。然后在三维网格空间中，对网络的13个方向上进行0-1整数规划处理。最后通过Lingo求解得到所需的棋子数为55。

逻辑推理；Lingo编程；0-1规划

1 棋盘中五子不相连情况分析

对于在6×7的棋盘中，取出最少的棋子使得留着棋盘里的棋子不满足五子相连的条件，有点类似于国际象棋的八皇后[1]问题，先对五子相连中最基本的5×5棋盘进行分析，分析取出的棋子的位置分布状态，并进行逻辑推理。

在5×5棋盘中，最长的行、列和斜线上的棋子数目均为5，设第i行j列的棋子为aij,如果取走一个棋子aij，那么它对应的行、列和斜线上的棋子数目均不会达到5，这样就不用再考虑是否取aij的行、列和斜线上的棋子。

(1)首先将5×5棋盘放满25个棋子[2,3]，如图1:

图1 5×5棋盘 Fig.1 5×5 chessboard

(2)取出一个棋子a11，标出其所能影响的行列数目aij，图2为棋子a11的影响范围：

图2 棋子a11的影响范围 Fig.2 Influence range of chess piece a11

(3)再取出不受影响的棋子，将棋子a23，a35依次取出，得出其影响范围，如图……