Eight Queens Problem (2)

[kaplis]

I'm a new registered user so I suppose I cannot open a new topic yet. I need to understand why the following 8 queens program is wrong when displaying all the 92 solutions with JPanels. Only the same erroneous result is displayed 92 times while in the console window using System.out.print the results are correct (I think that the problem has to do with bad use of recursion techniques. Also I would like to know how to display all the results side by side with scroll pane. I tried all the possible ways without success. Thank you very much! Here is the code (from Liang's Java Book exercise):

 

import java.awt.*;
import java.util.ArrayList;
import javax.swing.*;

public class Exercise20_37 extends JFrame
{
    public static final int SIZE = 8; // The size of the chessboard
    private int[] queens = new int[SIZE]; // Queen positions

    private ArrayList eightQueensArrayList = new ArrayList();

    private int numberOfSolution;

    public Exercise20_37()
    {
        JPanel jPanelEightQueens = new JPanel();
        //JScrollPane jScrollPaneEightQueens = new JScrollPane();

        search(0); // Search for a solution from row 0

        for (int i = 0; i < eightQueensArrayList.size(); i++)
            jPanelEightQueens.add((JPanel) eightQueensArrayList.get(i));

        add(jPanelEightQueens);

        //jScrollPaneEightQueens.add(jPanelEightQueens);
        //add(jScrollPaneEightQueens);              //The scroll pane doesn't work. Why????

        System.out.println();
        System.out.print(numberOfSolution);
    }

    public static void main(String args[])
    {
        Exercise20_37 frame = new Exercise20_37();
        frame.setTitle("Exercise20_37");
        frame.setSize(300, 300);
        frame.setLocationRelativeTo(null); // Center the frame
        frame.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);
        frame.setVisible(true);
    }

    /**
     * Check if a queen can be placed at row i and column j
     */
    private boolean isValid(int row, int column)
    {
        for (int i = 1; i <= row; i++)
            if (queens[row - i] == column // Check column
                    || queens[row - i] == column - i // Check up-left diagonal
                    || queens[row - i] == column + i) // Check upright diagonal
                return false; // There is a conflict
        return true; // No conflict
    }

    /**
     * Search for a solution starting from a specified row
     */
    private boolean search(int row)
    {
        boolean find = false;

        if (row == SIZE)
        {
            numberOfSolution++;

            System.out.println();
            printResult(queens);

            JPanel jPanelEightQueensPanel = new JPanel(new BorderLayout());
            jPanelEightQueensPanel.add(new JLabel(numberOfSolution + ""), BorderLayout.NORTH);
            jPanelEightQueensPanel.add(new ChessBoard(), BorderLayout.CENTER);

            eightQueensArrayList.add(jPanelEightQueensPanel);   // display a solution
        } else
        {
            int column = 0;

            while (!find && column < SIZE)
            {
                if (isValid(row, column))
                {
                    queens[row] = column;
                    find = search(row + 1);
                }
                column++;
            }
        }
        return find;
    }

    public static void printResult(int[] queens)
    {
        for (int i = 0; i < 8; i++)
        {
            for (int j = 0; j < queens[i]; j++)
                System.out.print("| ");
            System.out.print("|Q|");

            for (int j = queens[i] + 1; j < 8; j++)
                System.out.print(" |");
            System.out.println();
        }
    }

    class ChessBoard extends JPanel
    {
        // private Image queenImage =
        //        new ImageIcon("image/queen.jpg").getImage();

        ChessBoard()
        {
            this.setBorder(BorderFactory.createLineBorder(Color.BLACK, 2));
        }

        protected void paintComponent(Graphics g)
        {
            super.paintComponent(g);

            // Paint the queens
            for (int i = 0; i < SIZE; i++)
            {
                int j = queens[i]; // The position of the queen in row i

                // g.drawImage(queenImage, j * getWidth() / SIZE,
                //        i * getHeight() / SIZE, getWidth() / SIZE,
                //       getHeight() / SIZE, this);

                g.drawString("Q", j * getWidth() / SIZE + 10,
                        i * getHeight() / SIZE + 20);
            }

            // Draw the horizontal and vertical lines
            for (int i = 1; i < SIZE; i++)
            {
                g.drawLine(0, i * getHeight() / SIZE,
                        getWidth(), i * getHeight() / SIZE);
                g.drawLine(i * getWidth() / SIZE, 0,
                        i * getWidth() / SIZE, getHeight());
            }
        }

        public Dimension getPreferredSize()
        {
            return new Dimension(250, 250);
        }
    }
}

