За един Алгоритъм и Java

Много интересна задача:
Трябва да се напише Мравка. Която да намира най-краткия път между две точки в 2Д Пространство.
Мравката може да се движи с по една стъпка напред  int[][] board  =                                                                                                            {0, 0, 0, 0}
                                                                                                           {0, 0, 0, 0}
                                                                                                           {0, 0, 0, 0}
                                                                                                            {0, 0, 0, 0};
Щом мравката стъпи на поле, където може да избира къде да стъпи, и си избира произволно нa къде да отиде. И маркира броя на стъпките. И след това си правя още толкова нови мравки колкото са полетата за избор ( по дъската има препятствия ). Щом мравката няма възможност за движение "умира" - минава я Garbij Collector -a като куцо пиле домат. След като умре последната мравка пътя е намерен.
 Проблема, над който мисля: Да направя така, че всяка мравка да знае колко мравки има и всяка мравка да брои в различен Counter броя стъпки.
Или Всяка мравка да пише в полето ?? ( Ако пише в полето има много проблеми с синхронизацията ) Ама тоя, който води упражненията "намекна", че така трябва. И след като му предложих моята идея – каза, че ако я реализирам както трябва няма да има нищо против. Недостатък на моята идея - е че ми трябва много памет.
А това което не разбирам на неговото предложение е "в едно поле 100 х 100 може да живнат и около 6000 мравки и какво става ако вси4ки 6 000 се синхронизират с полето ??? - busy wait /  a ако объркам нещо и Dead Lock. Ако някои е правил подобна задача (това  е стандартна задача за упражняване на Threads ), може да коментира с някоя много яка идея.
И да направим RunTime ot O(n) na O(log n) :))) Това го сънувах една вечер - как SelectionSort прави RunTime O(log n) :) Луда работа ;)
Споменах ли че намразих Threads!