(UVA) 8 Queens Chess Problem - Solution

Link to the problem: https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=691

The problem determines that all the possible positions for eight queens in a board 8x8 must be presented. For this reason, the solution below is using backtracking.


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

class Main {
    public static int[][] invalid;
    public static ArrayList<Integer> rows;
    public static HashMap<Integer, ArrayList<Integer>> rowPosition;
    public static int defRow;
    public static int defCol;
    public static int index;
    public static int[] vi = {-1,-1,-1,0,0,1,1,1};
    public static int[] vj = {-1,0,1,-1,1,-1,0,1};
  
    public static void rec(int col) {
        if (col == 9) {
            rowPosition.put(index++, (ArrayList<Integer>) rows.clone());
            return;
        }
      
        if (col == defCol) {
            rec(col+1);
        }
        for (int i = 1; i < 9; i++) {
            if (invalid[i][col] == 0) {
                validate(i, col, 1);
                rows.set(col, i);
                rec(col+1);
                validate(i, col, -1);
            }
        }
    }
  
    public static void validate(int row, int col, int incDec) {
        for (int i = 0; i < 8; i++) {
            for (int j = 0; j < 8; j++) {
                if (row+vi[i]*j < 1 || col+vj[i]*j < 1 || row+vi[i]*j >= 9 || col+vj[i]*j >= 9) {
                    continue;
                }
                invalid[row+vi[i]*j][col+vj[i]*j] += incDec;
            }
        }
    }
  
    public static void process() throws NumberFormatException, IOException {
        Scanner sc = new Scanner(System.in);
      
        int numTests = sc.nextInt();
        for (int i = 0; i < numTests; i++) {
            if (i > 0) {
                System.out.println();
            }
          
            defRow = sc.nextInt();
            defCol = sc.nextInt();

            invalid = new int[9][9];
            validate(defRow, defCol, 1);
          
            rows = new ArrayList<>();
            for (int j = 0; j < 9; j++) {
                rows.add(j);
            }
            rows.set(defCol, defRow);
            rowPosition = new HashMap<>();
            index = 0;
            rec(1);
          
            System.out.println("SOLN       COLUMN");
            System.out.println(" #      1 2 3 4 5 6 7 8\n");
            for (int j = 0; j < rowPosition.size(); j++) {
                System.out.printf("%2s", (j+1));
                System.out.print("      ");
                for (int k = 1; k < rowPosition.get(j).size()-1; k++) {
                    System.out.print(rowPosition.get(j).get(k) + " ");
                }
                System.out.println(rowPosition.get(j).get(rowPosition.get(j).size()-1));
            }
        }
                                      
        return;
    }
  
    public static void main(String[] args) throws NumberFormatException, IOException {
        Main m = new Main();
        m.process();
      
        System.exit(0);
    }
}