Results 1 to 14 of 14
Like Tree1Likes
  • 1 Post By JosAH

Thread: Eight Queens Problem (2)

  1. #1
    kaplis is offline Member
    Join Date
    May 2012
    Posts
    9
    Rep Power
    0

    Default Eight Queens Problem (2)

    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):

    Java Code:
     
    
    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);
            }
        }
    }
    Last edited by kaplis; 06-10-2012 at 09:27 AM.

  2. #2
    JosAH's Avatar
    JosAH is offline Moderator
    Join Date
    Sep 2008
    Location
    Voorschoten, the Netherlands
    Posts
    13,522
    Blog Entries
    7
    Rep Power
    20

    Default Re: Eight Queens Problem (2)

    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
    cenosillicaphobia: the fear for an empty beer glass

  3. #3
    kaplis is offline Member
    Join Date
    May 2012
    Posts
    9
    Rep Power
    0

    Default Re: Eight Queens Problem (2)

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

  4. #4
    JosAH's Avatar
    JosAH is offline Moderator
    Join Date
    Sep 2008
    Location
    Voorschoten, the Netherlands
    Posts
    13,522
    Blog Entries
    7
    Rep Power
    20

    Default Re: Eight Queens Problem (2)

    Quote Originally Posted by kaplis View Post
    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
    cenosillicaphobia: the fear for an empty beer glass

  5. #5
    JosAH's Avatar
    JosAH is offline Moderator
    Join Date
    Sep 2008
    Location
    Voorschoten, the Netherlands
    Posts
    13,522
    Blog Entries
    7
    Rep Power
    20

    Default Re: Eight Queens Problem (2)

    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
    Fubarable likes this.
    cenosillicaphobia: the fear for an empty beer glass

  6. #6
    kaplis is offline Member
    Join Date
    May 2012
    Posts
    9
    Rep Power
    0

    Default Re: Eight Queens Problem (2)

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

  7. #7
    JosAH's Avatar
    JosAH is offline Moderator
    Join Date
    Sep 2008
    Location
    Voorschoten, the Netherlands
    Posts
    13,522
    Blog Entries
    7
    Rep Power
    20

    Default Re: Eight Queens Problem (2)

    Quote Originally Posted by kaplis View Post
    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
    cenosillicaphobia: the fear for an empty beer glass

  8. #8
    kaplis is offline Member
    Join Date
    May 2012
    Posts
    9
    Rep Power
    0

    Default Re: Eight Queens Problem (2)

    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.

    Java Code:
    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();
        }
    }
    Last edited by kaplis; 06-17-2012 at 07:13 AM.

  9. #9
    JosAH's Avatar
    JosAH is offline Moderator
    Join Date
    Sep 2008
    Location
    Voorschoten, the Netherlands
    Posts
    13,522
    Blog Entries
    7
    Rep Power
    20

    Default Re: Eight Queens Problem (2)

    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:

    Java Code:
    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
    cenosillicaphobia: the fear for an empty beer glass

  10. #10
    kaplis is offline Member
    Join Date
    May 2012
    Posts
    9
    Rep Power
    0

    Default Re: Eight Queens Problem (2)

    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:

    Java Code:
    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...
    Last edited by kaplis; 06-18-2012 at 05:09 AM.

  11. #11
    JosAH's Avatar
    JosAH is offline Moderator
    Join Date
    Sep 2008
    Location
    Voorschoten, the Netherlands
    Posts
    13,522
    Blog Entries
    7
    Rep Power
    20

    Default Re: Eight Queens Problem (2)

    Quote Originally Posted by kaplis View Post
    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
    cenosillicaphobia: the fear for an empty beer glass

  12. #12
    kaplis is offline Member
    Join Date
    May 2012
    Posts
    9
    Rep Power
    0

    Default Re: Eight Queens Problem (2)

    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

  13. #13
    JosAH's Avatar
    JosAH is offline Moderator
    Join Date
    Sep 2008
    Location
    Voorschoten, the Netherlands
    Posts
    13,522
    Blog Entries
    7
    Rep Power
    20

    Default Re: Eight Queens Problem (2)

    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
    cenosillicaphobia: the fear for an empty beer glass

  14. #14
    kaplis is offline Member
    Join Date
    May 2012
    Posts
    9
    Rep Power
    0

    Default Re: Eight Queens Problem (2)

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

    Java Code:
    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);
        }
    Last edited by kaplis; 06-24-2012 at 05:03 AM.

Similar Threads

  1. Replies: 1
    Last Post: 05-30-2012, 05:45 AM
  2. The N Queens Problem
    By IAmDan in forum New To Java
    Replies: 1
    Last Post: 03-19-2012, 08:45 AM
  3. Eight Queens Problem
    By Jtrtoday in forum New To Java
    Replies: 6
    Last Post: 01-28-2012, 11:53 PM
  4. Need help with the Eight Queens game
    By kiregad in forum New To Java
    Replies: 11
    Last Post: 03-26-2010, 06:50 PM
  5. Pruning?? (N-Queens problem)
    By n00neimp0rtant in forum New To Java
    Replies: 1
    Last Post: 02-14-2010, 06:41 AM

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •