Preferred ordering of directions:
The next step is to ask each dancer to state their desired locations. That is, each dancer decides the square he or she would like to occupy next. Usually this is to move into an adjacent square in one of his or her preferred directions, but if the dancer has already reached his or her goal then the dancer would simply prefer to stay put.
Often multiple dancers will want to occupy the same square. These conflicts need to be resolved.
To do this we sort the dancers by their priorities. Higher priorities are better; dancers who are far away from their goals (or made lots of unproductive moves) get to move before dancers who are close to their goals. Once sorted, iterate through the sorted dancer list.
For each dancer who has not been resolved already:
If the dancer's desired square has not been claimed by another dancer already, that square becomes claimed by the current dancer. If the square has already been claimed choose the next direction from the dancer's preferred ordering (above). Once an unclaimed square is found, claim it, and then repeat this process for the dancer who is currently occupying the claimed square. If no square can be claimed, backtrack to the last dancer who has another direction which can be tried.
In psuedo-python syntax:
def resolve( dancer ):
if dancer == nobody:
resolved = False
directions = dancer.get_preferred_directions()
for d in directions:
sq = dancer.get_square_in_direction( d )
sq.set_claimed_by( dancer )
occupant = sq.get_current_occupant()
if occupant == dancer:
resolved = True
resolved = resolve( occupant )
if not resolved:
sq.set_claimed_by( nobody )
dancer.set_resolved( resolved )
Once all the dancers have been resolved they all move into their claimed squares, and we go to the top of the loop. The algorithm terminates when all dancers reach their goal positions.
Of course, you will also need to make sure that two dancers don't collide with each other. That is an easy extension to this algorithm.