Meaningless Drivel is fun!
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: 24193

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!