Improved Backtracking with nqueen

Question

I am implementing conflict-based backjumping with nqueen. I want to optimize my code especially in recursive call.

In short,backjumping is similar to backtracking and it uses conflict set. When checking failure, it stores the fail value in conflict set.When it needs to backtrack,it jumps from the conflict set and not as stack by stack like backtracking.

public class Backjumping {
int                             size;
List<Integer>                   columns;
int                             numberofplaces;
int                             numberofbacktracks;
HashMap<Integer, List<Integer>> conflict;
boolean                         noBreak = true;

Backjumping(int size) {
    this.size = size;
    columns = new ArrayList();
    conflict = new HashMap<>(size);
    for (int i = 0; i < size; i++) {
        conflict.put(i, new ArrayList<>());
    }
}


List place(int startRow) {
    if (columns.size() == size) {
        System.out.println("Solution Found! The board size was :" + size);
        System.out.println(numberofplaces + " total nodes assigned were made.");
        System.out.println(numberofbacktracks + " total backtracks were executed.");
        return this.columns;
    } else {
        for (int row = 0; row < size; row++) {
            if (isSafe(columns.size(), row)) {
                if (indexExists(columns, columns.size()))
                    columns.set(columns.size(), row);
                else
                    columns.add(columns.size(), row);

                numberofplaces += 1;
                return place(startRow);
            }
        }
        if (noBreak) {
            List<Integer> lastRowList = conflict.get(columns.size());
            numberofbacktracks += 1;

            List<Integer> key = new ArrayList<>();
            Counter<Integer> counts = new Counter<Integer>();
            lastRowList.forEach(i -> {
                if (!key.contains(i)) {
                    key.add(i);
                }
                counts.add(i);
            });

            Object[] keyContent = key.toArray();
            List<Integer> temp = new ArrayList<>();

            for (int i = 0; i < counts.size(); i++) {
                temp.add(counts.count((int) keyContent[i]));
            }

            Integer value = Collections.max(temp);
            int index = temp.indexOf(value);
            int lastRow = (int) keyContent[index];

            conflict.replace(columns.size(), new ArrayList<>());
            int previous_variable = columns.remove(lastRow);
            place(previous_variable);
        }
    }
    return this.columns;
}

private boolean isSafe(int cols, int rows) {

    for (int threatrow : columns) {
        int threatcol = columns.indexOf(threatrow);
        if (rows == threatrow || cols == columns.indexOf(threatrow)) {
            (conflict.get(cols)).add(threatcol);
            return false;
        } else if ((threatrow + threatcol) == (rows + cols) || (threatrow - threatcol) == (rows - cols)) {
            (conflict.get(cols)).add(threatcol);
            return false;
        }
    }
    return true;
}

public boolean indexExists(final List list, final int index) {
    return index >= 0 && index < list.size();
}

public static void main(String[] args) {
    System.out.println("Enter the size of board");
    Scanner sc = new Scanner(System.in);
    int n = sc.nextInt();
    Backjumping bj = new Backjumping(n);
    double start = System.currentTimeMillis();
    List cols = bj.place(2);
    double end = System.currentTimeMillis();
    System.out.println("Time to solve in second       = " + (end - start) * 0.001 + " s");
    System.out.print("Ths solution is : ");
    cols.forEach(i -> System.out.print(((int) i + 1) + ", "));
    System.out.println("\n\nPlotting CSP result on N_Queens board");
    System.out.println("......................................\n");
    bj.getBoardPic(n, cols);
}

public void getBoardPic(int size, List columns) {
    int[] cols = Ints.toArray(columns);

    int[][] matrix = new int[size][size];

    for (int a = 0; a < size; a++) {
        int j = cols[a];
        matrix[a][j] = 1;
    }

    for (int a = 0; a < size; a++) {
        for (int b = 0; b < size; b++) {
            if (matrix[b][a] == 1)
                System.out.print(" Q ");
            else
                System.out.print(" - ");
        }
        System.out.println();
    }
}
}

class Counter<T> {

final Map<T, Integer> counts = new HashMap<>();

public void add(T t) {
    counts.merge(t, 1, Integer::sum);
}

public int count(T t) {
    return counts.getOrDefault(t, 0);
}

public int size() {
    return counts.size();
}

}

Answer 1

I haven't look too much at your algorithm, however there's a few things that stand out that you might want to look at.

startRow

You're passing start row into place. The only time you use it is when you pass it into the recursive calls. Are you supposed to be using it to limit the scope of the search, or is it simply unnecessary?

noBreak

There's a similar issue with noBreak. You set it when constructing your class to true and nothing ever changes it. If it's unnecessary, then it allows you to remove the level of nesting in your if block if(noBreak, since it's always true and so always going to be executed.

isSafe

The body of both your if clauses is the same, really you're doing if(A|B|C|D), rather than if(A|B) else if(C|D). I'd combine the clauses to make it more obvious that this is the case.

range checking

The application doesn't seem to work when its size is 3 or less. Consider adding some validation on the input.

+= 1

It's unusual to see += 1, I'd expect ++.

Fields

Class fields are usually marked as private, you've left them as the default of package private. Naming also usually follows the standard camelCase convention, you seem to have mixed an matched between it and alllowercase which is less easy to read.

getBoardPic

It's naming suggests that it returns a picture of the board (possibly in a string), however it actually prints the board to the console. This is a bit misleading.