programming forums Java Mobile Certification Databases Caching Books Engineering Micro Controllers OS Languages Paradigms IDEs Build Tools Frameworks Application Servers Open Source This Site Careers Other Pie Elite all forums
this forum made possible by our volunteer staff, including ...
Marshals:
• Campbell Ritchie
• Jeanne Boyarsky
• Ron McLeod
• Paul Clapham
• Liutauras Vilda
Sheriffs:
• paul wheaton
• Rob Spoor
• Devaka Cooray
Saloon Keepers:
• Stephan van Hulst
• Tim Holloway
• Carey Brown
• Frits Walraven
• Tim Moores
Bartenders:
• Mikalai Zaikin

# Determining whether a queen can attack another piece

Ranch Hand
Posts: 36
• Number of slices to send:
Optional 'thank-you' note:
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

Ranch Hand
Posts: 409
• Number of slices to send:
Optional 'thank-you' note:
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
• Number of slices to send:
Optional 'thank-you' note:

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: 409
• Number of slices to send:
Optional 'thank-you' note:
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
• Number of slices to send:
Optional 'thank-you' note:

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: 409
• 1
• Number of slices to send:
Optional 'thank-you' note:
If you're checking them all by "brute force," couldn't you just:

Jim Hester
Ranch Hand
Posts: 36
• Number of slices to send:
Optional 'thank-you' note:

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
• Number of slices to send:
Optional 'thank-you' note:
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
• Number of slices to send:
Optional 'thank-you' note:
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: 409
• Number of slices to send:
Optional 'thank-you' note:
A little faster, on average. Makes a significant difference when something is repeated many, many times.