N-Queens Problem: My Code Doesn't Work With n = 5, Sometimes Other n Too...

> while(totalAttacks() != 0) {

if totalAttacks is never 0 then it would hang, perhaps you need an additional exit condition here

objects -
I see what you mean, but I'm not sure what I might use as an exit condition besides that one. When have I exhausted all possible permutations? Plus it doesn't  explain why n = 5 doesn't return (0,2,4,1,3), which has totalAttacks = 0.

The more I test this code, the more I'm convinced that n > 12 do eventually find an answer, it just takes a really long time. So I'm revising my question: Why can't this code find an acceptable permutation for n = 5? And, is there anything I can do with this algorithm to speed it up for larger n? Thanks -supr

> Plus it doesn't  explain why n = 5 doesn't return (0,2,4,1,3), which has totalAttacks = 0.

have you verified totalAttacks() does return 0 for this case?
If you have then you need to check why that case is never reached.

objects-
I had never tried it with an explicit permutation, until now. I just checked it with permutation (0,2,4,1,3), and I get totalAttacks = 0, before I call optimize(). It does return the original permutation as the optimized one, so it is halting at totalAttacks = 0. But if I call it on a random permutation of n = 5, it still never halts. I'm going to include the whole Chessboard.java program, and the driver program, which may help you figure out whatever check I'm not making that keeps me in the while loop in optimize(). Thanks so far objects, I think we're gonna figure this baby out any time now. -supr

NQueens.java:

import java.io.*;

public class NQueens {
        public static void main(String args []) throws IOException {
                BufferedReader input = new BufferedReader(new InputStreamReader(System.in));
                while(true) {
                        System.out.print("Enter n, or zero to quit: ");
                        int n = Integer.parseInt(input.readLine());
                        if(n == 0)
                                System.exit(0);
                        Chessboard cb = new Chessboard(n);
                        cb.displayPerm();
                        for(int i = 0; i < n; i++)
                                System.out.print(cb.numAttacks(i) + " ");
                        System.out.println();
                        System.out.println(cb.totalAttacks());
                        cb.displayBoard();
                        cb.optimize();
                        System.out.println(cb.totalAttacks());
                        cb.displayPerm();
                        cb.displayBoard();
                        }
                }
        }



Chessboard.java:

public class Chessboard {
        static int [] board;
        static int n;

        public Chessboard(int size) {
                n = size;
                board = new int[n];
                fill();
                }

        public void usePerm(int a, int b, int c, int d, int e) {
                board[0] = a;
                board[1] = b;
                board[2] = c;
                board[3] = d;
                board[4] = e;
                }

        private void fill() {
                for(int i = 0; i < n; i++)
                        board[i] = i;

                for(int j = 0; j < n; j++)
                        swap(j, (int)(Math.random() * j));
                }

        private void swap(int a, int b) {
                int temp = board[b];
                board[b] = a;
                board[a] = temp;
                }

        public void displayPerm() {
                for(int i = 0; i < n; i++)
                        System.out.print(board[i] + " ");
                System.out.println();
                }

        public void displayBoard() {
                String line = "";
                for(int i = 0; i < n * 4 / 3 + 1; i++)
                        line += "---";
                line += "\n";

                for(int i = 0; i < n; i++) {
                        System.out.print("\n" + line + "| ");
                        for(int j = 0; j < n; j++)
                                if(board[i] == j)
                                        System.out.print("Q | ");
                                else
                                        System.out.print("  | ");

                        }
                System.out.println("\n" + line);
                System.out.println();

                }

        public int numAttacks(int i) {
                int attacks = 0;
                for(int j = 0; j < n; j++)
                        if(board[i]+i == board[j]+j || board[i]-i == board[j]-j)
                                attacks++;
                return --attacks;
                }

        public int totalAttacks() {
                int total = 0;

                for(int i = 0; i < n; i++)
                        total += numAttacks(i);

                return total;
                }

        public void optimize() {
                int iathen, ianow, jathen, janow;
                while(totalAttacks() != 0) {
                        for(int i = 0; i < n; i++) {
                                for(int j = i + 1; j < n; j++) {
                                        iathen = numAttacks(i);
                                        jathen = numAttacks(j);
                                        if(iathen != 0 && jathen != 0) {
                                                swap(i, j);
                                                ianow = numAttacks(i);
                                                janow = numAttacks(j);
                                                if(iathen < ianow && jathen < janow)
                                                        swap(i, j);
                                                }

                                        }
                                if(i == n - 1)
                                        fill();
                                }
                        }
                }

        }

Uh, I've just been printing out swaps and refills (new permutations), and I'm discovering that my swaps aren't doing anything, I'm just eventually refilling with the solution permutation. So, basically, my algorithm doesn't work at all, it simply halts when it randomly hits the right one. If anyone can help me figure out what it's doing wrong, I'd appreciate it -supr