Szukanie największych (zdefiniowanych) obszarów w tablicy [21x18]

Witam Serdecznie.

Mam pewien dylemat w związku z pisaną przeze mnie grą w Unity3d (C#).

Poszukuję algorytmu na odnajdywanie w dwu-wymiarowej tablicy [21x18] posiadającej ściany i puste pola największych (zdefiniowanych) pustych obszarów.
Kryterium odnajdywania to zbiór zdefiniowanych obszarów: [3x3] [3x2] [2x3] [2x2] [2x1] [1x2] [1x1] - priorytetowo od pierwszego do ostaniego.

Na obrazku widać tablicę, w której białe kratki oznaczją puste pola, a czarne - ściany. Obok wypełnione kolorami największe możliwe obszary pustych pól.

Jeżeli ktoś mnie zrozumiał (mam nadzieję), to będę wdzięczny za jakieś pomysły na realizację mojego problemu.

Dzięki za uwagę :)

Wyszykujesz wszystkie pola o wymiarach 3x3(zakładając ze musi być jak najwięcej dużych bloków) sprawdzasz wszystkie możliwe kombinacje ich ułożenia, potem robisz to samo dla bloków __2x3 i 3x2 __ potem 2x2 i tak dalej...
ed. tak nie zrobisz musisz wszysko naraz sprawdzić ;/

zalezy jak duza ta tablica ma byc wynikowa.
i czemu nie 1x6 (cala lewa strona?) no i masz jeszcze wieksza pusta przestrzen w prostokacie bo ja widze 10 ;) (lewy gorny rog, do konca na prawo i dwa dlugosci w dol)

wiec jaki to ma byc algorytm konkretnie? Bo na pewno nie bedzie to szukanie najwiekszych pustych miejsc

EDIT. Nie przeczytalem zalozen, to nie jest szukanie najwiekszych mozliwych miejsc, tylko szukanie miejsc juz z predefiniowanych mozliwosci. Takze strasznie pomieszales w poscie

Jezeli masz zdefiniowane jakie kwadraty moga byc to ich po prostu szukaj po calej tablicy. Jezeli bedzie za wolne to mozesz robic "przewidywania" Jezeli na obrzezach 3x3 jest czarny blok to mozesz od razu z szukaniem isc po za krawedz, jezeli znalazles w srodku to wiesz ze 2x2 tez sie nie zmiesci. itd.
Jezeli tablica bedzie tak mala jak ta (nawet 5x wieksza tablica niz ta co jest bedzie nadal mala) to nie ma sensu myslec o optymalizacji

naiwny brute force ma złożoność o(n⁴), co nie jest źle.
Sprawdź jak się to sprawdza na największej przewidywanej prze ciebie planszy, jasli będziesz zadowolony z czasu wykonania to nie ma co kombinować i tracić czas.
Jeśli jednak to nie wystarczy, to trzeba pomyśleć na czymś lespzym (ale algorytm do porównania poprawności wyników i generowania danych do testów już będziesz miał, więc to nie bedzie stracona praca).

Jedna z możliwości (gotowiec):

public class Program
    {
        static int[,] tab = new int[7,6]; 

        public static void Main(string[] args)
        {
            FillTab();
            ShowTab();
            CheckFreeSpaceAndMark(3, 3, 5); 
            CheckFreeSpaceAndMark(2, 3, 6);
            ShowTab();
            Console.ReadLine();
        }

        private static void FillTab()
        {
            tab[0, 5] = 1;
            tab[2, 3] = 1;
            tab[2, 4] = 1;
            tab[3, 1] = 1;
            tab[3, 2] = 1;
            tab[3, 3] = 1;
            tab[5, 4] = 1;
            tab[6, 2] = 1;
        }

        private static void ShowTab()
        {
            for (int i = 0; i < tab.GetLength(0); i++)
            {
                for (int j = 0; j < tab.GetLength(1); j++)
                {
                    Console.Write(tab[i, j] + " ");
                }
                Console.WriteLine();
            }
            Console.WriteLine("------------------------");
        }

        private static bool CheckFreeSpaceAndMark(int a, int b, int marker)
        {
            int tmp = 0;
            for (int i = 0; i < tab.GetLength(0)-a; i++)
            {
                for (int j = 0; j < tab.GetLength(1)-b; j++)
                {
                    tmp = 0;
                    for (int k=0; k <a;k++)
                    {
                        for (int l = 0; l < b; l++)
                        {
                            tmp += tab[i+k,j+l];
                            if (tmp>0)
                            {
                                continue;
                            }
                        }
                    }
                    if (tmp==0)
                    {
                        for (int k = 0; k < a ; k++)
                        {
                            for (int l = 0; l < b; l++)
                            {
                                tab[i + k, j + l] = marker;
                            }
                        }
                        return true;
                    }
                }
            }
            return false;
        }
    }

A może jakbyś zrobił obiektowe wypełnienie planszy to łatwiej było by się w niej ogarnąć.
Chyba, że będziesz musiał analizować zewnętrznie generowane, to odpada.