# An iterator returning all possible solutions to n-queen problem in Java

(See the next iteration.)

Given a positive integer $n$, I have an iterator that returns all possible solutions to $n$-queens problem one by one:

QueenIterableV1.java:

package net.coderodde.fun;

import java.util.Iterator;
import java.util.NoSuchElementException;

/**
* This awesome class iterates over all possible arrangements of queens on a
* <code>n<sup>2</sup></code> chess board such that no queen offends another
* one.
*
* @author Rodion "rodde" Efremov
* @version 1.6 (Feb 23, 2016)
*/
public class QueensIterableV1 implements Iterable<Queens> {

private final int dimension;

public QueensIterableV1(int dimension) {
if (dimension < 1) {
throw new IllegalArgumentException(
"Requested dimension is not a positive integer: " +
dimension + ".");
}

this.dimension = dimension;
}

@Override
public Iterator<Queens> iterator() {
return new QueensIterator();
}

private final class QueensIterator implements Iterator<Queens> {

private final int[] state = new int[dimension];
private int stackSize;
private Queens next;

QueensIterator() {
state[0] = -1;
push(-1);
solve();
}

@Override
public boolean hasNext() {
return next != null;
}

@Override
public Queens next() {
if (!hasNext()) {
throw new NoSuchElementException("Iteration exceeded.");
}

Queens ret = next;
solve();
return ret;
}

private int size() {
return stackSize;
}

private void push(int i) {
state[stackSize++] = i;
}

private int pop() {
return state[--stackSize];
}

private int peek() {
return state[stackSize - 1];
}

private boolean isSafePosition(int x, int y) {
// Check upwards.
for (int yy = y - 1; yy >= 0; --yy) {
if (state[yy] == x) {
return false;
}
}

// Check in diagonal (up and to the left).
for (int yy = y - 1, xx = x - 1; yy >= 0 && xx >= 0; --xx, --yy) {
if (state[yy] == xx) {
return false;
}
}

// Check in diagonal (up and to the right).
for (int yy = y - 1, xx = x + 1;
yy >= 0 && xx < dimension;
++xx, --yy) {
if (state[yy] == xx) {
return false;
}
}

return true;
}

private void solve() {
mainLoop:
while (size() > 0) {
int stackSize = size();
int y = stackSize - 1;

for (int x = peek() + 1; x < dimension; ++x) {
state[y] = x;

if (isSafePosition(x, y)) {
if (stackSize == dimension) {
next = new Queens(state);
return;
}

push(-1);
continue mainLoop;
}
}

pop();
}

next = null;
}
}
}


Queens.java:

package net.coderodde.fun;

/**
* This class represents a feasible layout of queens in a <code>n</code>-queens
* problem.
*
* @author Rodion "rodde" Efremov
* @version 1.6 (Feb 23, 2016)
*/
public class Queens {

private final int[] layout;

Queens(int[] layout) {
this.layout = layout.clone();
}

public int getSize() {
return layout.length;
}

public int[] getRepresentationArray() {
return layout.clone();
}

@Override
public String toString() {
StringBuilder sb = new StringBuilder();
String horizontalBar = getHorizontalBar();
sb.append(horizontalBar);

for (int y = 0; y < layout.length; ++y) {
sb.append(getRow(layout[y]));
sb.append(horizontalBar);
}

return sb.toString();
}

private String getRow(int x) {
StringBuilder sb = new StringBuilder().append("|");

for (int i = 0; i < layout.length; ++i) {
sb.append((i == x) ? " Q |" : "   |");
}

return sb.append('\n').toString();
}

private String getHorizontalBar() {
StringBuilder sb = new StringBuilder().append('+');

for (int i = 0; i < layout.length; ++i) {
sb.append("---+");
}

return sb.append('\n').toString();
}
}


Demo.java:

package net.coderodde.fun;

public class Demo {

public static void main(String[] args) {
int n = 8;
int count = 0;

if (args.length > 0) {
n = Integer.parseInt(args[0]);
}

Iterable<Queens> iterable = new QueensIterableV1(n);

if (args.length > 1) {
for (Queens queens : iterable) {
System.out.println("Board " + (++count) + ":");
System.out.println(queens);
}
}

long startTime = System.nanoTime();
count = 0;

for (Queens queens : iterable) {
++count;
}

long endTime = System.nanoTime();

System.out.printf("Duration: %d milliseconds.\n",
(endTime - startTime) / 1_000_000);
System.out.println(count + " boards generated.");
}
}


Critique request

As usual, tell me anything that comes to mind. However, it would be nice if you would not review the actual algorithm as I want to play with it a little bit myself.