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

# Recursive array search

Greenhorn
Posts: 1
• Number of slices to send:
Optional 'thank-you' note:
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
Posts: 24207
46
• Number of slices to send:
Optional 'thank-you' note:
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
• Number of slices to send:
Optional 'thank-you' note:
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).

 Politics is a circus designed to distract you from what is really going on. So is this tiny ad: a bit of art, as a gift, that will fit in a stocking https://gardener-gift.com