Floodfill ©

Caribou in Covid: Contests are running online as usual. Check out the FAQ for further questions.

300000

373803

193411

Floodfill^©

In contests, the number of needed colours is not specified

A Guide for Playing Floodfill

The problem of using a minimal number of colours to colour a map has a long history as explained, for example, in the Wikipedia article https://en.wikipedia.org/wiki/Four_color_theorem. The theorem that 4 colours are always enough to colour a plane map became famous as the first big mathematical theorem that could be proven only by computer and not through a human produced 'mathematical' proof.

There is no algorithm known that always colours maps efficiently. With 'efficiently' we mean that if the number of regions N is very large then the number of necessary colouring attempts grows only like N^k where k is a number that does not depend on N. In other words, for 'efficient' algorithms the number of attempts grows only like a polynomial of N. Instead, known colouring algorithms have a so-called exponential complexity, i.e. the number of tries depends on N like 4^N.

If one were allowed to use 5 or 6 colours, or if the map needs only 2 colours, then efficient algorithms are known.

Another opportunity to get an efficient method is to drop the requirement that the algorithm is ALWAYS efficient. Such a heuristic (i.e. a set of instructions) that works at least in many cases is to be discussed below:

Q. Which region should be colored first?

Q. Which choice of colours is free?

Q. Which region should be coloured next?

We should colour a region next for which there is only one possible colour left so that we can not make a mistake in this colouring.
The number of colouring attempts is definitely less than 4^N (trying all 4 colours for all N regions). So this number of colouring attempts depends critically on the number of regions N. Consequently it is useful if a colouring splits the white (uncoloured) part of the map into separate disconnected white sub-maps which then can be coloured on their own. These regions have only N₁ and N₂ regions (N = N₁ + N₂), needing now at most only 4^N₁ + 4^N₂ tries which is much less than 4^N₁ × 4^N₂ = 4^N tries.
If one wants to find the smallest number of colours that can colour a given map then one first has to check whether 2 colours are enough. This can be done efficiently.

If only two colours A and B are to be used and one of the regions already has a colour, then going around the point of intersection fixes the colour of all other regions:

This rule is also useful for a first colouring attempt of maps that need 3 or 4 colours. For example, if region 1 below has already colour A then regions 2 and 4 need a different colour and we have no idea what that could be but we know that colouring region 3 with colour A does not pose extra conditions on the colouring of regions 2 and 4, because they already have a neighbour of colour A.

Figure 3 shows only a small part of the map but the above heuristic can be made more precise for any map. If all neighbours of region 3 (in Figure 3, regions 2 and 4) have at least one neighbour of colour A (in Figure 3, region 1), then colouring region 3 with colour A can not be a mistake. The reason is that colouring region 3 with A does not create any new restriction on its neighbours because they are already forbidden to have colour A. So if in the further colouring process it turns out that a mistake has been made (because the number of colours is not enough), then there is no point in giving region 3 a different colour than A, some other colouring must be re-tried.
What if region 3 above is also a diagonal neighbour to another region, say region 9, which already has a different colour, like colour B? Should 3 be coloured with A or B? Also here it helps to check all neighbours of 3 whether they are already forbidden to have colour A or forbidden to have colour B. If neither is the case then we might wait with colouring 3.

Guide de Jeu pour Floodfill

Le problème avec l’utilisation d'un nombre minimal de couleurs pour colorier une carte a une longue histoire, qui est expliqué, par exemple, dans l'article de Wikipédia https://en.wikipedia.org/wiki/Four_color_theorem. Le théorème que 4 couleurs sont toujours assez pour colorier une carte d'avion est devenu célèbre comme le premier grand théorème mathématique qui pourrait être prouvé par ordinateur plutôt que par un humain.

Il n'y a aucun algorithme connu qui toujours colore des cartes efficacement. Cela veut dire que si le nombre de régions N est très grand, le nombre de essais de colorants nécessaires se comporte selon la relation N^k. Ici k est un nombre qui ne dépend pas de N. Ainsi, pour des algorithmes «efficaces» le nombre d’essais se comportent selon le polynôme de N. Au lieu de cela, les algorithmes de coloration connus ont une complexité exponentielle. C'est-à-dire le nombre d’essais dépend de N comme 4^N.

Si on puisse utiliser cinq ou six couleurs, ou si la carte a besoin de seulement deux couleurs, on peut dire que des algorithmes efficaces sont connus.

