• Post Reply Bookmark Topic Watch Topic
  • New Topic
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
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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.
 
author and iconoclast
Posts: 24207
46
Mac OS X Eclipse IDE Chrome
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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).
 
Consider Paul's rocket mass heater.
reply
    Bookmark Topic Watch Topic
  • New Topic