Eight queens puzzle logic errors

Question

I am writing a program to recursively solve the eight queens puzzle, but I am having a hard time wrapping my head around how exactly i am supposed to make my program "backtrack" to solve the problem. My Solve() method and my isOpen() method are probably both erroneous, but I can't figure out what i'm doing wrong. I have my code below (and the driver). Sorry it's so long, but i'd appreciate it if I could get a couple of hints.

Note* the image icon is just a picture of Freddie Mercury

import java.io.*;
import java.util.Formatter;
import javax.swing.*;

import java.awt.*;

public class EightQueens extends JFrame {

// declare class constants as needed
final int BOARD_DIMENSION = 8;
final boolean[][] BOARD = new boolean[8][8];
// declare instance variables
PrintWriter output;
int backtrack;
int comparison;
File file;
// gui components
JPanel chessPanel;
JPanel square[];
Icon queenIcon;
JLabel imageLabel;

// constructor method
public EightQueens() throws FileNotFoundException {

    // gui stuff
    setTitle("8 Queens: Freddie Style");
    setPreferredSize(new Dimension(800, 800));
    chessPanel = new JPanel(new GridLayout(8, 8));
    chessPanel.setPreferredSize(new Dimension(100, 100));
    chessPanel.setBackground(Color.BLACK);
    square = new JPanel[64];
    queenIcon = new ImageIcon(getClass().getResource(
            "/resource/mercury.jpg"));
    JLabel imageLabel = new JLabel("", queenIcon, JLabel.CENTER);

    // CREATE AND INITIALIZE THE OUTPUT FILE
    file = new File("TraceQueens.txt");
    output = new PrintWriter(file);

    // CREATE AND INITIALIZE BOARD
    for (int i = 0; i < 8; i++)
        for (int j = 0; j < 8; j++)
            BOARD[i][j] = false;

    // add the squares to the chess panel
    for (int i = 0; i < square.length; i++)// adds chess squares to the
                                            // board
    {
        square[i] = new JPanel(new BorderLayout());
        square[i].setBackground(Color.BLACK);
        chessPanel.add(square[i]);
    }
    // this will make the squares the correct colors
    for (int i = 0; i < BOARD_DIMENSION; i = i + 2)
        square[i].setBackground(Color.WHITE);
    for (int i = BOARD_DIMENSION + 1; i < (2 * BOARD_DIMENSION)
            && i > BOARD_DIMENSION; i = i + 2)
        square[i].setBackground(Color.WHITE);
    for (int i = (2 * BOARD_DIMENSION); i < (3 * BOARD_DIMENSION)
            && i >= (2 * BOARD_DIMENSION); i = i + 2)
        square[i].setBackground(Color.WHITE);
    for (int i = (3 * BOARD_DIMENSION) + 1; i < (4 * BOARD_DIMENSION)
            && i > (3 * BOARD_DIMENSION); i = i + 2)
        square[i].setBackground(Color.WHITE);
    for (int i = (4 * BOARD_DIMENSION); i < (5 * BOARD_DIMENSION)
            && i >= (4 * BOARD_DIMENSION); i = i + 2)
        square[i].setBackground(Color.WHITE);
    for (int i = (5 * BOARD_DIMENSION) + 1; i < (6 * BOARD_DIMENSION)
            && i > (5 * BOARD_DIMENSION); i = i + 2)
        square[i].setBackground(Color.WHITE);
    for (int i = (6 * BOARD_DIMENSION); i < (7 * BOARD_DIMENSION)
            && i >= (6 * BOARD_DIMENSION); i = i + 2)
        square[i].setBackground(Color.WHITE);
    for (int i = (7 * BOARD_DIMENSION) + 1; i < (8 * BOARD_DIMENSION)
            && i > (7 * BOARD_DIMENSION); i = i + 2)
        square[i].setBackground(Color.WHITE);

    // puts the chess panel on the EightQueens frame
    add(chessPanel);

} // end constructor

// user interface method used to wrap the parameter representing the first
// column
public boolean solve() {
    return solve(0);
}

// recursive method solve

public boolean solve(int column) {

    // The Queen has been placed on the board in column
    int row = 0; 
    BOARD[row][column] = true;
    output.println("The queen has been placed at [0][" + column + "]");

    // if column is beyond the last column, then the problem is solved
    // base case
    for(int r = 0; r < BOARD_DIMENSION; r++); 
    if (column == BOARD_DIMENSION) {
        output.println("The problem has been solved");
        output.println("The program backtracked " + backtrack
                + " times and made " + comparison + " comparisons");

        // CLOSE FILE
        output.close();
        // RETURN TRUE
        return true;
    } else // attempt a solution from column
    {
        output.println("Attempting solution from column " + column);
        for (int i = 0; i < BOARD_DIMENSION; i++) {

            if (isOpen(i, column)) {
                BOARD[i][column] = true;
                comparison++;

                // solve the "rest of the board"
                if (solve(column + 1)) {
                    output.println("The queen has beel placed at [" + i
                            + "] + [" + column + "]");
                    square[((i * 2) + column)].add(imageLabel,
                            BorderLayout.CENTER);// this converts the 2-d
                                                    // array location into a
                                                    // single value to
                                                    // make it compatible with the gui representation of the
                                                    // board
                    return true;
                }

                else {

                    BOARD[i][column] = false;
                    output.println("the queen has been removed from ["+i+"]["+column+"]"); 
                }
            } else
                output.println("The queen cannot be placed at [" + i
                        + "][" + column + "]");
        }
        backtrack++;
        //output.close(); //This is for testing only
        return false;

        // return false to Backtrack to previous column since no squares in
        // current row will solve problem
    }
}

// Method to verify that the square is open.
public boolean isOpen(int row, int column) {
    {
        for (int i = 0; i < BOARD_DIMENSION; i++)// tests for the same row
        {
            if (BOARD[row][i] == true)
                return false;
        }

        for (int i = 0; i < BOARD_DIMENSION; i++)// test for the same column
        {
            if (BOARD[i][column] == true)
                return false;
        }

        for (int i = 0; i < BOARD_DIMENSION; i++)
            // test for diagonal down to the left
            while (row - 1 >= 0 && column - 1 >= 0) {
                if (BOARD[row - 1][column - 1] == true)
                    return false;
            }

        for (int i = 0; i < BOARD_DIMENSION; i++)
            // test for diagonal up to the left
            while (row + 1 < BOARD_DIMENSION && column - 1 >= 0)
                if (BOARD[row + 1][column - 1] == true)
                    return false;
    }
    return true;
}

// output the board
public void printBoard()// this is probably wrong, but
                        // I want to find my mistakes in
                        // the rest of the code before fixing it
{
    for (int i = 0; i < BOARD_DIMENSION; i++)
        for (int j = 0; j < BOARD_DIMENSION; j++) {
            if (BOARD[i][j] == false) {
                System.out.print("*");
                if (i == BOARD_DIMENSION - 1)
                    System.out.print("\n");
            }

            else
                System.out.print("Q");
        }

}

} // end class EightQueens

