You have an n×n game board. Some squares contain obstacles, except the left- and right-most columns which are obstacle-free. The left-most column is filled with your n pieces, 1 per row. Your goal is to move all your pieces to the right-most column as quickly as possible. In a given turn, you can move each piece N, S, E, or W one space, or leave that piece in place. A piece cannot move onto a square containing an obstacle, nor may two pieces move to the same square on the same turn. All pieces move simultaneously, so one may move to a location currently occupied by another piece so long as that piece itself moves elsewhere at the same time.
Given n and the obstacles, determine the fewest number of turns needed to get all your pieces to the right-hand side of the board.
5 ..... .x... ...x. ..x.. ..... 5 .x... .x... .x... .xxx. ..... 0
Case 1: 6 Case 2: 8