5
\$\begingroup\$

Place N amount of queens in such a way that none of them can attack each other.

import java.util.*;

public class NQueensRewrite {
    public static void main(String[] args) {
        Scanner input = new Scanner(System.in);
        System.out.println("Enter amount of queens");
        int n = input.nextInt();
        int[] board = new int[n];
        fillBoard(board);
        printBoard(board);
    }

    public static void fillBoard(int[] board) {
        int queens = 1;
        while (queens < board.length) {
            boolean validColumnFound = false;
            //Start from previous confirmed column or check all if valid column found in row
            for (int column = board[queens] + 1; column < board.length; column++) {
                if (isValid(column, queens, board)) {
                    board[queens] = column;
                    queens++;
                    validColumnFound = true;
                    break;
                }
            }
            //If no other valid column is found, then clear the row and go back to try another column
            if (!validColumnFound) {
                board[queens] = 0;
                queens--;
            }
        }
    }

    public static boolean isValid(int column, int row, int[] board) {
        //Check if any other row has the specified column
        for (int i = 0; i < row; i++) {
            if (board[i] == column) {
                return false;
            }

            //Check the differences bewteen the spaces if they are uniform (even)
            //If the difference between the column of ith row and column being checked is
            //the same as the difference between the current row and row being checked,
            //then some previous queen is diagnal to the current spot being checked
            if (Math.abs(board[i] - column) == Math.abs(i - row)) {
                return false;
            }
        }
        return true;
    }


    public static void printBoard(int[] board) {
        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board.length; j++) {
                if (board[i] == j) {
                    System.out.print("|Q");
                }
                else {
                    System.out.print("| ");
                }
            }
            System.out.println("|");
        }
    }
}
\$\endgroup\$
  • 2
    \$\begingroup\$ I've given answers to N-Queens questions before. A Java one and a C++ one. I don't know how well they would apply to your code, but they might be worth reading. There are surely other good answers on the site, too. \$\endgroup\$ – Veedrac May 11 '15 at 14:25
  • \$\begingroup\$ Follow-up question \$\endgroup\$ – 200_success Jun 1 '15 at 22:27
4
\$\begingroup\$

It took me a while to figure out your code. I have solved this problem a couple of times before, but found your code hard to read. In large part, because your variable names are misleading....

  • board is not a board, it is an array of int, with the value of the queen's column. I see the board as being a 2D matrix, you have it as a 1D array.
  • queens is not the number of queens, but the number of rows you have currently populated.

Then, your code is not as general-purpose as I was expecting.... Your code only ever finds solutions where the position (0,0) is a queen. Now, that's not to say that solutions with a queen there are wrong, but, are you sure? What if there is no solution with a queen in the corner....

If you know for sure there will be one, then you should at least document that..... if not, then it's a bug.

All in all, your code could use some more help to get it readable.

\$\endgroup\$
  • \$\begingroup\$ Ah I think I understand... What are some good resources or guidelines I could use to begin to write more readable code? \$\endgroup\$ – FabZeros May 12 '15 at 14:53

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.