Driver:

import javax.swing.*;
import java.io.*;
import java.util.*;

public class EightQueensGame {
public static void main(String args[]) throws FileNotFoundException {
    EightQueens eightQueens = new EightQueens();

    eightQueens.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);
    eightQueens.pack();

    eightQueens.setVisible(true);//just for testing
    if (eightQueens.solve())
    {
        eightQueens.setVisible(true);
        eightQueens.printBoard();


    }

    else
        System.out.println("Sorry, there is no solution");
}
}

Answer 1

I made an implementation which is somewhat more OO than the already given and accepted answer. I do not claim that it's more efficient though, but the code is actually quite clean and easy to read. The most important part is the branch() method. But again, it's not optimized in any way, it's brute force, and the creation of objects etc makes it not the best implementation. Have a look at the branch() method, I think it's a very clean way of implementing the backtracking.

import java.util.ArrayList;
import java.util.List;


public class EightQueens {

    public static final int DIMENSION = 20;
    private Board board;

    public EightQueens() {
        board = new Board();
    }

    public void solve() {
        boolean result = branch(0);
        System.out.println(result);
        print();
    }

    private boolean branch(int level) {
        Queen queen = new Queen(level, 0);
        for (int y = 0; y < DIMENSION; y++) {
            queen.setY(y);
            if (board.add(queen)) { // true: adding succeeded. valid position
                if (board.getCount() == DIMENSION || branch(level + 1)) {
                    // cond1: we added the last queen at a valid position, so we're done here.
                    // cond2: not adding the last queen => check if there exists subsolution
                    return true;
                } else {
                    // branch with (level + 1) failed, so remove the queen and go further
                    board.remove(queen);
                }
            }
        }

        return false;
    }

