Я думаю що можна так, але я не перевіряв на практиці. Находимо чотири точки фігури: top-left (min x & min y), top-right (max x & min y), bottom-left (min x & max y), bottom-right (max x & max y). Якщо top-left і top-right мають одинакове значення координати y то вони на одному рівні по ігрику а також якщо top-right і bottom-right мають одинакове значення координати x то вони на одному рівні по іксу а також якщо bottom-right і bottom-left  мають одинакове значення координати x то вони на одному рівні по іксу а також якщо bottom-left і top-left мають одинакове значення координати y то вони на одному рівні по ігрику а це значить що фігура або прямокутник або квадрат.
п.с. якщо щось не зрозуміло у моїй логіці то питайте я спробую детальніше пояснити.

Замальовані фігури не можна відмічати, тобто юзер не зможе позначити її ще раз.

як на мене потрібно провести спочатку базові провірки.
1. вибираємо 4 точки
крайню ліву верхню, крайню праву верхню, крайню ліву нижню, крайню праву верхню
2. Перевіряємо їх на правило: крайні ліві точки мають бути розташовані на одній лінії по вертикалі, крайні праві теж, 2 верхні мають бути розташовані на 1ній горизонталі і дві нижні точки теж на одній горизонталі
якщо правило 2 не виконується значить фігура не підходить
3. наступним кроком ми маємо визначити чи у фігурі є пусті проміжки. Тобто це може бути прямокутник але в середині може бути пустий квадрат
беремо координати крайньої лівої верхньої точку і ідемо по лінії до того часу поки не дійдемо до крайньої правої координати
якщо один з квадратів на цій лінії  не заповнений тоді у фігурі є пробіли значить фігура не підходить
дальше перевіряємо наступну лінію і так до того часу поки не дійдемо до крайньої нижньої правої точки)
Здається такий алгоритм якщо я вас правильно зрозумів

Так.

А довільним чотирикутником в цій геометрії може бути лише прямокутник. І за умовою цей прямокутник лише один. Тому, я думаю робити так:

1. знаходимо найвищий найлівіший вибраний: (x_min, y_min).
2. Знаходимо найнижчий найправіший вибраний: (x_max, y_max).
3. Для всіх квадратиків перевіряємо умову:
    вибраний(x, y) == (x >= x_min) and (y >= y_min) and (x <= x_max) and (y <= y_max)
4. Якщо умова всюди виконалась - область правильна, інакше ні.

А там не більше 20 кутівт? І той квадратик справа вгорі хіба суміжний?

На моїй світлині запікселений чотирикутник)

2 Hanter Тобто допускається лише прямокутник?
Якщо так то це простіше:
Скануємо пострічково зображення, запам'ятовуємо координату x крайніх точок першого зустрічного відрізка з чорних квадратиків, якщо у рядку більше одного відрізка - помилка.
Далі перевіряємо чи координати x крайніх точок наступних відрізків рівні x координатам першого відрізку, якщо координати не збігаються, або знайдено більш ніж два відрізки - помилка.
Відколи зустрічаємо рядок без чорних відрізків - слідкуємо щоб надалі чорних квадратиків не було, якщо є - помилка.

Взагалі алгоритми подібні можна просто звести все в правильний ланцюжок, оптимізувати можна на етапі коли юзер малює фігуру, на цьому кроці можна простою формулою оприділяти крайні точки)

Отже самий оптимальний алгоритм.
Юзерів клікнув ми записуємо кількість кліків на дошці. Тобто лічильник чорних квадратів $numberOfBlack++ (якось так)
На цьому етапі ми перераховуємо крайні точки. Тобто маємо 4 точки   якщо юзер клікнув дальше за нашу крайню точку переписуємо координати
Юзер от так поклікав і ми маємо 4 крайні точки і кількість чорних квадратів.

Валідація: 1н крок)
Відносно крайніх точок визначаємо скільки в середині є квадратів отримуємо число і порівнюємо з $numberOfBlack
Якщо рівне все ок, якщо не рівно не все ок

Ще один нюанс якщо юзер знімає виділення треба брати бокові точки і перераховувати чи вони попадають під оприділення крайніх точок чи ні:) Ну взагалі реалізація реальня і не складна )