Coding for Interviews - N-Queens - Java

!nqueens_introduction.md

N-Queens solution using naive recursion.

We know all queens must be on distinct columns. Hence for each column recursively attempt each row, terminating if the current configuration with the current subset of columns is invalid.

Validity checking does not need to check if any columns overlap (by definition they do not); we only check if both conditions are false:

1. any rows overlap, placement[i] == placement[j], and
2. any queen lies on the same diagonal as another, Math.abs(i - j) == Math.abs(placement[i] - placement[j])

This is not the worst solution (the worst involves 64 choose 8 ~= 4 * 10^9!!), but not the best (a DFS graph search would do better). Indeed results show this code is too inefficient above n=14.

CodingForInterviewsNQueen.java

import java.util.Arrays;
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

class CodingForInterviewsNQueens {
    public static int[][] getPlacements(int n) {
        List<int[]> placements = new ArrayList<int[]>();
        int[] current = new int[n];
        getPlacements(current, 0, placements);
        return placements.toArray(new int[placements.size()][n]);
    }

    private static void getPlacements(int[] current, int currentCol, List<int[]> placements) {
        if (currentCol == current.length) {
            placements.add(Arrays.copyOf(current, current.length));
            return;
        }
        for (int i = 0; i < current.length; i++) {
            current[currentCol] = i;
            if (!isValid(current, currentCol)) {
                continue;
            }
            getPlacements(current, currentCol + 1, placements);
        }
    }

    private static boolean isValid(int[] placement, int currentCol) {
        for (int i = 0; i <= currentCol; i++) {
            for (int j = i + 1; j <= currentCol; j++) {
                if (placement[i] == placement[j])
                    return false;
                if (Math.abs(i - j) == Math.abs(placement[i] - placement[j]))
                    return false;
            }
        }
        return true;
    }

    public static void printPlacements(int[][] placements) {
        System.out.println(String.format(
            "Number of placements is %d",placements.length));
        for (int i = 0; i < placements.length; i++)
            System.out.println(String.format(
                "Placement %d: %s", i, Arrays.toString(placements[i])));
    }

    public static void main(String[] args) {
        printPlacements(getPlacements(8));
    }
}

n=8 output

Number of placements is 92
Placement 0: [0, 4, 7, 5, 2, 6, 1, 3]
Placement 1: [0, 5, 7, 2, 6, 3, 1, 4]
Placement 2: [0, 6, 3, 5, 7, 1, 4, 2]
Placement 3: [0, 6, 4, 7, 1, 3, 5, 2]
Placement 4: [1, 3, 5, 7, 2, 0, 6, 4]
Placement 5: [1, 4, 6, 0, 2, 7, 5, 3]
Placement 6: [1, 4, 6, 3, 0, 7, 5, 2]

timings

8:  Number of placements is 92 (0.7s)
9:  Number of placements is 352 (0.7s)
10: Number of placements is 724 (0.8s)
11: Number of placements is 2680 (0.9s)
12: Number of placements is 14200 (1.8s)
13: Number of placements is 73712 (8.7s)
14: Number of placements is 365596 (58.1s)