[JosAH]

I moved your post to its own thread (there's a button near the top on the post listing page reading "Post New Thread"); never hijack someone else's thread.

kind regards,

Jos

[kaplis]

My deepest apologizes... I tried to find that button because my intention was to create a new topic before "hijacking" another thread thinking there was not that button because I was a new registered user. I'm going to be more cautelous... Really I'm feel embarrased and bad for what I did. Best regards!....

[JosAH]

My deepest apologizes... I tried to find that button because my intention was to create a new topic before "hijacking" another thread thinking there was not that button because I was a new registered user. I'm going to be more cautelous... Really I'm feel embarrased and bad for what I did. Best regards!....

No need to feel sorry, you're new to this forum after all; back to your question: do those 92 panels themselves show ok? Are only the solutions incorrect?

kind regards,

Jos

[JosAH]

I found your problem: you're using that queens array for all your solutions therefore destroying any previous solution that was stored in the array. Your Chessboard class should copy a current solution so that the copy can be displayed later.

kind regards,

Jos

[kaplis]

Thank you very much. I tried to create a copy of each solution in different forms and display it later with no results. Also the another problem pending is how to display all the solutions JPanels in a scroll pane.
I really appreciate your help. Thanks again...

[JosAH]

I tried to create a copy of each solution in different forms and display it later with no results.

All can say (given only this bit of information) is that you didn't do it the right way.

kind regards,

Jos

[kaplis]

This is an improved version with the help of a file that keep track of all the queen's movements.
The final problem again is how to display all the JPanel solutions in a JScrollPane.

import java.awt.*;
import java.util.Scanner;
import javax.swing.*;
import javax.swing.border.LineBorder;

public class Exercise20_37C extends JFrame {
    public static final int SIZE = 8; // The size of the chessboard
    private static int[] queens = new int[SIZE]; // Queen positions
    private static int solutionNumber;
    private java.io.PrintWriter output;
    private JPanel jPanel = new JPanel();

    public Exercise20_37C() {
        int counter = 0;
        int[] tempQueens = new int[SIZE];
        java.io.File file;
        try {
            file = new java.io.File("QueenPositions.txt");
            output = new java.io.PrintWriter(file);

            search(0); // Search for a solution from row 0

            System.out.println();
            System.out.print(solutionNumber + " solutions");

            output.close();

            Scanner input = new Scanner(file);
            int solutionCounter = 0;

            while (input.hasNext()) {
                tempQueens[counter] = input.nextInt();
                counter = (counter + 1) % SIZE;
                if (counter == 0) {
                    JLabel label = new JLabel("Solution " + ++solutionCounter);
                    label.setBorder(new LineBorder(Color.black, 2));
                    label.setHorizontalAlignment(SwingConstants.CENTER);
                    JPanel jPanelTemp = new JPanel(new BorderLayout());
                    jPanelTemp.add(label, BorderLayout.NORTH);
                    jPanelTemp.add(new ChessBoard(tempQueens), BorderLayout.CENTER);
                    jPanel.add(jPanelTemp);
                    tempQueens = new int[SIZE];
                }
            }
            input.close();
            add(jPanel);
        } catch (Exception ex) {
            System.out.println("IO error");
        }
    }

    public static void main(String args[]) {
        Exercise20_37C frame = new Exercise20_37C();
        frame.setTitle("Exercise20_37C");
        frame.setSize(600, 600);
        frame.setLocationRelativeTo(null); // Center the frame
        frame.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);
        frame.setVisible(true);
    }

    /**
     * Check if a queen can be placed at row i and column j
     */
    private boolean isValid(int row, int column) {
        for (int i = 1; i <= row; i++)
            if (queens[row - i] == column // Check column
                    || queens[row - i] == column - i // Check up-left diagonal
                    || queens[row - i] == column + i) // Check upright diagonal
                return false; // There is a conflict
        return true; // No conflict
    }

    /**
     * Search for a solution starting from a specified row
     */
    private void search(int row) throws Exception {
        if (row == SIZE) {
            solutionNumber++;
            System.out.println();
            System.out.println(solutionNumber);
            printResult(queens);
            createQueenPositionsDataFile(queens);

            for (int i = 0; i < queens.length; i++) {
                System.out.print(" " + queens[i]);
            }
            System.out.println();

        } else {

            int column = 0;

            while (column < SIZE) {
                if (isValid(row, column)) {
                    queens[row] = column;
                    search(row + 1);
                }
                column++;
            }
        }
    }

    static class ChessBoard extends JPanel {
        private int[] queen = new int[SIZE];
        //private Image queenImage =
        //        new ImageIcon("image/queen.jpg").getImage();

        public ChessBoard(int[] queen) {
            this.queen = queen;
            this.setBorder(BorderFactory.createLineBorder(Color.BLACK, 2));
        }

        protected void paintComponent(Graphics g) {
            super.paintComponent(g);

            // Paint the queens
            for (int i = 0; i < SIZE; i++) {
                int j = queen[i]; // The position of the queen in row i

                //g.drawImage(queenImage, j * getWidth() / SIZE,
                //        i * getHeight() / SIZE, getWidth() / SIZE,
                //        getHeight() / SIZE, this);

                g.drawString("Q", j * getWidth() / SIZE + 10,
                        i * getHeight() / SIZE + 20);
            }
            // Draw the horizontal and vertical lines
            for (int i = 1; i < SIZE; i++) {
                g.drawLine(0, i * getHeight() / SIZE,
                        getWidth(), i * getHeight() / SIZE);
                g.drawLine(i * getWidth() / SIZE, 0,
                        i * getWidth() / SIZE, getHeight());
            }
        }

        public Dimension getPreferredSize() {
            return new Dimension(250, 250);
        }
    }

    public void printResult(int[] queens) {
        for (int i = 0; i < SIZE; i++) {
            for (int j = 0; j < queens[i]; j++)
                System.out.print("| ");
            System.out.print("|Q|");

            for (int j = queens[i] + 1; j < SIZE; j++)
                System.out.print(" |");
            System.out.println();
        }
    }

    public void createQueenPositionsDataFile(int[] queens) throws Exception {
        for (int i = 0; i < SIZE; i++)
            output.print(queens[i] + " ");
        output.println();
    }
}

