(UVA) Knights in FEN - Solution

I solved this problem by a simple brute force. I used Depth-First Search-like algorithm to try all the moves. Then, I registered the optimal solution among all solutions that I found.


import java.io.*;
import java.util.*;

class Main  {
    public static int[][] m = new int[5][5];
    public static int[][] model = {{1,1,1,1,1}, {0,1,1,1,1}, {0,0,2,1,1}, {0,0,0,0,1}, {0,0,0,0,0}};
    public static int moves = 0;
    public static int resultMoves = 1000000000;
    public static int[] vi = {-2,-2,2,2,-1,-1,1,1};
    public static int[] vj = {-1,1,-1,1,-2,2,-2,2};
       
    public static boolean checkStatusBoard() {
        for (int i = 0; i < 5; i++) {
            for (int j = 0; j < 5; j++) {
                if (m[i][j] != model[i][j]) {
                    return false;
                }
            }
        }
       
        return true;
    }
   
    public static void dfs(Coord blankSpace) {
        boolean checkStatus = checkStatusBoard();
        if (moves == 10 || checkStatus) {
            if (checkStatus && moves < resultMoves) {
                resultMoves = moves;
            }
            return;
        }
       
        for (int k = 0; k < 8; k++) {
            int nextI = blankSpace.i+vi[k];
            int nextJ = blankSpace.j+vj[k];
            if (nextI >= 0 && nextJ >= 0 && nextI < 5 && nextJ < 5) {
                moves++;
                m[blankSpace.i][blankSpace.j] = m[nextI][nextJ];
                m[nextI][nextJ] = 2;
               
                Coord newBlankSpace = new Coord(nextI, nextJ);
                dfs(newBlankSpace);

                m[nextI][nextJ] = m[blankSpace.i][blankSpace.j];
                m[blankSpace.i][blankSpace.j] = 2;
                moves--;
            }
        }
    }
       
    public static void process() throws NumberFormatException, IOException {   
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
       
        int numTests = Integer.parseInt(br.readLine());
        for (int i = 0; i < numTests; i++) {
            Coord blankSpace = new Coord();
            for (int j = 0; j < 5; j++) {
                String line = br.readLine();
                for (int k = 0; k < 5; k++) {
                    char c = line.charAt(k);
                    if (c == ' ') {
                        m[j][k] = 2; // blankSpace is number 2
                        blankSpace = new Coord(j, k);
                    }
                    else {
                        m[j][k] = c-'0';
                    }
                }
            }
      
            moves = 0;
            resultMoves = 100000000;
            dfs(blankSpace);
            if (resultMoves > 10) {
                System.out.println("Unsolvable in less than 11 move(s).");
            }
            else {
                System.out.println("Solvable in " + resultMoves + " move(s).");
            }
        }
       
        return;
    }
   
    public static void main(String[] args) throws NumberFormatException, IOException {
        Main m = new Main();
        m.process();

        System.exit(0);
    }
}

class Coord {
    int i;
    int j;
   
    public Coord() {
    }
   
    public Coord(int i, int j) {
        this.i = i;
        this.j = j;
    }
}