This week's giveaway is in the EJB and other Java EE Technologies forum.
We're giving away four copies of EJB 3 in Action and have Debu Panda, Reza Rahman, Ryan Cuprak, and Michael Remijan on-line!
See this thread for details.
The moose likes Java in General and the fly likes Determining whether a queen can attack another piece Big Moose Saloon
  Search | Java FAQ | Recent Topics | Flagged Topics | Hot Topics | Zero Replies
Register / Login


Win a copy of EJB 3 in Action this week in the EJB and other Java EE Technologies forum!
JavaRanch » Java Forums » Java » Java in General
Bookmark "Determining whether a queen can attack another piece" Watch "Determining whether a queen can attack another piece" New topic
Author

Determining whether a queen can attack another piece

Jim Hester
Ranch Hand

Joined: Sep 19, 2009
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

Joined: Feb 16, 2007
Posts: 349
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

Joined: Sep 19, 2009
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

Joined: Feb 16, 2007
Posts: 349
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

Joined: Sep 19, 2009
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

Joined: Feb 16, 2007
Posts: 349
If you're checking them all by "brute force," couldn't you just:

Jim Hester
Ranch Hand

Joined: Sep 19, 2009
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

Joined: Sep 19, 2009
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

Joined: Sep 19, 2009
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

Joined: Feb 16, 2007
Posts: 349
A little faster, on average. Makes a significant difference when something is repeated many, many times.

 
 
subject: Determining whether a queen can attack another piece
 
Similar Threads
Just wanted to share my code SudokuSolver !
Have board printed twice in second method. Board class.
Why does this recursion try each permutation?
2D array battleship
cleaner code