My first attempt gained about 98.8%.
The idea was:
- In each row move positive balls to even columns, and negative ones to odd columns. If there are several positive or negative balls with no balls of another sign between them, then try to unite them with one shot in the process. This would reduce total number of balls to deal with on step 2, and give other balls some space to move.
- For each column with positive balls, move them to the main diagonal (I used 2 vertical moves, if I used one, like sdssudhu, it would save about 50 moves per test case). Then get rid of negative balls on main diagonal.
- Push all positive balls on the main diagonal to the top left corner to finish.
To improve this result, I tried to put positive balls only in each 4th, 5th, etc column, and negative everywhere else. I thought that then there would be fewer moves to do to finish step 2, and also negative balls may not need to move so much.
Also, I wrote a separate procedure for the case of no negative balls, since in that case the solution is straightforward.
The best result was about 99.1% for every 5th column.
I also tried other orders of moves on steps 2 and 3, and one of my 99.1% solutions has positive balls in each 3rd column, they are pushed down to the bottom row, and then to the bottom right corner and out.
I was not able to improve it any further.