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 Nk 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 4N.
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 coloured first?
- It is useful to colour at first a region that has as many neighbours as possible because if that region gets colour A then all its neighbours will obtain a restriction not to get colour A. This reduces the number of colour choices for these neighbouring regions and thus reduces the number of later tries if colouring turns out to be hard.
Q. Which choice of colours is free?
- The colour used in the very first colouring is definitely free.
- The first time that a second colour is used to colour a region this choice of colour is free if this region touches a region with the first colour, i.e. if a second colour is necessary.
- The first time that a third colour is used to colour a region, this choice of colour is free if this region touches a region with the first colour and a region with the second colour, i.e. if a third colour is necessary.
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 4N (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 N1 and N2 regions (N = N1 + N2), needing now at most only 4N1 + 4N2 tries which is much less than 4N1 × 4N2 = 4N 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.
Un Manuel pour Jouer 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 Nk. 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 4N.
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?
- Il est utile d'abord de colorer une région qui a beaucoup de pays voisins que possible. En effet, si cette région est colorée en utilisant la couleur A, puis tous ses voisins obtiendront une restriction de ne pas obtenir la couleur A. Cela réduit le nombre de choix de couleurs pour ces régions voisines et réduit le nombre d'essais plus tard si la difficulté du processus augmente.
Q. Lesquelles des choix de couleurs sont disponibles?
- Le couleur utilisé d’abord est certainement disponible.
- La première fois qu’un couleur deuxième est utilisé, le couleur est disponible si la région est voisinée par une région qui a été colorée avec le premier couleur (au cas où un couleur deuxième est nécessaire).
- La première fois qu’un couleur troisième est utilisé, le couleur est disponible si la région est voisinée par une région qui a été colorée avec le premier couleur et une région qui a été colorée avec le troisième couleur (au cas où un couleur troisième est nécessaire).
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 à 4N (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 N1 et N2 (N = N1 + N2) seulement. Maintenant elles ont besoin de seulement 4N1 + 4N2 essais au plus, qui est beaucoup moins que 4N1 × 4N2 = 4N 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.哪个区域应该先被填色？
- 先涂有尽可能多相邻区域的部分会很有效，因为如果该部分被涂上颜色A那么它所有的相邻区域将不能涂颜色A。这会减少这些相邻区域的颜色选择，同时如果填色过难，这将减少后续的尝试次数。
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.
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 رنگ مجاز باشد، یا نقشه فقط دو رنگ نیاز داشته باشد، الگوریتم های بهینه شناخته شده اند.
فرصتی دیگر برای رسیدن به روش بهینه این است که، اینکه الگوریتم همیشه بهینه است، کنار گذاشته شود. همچین ابتکاری (یعنی مجموعه ی دستورالعمل ها) که حداقل در بیشتر موارد قابل به کار گیری است باید ذیل مطرح شود:
سوال اول. کدام ناحیه باید اول رنگ شود؟
- مفید است اگر در ابتدا ناحیه ای رنگ شود که بیشترین همسایه ممکن رادارد به این دلیل که اگر آن ناحیه رنگ A شود آنگاه همه ی همسایه ها محدود خواهند شد مه رنگ A نداشته باشند. این مساله تعداد انتخاب های رنگ را برای نواحی همسایه و بنابراین تعداد تلاش های بعدی را در شرایطی که رنگ کردن دشوار باشد را کاهش می دهد.
سوال دوم. چه انتخابی از رنگها آزاد است؟
- رنگی که در اولین رنگ آمیزی استفاده می شود قطعا آزاد است.
- اولین باری که رنگ دوم برای رنگ کردن یک ناحیه استفاده می شود این انتخاب رنگ آزاد است اگر این ناحیه در همسایگی ناحیه ای باشد که در ابتدا رنگ شد، یعنی اگر رنگ دوم لازم باشد.
- اولین باری که رنگ سوم برای رنگ کردن یک ناحیه استفاده می شود، این انتخاب رنگ آزاد است اگر این ناحیه در همسایگی ناحیه هایی باشد که در ابتدا و همچنین دوم رنگ آمیزی شدند، یعنی اگر رنگ سوم لازم باشد.
سوال سوم. کدام ناحیه در مرحله بعدی باید رنگ شود؟
- در مرحله ی بعدی ناحیه ای را رنگ کنیم که برای آن فقط یک رنگ محتمل باقی مانده باشد به گونه ای که نتوانیم اشتباهی در این رنگ آمیزی داشته باشیم.
- تعداد تلاش ها برای رنگ آمیزی قطعا کمتر از ۴N (امتحان کردن همه ی ۴ رنگ برای همه ی N ناحیه). بنابراین این تعداد تلاش ها برای رنگ آمیزی به صورت مهمی بستگی به تعداد ناحیه ها N دارد. در نتیجه این مفید خواهدبود که رنگ آمیزی قسمت سفید (رنگ نشده) نقشه را به زیر نقشه های غیر متصل جدا از هم که بعدا می توانند جداگانه رنگ شوند، تقسیم کرد. این نواحی فقط N۱ و N۲ ناحیه دارند (=N۱+N۲ N) ، که نیاز به حداکثر ۴(N۱ )+۴(N۲ )=۴N تلاش دارد که بسیار کمتر از ۴(N۱ )*۴(N۲ )=۴N تلاش است.
- اگر کسی می خواهد که کمترین تعداد رنگ های لازم برای رنگ کردن یک نقشه ی داده شده را پیدا کند آنگاه می تواند در ابتدا بررسی کند که آیا ۲ رنگ کافی است. این کار می تواند به صورت بهینه انجام شود.
اگر فقط دو رنگ (الف) و (ب) قرار باشد که استفاده شوند و یکی از نواحی رنگ آمیزی شده باشد، آنگاه چرخیدن پیرامون نقطه ی اشتراک، رنگ سایر نواحی را تنظیم می کند:
این قانون همچنین برای اولین تلاش رنگ آمیزی نقشه مفید است که ۳ یا ۴ لازم دارد. به عنوان مثال، اگر ناحیه ی ۱ در زیر به رنگ (الف) رنگ آمیزی شده، آنگاه نواحی ۲ و ۴ رنگ های متفاوتی نیاز دارندو ما هیچ ایده ای نداریم که آن رنگ چه خواهد بود اما می دانیم که رنگ کردن ناحیه ی ۳ با رنگ (الف) شرایط بیشتری بر رنگ آمیزی نواحی ۲ و ۴ اعمال نمی کند، چرا که آنها از پیش در همسایگی ناحیه ای با رنگ (الف) قرار گرفته اند.
شکل ۳ فقط یهک بخش کوچکی از نقشه را نشان می دهد اما روش فوق می تواند به شکل دقیق تری برای هر نقشه ای استفاده شود. اگر همه ی همسایه های ناحیه ی ۳ (در شکل ۳، نواحی ۲ و ۴) حداقل یک همسایه با رنگ (الف) دارند (در شکل ۳، ناحیه ی ۱)، رنگ کردن ناحیه ی ۳ با رنگ (الف) نمی تواند اشتباه باشد. دلیل آن این است که رنگ کردن ناحیه ی ۳ با رنگ (الف) هیچ محدودیت جدیدی برای همسایه های آن به وجود نمی آورد، چرا که آنها از پیش از داشتن رنگ (الف) ممنوع شده اند. بنابراین اگر رنگ آمیزی های بعدی مشخص شود که اشتباهی رخ داده است (به این دلیل که تعداد رنگ ها کافی نیست)، آنگاه هیچ امتیازی در اینکه برای ناحیه ی ۳ رنگی غیر از (الف) در نظر گرفته شود وجود ندارد، رنگ آمیزی های های دیگری باید دوباره امتحان شوند. - چه می شود اگر ناحیه ی ۳ در بالا، به صورت قطری همسایه ی ناحیه ی دیگری باشد، مثلا ناحیه ی ۹، که از پیش رنگ دیگری دارد، مثلا رنگ (ب)؟ آیا ۳ باید به رنگ (الف) یا (ب) رنگ شود؟ همچنین اینجا چک کردن همه ی همسایه های ۳ کمک کننده است چه آنها از پیش از داشتن رنگ (الف) یا (ب) ممنوع شده باشند. اگر هیچ یک از این موارد نباشد آنگاه ما می توانیم با رنگ آمیزی ۳ منتظر بمانیم.
