CODEWITHSUNDEEP
algorithmcombinations
Juanillo
Juanillo

Reputation: 875

Algorithm to find out all the possible positions

I need an algorithm to find out all the possible positions of a group of pieces in a chessboard. Like finding all the possible combinations of the positions of a number N of pieces.

For example in a chessboard numbered like cartesian coordinate systems any piece would be in a position 

(x,y) where 1 <= x <= 8 and 1 <= y <= 8

I'd like to get an algorithm which can calculate for example for 3 pieces all the possible positions of the pieces in the board. But I don't know how can I get them in any order. I can get all the possible positions of a single piece but I don't know how to mix them with more pieces.

for(int i = 0; i<= 8; i++){
    for(int j = 0; j<= 8; j++){
        System.out.println("Position: x:"+i+", y:"+j);
    }
}

How can I get a good algoritm to find all the posible positions of the pieces in a chessboard?

Thanks.

Upvotes: 1

Views: 1265

Answers (3)

amit
amit

Reputation: 178461

You got 8x8 board, so total of 64 squares.
Populate a list containing these 64 sqaures [let it be list], and find all of the possibilities recursively: Each step will "guess" one point, and invoke the recursve call to find the other points.

Pseudo code:

choose(list,numPieces,sol):
   if (sol.length == numPieces): //base clause: print the possible solution
       print sol
       return
   for each point in list:
       sol.append(point) //append the point to the end of sol
       list.remove(point)
       choose(list,numPieces,sol) //recursive call
       list.add(point)  //clean up environment before next recursive call
       sol.removeLast()

invoke with choose(list,numPieces,[]) where list is the pre-populated list with 64 elements, and numPieces is the pieces you are going to place.

Note: This solution assumes pieces are not identical, so [(1,2),(2,1)] and [(2,1),(1,2)] are both good different solutions.

EDIT:
Just a word about complexity, since there are (n^2)!/(n^2-k)! possible solutions for your problem - and you are looking for all of them, any algorithm will suffer from exponential run time, so trying to invoke it with just 10 pieces, will take ~400 years
[In the above notation, n is the width and length of the board, and k is the number of pieces]

Upvotes: 3

ony
ony

Reputation: 13223

As I understand you should consider that some firgure may come block some potential position for figures that can reach them on the empty board. I guess it is the most tricky part. So you should build some set of vertexes (set of board states) that is reached from some single vertex (initial board state).

The first algorithm that comes to my mind:

Pre-conditions:

  • Order figures in some way to form circle.
  • Assume initial set of board states (S0) to contain single element which represents inital board state.

Actions

  1. Choose next figure to extend set of possible positions
  2. For each state of board within S(n) walk depth-first all possible movements that new board states and call it F(n) (frame).
  3. Form S(n+1) = S(n) ∪ F(n).
  4. Repeat steps till all frames of updates during whole circle pass will not be empty.

This is kind of mix breath-first and depth-first search

Upvotes: 0

Cybercartel
Cybercartel

Reputation: 12592

You can use a recursive algorithm to generate all possiblities:

void combine(String instr, StringBuffer outstr, int index)
{
    for (int i = index; i < instr.length(); i++)
    {
       outstr.append(instr.charAt(i));
       System.out.println(outstr);
       combine(instr, outstr, i + 1);
       outstr.deleteCharAt(outstr.length() - 1);
   }
}

combine("abc", new StringBuffer(), 0);

Upvotes: 0

Related Questions