Skip to content

Instantly share code, notes, and snippets.

@Todd-Davies
Created August 15, 2016 08:44
Show Gist options
  • Save Todd-Davies/c9f3b2051274349401d914443445fe1b to your computer and use it in GitHub Desktop.
Save Todd-Davies/c9f3b2051274349401d914443445fe1b to your computer and use it in GitHub Desktop.
import java.util.Arrays;
public class Queens {
public static final int SIZE = 8;
public static void main(String[] args) {
int grid[][] = new int[SIZE][SIZE];
int soln[] = new int[SIZE];
nQ(grid, 0, soln);
}
static boolean place(int r, int c, int[][] grid) {
if (grid[r][c] != 0) {
return false;
} else {
grid[r][c] = 1;
fill(r, c, grid, true);
return true;
}
}
static void fill(int r, int c, int[][] grid, boolean place) {
for (int i = r + 1, j = 1; i < grid.length; i++, j++) {
grid[i][c] += place ? 2 : -2;
if (c - j >= 0) {
grid[i][c - j] += place ? 2 : -2;
}
if (c + j < grid.length) {
grid[i][c + j] += place ? 2 : -2;
}
}
}
static void nQ(int[][] grid, int r, int[] soln) {
for (int c = 0; c < soln.length; c++) {
if (place(r, c, grid)) {
soln[r] = c;
if (r == soln.length - 1) {
System.out.println(Arrays.toString(soln));
} else {
nQ(grid, r + 1, soln);
}
fill(r, c, grid, false);
grid[r][c] = 0;
}
}
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment