寶石方塊與圖的著色理論

從11月的某個星期六下午開始 , 我跟宜伶表妹兩人展開寶石方塊的大車拼 , 哈哈 , 不過終究是自己家裡的電腦 , 六十五萬分的最高分目前仍是本老爺打出來 , 不過表妹的63萬分可以說緊追在後
下面是該遊戲網址:
http://reflexive.net/index.php?PAGE=game_detail&AID=394&CID=21443
在 接觸這個遊戲時 , 我第一個想到的問題就是 , 在每次的消去後 , 隨機掉落的方塊有沒有可能讓我的下一步變成無解 , 也就是我無法再Swap任兩個方塊達成消去效果 , 要贏得寶石方塊的遊戲 , 我必須解決我這個疑惑 , 先說明該遊戲規則是 : 每次只能對調兩方塊 , 當三個直或橫相連且顏色相同的寶石會立即消除 , 我沒有太多的想法可以立即解答我這個問題 , 但我直覺反應就是 , 即時有機率也極低 , 甚至我可以大膽推論就是"沒有" , 不過 , 我表妹跟我說她在玩MSN的寶石方塊時有碰過無法消除的狀況 , 真的嗎!? OK!! Anyway , 是否會存在無法消除的寶石方陣 , 這牽扯到兩個變數 , 一個是該寶石方陣的 Size , 以Reflexive 的 Bejewled 2 遊戲來講 , 是8*8的方陣 , 第二個就是該方塊的顏色種類 , 以該遊戲(Bejewled 2)來看 , 我數過是7種顏色 , 所以 , 現在的問題用通俗的語言來問:

N x N 的方陣中用 N-1 種方塊去填它 , 則永遠都存在可經Swap後消去的解

這 句話還沒用數學去公理化它但已十足的非常咬文爵字 , 所以在看本篇文章的數學同好 , 建議先去Reflexive下載該寶石方塊的遊戲來玩玩 , 不過我可沒有在幫該網站打廣告 , 現在回到上述這個問題 , 我要提出一個 Capacity 或是 Threshold的概念 ,

是否永遠存在可經Swap而消去的N x N的方陣的寶石方塊種類的最大值為 N-1 !?

換個角度說 :

是否對於所有 M>N-1 , 則必定會存在一個無法經Swap而消去的 N x N 方陣 with M種寶石 entry !?

這問題的猜想是否正確 , 可以先從小例子出發 , 首先 , 我們簡稱永遠都會有可經由Swap而消去的方陣為 eliminatable square :

考慮 N=3 的方陣 , 該方陣在填入M種寶石後 , 則仍是eliminatable square的M最大值為何 ??

YA!! M= 2 , Why !? Obviously , Because 動手用兩個數字填 3 x 3 的方陣 , 暴力法也只需要
2^9=512種 , But 如何確定 M=3的時候會破功 , 也就是會存在經由倆倆Swap後仍然無法eliminate的方陣 , 有呀 , 下面這就是一例 :

0 0 1
0 0 1
1 2 2

不過 , 當初再思考這問題時 , 我曾經考慮下面這個例子是否符合我現在該遊戲面臨的問題

0 0 1
0 0 1
0 0 1

該例子很明顯經由倆倆Swap後決對無法產生可消去的方塊 , 但這例子是不成立的 , 因為我們必須對我們討論的方陣加一個條件就是 :

該方陣本身沒有連續三個相同數字相連(不論直或橫來看)

從上面這個敘述開始 , 我發現我面臨的也許是在組合數學領與中相當有名的 "著色問題" 的變形 ,
更精準來說 , 應該是傳統著色理論的極大推廣並再變形處理 , 為什麼說是推廣 ? 因為之前處理圖著色問題都是在"兩個Vertex之間的Relation"給予某特條件 , 簡單來說 , 我現在有 "連續相連的三點需不能同時著相同顏色" , 注意喔 , 這句話是指"不能同時" , 也就是相連三點中至少需存在一點
顏色要不相同例如:

100 , 010 , 001 , 011 , 101 , 110

於是決定廢話不多說 , 我在沒有相關文獻的支援下, 我要給一個著色理論的定義推廣來數學公理化寶石方陣問題 :

(待續)