尐涏吧 关注:33贴子:12,566
  • 13回复贴,共1

4行9列单车擒马

只看楼主收藏回复

题目:
在4行9列格子里,红方一车与黑方一马任意放置,车方能否擒马。比如下图


IP属地:北京来自Android客户端1楼2020-09-09 21:12回复
    韧竹renzhu、Lucky·Roo、本格罗纳尔多. . . 被楼主禁言,将不能再进行回复
    方法论:
    考虑用图形式表达思考过程。
    以每一个局面为一个顶点,两个差一步的相邻局面之间连接一条边。目标是找到最终擒马局面。于是任务变成从初始局面开始,寻找一条轨迹通往最终局面。那么流程如下:
    1,找到一条从特定初始局面通往最终局面的轨迹,即:不限步数找到擒马方案(此步骤最重要也最难)
    2,由于1已经实现,所以做出的解法图是一个连通的有向图,且由于我们可以人为地排除掉圈(循环着法),所以解法图可以认为是一颗树。我们进而在这个树中,找到主干和主干上最开始的次数最多的顶点集(所有局面都能转化形成的一般局面集)。该局面集满足:可以轻易实现其中之一,且能按照顺序通往胜利。这个顶点集我们称为:第一节点组。
    3,研究第一节点组某一节点到终点的轨迹,并记其为第一节点组的末端节点an。
    4,研究第一节点组其他顶点通往an或后方节点的轨迹。将其按顺序记为a1,a2,..an-1
    5,树结构完成。


    IP属地:北京来自Android客户端5楼2020-09-09 21:45
    回复
      第一步,对于1楼局面,找到如下的非最优解法。
      车平5,马进3
      车进2,......
      1.马退1或马进2
      车平9或车平6控死
      2.马进1
      车平6,马进3(退2则车平8控死)
      车退1,马退2
      车退1,控死
      3.马进4
      车退1,马退3
      车退1,......
      3.1 马退1
      车平7,马进2
      车进1,马退1
      车进2,马进2
      车平6,控死
      3.2 马进1
      车平6,马退3(退2则车进1控死)
      车进2,......
      3.2.1 马进1
      车平8,马进3
      车平5,马退1
      车平6,马进3(退2则车退1控死)
      车退1,马退2
      车退1,控死
      3.2.2 马进2
      车平8,马退4
      车平5,马进6(进2则车平6控死)
      车平6,马退8
      车平3,马进6,
      车退1,马退5,
      车平4,马退3(退7则车进1,马进8,车进1,控死)
      车平5,马进1
      车平6,马退3
      车进1,马进2
      车进1,控死


      IP属地:北京来自Android客户端6楼2020-09-09 21:45
      回复
        第二步,在过程中总结发现:车与马隔行控制是可以轻易走出的,且能通往最终胜利。考虑到对称性和非平凡解,第一节点组就是如下三个局面。
        马在上或下边缘行的中路,肋道,37路。车与之形成田字。且该马方走。暂且不标顶点号。




        IP属地:北京来自Android客户端7楼2020-09-09 21:45
        回复
          第三步,
          由于第一节点组有3个点,所以n=3
          在第一步的解法中,涉及到图2,也就是马在肋道的情况。所以设图2为a3


          IP属地:北京来自Android客户端8楼2020-09-09 21:49
          回复
            通过分拆第一节点组其他两个局面和后方局面,得到第二节点


            IP属地:北京来自Android客户端9楼2020-09-09 21:50
            回复
              以及第三节点


              IP属地:北京来自Android客户端11楼2020-09-09 21:51
              回复
                不妨记第二节点和第三节点为b,c
                经过推演也可以发现第一节点组中,马在中路(记为a1)可以经过两步衍化为马在肋道的a3,马在37路(记为a2)可以经过两步衍化为第三节点,故而整体的解法图补全如下(补全后不是树)。


                IP属地:北京来自Android客户端13楼2020-09-09 22:04
                回复
                  首先说明从第一节点组an,即:马在肋道(7楼图2)通往终点的方法。
                  ………,马退2
                  车平7,马进4
                  车退1,马退5
                  车平6,………
                  此时形成了第二节点b(9楼对称图)
                  此时马只能退3或退7
                  如果退3,则车进1形成第三节点(11楼)。马进2,车进1,控死。
                  如果退7,则车方多一顿挫。车平5,马进9。车平4,马退7。车进1(形成第三节点),马进8。车进1,控死。


                  IP属地:北京来自Android客户端14楼2020-09-09 22:16
                  回复
                    接着说明第一节点组a1(马在中路边缘,7楼图1)到终点的轨迹。
                    ………,马退3
                    车退1,………
                    如果马退1,则车平6,马退3,车进1(形成第三节点车方胜)
                    如果马退5,则车平4(形成第二节点车方胜)
                    如果马退4,则车平4(形成第一节点车方胜)


                    IP属地:北京来自Android客户端15楼2020-09-09 22:19
                    回复
                      然后说明第一节点组a2(马在37路边缘,7楼图3)到终点的轨迹。
                      ………,马退1
                      车平6,马进3
                      车退1(形成第三节点车方胜)


                      IP属地:北京来自Android客户端16楼2020-09-09 22:21
                      回复
                        由于第一节点组a1,a2,a3局面可以轻易实现,所以车方必擒马。
                        以1楼图为例,解法如下:
                        由于马方必定顽强防守,所以直接奔着第一节点走
                        车进1,
                        此时1步变成a1…
                        ………,马进7
                        车进1,马进6(走向第一节点,否则输得更快)
                        车平6,………
                        此时红走了3步,形成第一节点…
                        以下按套路进行即可…
                        ………,马退8
                        车平3,马进6
                        车退1,马退5
                        车平4(形成第二节点),马退3
                        车平5,马进1
                        车平6,马退3
                        车进1(形成第三节点),马进2
                        车进1,控死
                        10步控死,11步吃马。


                        IP属地:北京来自Android客户端19楼2020-09-09 22:28
                        回复
                          ---END---


                          IP属地:北京来自Android客户端20楼2020-09-09 22:28
                          回复
                            PS:由灯神扩展4*10的格子问题。
                            目前研究结果为:不是全图可擒马,仅特殊局面巧胜。
                            拓展定义:马在边线且与某一侧边缘有4个及以上空位,车控田,该马走的局面为a1。马在边线且与某一侧边缘有3个空位,车控田,该马走的局面为a3。马在边线且与某一侧边缘只有2个空位,车控田,该马走的局面为a2。
                            容易看出,a2局面如同4*9中讨论的,仍然可以通往第三节点,是车必胜局面。但a1与a3则不然。
                            在4*9中,由于可以通过一系列走法形成第三节点,将马迫至角落,同时占了一条线的便宜。但是在4*10中的第三节点图多了一列(竖看为一行),马在第三节点处有位可逃,进而重新形成第一节点组的a1或a3情况,因而丧失了4*10格子第三节点到终点的通路。解法图不连通,擒马失败。


                            IP属地:北京来自Android客户端21楼2020-09-10 11:23
                            回复