File APIs for Java Developers
Manipulate DOC, XLS, PPT, PDF and many others from your application.
The moose likes Beginning Java and the fly likes Recursive array search Big Moose Saloon
  Search | Java FAQ | Recent Topics | Flagged Topics | Hot Topics | Zero Replies
Register / Login
JavaRanch » Java Forums » Java » Beginning Java
Bookmark "Recursive array search" Watch "Recursive array search" New topic

Recursive array search

Jenna Williams

Joined: Aug 02, 2003
Posts: 1
Hi everyone. I have a problem and would like some help. I would ask that rather than post the whole solution, you gently nudge me in the right direction as I am trying very hard to learn java
Ok, here is the problem. I am working on an assignment for school which involves testing all possible positions on a board of a determined size that a chess queen can occupy without being able to take the other queens.
I have the array all set up and can print the board out. The first Queen always starts at [0][0] of the board array. Now, I need to place a queen in the next position and then test to see whether any other queens can take it. My original thoughts were to create 2 arrays that contain the x/y directions of the moves a queen can make
ie. xPos = {-1,-1,0,1,1,1,0,-1};
yPos = {0,-1,-1,-1,0,1,1,1};
then use these to step back through the array and test for a 'Q'.
This is where I get stuck, how can I utilize this or another solution in a recursive method. That is a condition of the assignment, I must use a recursive method to place and test the queens.
If anyone needs any more information from me please ask and thankyou for taking the time to read/reply.
Ernest Friedman-Hill
author and iconoclast

Joined: Jul 08, 2003
Posts: 24199

The problem you're working on is a well-known problem called the "N Queens Problem." The best hint I can give you is to go to Google and type in "N Queens". There are a dozen excellent links on the first page.
Another hint: try to solve the problem conceptually, before trying to solve it in Java. I.e., don't think in terms of "2-d arrays" first. Think in terms of a real chessboard, and looking and searching.
Final hint: many simple solutions to this problem are recursive -- i.e., they will use functions that call themselves.

[Jess in Action][AskingGoodQuestions]
David Weitzman
Ranch Hand

Joined: Jul 27, 2001
Posts: 1365
Note that if two queens are on the same row, they can kill each other. Thus they will all have different X (and Y) coordinates. Your recursive function can look for a place to put a queen in each row (or column).
I agree. Here's the link:
subject: Recursive array search
It's not a secret anymore!