java - 为我的骑士之旅的前 32 步实施warndorffs 规则，然后使用堆栈和蛮力回溯

Question

我更改了代码，甚至从 0,0 开始进行骑士之旅，但自从我第一次遵守以来，我还没有让它工作，而且我对它第一次如何正确工作感到有点困惑时间。

样本输出：0 61 14 23 50 27 12 25 15 22 63 60 13 24 51 28 62 1 58 49 52 55 26 11 21 16 37 56 59 48 29 54 2 57 20 45 36 53 3 5 47 17 4 4 7 4 30 34 3 42 19 32 5 40 9 43 18 33 4 39 8 31 6

import java.util.Stack;
import java.util.concurrent.ThreadLocalRandom; 


public class KnightsTour {




    public static int N = 8;

    static Stack<KnightPiece> stackOfKnights = new Stack<KnightPiece>();

    public static int xMoves[] = {1, 1, 2, 2, -1, -1, -2, -2}; //these two arrays reflect the moves that are possible from the knight by subtracting or adding the value 
    public static int yMoves[] = {2, -2, 1, -1, 2, -2, 1, -1};


    static boolean validMove(int x, int y, int sol[][]) //Need to check if the possible spot im putting a knight on is inside the matrix and is not equal to -1
    { 
            if (x >= 0 && x < N && y >= 0 && y < N && sol[x][y] == -1)
            return true;
            else
            return false;
        } 

    static void printSolvedBoard(int sol[][]) // to easily print the solved board
    { 
        for (int x = 0; x < N; x++)  
        {
            System.out.println(); 
            for (int y = 0; y < N; y++) 
            {
                System.out.print(sol[x][y] + "    "); 
            }

        } 

    }


    static int getDegree(int board[][], int x, int y) 
    { 
        int count = 0; 
        for (int i = 0; i < N; i++) 
            if (validMove((x + xMoves[i]),(y + yMoves[i]), board))
            {
                count++; 
            }
        return count; 
    } 
    static KnightPiece Heurisitic(int board[][], KnightPiece knight)

    {

        int min_deg_idx = -1, c, min_deg = (N + 1), nx, ny; 


            int start = ThreadLocalRandom.current().nextInt(1000) % N; 
            for (int count = 0; count < N; ++count) 
            { 
                int i = (start + count) % N; 
                nx = knight.x + xMoves[i]; 
                ny = knight.y + yMoves[i]; 
                if ((validMove(nx, ny, board)) && 
                    (c = getDegree(board, nx, ny)) < min_deg) 
                { 
                    min_deg_idx = i; 
                    min_deg = c; 
                } 
            } 

            if (min_deg_idx == -1) 
                return null; 

            // Store coordinates of next point 
            nx = knight.x + xMoves[min_deg_idx]; 
            ny = knight.y + yMoves[min_deg_idx]; 

            // Mark next move 

            board[nx][ny] = board[knight.x][knight.y];

            // Update next point 
            knight.x = nx; 
            knight.y = ny; 

            return knight; 
    }

    public static void FindKnightsTour()
    {
        int board[][] = new int[N][N];
        int count = 0;

        int previousPop = -1;

        for (int x = 0; x < N; x++) //Making my chess board filling it with -1's as the place holder for not having a knight on it
                for (int y = 0; y < N; y++) 
                    board[x][y] = -1; 



        KnightPiece KnightS = new KnightPiece(0,0); //the "starting" position for the knight passed to it by the user

        stackOfKnights.push(KnightS);



        int startX = stackOfKnights.peek().getX();

        int startY = stackOfKnights.peek().getY();

        board[startX][startY] = count;




    while( count < 63)
        {   

        if(count < 31) // for the first 32 knights use warndorffs heuristic in order to choose coordinates for the knight piece
        {

            ;

            KnightPiece Knight = Heurisitic(board, stackOfKnights.peek());

            if (Knight != null)
            {


            stackOfKnights.push(Knight);

            int x = stackOfKnights.peek().getX();

            int y = stackOfKnights.peek().getY();

            count++;

            board[x][y] = count;

            }


        }
        else
        {
            count++;
            for (int k = 0; k < N; k++)
            {
                int newXmove = xMoves[k] + stackOfKnights.peek().getX();
                int newYmove = yMoves[k] + stackOfKnights.peek().getY();

                if(validMove(newXmove, newYmove, board) == true && (newXmove + newYmove) != previousPop)
                {
                    KnightPiece KnightN = new KnightPiece(newXmove,newYmove);

                    board[newXmove][newYmove] = count;
                    previousPop = -1;
                    stackOfKnights.push(KnightN);

                    break;
                }
                else if(k == 8)
                {
                    int removeX = stackOfKnights.peek().getX();
                    int removeY = stackOfKnights.peek().getY();

                    stackOfKnights.pop();

                    board[removeX][removeY] = -1;

                    previousPop = removeX + removeY;
                    count--;

                }
            }

        }


    }
    printSolvedBoard(board);
    }
static class KnightPiece //Knight object, has an x,y cordinate to reflect its spot on the board
{

    int x;
    int y;

    public KnightPiece(int x, int y)
    {
        this.x = x;
        this.y = y;
    }

    int getX()
    {
        return this.x;
    }
    int getY()
    {
        return this.y;
    }


}
public static void main(String args[]) { 
    FindKnightsTour(); 
} 

}

标签： javaknights-tour