knightst.doc

来自「这是一个骑士周游java编程问题三维效果」· DOC 代码 · 共 61 行

                          ********************
								  Knight's Tour Problem
                          ********************
								  
								  
      Knight's Tour is one of the interesting Chess Board puzzle. The knight
      starts from any square and by knight's move it has to visit all the 
      squares in exactly 64 moves.
		
		
      If you use brute force method, examining all possible moves, you will
      soon encounter combinatorial explostion and the number of alternatives
      you have to examine becomes astronomical. Even the best supercomputer
      will be inadequte. What one needs is,  some heuristics which makes it
      possible to find the paths in reasonable time with reasonable resources.
		
		The heuristics I used is the following:
		
      If there are more than one possible next moves, choose among the next 
      moves which has the least ( > 0 )number of  legal next moves.
		
		When you use heuristics, usually you can not prove that you have got the
      best or optimal solution. With the above heuristics it so happens that
      out of 64 possible starting squares you succeed with 63. When you start
      with one particular square you fail ! In this case what is to be done
      is one has to backtrack and try another alternateive. When I originally
		thought of the heuristics I did not expect I would fail with only
      one square. So I am leaving the solution as it is.
		
		
      History
      I read about this problem some time around late sixites 
      in a Sunday magazine as a puzzle, and solved it, may be in
      10 minutes using an actual  chess board and noted down the path.
      Later I thougt I would write a general program to find the
      path from any starting position if it exists.
      I tried it sometime in late seventies on a CDC CYBER computer
      (Erlangen University) and could not examine moves 
      beyond 20-25 due to combinatorial explosion. (Since
      it was obvious that there would be combinatorial explosion
      I should not have  tried it in the first place. However I thought I might
      hit the right path in the first few alternatives, and may not
      have to store/examine all the alternatives. I did not succeed.)
      Without  heuristics such problems can not be tackled.
      Though I devised a heuristic solution, I did not code it since it
      was quite messy. I made another attempt in 1983 but abandoned it.
		These attempts used Fortran for coding.
*     
      20/4/98
      I decided you try the problem using Java. Object oriented 
      languages makes it really easy to tackle real world complexities.
      I could solve the entire problem in about 3 hours.
      Full credits to Java
      However it took couple of mores days to make it publishable.
*