Solve Eight Queens puzzle using Single Dimensional Array in Java

Question

The Eight Queens puzzle is to place eight queens on a chessboard so that no two queens can attack each other(i.e. no two queen are on the same row, same column or same diagonal). There are many solutions and one of them is : solutionImage

The solution has to be using one dimensional array. Can someone help me out with this?

Answer 1

If you have a one dimensional array you can use this method to use it as a bi-dimensional :

public Object getElement(int x, int y){
    return array[x+8*y];
}

From there you can use any method you want.

A good way to start is the fact that you know your queens can't be on the same line/column. From here you can easily do a relatively fast brute force algorithm.

Another way to start would the the usage of backtracking, you try to put your first queen on the first line/column, and you put the next queen to the nearest legal square, etc. Each time a queen can't be placed without breaking the rules, you go back and move your queen to the very next possible place.

---

Resources :

• Wikipedia - The eight queens puzzle as an exercise in algorithm design

Answer 2

Well use one dimensional array and convert it the fly to 2D coordinate using modulo...

Answer 3

Use an array to store the row positions of the queens for each column, let's say a[], then to check if you can put a queen in column x, row a[x], you need to check:

• That it's not in the same row that the previously placed queens: a[x] != a[i] for all i < x

• It's not in the same diagonal as previously placed queens: a[x]+x != a[i]+i && a[x]-x != a[i]-i for all i < x

This is slower that using a two dimensional array, of course.