一道有趣的、老少皆宜的“迷宫”题

gxqcn 发表于 2007-12-28 08:25:57

<TABLE class=t_table cellSpacing=0 cellPadding=0>
<TBODY>
<TR>
<TD>    如右图，为一个 5x5 的正方形，但被“挖”去了一格（已用“<FONT color=#ff0000>■</FONT>”标记），还剩 24 格。<BR>    从这 24 格中任选之一开始，请在最短的时间内连续遍历余下的方格。<U>要求</U>：<B>不重、不漏、不跳格、不走斜线</B>。<BR><IMG height=10 src="http://www.emath.ac.cn/image/bbs/line.gif" width=494 vspace=4 border=0> <BR><FONT color=#ff0000><B>注：</B></FONT>
<UL type=square>
<LI>该问题是我根据一“江湖骗子”的题目改编（1996 年春节期间）——版权归我个人所有！：）
<LI>该问题老少皆宜，大家不妨一试，并可推荐给亲朋好友。
<LI>当该贴点击次数在 40 次以上时，我将公布答案。</LI></UL></TD>
<TD width=125>
<TABLE style="BORDER-RIGHT: rgb(255,0,0) 2px dotted; BORDER-TOP: rgb(255,0,0) 2px dotted; BORDER-LEFT: rgb(255,0,0) 2px dotted; BORDER-BOTTOM: rgb(255,0,0) 2px dotted" borderColor=#0000ff height=120 cellSpacing=2 cellPadding=0 width=120 align=right border=2>
<COLGROUP>
<COL span=5 align=middle width="20%">
<TBODY>
<TR>
<TD></TD>
<TD></TD>
<TD></TD>
<TD></TD>
<TD></TD></TR>
<TR>
<TD></TD>
<TD></TD>
<TD></TD>
<TD></TD>
<TD></TD></TR>
<TR>
<TD></TD>
<TD></TD>
<TD></TD>
<TD></TD>
<TD></TD></TR>
<TR>
<TD></TD>
<TD></TD>
<TD align=middle bgColor=#ff0000></TD>
<TD></TD>
<TD></TD></TR>
<TR>
<TD></TD>
<TD></TD>
<TD></TD>
<TD></TD>
<TD></TD></TR></TBODY></TABLE></TD></TR></TBODY></TABLE>
这个题目不难，具体解答以及该问题的背景请浏览我2001/10/11发在<A href="http://club.xilu.com/rd/msgview-950394-161.html" target=_blank>老“数学研发论坛”上的帖子</A>

风云剑 发表于 2007-12-28 13:21:24

貌似无解啊！

风云剑 发表于 2007-12-28 13:22:02

如果这个程序没有BUG，那么无解

/*
如右图，为一个 5x5 的正方形，但被“挖”去了一格（已用“■”标记），还剩 24 格。
从这 24 格中任选之一开始，请在最短的时间内连续遍历余下的方格。要求：不重、不漏、不跳格、不走斜线。

EEEEE
EEEEE
EEEEE
EEOEE
EEEEE

*/

#include <iostream>

using namespace std;

long dir[]={-1, 1, -7, 7};
long map[]=
{
1, 1, 1, 1, 1, 1, 1,
1, 0, 0, 0, 0, 0, 1,
1, 0, 0, 0, 0, 0, 1,
1, 0, 0, 0, 0, 0, 1,
1, 0, 0, 1, 0, 0, 1,
1, 0, 0, 0, 0, 0, 1,
1, 1, 1, 1, 1, 1, 1,
};
long count;
long way;

void go(long pos)
{
if(map != 0)
{
   return;
}

map=1;
way=pos;
count++;
if(count == 24)
{
   cout << "Find a way!" << endl;
}

for(long i=0; i < 4; i++)
{
   go(pos + dir);
}

count--;
map=0;
}

int main()
{
for(long i=0; i < 49; i++)
{
   count=0;
   go(i);
}

return 0;
}

gxqcn 发表于 2007-12-28 13:30:09

这确实是个无解的问题，在原贴上已有证明（证明过程亦通俗易懂），难得楼上用编程去验证。:)

mathe 发表于 2007-12-28 18:36:00

呵呵，应该增加正方形的大小，计算机估计就不行了:lol

页: [1]

数学研发论坛's Archiver

一道有趣的、老少皆宜的“迷宫”题

如果这个程序没有BUG，那么无解