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

# Diagonal in 2 Dim array

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
}

Thanks
• ###### 1. Re: Diagonal in 2 Dim array
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
Note that there are two diagonals.
• ###### 3. Re: Diagonal in 2 Dim array
I see that i have to increment x and y but i just can't see how.
• ###### 4. Re: Diagonal in 2 Dim array
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
Specifically for this problem. Its a bit complicated.
• ###### 6. Re: Diagonal in 2 Dim array
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
``````\$ 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
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
The diagonal is in fact the diagonals of a Queen on a chessboard.

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
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
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
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++)="*";
}``````