1 2 Previous Next 21 Replies Latest reply: Jan 14, 2011 4:34 PM by 796440 RSS

    Diagonal in 2 Dim array

    830771
      Hello,

      I have been trying to design a program that solves the NQueens problem using an ADT Line, Column and Diagonal.
      I don't know if you are familiar with this problem but this isn't the point.
      In designing the ADT Diagonal i'm having a little trouble finding an effective method that returns the diagonal within a position a[x][y].

      For instance,

      char a[][]=new char[8][8];

      public Diagonal(int x,int y){
      // traces the diagonal "*" that pass through the indexes x and y of the array
      }

      Any tips about this would be welcome.

      Thanks
        • 1. Re: Diagonal in 2 Dim array
          804650
          Are you asking how to find all the cells on the diagonal from a given point? Then you need to increment and/or decrement the x and y values accordingly.
          • 2. Re: Diagonal in 2 Dim array
            tschodt
            Note that there are two diagonals.
            • 3. Re: Diagonal in 2 Dim array
              830771
              I see that i have to increment x and y but i just can't see how.
              • 4. Re: Diagonal in 2 Dim array
                Kayaman
                Al'Hazrad wrote:
                I see that i have to increment x and y but i just can't see how.
                You don't know how to increment?
                • 5. Re: Diagonal in 2 Dim array
                  830771
                  Specifically for this problem. Its a bit complicated.
                  • 6. Re: Diagonal in 2 Dim array
                    tschodt
                    Al'Hazrad wrote:
                    Specifically for this problem. Its a bit complicated.
                    Huh?

                    when you decrease both x and y you move in the general direction of (0,0)
                    when you increase both x and y you move in the general direction of (7,7)
                    when you decrease x and increase y you move in the general direction of (0,7)
                    when you increase x and decrease y you move in the general direction of (7,0)
                    • 7. Re: Diagonal in 2 Dim array
                      tschodt
                      $ java Diagonal 3 6
                      java.awt.Point[x=0,y=3]
                      java.awt.Point[x=3,y=6]
                      java.awt.Point[x=1,y=4]
                      java.awt.Point[x=6,y=3]
                      java.awt.Point[x=2,y=5]
                      java.awt.Point[x=4,y=5]
                      java.awt.Point[x=5,y=4]
                      java.awt.Point[x=2,y=7]
                      java.awt.Point[x=7,y=2]
                      java.awt.Point[x=4,y=7]
                      • 8. Re: Diagonal in 2 Dim array
                        Kayaman
                        Al'Hazrad wrote:
                        Specifically for this problem. Its a bit complicated.
                        My facebook relationships are a bit complicated. Incrementing is not.

                        Would you care to explain what's so complicated about incrementing in this particular case?
                        • 9. Re: Diagonal in 2 Dim array
                          830771
                          The diagonal is in fact the diagonals of a Queen on a chessboard.

                          [http://www.uploadimage.co.uk/images/43808806854601838124.jpg]

                          I just can't find a proper algorithm to return the diagonals passing through a particular square in the board.
                          I'm not expecting you to give me the solution but just some tips so i could reach my own solution.

                          Thanks
                          • 10. Re: Diagonal in 2 Dim array
                            800268
                            Can you take a piece of paper, draw a checkerboard on it, pick a random square and then draw an X in all squares which are on the diagonal(s)?

                            If yes, write down in you own language in the smallest steps possible what makes you decide to put an X somewhere. Try to make the step in the form of "if square (4,4) is on a diagonal then square (?, ?) is on the diagonal as well". Then translate the steps to Java code (try to find a pattern so you can use a loop).

                            If no, get someone to explain to you in your own language what a diagonal is.
                            • 11. Re: Diagonal in 2 Dim array
                              796440
                              First, there seems to be some confusion in terminology here. You seem to be speaking of "diagonal" as a path that leads from any square outward through all the diagonally adjacent squares to the edge of the board. Others are speaking of +The Two Diagonals+ that run from one corner of the board all the way across to the other.

                              Are you in fact talking about the more general case I described first?

                              If so, then forget Java. I give you the square f4. Now, you tell me, what are all the squares that are on the 2 diagonals running through the square I gave you? How do you know that, how did you figure it out?
                              • 12. Re: Diagonal in 2 Dim array
                                830771
                                I guess this would do it
                                 public Diagonal(int x, int y) {
                                         int r=x;
                                         int t=y;
                                         
                                         //upper left diagonal
                                         while(r>0 && t>0 && r<board.size() && t<board.size()){
                                              board.boardAt(r--,t++)="*";
                                         }
                                    
                                         //down left diagonal     
                                         r=x,t=y;
                                         
                                         while(r>0 && t>0 && r<board.size() && t<board.size()){
                                              board.boarAt(r++,y--)="*";
                                         }
                                         
                                         //upper right diagonal
                                         r=x,y=t;
                                         
                                         while(r>0 && t>0 && r<board.size() && t<board.size()){
                                              board.boardAt(r--,t--)="*";
                                         }
                                         
                                         //down left diagonal
                                         r=x,t=y;
                                         
                                         while(r>0 && t>0 && r<board.size() && t<board.size()){
                                              board.boardAt(r++,t++)="*";
                                         }
                                • 13. Re: Diagonal in 2 Dim array
                                  796440
                                  Al'Hazrad wrote:
                                  I guess this would do it
                                  Don't guess. Test. Test it for corners, edges, and non-corner, non-edge squares. Hell, there are only 64 possible inputs, so test all of them.
                                  • 14. Re: Diagonal in 2 Dim array
                                    804650
                                    jverd wrote:
                                    Others are speaking of +The Two Diagonals+ that run from one corner of the board all the way across to the other.
                                    I wasn't!
                                    1 2 Previous Next