Floodfill ©

300000

Floodfill^©

Total number of plays: 427326
Total number of wins: 209822

Інструкція до гри Заливка

Проблема використання мінімальної кількості кольорів для розфарбування карти має довгу історію, наприклад про це можна почитати у статті на Вікіпедії https://en.wikipedia.org/wiki/Four_color_theorem. Теорема про те, що 4 кольорів завжди достатньо для забарвлення плоскої карти, стала відомою як перша велика математична теорема, яку можна було довести лише за допомогою комп’ютера, а не за допомогою „математичного” доведення, створеного людиною.

Не існує алгоритма, який завжди ефективно розфарбовує карти. Під «ефективно» ми маємо на увазі, що якщо кількість регіонів N дуже велика, то кількість необхідних спроб забарвлення зростає як N^k, де k - число, яке не залежить від N. Іншими словами, для «ефективних» алгоритмів кількість спроб зростає поліноміально. Натомість відомі алгоритми забарвлення мають так звану експоненціальну складність, тобто кількість спроб залежить від N, наприклад, як 4N.

Якщо дозволити використати 5 або 6 кольорів, на карті, де потрібно лише 2 кольори, то ефективні алгоритми відомі.

Іншою можливістю отримати ефективний метод є відмова від вимоги, що алгоритм ЗАВЖДИ ефективний. Таку евристику (тобто набір інструкцій), яка працює принаймні у багатьох випадках, слід обговорити нижче:

Який регіон слід пофарбувати першим?

Який вибір кольорів вільний?

Який регіон слід пофарбувати наступним?

Наступним ми повинні розфарбувати регіон, для якого залишився лише один можливий варіант кольору, щоб ми не помилилися із забарвленням.
Кількість спроб забарвлення, безумовно, менше ніж 4^N (спроба використати всі 4 кольори для всіх N регіонів). Отже, ця кількість спроб забарвлення критично залежить від кількості регіонів N. Отже, корисно, якщо забарвлення розділяє білу (не забарвлену) частину карти на окремі від’єднані білі “підкарти”, які потім можна розфарбувати самостійно. У цих регіонах є лише регіони N₁ і N₂ (N = N₁ + N₂), тепер їм потрібно не більше 4^N₁ + 4^N₂ спроб, що набагато менше, ніж 4^N₁ × 4^N₂ = 4^N спроб.
Якщо ми хочемо знайти найменшу кількість кольорів, які можуть забарвити дану карту, то спочатку потрібно перевірити, чи достатньо 2 кольорів. Це можна зробити ефективно.

Якщо потрібно використовувати лише два кольори A і B, а один з регіонів вже має колір, то обхід точки перетину фіксує колір усіх інших регіонів:

Це правило також корисне для першої спроби розфарбовування карт, які потребують 3 або 4 кольори. Наприклад, якщо регіон 1 нижче вже має колір А, то регіони 2 і 4 потребують іншого кольору, і ми не маємо уявлення, яким він може бути, але ми знаємо, що забарвлення кольором А регіону 3 не створює додаткових умов щодо забарвлення регіонів 2 і 4, оскільки вони вже мають сусіда кольору А.

Малюнок 3 показує лише невелику частину карти, але наведену вище евристику можна зробити більш точною для будь-якої карти. Якщо всі сусіди регіону 3 (на Малюнку 3 - регіони 2 і 4) мають принаймні одного сусіда кольору А (на Малюнку 3 - регіон 1), то забарвлення регіону 3 кольором А не може бути помилкою. Причина в тому, що забарвлення регіону 3 кольором A не створює жодних нових обмежень для сусідів, оскільки їм вже заборонено мати колір A. Отже, якщо в подальшому процесі фарбування виявиться, що ми припустилися помилки (через недостатню кількість кольорів), то немає сенсу надавати регіону 3 інший колір, ніж А, необхідно спробувати по-іншому розфарбувати інші регіону.
Що робити, якщо регіон 3 вище також є діагональним сусідом з іншим регіоном, скажімо, регіоном 9, яка вже має інший колір, наприклад колір В? Область 3 слід зафарбувати кольором А чи В? Тут також допоможе перевірити всіх сусідів області 3, чи їм вже заборонено мати колір А чи заборонено мати колір В. Якщо таких заборон немає, ми можемо зачекати з розфарбуванням 3.

Floodfill©

Інструкція до гри Заливка

Floodfill^©