(UVA) Back to the 8-Queens - Solution

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

For this problem, it is only necessary to try all the possible row positions for every queen in a column. The approach used was backtracking.


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

class Main {
    public static int[] rows;
    public static int[][] matrixAttacks;
    public static int maxUnchange;
    public static int unchange;
    //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 row, int indexRow, int col) {
        if (col == 9) {
            if (unchange > maxUnchange) {
                maxUnchange = unchange;
            }
            return;
        }
        if (indexRow-unchange > 8-maxUnchange) {
            return;
        }
       
        for (int i = 1; i <= 8; i++) {
            if (matrixAttacks[i][col] != 0) {
                continue;
            }
            if (i == row) {
                unchange++;
            }
            updateMatrix(i, col, 1);
            rec(rows[indexRow+1], indexRow+1, col+1);
            updateMatrix(i, col, -1);
            if (i == row) {
                unchange--;
            }
        }
    }
   
    public static void updateMatrix(int row, int col, int incDec) {
        for (int i = 1; i <= 8; i++) {
            matrixAttacks[i][col] += incDec;
        }
       
        for (int i = 1; i <= 8; i++) {
            matrixAttacks[row][i] += incDec;
        }
       
        for (int i = row, j = col; i <= 8 && j <= 8; i++, j++) {
            matrixAttacks[i][j] += incDec;
        }
       
        for (int i = row, j = col; i >= 0 && j <= 8; i--, j++) {
            matrixAttacks[i][j] += incDec;
        }
       
        for (int i = row, j = col; i <= 8 && j >= 8; i++, j--) {
            matrixAttacks[i][j] += incDec;
        }
       
        for (int i = row, j = col; i >= 0 && j >= 0; i--, j--) {
            matrixAttacks[i][j] += incDec;
        }
    }
   
    public static void process() throws NumberFormatException, IOException {
        Scanner sc = new Scanner(System.in);
       
        int numCase = 0;
        while (sc.hasNext()) {
            rows = new int[10];
            for (int i = 1; i <= 8; i++) {
                rows[i] = sc.nextInt();
            }
           
            matrixAttacks = new int[9][9];
           
            unchange = 0;
            maxUnchange = 0;
            rec(rows[1], 1, 1);
           
            System.out.println("Case " + ++numCase + ": " + (8-maxUnchange));
        }
                                       
        return;
    }
   
    public static void main(String[] args) throws NumberFormatException, IOException {
        Main m = new Main();
        m.process();
       
        System.exit(0);
    }
}