[JosAH]

I don't know what you're trying to do but you still don't copy the current solution in your ChessBoard class; make it like this:

class ChessBoard {
   private int[] queen; // copy of a solution
   public ChessBoard(int[] queen) {
      this.queen= Arrays.copyOf(queen, queen.length); // copy the solution
   }
   ...
}

kind regards,

Jos

[kaplis]

Thanks a lot. Using Arrays.copyOf() as you've suggested was the key that made the big difference because before I'd tried with a direct copy of each queens[] result in the ChessBoard constructor with the sentence this.queen = queen with fatal results. This is the corrected version:

import java.awt.*;
import java.util.ArrayList;
import java.util.Arrays;
import javax.swing.*;
import javax.swing.border.LineBorder;

public class Exercise20_37D extends JFrame {
    public static final int SIZE = 8; // The size of the chessboard
    private int[] queens = new int[SIZE]; // Queen positions
    private ArrayList<JPanel> eightQueensArrayList = new ArrayList<JPanel>();
    private int solutionNumber;

    public Exercise20_37D() {
        JPanel jPanelEightQueens = new JPanel();

        search(0); // Search for a solution from row 0

        System.out.println();
        System.out.print(solutionNumber + " solutions");

        for (JPanel i : eightQueensArrayList)
            jPanelEightQueens.add(i);

        add(jPanelEightQueens);
    }

