一笔画写“田”字的计算机求解

昨天室友让我一笔写“田”字，想了好久没有结果，百度一下，有如下定理：

一笔画的规律：
1．凡是由偶点组成的连通图，一定可以一笔画成。画时可以把任一偶点为起点，最后一定能以这个点为终点画完此图。

2．凡是只有两个奇点的连通图（其余都为偶点），一定可以一笔画成。画时必须把一个奇点为起点，另一个奇点终点。

3．其他情况的图都不能一笔画出。

注：与奇数（单数）条边相连的点叫做奇点；与偶数（双数）条边相连的点叫做偶点。

由于“田”字有4个奇点、5个偶点，因此，该字不可能一笔完成。

 

没事干就想写个小程序找下其解，根据对称性，分别从“田”字的顶点（四个角的点）、外边中间的点、和中心点出发，搜寻是否可以不重复遍历“田”字12条边的情况，根据运行结果找不到这样的笔法，也就是说按常规写法，一笔写不出“田”字。

 

从顶点出发的最好结果：走过9条边

从中间点出发的最好结果：走过10条边

从中心点出发的最好结果：走过9条边

 

搜寻过程的代码：

public void findWay(){
		boolean flag=true; //是否有解
		int cnt=0; //搜寻次数
		while(getLineValue()<12){
			currDirection=getNextDirection(); //寻找下一个方向
			while(currDirection==-1){
				cnt++;
				if(trace.empty()){
					System.out.println("no answer!");
					flag=false;
					break;
				}
				
				UnicursalNode tmp=trace.pop();
				updateLineValue(currPos,tmp.getCurrPos(),0);
				currPos=tmp.getCurrPos();
				currDirection=tmp.getCurrDirection();
				
				currDirection=getNextDirection();				
			}
			if(!flag)
				break;
			Point pt=new Point(currPos.getX(),currPos.getY());
			UnicursalNode node=new UnicursalNode(pt, currDirection);
			trace.push(node);
			currPos.move(currDirection, 2);
			updateLineValue(node.getCurrPos(), currPos,1);
			currDirection=0;			
		}
		System.out.println(trace+", cnt="+cnt);
	}

 

评论

1 楼 gurudk 2008-11-19  

有前途！