    private void print() {

        for (int y = 0; y < DIMENSION; y++) {
            for (int x = 0; x < DIMENSION; x++) {
                System.out.print(board.queenOn(x, y) ? "x" : "-");
            }
            System.out.print("\n");
        }
    }

    public static void main(String[] args) {
        EightQueens queens = new EightQueens();
        queens.solve();
    }

    // helper objects: Board and Queen
    private class Board {

        private final List<Queen> queens;

        public Board() {
            queens = new ArrayList<Queen>();
        }

        public int getCount() {
            return queens.size();
        }

        public boolean add(Queen queen) {
            for (Queen q : queens) {
                // same row
                if (q.getX() == queen.getX())
                    return false;
                // same column
                if (q.getY() == queen.getY())
                    return false;
                // same diagonal
                if (Math.abs(q.getY() - queen.getY()) == Math.abs(q.getX() - queen.getX()))
                    return false;
            }
            queens.add(queen);
            return true;
        }

        public boolean queenOn(int x, int y) {
            for (Queen queen : queens) {
                if (queen.x == x && queen.y == y) {
                    return true;
                }
            }
            return false;
        }

        public void remove(Queen queen) {
            queens.remove(queen);
        }
    }

    private class Queen {
        private int x, y;

        public Queen(int x, int y) {
            this.x = x;
            this.y = y;
        }

        public int getX() {
            return x;
        }

        public int getY() {
            return y;
        }

        public void setX(int x) {
            this.x = x;
        }

        public void setY(int y) {
            this.y = y;
        }
    }
}

Remark #1: running this program with DIMENSION equal to 2 or 3 will print "false", and an empty board of the given dimension. Correct behavior, as there do not exist solutions for those dimensions.

Remark #2: this program only finds the first solution and does not continue to look for more solutions. But that's not the point of this answer of course.

Answer 2

You are over thinking the problem. I had to remove many of your code because it is redundant and can be achieved with more efficient way. check this google code repository : https://code.google.com/p/8queens/ for more methods other than backtracking. By the way, you violate the MVC rule here. you should have implemented the solver then the user interface, this way you can decide to change the view as you which.

EightQueensSolver.java

public class EightQueensSolver {

    final boolean[][] board ;
    final int[] queensPositions;

    public EightQueensSolver(int boardSize) {
        if(boardSize<4){
            throw new RuntimeException("Can not solve boards of size < 4");
        }
        board = new boolean[boardSize][boardSize];
        queensPositions = new int[boardSize];
    }

    boolean solve(){
        return solve(0);
    }

    boolean solve(int row){
        for(int col=0;col<board.length;col++){

            if(isSafe(row, col)){
                //place the queen for now in this spot
                board[row][col]=true;
                queensPositions[row] = col;
                //if we have finished the board, done.
                if(row==board.length-1) return true;
                //otherwise keep placing queens on next rows
                if(solve(row+1)){
                    //if placing the next queen will make the board solved, OK
                    return true;
                }else{
                    //otherwise backtrack and try other move
                    board[row][col]=false; 
                }
            }

        }
        return false;
    }

    boolean isSafe(int row,int col){
        //no need to test if on the same row, because we 
        //place a single queen on each row.
        //we only need to check if two queens are on 
        //same column or same diagonal
        for(int r=0;r<row;r++){
            for(int c=0;c<board.length;c++){
                if(board[r][c] && (c==col || Math.abs(c-col)==Math.abs(r-row))) 
                    return false;
            }
        }
        return true;
    }


