Win a copy of Java EE 8 High Performance this week in the Java/Jakarta EE forum!
programming forums Java Mobile Certification Databases Caching Books Engineering Micro Controllers OS Languages Paradigms IDEs Build Tools Frameworks Application Servers This Site Careers Other all forums
this forum made possible by our volunteer staff, including ...
Marshals:
Sheriffs:
Saloon Keepers:
Bartenders:

# Recursive array search

Greenhorn
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.

author and iconoclast
Sheriff
Posts: 24217
38
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.

Ranch Hand
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).