Jim Hester

Ranch Hand

Posts: 36

posted 6 years ago

I'm working on a program to solve the n-queens problem, and am having trouble with determining whether a queen can attack another queen. For the problem, I assume that there is only 1 queen on each row, and they only move within that row to solve the problem. Thus, I can represent the locations of the queens with an array (int[] queens), where the position in the array is the row, and the value of the integer is the column. For example, queens[0] = 0 would mean the queen is in the top left corner of a board, and if there are 5 queens, queens[4] = 4 would indicate it's in the bottom right hand corner. I tried to make a simple problem below that just has a 5x5 board that sets the queens so they cannot attack each other. And I've narrowed down my problem to the "testAttack" method, but it's not working like I want it to. For that method, I assume that queens are not going to be in the same row, so the horizontal check would be redundant, so I'm just trying to implement the column check and the diagonal check.

Any help to improve the testAttack method would be helpful. thanks!

for reference, I also requested help here: http://www.java-forums.org/new-java/33235-determining-whether-queen-can-attack-another-piece.html#post147714

Any help to improve the testAttack method would be helpful. thanks!

for reference, I also requested help here: http://www.java-forums.org/new-java/33235-determining-whether-queen-can-attack-another-piece.html#post147714

Roger F. Gay

Ranch Hand

Posts: 408

posted 6 years ago

This is the first time I've ever heard of this problem, so forgive me if I'm being naive. Checking to see if the column is the same seems to be just a matter of seeing if the position value is equal, while an opportunity for a diagonal attack is one in which the absolute value of delta x and delta y are the same. So, what's the real point of building the algorithm? Are you trying to find the fastest method, or what? Should it gear up to large numbers of queens (so you need speed)?

Correlation does not prove causality.

Jim Hester

Ranch Hand

Posts: 36

posted 6 years ago

This one. The problem I'm working on actually has a minimum of 10 queens on a n x n board (where n is the number of queens). Needs to be able to ramp up to N queens where N can be a very large value. Thanks for your response.

Roger F. Gay wrote: Should it gear up to large numbers of queens (so you need speed)?

This one. The problem I'm working on actually has a minimum of 10 queens on a n x n board (where n is the number of queens). Needs to be able to ramp up to N queens where N can be a very large value. Thanks for your response.

Roger F. Gay

Ranch Hand

Posts: 408

posted 6 years ago

OK, and it's not difficult to notice that testing every possibility becomes computationally expensive very quickly. Wikipedia supplies some numbers: http://en.wikipedia.org/wiki/Eight_queens_puzzle

Is there a description of your testAttack method somewhere, so we can easily understand how you're logically approaching the problem without figuring it out for ourselves?

Is there a description of your testAttack method somewhere, so we can easily understand how you're logically approaching the problem without figuring it out for ourselves?

Correlation does not prove causality.

Jim Hester

Ranch Hand

Posts: 36

posted 6 years ago

well, I reworked the 'testAttack' by both renaming it so it's clear what it should be returning (it should return true if the queen on the row,column provided can attack another queen, otherwise it should return false) and b/c it wasn't testing in all 4 directions that a diagonal could exist. It's not elegant, but it should be a lot more straightforward. Unfortunately, it still finds collisions when it should return false, so I did something wrong.

Roger F. Gay wrote:OK, and it's not difficult to notice that testing every possibility becomes computationally expensive very quickly. Wikipedia supplies some numbers: http://en.wikipedia.org/wiki/Eight_queens_puzzle

Is there a description of your testAttack method somewhere, so we can easily understand how you're logically approaching the problem without figuring it out for ourselves?

well, I reworked the 'testAttack' by both renaming it so it's clear what it should be returning (it should return true if the queen on the row,column provided can attack another queen, otherwise it should return false) and b/c it wasn't testing in all 4 directions that a diagonal could exist. It's not elegant, but it should be a lot more straightforward. Unfortunately, it still finds collisions when it should return false, so I did something wrong.

Roger F. Gay

Ranch Hand

Posts: 408

Jim Hester

Ranch Hand

Posts: 36

Jim Hester

Ranch Hand

Posts: 36

Jim Hester

Ranch Hand

Posts: 36