    public static void main(String args[]) {
        Exercise20_37D frame = new Exercise20_37D();
        frame.setTitle("Exercise20_37D");
        frame.setSize(600, 600);
        frame.setLocationRelativeTo(null); // Center the frame
        frame.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);
        frame.setVisible(true);
    }

    /**
     * Check if a queen can be placed at row i and column j
     */
    private boolean isValid(int row, int column) {
        for (int i = 1; i <= row; i++)
            if (queens[row - i] == column // Check column
                    || queens[row - i] == column - i // Check up-left diagonal
                    || queens[row - i] == column + i) // Check upright diagonal
                return false; // There is a conflict
        return true; // No conflict
    }

    /**
     * Search for a solution starting from a specified row
     */
    private void search(int row) {
        if (row == SIZE) {
            solutionNumber++;

            System.out.println();
            System.out.println(solutionNumber);
            printResult(queens);

            JLabel jLabel = new JLabel(solutionNumber + "");
            jLabel.setBorder(new LineBorder(Color.black, 2));
            jLabel.setHorizontalAlignment(SwingConstants.CENTER);
            JPanel jPanelEightQueensPanel = new JPanel(new BorderLayout());
            jPanelEightQueensPanel.add(jLabel, BorderLayout.NORTH);
            jPanelEightQueensPanel.add(new ChessBoard(queens), BorderLayout.CENTER);

            eightQueensArrayList.add(jPanelEightQueensPanel);
        } else {
            int column = 0;

            while (column < SIZE) {
                if (isValid(row, column)) {
                    queens[row] = column;
                    search(row + 1);
                }
                column++;
            }
        }
    }

    public static void printResult(int[] queens) {

        for (int i = 0; i < SIZE; i++) {
            for (int j = 0; j < queens[i]; j++)
                System.out.print("| ");
            System.out.print("|Q|");

            for (int j = queens[i] + 1; j < SIZE; j++)
                System.out.print(" |");
            System.out.println();
        }

        for (int i : queens) {
            System.out.print(" " + i);
        }
        System.out.println();
    }

    class ChessBoard extends JPanel {
        private int[] queen;
        // private Image queenImage =
        //        new ImageIcon("image/queen.jpg").getImage();

        ChessBoard(int[] queen) {
            this.queen = Arrays.copyOf(queen, queen.length); // copy the solution
            this.setBorder(BorderFactory.createLineBorder(Color.BLACK, 2));
        }

        protected void paintComponent(Graphics g) {
            super.paintComponent(g);

            // Paint the <span class="highlight">queens</span>
            for (int i = 0; i < SIZE; i++) {
                int j = queen[i]; // The position of the queen in row i

                // g.drawImage(queenImage, j * getWidth() / SIZE,
                //        i * getHeight() / SIZE, getWidth() / SIZE,
                //       getHeight() / SIZE, this);

                g.drawString("Q", j * getWidth() / SIZE + 10,
                        i * getHeight() / SIZE + 20);
            }

            // Draw the horizontal and vertical lines
            for (int i = 1; i < SIZE; i++) {
                g.drawLine(0, i * getHeight() / SIZE,
                        getWidth(), i * getHeight() / SIZE);
                g.drawLine(i * getWidth() / SIZE, 0,
                        i * getWidth() / SIZE, getHeight());
            }
        }

        public Dimension getPreferredSize() {
            return new Dimension(250, 250);
        }
    }
}

By now I'm waiting how to display all the results in the JScrollPane...

[JosAH]

By now I'm waiting how to display all the results in the JScrollPane...

Waiting? The program doesn't wrirte itself and we are not going to do it for you. Describe what went wrong and what your program does instead.

kind regards,

Jos

[kaplis]

My excuses. I'm not a native English speaker. What I really wanted to say is that I'm waiting for someone who could give me a hint about the JScrollPane problem. I'm learning by myself how to program Java without any previous experience in programming reading different textbooks and trying to do all the exercises and until now the results have been very satisfactory, but sometimes I think some exercises surpass in excess my limited knowledge so I recurre to you. Believe me, I'm trying to do my best in order to solve alone the exercises and sometimes I spend hours, days or weeks solving only one exercise. I'm new in the world of forums so my apologizes. I promise that I'm not to talk more about me because I know this is a forum for discussing Java code issues. I'm going to be more specific from now on and to show Java's world community relevant issues.

kind regards,

Kaplis

[JosAH]

First try to display a single solution in your JPanel; if that works, all you have to do is build a 'slide show' of 92 JPanels; a JScrollPane is the way to go. The pane holds a single JPanel with a flow layout manager; it stores the other 92 panels.

kind regards,

Jos

[kaplis]

I've found the solution. Just adding jScrollPane.getViewport().setView(jPanelEightQueen s) method in Exercise20_37D constructor solved the problem:

public Exercise20_37D() {
        JPanel jPanelEightQueens = new JPanel();
        JScrollPane jScrollPane = new JScrollPane(); 
        jScrollPane.getViewport().setView(jPanelEightQueens);  

        search(0); // Search for a solution from row 0

        System.out.println();
        System.out.print(solutionNumber + " solutions");

        for (JPanel i : eightQueensArrayList)
            jPanelEightQueens.add(i);

        add(jScrollPane);
    }