I've solved the N Queens problem to return an ArrayList that holds all the possible solutions.
I know that the algorithm itself is correct because it prints the correct solutions out. However, when I iterate through the returned ArrayList, I don't see the correct solutions. I just see empty grids (i.e. 4 rows of 0s).
Could anyone tell me why I'm printing the correct answers in the program but they're not correctly being added to the ArrayList?
Here's my code to give context, but you should really pay attention to the first if statement in queens() where printGrid() prints the correct solution which I (assumedly) add to my list. However, when I iterate through the list in the main method, I get 0s.
public class Question {
static int GRID_SIZE = 4;
public static ArrayList<int[][]> queens(int[][] grid) {
ArrayList<int[][]> list = new ArrayList<int[][]>();
queens(grid, 0, list);
return list;
}
public static void queens(int[][] grid, int row, ArrayList<int[][]> list) {
// if you reached the end of the grid successfully
if (row == GRID_SIZE) {
//print grid - shows correct solution
printGrid(grid);
//adding correct solution to list?
list.add(grid);
}
else {
//iterate through columns
for (int i = 0; i < GRID_SIZE; i++) {
// check if the spot is free
if (valid(grid, row, i)) {
// place queen
grid[row][i] = 1;
// move onto next row
queens(grid, row + 1, list);
//backtrack if placement of queen does not allow successful solution
grid[row][i] = 0;
}
}
}
}
// need to check previous rows to see if it's safe to place queen
public static boolean valid(int[][] grid, int row, int col) {
// check columns of each previous row
for (int i = 0; i < row; i++) {
if (grid[i][col] == 1) {
return false;
}
}
// check left diagonal
int rowNum = row;
int colNum = col;
while (rowNum >= 0 && colNum >= 0) {
if (grid[rowNum--][colNum--] == 1) {
return false;
}
}
// check right diagonals
rowNum = row;
colNum = col;
while (rowNum >= 0 && colNum < GRID_SIZE) {
if (grid[rowNum--][colNum++] == 1) {
return false;
}
}
return true;
}
public static void printGrid(int[][] grid) {
System.out.println("---------");
for (int i = 0; i < grid.length; i++) {
for (int j = 0; j < grid.length; j++) {
System.out.print(grid[i][j] + " ");
}
System.out.println();
}
System.out.println("---------");
}
public static void main(String[] args) {
int[][] grid = new int[GRID_SIZE][GRID_SIZE];
for (int i = 0; i < grid.length; i++) {
for (int j = 0; j < grid.length; j++) {
grid[i][j] = 0;
}
}
ArrayList<int[][]> list = queens(grid);
System.out.println(list.size());
printGrid(list.get(0));
}
}
Here's the output:
---------
0 1 0 0
0 0 0 1
1 0 0 0
0 0 1 0
---------
---------
0 0 1 0
1 0 0 0
0 0 0 1
0 1 0 0
---------
ITERATING THROUGH ARRAYLIST:
---------
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
---------
---------
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
---------
You only have one array instance which you keep mutating and add it to the List multiple times. At the end, the List contains references to that single array in its final state.
Instead of list.add(grid); you should be adding a copy of grid (note that Arrays.copyOf() or System.arraycopy() won't be enough here, since they perform shallow copy and your array is 2 dimentional).