    void printBoard(){
        System.out.println(Arrays.deepToString(board)
                .replace('[', '\n').replace("]", "")
                .replace("true", "Q").replace("false", " ")
        );
    }

    int getQueenColumnPosition(int row){
        return queensPositions[row];
    }
}

EightQueensUI.java

public class EightQueensUI extends JFrame {

    // gui components
    Icon queenIcon;
    JLabel imageLabel;
    EightQueensSolver solver;

    // constructor method
    public EightQueensUI(int boardSize) {
        super("8 Queens: Freddie Style");
        setPreferredSize(new Dimension(800, 800));
        getContentPane().setLayout(new GridLayout(boardSize, boardSize));
        queenIcon = new ImageIcon(getClass().getResource("circle.png"));
        solver = new EightQueensSolver(boardSize);

        solver.solve();

        for(int row=0;row<boardSize;row++){
            for(int col=0;col<boardSize;col++){
                JPanel panel = new JPanel(new BorderLayout());
                panel.setBackground( (col-row)%2 == 0 ? Color.BLACK : Color.WHITE);
                if(solver.getQueenColumnPosition(row)==col){
                    panel.add(new JLabel(queenIcon));
                }
                getContentPane().add(panel);
            }
        }

    } // end constructor

} // end class EightQueensUI

EightQueensGame.java

public class EightQueensGame {
    public static void main(String[] args) throws FileNotFoundException {
        EightQueensUI eightQueens = new EightQueensUI(8);

        eightQueens.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);
        eightQueens.pack();

        eightQueens.setVisible(true);//just for testing
        eightQueens.solver.printBoard();
    }
}

the output is

Q,  ,  ,  ,  ,  ,  ,  , 
 ,  ,  ,  , Q,  ,  ,  , 
 ,  ,  ,  ,  ,  ,  , Q, 
 ,  ,  ,  ,  , Q,  ,  , 
 ,  , Q,  ,  ,  ,  ,  , 
 ,  ,  ,  ,  ,  , Q,  , 
 , Q,  ,  ,  ,  ,  ,  , 
 ,  ,  , Q,  ,  ,  ,  

edit

i have made some modifications to the EightQueensSolver to make it a little more efficient by using a list instead of a matrix, thus improving the computation time a little bit for larger board sizes.

public class EightQueensSolver {

    final int[] queensPositions;

    public EightQueensSolver(int boardSize) {
        if(boardSize<4){
            throw new RuntimeException("Can not solve boards of size < 4");
        }
        queensPositions = new int[boardSize];
        Arrays.fill(queensPositions, -1);
    }

    boolean solve(){
        return solve(0);
    }

    boolean solve(int row){
        for(int col=0;col<queensPositions.length;col++){

            if(isSafe(row, col)){
                //place the queen for now in this spot
                queensPositions[row] = col;
                //if we have finished the board, done.
                if(row==queensPositions.length-1) return true;
                //otherwise keep placing queens on next rows
                if(solve(row+1)){
                    //if placing the next queen will make the board solved, OK
                    return true;
                }else{
                    //otherwise backtrack and try other move
                    queensPositions[row]=-1; 
                }
            }

        }
        return false;
    }

    boolean isSafe(int row,int col){
        //no need to test if on the same row, because we 
        //place a single queen on each row.
        //we only need to check if two queens are on 
        //same column or same diagonal
        for(int r=0;r<row;r++){
            int c = queensPositions[r];
            if(c==col || Math.abs(c-col)==Math.abs(r-row)) 
                return false;
        }
        return true;
    }


    void printBoard(){
        for(int row=0;row<queensPositions.length;row++){
            for(int col=0;col<queensPositions.length;col++){
                if(queensPositions[row]==col) System.out.print("Q,");
                else System.out.print(" ,");
            }
            System.out.println();
        }
    }

    int getQueenColumnPosition(int row){
        return queensPositions[row];
    }
}