3
\$\begingroup\$

(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.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.