java实现马踏棋盘问题

1.问题描述:

　　在国际象棋中，马走日，用户输入棋盘的起始位置从x:0-4，y:0-3输出从这一点开始，马走完整个棋盘的各个方案，并输出方案数

2.输入样式:

　　请输入棋盘马起始位置:
　　0 0

3.输出样式:

1    4   17   12
   18   13    2    5
    3    8   11   16
   14   19    6    9
    7   10   15   20
==========================
    1    4   15   20
   14   19    2    5
    3    8   11   16
   18   13    6    9
    7   10   17   12
==========================

.......

4.解题思路:

　　　　我们用一个二维数组模拟马走的方向，通过函数move(x,y)，来达到马走。如果棋盘next_x>=0 && next_x<=4 && next_y>=0 && next_y<=3表示next_x,next_y在棋盘内，棋盘qipan[next_x][next_y] = = 0表示起盘没有走过，即下一步满足这些条件，则把下一步置为走过的状态，step++，调用move(next_x,next_y)函数，调用完再回溯。

5.代码实例:

package com.zzl;

import java.util.Scanner;

/**
*            1.问题描述在国际象棋中，马只能走日，但是马位于不同的方位可以走的方向有所区别
*                当马位于棋盘中间位置的时候
*
*
*/
public class 马踏棋盘问题求解 {
       //马能走的8个方向
   static int weizhi[][] = {{-2,1},{-2,-1},{-1,2},{-1,-2},{1,2},{1,-2},{2,1},{2,-1}};

   static int step = 1;//先走哪一步，步数
   static int qipan[][] = new int[5][4];
   static int count = 0;
   public static void main(String[] args) {
       //初始化棋盘
       for(int i=0;i<qipan.length;i++){
           for(int j=0;j<qipan[i].length;j++){
               qipan[i][j] = 0;
           }
       }
       //输入起始位置，起始位置从1,1开始算，计算机数组从0,0开始算，所以x--，y--；
       Scanner scn = new Scanner(System.in);
       System.out.println("请输入棋盘马起始位置:");
       int x = scn.nextInt();
       int y = scn.nextInt();

       qipan[x][y] = step;
       step++;
       move(x,y);
       System.out.println("共有" + count + "种方案");
   }
   public static void move(int x, int y) {
       int next_x = 0;
       int next_y = 0;
       if(step>20){
           for(int i=0;i<5;i++){
               for(int j=0;j<4;j++){
                   System.out.printf("%5d",qipan[i][j]);
               }
               System.out.println();
           }
           System.out.println("==========================");
           count ++;
           return;
       }else{
           for(int i=0;i<8;i++){
               next_x = x + weizhi[i][0];
               next_y = y + weizhi[i][1];

　　　　//下一步棋满足条件
               if(next_x>=0 && next_x<=4 && next_y>=0 && next_y<=3 && qipan[next_x][next_y] ==0){
                   qipan[next_x][next_y] = step;
                   step++;
                   move(next_x,next_y);
                   step--;
                   qipan[next_x][next_y] = 0;
               }
           }
       }
   }
}

巴特西

java实现马踏棋盘问题

最新文章

热门文章