Win a copy of Functional Reactive Programming this week in the Other Languages forum!

# Determining whether a queen can attack another piece

Jim Hester
Ranch Hand
Posts: 36
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

Roger F. Gay
Ranch Hand
Posts: 408
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)?

Jim Hester
Ranch Hand
Posts: 36
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
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?

Jim Hester
Ranch Hand
Posts: 36
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
• 1
If you're checking them all by "brute force," couldn't you just:

Jim Hester
Ranch Hand
Posts: 36
Roger F. Gay wrote:If you're checking them all by "brute force," couldn't you just:

I took this and created the method below, but it still isn't finding conflicts AND it's finding conflicts where it isn't supposed to (on row 3 of my test setup)... Any idea what I'm doing wrong?

>

Jim Hester
Ranch Hand
Posts: 36
never mind, found and corrected problem. First correction found the queen on the row I was checking. This one doesn't.

Jim Hester
Ranch Hand
Posts: 36
ok, it was failing to check for itself in the diagonals. Now it does. Works like a champ! Thanks, Roger!

Roger F. Gay
Ranch Hand
Posts: 408
A little faster, on average. Makes a significant difference when something is repeated many, many times.