Une autre occasion d'obtenir une méthode efficace est de ne plus exiger que l'algorithme est TOUJOURS efficace. Une telle heuristique (ou un ensemble d'instructions) qui fonctionne dans plusieurs cas doit être discuté ci-dessous:

Q. Quelle est la région qui devrait être colorée d’abord?

Q. Lesquelles des choix de couleurs sont disponibles?

Q. Quelle est la prochaine région qui devrait être colorée.

La prochaine région que nous allons colorer doit être celle pour laquelle il y a une seule couleur possible qui reste, de sorte que nous ne pouvons pas faire une erreur dans le processus.
Le nombre d'essais de coloration est certainement inférieur à 4^N (en essayant tous les 4 couleurs pour toutes les régions N). Ainsi, le nombre d’essais de coloration dépend du nombre de régions N. Par conséquent, il est utile si une coloration divise la partie blanche (incolore) de la carte en sous-cartes blanches déconnectées distincts qui peuvent ensuite être colorée elles-mêmes. Ces régions ont des régions N₁ et N₂ (N = N₁ + N₂) seulement. Maintenant elles ont besoin de seulement 4^N₁ + 4^N₂ essais au plus, qui est beaucoup moins que 4^N₁ × 4^N₂ = 4^N essais.
Si on veut trouver le plus petit nombre de couleurs qui peuvent colorer une carte donnée, il faut d'abord vérifier si 2 couleurs sont assez. Ceci peut être fait de manière efficace.

Si seulement deux couleurs A et B doivent être utilisés et une région est déjà colorée, d'aller autour du point d'intersection fixe la couleur de toutes les autres régions:

Cette règle est également utile pour un premier essai de coloration des cartes qui ont besoin de 3 ou 4 couleurs. Par exemple, si la région 1 ci-dessous a déjà été colorés en utilisant la couleur A, les régions 2 et 4 ont besoin d'une couleur différente. Nous ne savons pas ce que cette couleur pourrait être. Mais nous savons que la coloration de la région 3 avec la couleur A ne pose pas de conditions supplémentaires sur la coloration des régions 2 et 4. C’est parce qu'ils ont déjà un voisin de la couleur A.

La figure 3 montre qu'une petite partie de la carte, mais l'heuristique ci-dessus peut être rendue plus précise pour n'importe quelle carte.Si tous les voisins de la région 3 (dans figure 3, les régions 2 et 4) ont au moins un voisin de la couleur A (dans figure 3, la région 1), en choisissant la couleur A pour la région 3 on ne peut pas faire une erreur. La raison est à cause du fait que la coloration de la région 3 avec le couleur A ne crée aucune nouvelle restriction sur ses voisins; ils sont déjà interdit d'avoir la couleur A. Donc, si pendant le processus de la coloration, il se révèle qu'une erreur a été commise (parce que le nombre de couleurs ne suffit pas), il n’a pas de sens de donner à région 3 une couleur différente. Donc, une autre coloration doit être reconsidérée.
Qu’est-ce qu’il faut faire si la région 3 ci-dessus est également un voisin diagonal pour une autre région, telles que la région 9, qui a été déjà donnée une couleur différente (couleur B)? Faut-il colorer la région 3 avec A ou B? Ici, il serait utile de vérifier tous les voisins de la région 3 sont déjà interdits d'avoir la couleur A ou interdits d'avoir la couleur B. Si ce n’est pas le cas, nous pourrions attendre avant de colorer 3.

填色游戏指南

正如所介绍的，用最少的颜色来填充一个地图的问题具有很长的历史，比如，在维基百科的文章中https://en.wikipedia.org/wiki/Four_color_theorem.仅用4个颜色就可以填涂一个空白地图的定理是一个有名的只能运用电脑证明而不能被人类计算所证明的头号数学定理。

没有已知算法可以每次都有效率地填涂地图。所谓有效率即指如果有N个很大的区域，那么需要的填色尝试次数只以 N^k增长，k并不取决于N.换句话说，在最有效率的算法中尝试的次数应只以N的多项式增长。然而，已知的填色算法有所谓的指数复杂性，换句话说，填色尝试次数取决于N，比如4^N。.

如果可以使用5或6个颜色，或者如果地图只需要两个颜色，最有效率的算法是已知的。

另一个得到最有效率的方法的机会是放弃任何情况下都最有效率这一要求。至少在多数情况下有效的这种探索性步骤（换句话说，一组指令）会在下面进行讨论：

Q.哪个区域应该先被填色？

Q.哪一种颜色选择不受限制？

Q.哪一个区域应该下一个被涂色？

下一个要涂的区域应该只有一种可涂颜色，这样我们就不会在涂色上出错。
涂色的尝试应小于4^N次（对于N个区域的每一个都尝试所有的4种颜色）。所以涂色的尝试次数很大程度上取决于区域的个数N。所以，如果填色后地图的白色（未填涂的）部分被分成了单独而不相邻的，而且后续可被自行填涂的白色子地图，将会很有用。这些区域只有N^1和N^2个部分(N = N^1 + N^2)，现在最多只需要4^N1 + 4^N2次尝试，这比4^N1 * 4^N2 = 4^N次尝试要少得多。
如果想要找到填涂一个已知的地图最少的使用的颜色个数，必须先检查2个颜色是否足够。这可以有效率地完成。

如果只有两种颜色A和B可以使用并且其中一个区域已经被涂上一种颜色，那么在交点附近检查可以确定其它所有区域的颜色：

这个规则对于需要用3或4种颜色填涂的首次尝试的地图也适用。例如，如果下方区域1已经有颜色A那么区域2和4需要不同的颜色，我们并不知道有可能是那种颜色但我们知道用颜色A填涂区域3不会影响填涂区域2和4的条件，因为它们已经有相邻的颜色A。

图3只显示了地图的一小部分但是上方的探索性步骤对于任何地图都可以变得更加精准。如果区域3的所有邻近区域（在图3中，区域2和4）都至少有一个相邻的区域被涂上颜色A（在图3中，区域1），那么用颜色A涂区域3不会出错。这是因为这样做不会为其相邻区域带来限制，因为这些区域已经不能使用颜色A。所以如果在后续涂色过程发现了错误（因为颜色的个数不足），区域3也不会有除了A外的其它选择，应该尝试在其它涂色步骤中更改颜色。
如果区域3的上方也有一个对角相邻的区域，比如有颜色B的区域9，这会怎么样呢？区域3应该用A或B着色吗？在这里，检查所有3的邻接区域是否已经不可用颜色A或者颜色B将十分有帮助。如果两种情况都不对那么我们可先不涂3.

ការណែនាំសម្រាប់ការលេងហ្គេម Floodfill

បញ្ហានៃការប្រើចំនួនពណ៌តិចបំផុតដើម្បីដាក់ពណ៌លើផែនទី មានប្រវត្តិយូរយារណាស់មកហើយដូចដែលបានពន្យល់ ជាឧទាហរណ៍នៅក្នុងអត្ថបទវិគីភីឌា ទ្រឹស្តីបទដែលថា ៤ ពណ៌គឺគ្រប់គ្រាន់សម្រាប់ដាក់ពណ៌ប្លង់ផែនទីបានក្លាយជាល្បីល្បាញដោយសារជាទ្រឹស្តីបទគណិតវិទ្យាធំដំបូងគេបង្អស់ដែលអាចស្រាយបញ្ជាក់បានតែតាមរយៈកុំព្យូទ័រប៉ុណ្ណោះ មិនមែនតាមរយៈសម្រាយបញ្ជាក់គណិតវិទ្យាដែលមនុស្សផលិតឡើយ។

គេមិនទាន់ដឹងក្បួនដោះស្រាយច្បាស់លាស់ដើម្បីដាក់ពណ៌ផែនទីប្រកបដោយប្រសិទ្ធភាពនៅឡើយទេ។ ជាមួយពាក្យ 'ប្រកបដោយប្រសិទ្ធភាព' យើងមានន័យថា ប្រសិនបើចំនួនតំបន់ N មានទំហំធំខ្លាំងនោះចំនួននៃការព្យាយាមលាបពណ៌ចាំបាច់នឹងកើនឡើងដូច N^k ដែល k គឺ ជាចំនួនដែលមិនអាស្រ័យលើ N។ និយាយម្យ៉ាងទៀត សម្រាប់ក្បួនដោះស្រាយដែលមានប្រសិទ្ធភាព ចំនួននៃការប៉ុនប៉ងមានចំនួនកើនឡើងតាមពហុធានៃ N។ ជាងនេះទៅទៀត ក្បួនដោះស្រាយការដាក់ពណ៌ត្រូវបានគេហៅថា exponential complexity ជាឧទាហរណ៍ ចំនួននៃការព្យាយាមអាស្រ័យលើ N ឧទាហរណ៍ដូចជា 4^N ។

ប្រសិនបើគេត្រូវបានអនុញ្ញាតឱ្យប្រើ ៥ ឬ ៦ ពណ៌ ឬប្រសិនបើផែនទីត្រូវការតែ ២ ពណ៌ នោះក្បួនដោះស្រាយដែលមានប្រសិទ្ធភាពនឹងត្រូវបានគេដឹង។

ឱកាសមួយទៀតដើម្បីទទួលបានវិធីសាស្ត្រមានប្រសិទ្ធភាពគឺត្រូវពិភាក្សានិងអនុវត្តតាមក្បួនដោះស្រាយដ៏មានប្រសិទ្ធិភាពមួយ។ វិធីសាស្រ្ត (ជាការណែនាំ) ដែលមានប្រសិទ្ធភាពលើករណីជាច្រើននឹងត្រូវពិភាក្សាដូចខាងក្រោម៖

សំណួរ៖ តើតំបន់ណាដែលត្រូវលាបពណ៌មុនគេ?

សំណួរ៖ តើជម្រើសពណ៌មួយណាដែលរើសបានតាមចិត្ត?

សំណួរ៖ តើត្រូវដាក់ពណ៌តំបន់ណាបន្ទាប់?

តំបន់បន្ទាប់ដែលយើងគួរដាក់ពណ៌គឺតំបន់ដែលនៅសល់ពណ៌តែមួយពណ៌គត់ដែលអាចដាក់បាន ដូចនេះយើងមិនត្រូវមានកំហុសក្នុងការដាក់ពណ៌តំបន់នេះទេ។ .
ចំនួននៃការប៉ុនប៉ងដាក់ពណ៌គឺពិតជាតិចជាង 4^N (បើសាកល្បងដាក់ពណ៌ទាំង ៤ សម្រាប់តំបន់ N នីមួយៗ)។ ដូច្នេះចំនួននៃការប៉ុនប៉ងលាបពណ៌នេះពឹងផ្អែកយ៉ាងសំខាន់ទៅលើចំនួនតំបន់ N។ ហេតុដូច្នេះ វាមានប្រយោជន៍ប្រសិនបើតំបន់ដែលដាក់ពណ៌ញែកតំបន់ពណ៌ស (មិនទាន់ដាក់ពណ៌) ជាផែ្នកផ្សេងៗដែលមិនជាប់គ្នា ដែលធ្វើឲ្យតំបន់ពណ៌សនោះអាចត្រូវបានដាក់ពណ៌ដោយខ្លួនឯង។
ប្រសិនបើអ្នកចង់រកចំនួនពណ៌តិចបំផុតដែលអាចដាក់ពណ៌លើផែនទីដែលឲ្យ នោះដំបូងអ្នកត្រូវពិនិត្យមើលចំនួន ២ ពណ៌ជាការគ្រប់គ្រាន់។ នេះអាចត្រូវបានធ្វើយ៉ាងមានប្រសិទ្ធិភាព។

ប្រសិនបើមានតែពីរពណ៌ A និង B ដែលត្រូវដាក់ តែតំបន់នោះមានពណ៌រួចហើយខុសពីពណ៌ដែលត្រូវដាក់ នោះគេត្រូវជួសជុល(ដាក់ពណ៌សារថ្មី)ចាប់ផ្តើមចេញពីជុំវិញចំនុចប្រសព្វ៖

វិធាននេះក៏មានប្រយោជន៍ចំពោះផែនទីដែលត្រូវប្រើ ៣ ពណ៌ ឬ ៤ ពណ៌ ដែរ ។ ឧទាហរណ៍ ប្រសិនបើតំបន់ទី ១ ខាងក្រោមបានដាក់ពណ៌ A នោះតំបន់ទី ២ និង ទី៤ ត្រូវតែដាក់ពណ៌ផ្សេង ហើយយើងមិនទាន់ដឹងថាត្រូវដាក់ពណ៌ណានៅឡើយទេ ប៉ុន្តែយើងដឹងថាការដាក់ពណ៌ A លើតំបន់ទី ៣ មិនបង្កលក្ខខណ្ឌបន្ថែមលើការដាក់ពណ៌តំបន់ទី ២ និងទី ៤ ទេ ពីព្រោះពួកវាសុទ្ធតែមានតំបន់ជិតខាងដែលមានពណ៌ A រួចហើយ។

រូបភាពទី ៣ បង្ហាញតែផ្នែកតូចមួយនៃផែនទីប៉ុណ្ណោះ ប៉ុន្តែវាអាចធ្វើឱ្យយល់ច្បាស់ដែលអាចយកទៅអនុវត្តសម្រាប់ផែនទីផ្សេងជាច្រើនទៀត។ ប្រសិនបើតំបន់ជិតខាងទាំងអស់នៃតំបន់ទី ៣ (តំបន់ទី ២ និងទី ៤ ក្នុងរូបភាពទី ៣) ក្នុងចំណោមនេះបើវាមានតំបន់ជិតខាងយ់ាងតិចមួយដែលមានពណ៌A (តំបន់ ១ នៅក្នុងរូបភាពទី ៣) នោះការដាក់ពណ៌ A លើតំបន់ទីដែរ មិនអាចជាកំហុសទេ។ មូលហេតុគឺថា ការដាក់ពណ៌ A លើតំបន់ពណ៌ទី ៣ មិនបង្កើតការរឹតត្បិតថ្មីលើតំបន់ជិតខាងទេពីព្រោះពួកគេត្រូវបានហាមឃាត់មិនឱ្យមានពណ៌ A រួចទៅហើយ។ ដូច្នេះ ប្រសិនបើនៅក្នុងដំណើរការដាក់ពណ៌បន្តបន្ទាប់ទៀត បង្ហាញឲ្យឃើញថាមានកំហុស (ដោយសារពណ៌ដែលត្រូវដាក់ជាន់ជាមួយពណ៌នៃតំបន់ជិតខាង) នោះគេត្រូវសាកល្បងដាក់ពណ៌ផ្សេងលើតំបន់ទី ៣ ជំនួសពណ៌ A វិញ។
ចុះបើតំបន់ទី ៣ ខាងលើក៏ជាតំបន់ជិតខាងតាមទិសអង្កត់ទ្រូងទៅនឹងតំបន់ផ្សេងទៀតដែរ ឧទាហរណ៍តំបន់ទី ៩ ដែលមានពណ៌ផ្សេងរួចទៅហើយ ឧទាហរណ៍ដូចជាពណ៌ B នោះតើតំបន់ទី ៣ គួរតែដាក់ពណ៌ A ឬ ពណ៌B? ដូចគ្នានេះដែរ គេត្រូវពិនិត្យមើលតំបន់ជិតខាងទាំងអស់របស់តំបន់ទី ៣ ថាតើពួកគេត្រូវបានហាមឃាត់មិនឱ្យដាក់ពណ៌ A ឬក៏ហាមឃាត់មិនឱ្យមានពណ៌ B ។ ប្រសិនបើមិនចូលករណីណាមួយនោះទេ ការដាក់ពណ៌លើតំបន់ទី៣ អាចត្រូវរង់ចាំសិន (ដាក់ពណ៌កន្លែងផ្សេងសិន) ។

A Guide for Playing Floodfill

مشکل استفاده از کمترین تعداد رنگ برای رنگ کردن نقشه، بر اساس توضیحات ارائه شده، تاریخ طولانی دارد، به عنوان مثال، در یک مقاله ی ویکی پدیا https://fa.wikipedia.org/wiki/%D9%82%D8%B6%DB%8C%D9%87_%DA%86%D9%87%D8%A7%D8%B1%D8%B1%D9%86%DA%AF. این قضیه که 4 رنگ همیشه کافی است که یک نقشه ی ساده را رنگ کرد به عنوان اولین قضیه ی ریاضی بزرگ معروف شد که فقط می توانست توسط رایانه ثابت شود و نه توسط اثبات ریاضی تولید شده توسط انسان.

هیچ الگوریتم شناخته شده ای برای بهینه رنگ کردن نقشه وجود ندارد. منظور از "بهینه" این است که اگر تعداد نواحی N عدد بزرگی است، آنگاه تعداد تلاش های لازم برای رنگ کردن مثل N^k رشد می کندکه در آن k عددی است که به N بستگی ندارد. به بیان دیگر، برای الگوریتم های "بهینه"، تعداد تلاش ها مثل یک چند جمله ای از N رشد می کند. در عوض، الگوریتم های رنگ آمیزی شناخته شده یک پیچیدگی توانی دارند، یعنی تعداد تلاش ها به N با رابطه ی ۴^N بستگی دارد.

اگر استفاده از 5 یا 6 رنگ مجاز باشد، یا نقشه فقط دو رنگ نیاز داشته باشد، الگوریتم های بهینه شناخته شده اند.

فرصتی دیگر برای رسیدن به روش بهینه این است که، اینکه الگوریتم همیشه بهینه است، کنار گذاشته شود. همچین ابتکاری (یعنی مجموعه ی دستورالعمل ها) که حداقل در بیشتر موارد قابل به کار گیری است باید ذیل مطرح شود:

سوال اول. کدام ناحیه باید اول رنگ شود؟

سوال دوم. چه انتخابی از رنگها آزاد است؟

سوال سوم. کدام ناحیه در مرحله بعدی باید رنگ شود؟

در مرحله ی بعدی ناحیه ای را رنگ کنیم که برای آن فقط یک رنگ محتمل باقی مانده باشد به گونه ای که نتوانیم اشتباهی در این رنگ آمیزی داشته باشیم.
تعداد تلاش ها برای رنگ آمیزی قطعا کمتر از ۴^N (امتحان کردن همه ی ۴ رنگ برای همه ی N ناحیه). بنابراین این تعداد تلاش ها برای رنگ آمیزی به صورت مهمی بستگی به تعداد ناحیه ها N دارد. در نتیجه این مفید خواهدبود که رنگ آمیزی قسمت سفید (رنگ نشده) نقشه را به زیر نقشه های غیر متصل جدا از هم که بعدا می توانند جداگانه رنگ شوند، تقسیم کرد. این نواحی فقط N_۱ و N_۲ ناحیه دارند (=N_۱+N_۲ N) ، که نیاز به حداکثر ۴^{(N_۱ )}+۴^{(N_۲ )}=۴^N تلاش دارد که بسیار کمتر از ۴^{(N_۱ )}*۴^{(N_۲ )}=۴^N تلاش است.
اگر کسی می خواهد که کمترین تعداد رنگ های لازم برای رنگ کردن یک نقشه ی داده شده را پیدا کند آنگاه می تواند در ابتدا بررسی کند که آیا ۲ رنگ کافی است. این کار می تواند به صورت بهینه انجام شود.

اگر فقط دو رنگ (الف) و (ب) قرار باشد که استفاده شوند و یکی از نواحی رنگ آمیزی شده باشد، آنگاه چرخیدن پیرامون نقطه ی اشتراک، رنگ سایر نواحی را تنظیم می کند:

این قانون همچنین برای اولین تلاش رنگ آمیزی نقشه مفید است که ۳ یا ۴ لازم دارد. به عنوان مثال، اگر ناحیه ی ۱ در زیر به رنگ (الف) رنگ آمیزی شده، آنگاه نواحی ۲ و ۴ رنگ های متفاوتی نیاز دارندو ما هیچ ایده ای نداریم که آن رنگ چه خواهد بود اما می دانیم که رنگ کردن ناحیه ی ۳ با رنگ (الف) شرایط بیشتری بر رنگ آمیزی نواحی ۲ و ۴ اعمال نمی کند، چرا که آنها از پیش در همسایگی ناحیه ای با رنگ (الف) قرار گرفته اند.

شکل ۳ فقط یهک بخش کوچکی از نقشه را نشان می دهد اما روش فوق می تواند به شکل دقیق تری برای هر نقشه ای استفاده شود. اگر همه ی همسایه های ناحیه ی ۳ (در شکل ۳، نواحی ۲ و ۴) حداقل یک همسایه با رنگ (الف) دارند (در شکل ۳، ناحیه ی ۱)، رنگ کردن ناحیه ی ۳ با رنگ (الف) نمی تواند اشتباه باشد. دلیل آن این است که رنگ کردن ناحیه ی ۳ با رنگ (الف) هیچ محدودیت جدیدی برای همسایه های آن به وجود نمی آورد، چرا که آنها از پیش از داشتن رنگ (الف) ممنوع شده اند. بنابراین اگر رنگ آمیزی های بعدی مشخص شود که اشتباهی رخ داده است (به این دلیل که تعداد رنگ ها کافی نیست)، آنگاه هیچ امتیازی در اینکه برای ناحیه ی ۳ رنگی غیر از (الف) در نظر گرفته شود وجود ندارد، رنگ آمیزی های های دیگری باید دوباره امتحان شوند.
چه می شود اگر ناحیه ی ۳ در بالا، به صورت قطری همسایه ی ناحیه ی دیگری باشد، مثلا ناحیه ی ۹، که از پیش رنگ دیگری دارد، مثلا رنگ (ب)؟ آیا ۳ باید به رنگ (الف) یا (ب) رنگ شود؟ همچنین اینجا چک کردن همه ی همسایه های ۳ کمک کننده است چه آنها از پیش از داشتن رنگ (الف) یا (ب) ممنوع شده باشند. اگر هیچ یک از این موارد نباشد آنگاه ما می توانیم با رنگ آمیزی ۳ منتظر بمانیم.

Hướng dẫn chơi trò Floodfill

Việc sử dụng số lượng màu sắc ít nhất có thể để tô màu bản đồ có lịch sử lâu đời như đã giải thích, ví dụ như trong bài viết trên Wikipedia https://en.wikipedia.org/wiki/Four_color_theorem. Định lý rằng 4 màu luôn là đủ để tô màu một bản đồ mặt phẳng đã trở nên nổi tiếng như một định lý toán học lớn đầu tiên chỉ có thể được chứng minh bằng máy tính mà không phải thông qua một bằng chứng 'toán học' do con người tạo ra.

Không có thuật toán nào được biết là sẽ luôn tô màu bản đồ một cách hiệu quả. 'Hiệu quả' ở đây có nghĩa là nếu số vùng N rất lớn thì số lần tô màu cần thiết chỉ tăng lên giống như N^k trong đó k là số không phụ thuộc vào N. Nói cách khác, đối với các thuật toán 'hiệu quả', số lần thử chỉ tăng lên giống như một đa thức của N. Thay vào đó, các thuật toán tô màu hiện có cái gọi là độ phức tạp theo cấp số nhân, tức là số lần thử phụ thuộc vào N như 4^N.

Nếu một người được phép sử dụng 5 hoặc 6 màu, hoặc nếu bản đồ chỉ cần 2 màu, thì các thuật toán hiệu quả được công nhận.

Một cơ hội khác để có được một phương pháp hiệu quả là loại bỏ yêu cầu rằng thuật toán LUÔN LUÔN hiệu quả. Phương pháp heuristic như vậy (tức là một tổ hợp các hướng dẫn) ít nhất có hoạt động trong các trường hợp sẽ được thảo luận dưới đây:

Q. Nên tô màu khu vực nào trước?

Q. Lần tô nào được tự do chọn màu?

Q. Nên tô màu khu vực nào tiếp theo?

Chúng ta nên tô màu cho một vùng tiếp theo khi vùng này chỉ có thể tô một màu duy nhất khả thi để chúng ta không mắc lỗi khi tô màu này.
Số lần thử tô màu luôn ít hơn 4^N (thử cả 4 màu cho tất cả N vùng). Vì vậy, số lần thử tô màu này phụ thuộc rất nhiều vào số vùng N. Do đó, sẽ rất hữu ích nếu việc tô màu chia phần màu trắng (chưa tô màu) của bản đồ thành các bản đồ con màu trắng riêng biệt không kết nối với nhau mà sau đó lại tiếp tục được tô màu theo cách riêng. Những vùng này chỉ có N^1 và N^2 vùng (N = N^1 + N^2), bây giờ chỉ cần nhiều nhất là 4^N1 + 4^N2 lần thử mà rõ ràng là nhỏ hơn nhiều so với 4^N1 * 4^N2 = 4^N lần thử.
Nếu một người muốn tìm số lượng màu tối thiểu để có thể tô màu cho một bản đồ nhất định thì trước tiên người ta phải kiểm tra xem liệu 2 màu có đủ không. Điều này có thể được thực hiện một cách hiệu quả.

Nếu chỉ sử dụng hai màu A và B và một trong số các vùng đã có màu, thì việc di chuyển xung quanh điểm giao nhau sẽ sửa màu của tất cả các vùng khác:

Quy tắc này cũng hữu ích để áp dụng cho lần thử tô màu đầu tiên của bản đồ cần 3 hoặc 4 màu. Ví dụ: nếu vùng 1 bên dưới đã có màu A thì vùng 2 và 4 cần một màu khác và ta không biết đó có thể là màu gì nhưng ta biết rằng việc tô màu vùng 3 với màu A không làm nảy sinh thêm các điều kiện về tô màu của vùng 2 và 4, bởi vì chúng sẵn đã tiếp xúc một vùng lân cận có màu A.

Hình 3 chỉ thể hiện một phần nhỏ của bản đồ tuy nhiên phương pháp heuristic ở trên có thể được thực hiện một cách chính xác đối với bất kỳ bản đồ nào. Nếu tất cả các vùng lân cận của vùng 3 (trong Hình 3, vùng 2 và 4) có ít nhất một vùng lân cận sử dụng màu A (trong Hình 3, vùng 1), thì việc tô màu vùng 3 với màu A sẽ không gây ra lỗi sai nào. Lý do là việc tô màu vùng 3 với màu A không tạo ra bất kỳ hạn chế nào đối với các vùng xung quanh nó bởi vì chúng vốn đã không được sử dụng màu A. Vì vậy, nếu trong quá trình tô màu tiếp theo, cuối cùng lại xảy ra một lỗi sai (vì số lượng màu không đủ), thì việc cho khu vực 3 một màu khác với màu A là vô nghĩa, một số màu khác phải được thay đổi.
Điều gì sẽ xảy ra nếu vùng 3 ở trên cũng là vùng tiếp xúc theo đường chéo của vùng khác, chẳng hạn như vùng 9 đã có một màu khác ví dụ là màu B? Câu hỏi là vùng 3 nên được tô màu A hay B? Ở trường hợp này nó cũng giúp kiểm tra tất cả những vùng xung quanh của 3 xem chúng có bị hạn chế không được tô màu A hay không được tô màu B không. Nếu đều không hạn chế tô màu nào cả thì chúng ta có thể tạm thời chưa vội tô vùng 3.

Panduan untuk Permainan Floodfill

Soalan menggunakan warna yang minimum untuk mewarnai peta memiliki sejarah panjang seperti yang dijelaskan dalam artikel Wikipedia https://en.wikipedia.org/wiki/Four_color_theorem. Teorem mengenai 4 warna selalunya cukup untuk mewarnai satu peta menjadi terkenal sebagai teorem matematik besar pertama yang dapat dibuktikan hanya dengan komputer dan bukan melalui bukti 'mathematical' yang dihasilkan oleh manusia.

Tidak ada algoritma yang diketahui yang selalu mewarnai peta dengan cekap (efficiently). Dengan 'efficiently' kita bermaksud bahawa jika bilangan kawasan N sangat besar maka jumlah percubaan mewarna yang diperlukan hanya muncul seperti N^k di mana k adalah nombor yang tidak bergantung kepada N.

Jika seseorang dibenarkan menggunakan 5 atau 6 warna, atau jika peta hanya memerlukan 2 warna, algoritma yang cekap akan diketahui.

Peluang lain untuk mendapatkan kaedah yang cekap adalah melepaskan syarat bahawa algoritma SELALU cekap. Heuristik seperti itu (iaitu sekumpulan arahan) yang berfungsi sekurang-kurangnya dalam banyak kes akan dibincangkan di bawah:

Q. Kawasan mana yang mesti diwarnakan terlebih dahulu?

Q. Pilihan warna mana adalah bebas?

Q. Kawasan mana perlu diwarnakan seterusnya?

Kita harus mewarnai kawasan seterusnya yang hanya ada satu kemungkinan warna yang tertinggal supaya tidak melakukan kesilapan dalam pewarnaan ini.
Jumlah percubaan mewarna pasti kurang dari 4^N (mencuba semua 4 warna di seluruh kawasan N). Oleh itu, jumlah percubaan pewarnaan ini sangat bergantung pada bilangan kawasan N. Oleh itu, adalah berguna jika pewarnaan pisahkan bahagian putih (tidak berwarna) kepada peta sampingan putih yang terasing yang kemudian boleh diwarnakan sendiri. Kawasan-kawasan ini hanya menpunyai kawasan N^1 dan N^2 (N= N^1 + N^2),memerlukan sekarang paling banyak hanya 4^N1 +4^N2 percubaan yang jauh lebih sedikit daripada 4^N1 * 4^N2 = 4^N mencuba.
Sekiranya seseorang ingin mencari bilangan warna terkecil yang dapat mewarnai peta tertentu, seseorang harus memeriksa terlebih dahulu sama ada 2 warna sudah mencukupi. Ini dapat dilakukan dengan cekap.

Sekiranya hanya dua warna A dan B yang akan digunakan dan salah satu kawasan sudah berwarna, maka mewarnai di sekelliling titik persimpangan akan membetulkan warna semua kawasan lain:

Peraturan ini juga berguna untuk percubaan mewarna peta pertama yang memerlukan 3 atau 4 warna. Sebagai contoh, jika kawasan 1 di bawah sudah berwarna A maka kawasan 2 dan 4 memerlukan warna yang berbeza dan kita tidak tahu tetapi kita tahu bahawa mewarnakan kawasan 3 dengan warna A tidak menimbulkan syarat tambahan pada pewarnaan kawasan 2 dan 4, kerana mereka sudah mempunyai jiran berwarna A.

Rajah 3 menunjukkan hanya sebahaguan kecil peta tetapi heuristik sebelumnya dapat dibuat lebih tepat untuk sebarang peta. Sekiranya semua jiran kawasan 3(dalam Rajah 3, kawasan 2 dan 4)mempunyai sekurang-kurangnya satu jiran berwarna A (dalam Rajah 3, kawasan 1), maka mewarnai kawasan 3 dengan warna A tidak akan menjadi salah. Sebabnya ialah bahawa mewarnai kawasan 3 dengan warna A tidak akan menimbulkan sekatan baru pada jirannya kerana mereka sudah dilarang untuk memiliki warna A. Oleh itu, jika dalam proses pewarnaan selanjutnya menimbulkan kesalahan (kerana jumlah warna tidak cukup), maka tidak ada gunanya memberi kawasan 3 warna yang berbeza daripada A, beberapa pewarna lain mesti dicuba semula.
Bagaimana jika kawasan 3 di atas juga merupakan jiran pepenjuru kepada kawasan lain, katakan kawasan 9, yang sudah mempunyai warna yang berbeza, seperti warna B? Kawasan 3 patut diwarnai A atau B? Ia juga berguna untuk menyemak semua jiran kawasan 3 sama ada mereka dilarang mempunyai warna A atau dilarang mempunyai warna B. Sekiranya tidak berlaku, maka kita mungkin manunggu dengan mewarnai kawasan 3.