Floodfill ©

300000

427276

209822

Floodfill^©

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₁ dan N₂ (N= N₁ + N₂),memerlukan sekarang paling banyak hanya 4^N₁ +4^N₂ percubaan yang jauh lebih sedikit daripada 4^N₁ × 4^N₂ = 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.

Floodfill©

Panduan untuk Permainan Floodfill

Floodfill^©