Meowdoku 解題器怎麼從截圖讀出棋盤
Meowdoku 解題器接受一種不尋常的輸入：一張謎題的照片，而不是謎題本身。在解出任何東西之前，它得先搞清楚棋盤在截圖裡的哪個位置、被分成幾格、哪些格子共用顏色。以下是每一步實際怎麼判斷的，以及它現在還會在哪裡出錯。
真正困難的不是讀顏色
Meowdoku 的截圖大部分都不是棋盤本身。裡面通常有標題列、一排規則小標籤、計時器，還有系統狀態列，上面往往還有某人的電量百分比。棋盤只是中間某處的一個正方形色塊，位置和大小都取決於截圖來自哪支手機，而且畫面裡什麼都沒有標示。
在讀出任何一個顏色之前，有三個未知數必須先確定下來，只要漏掉其中任何一個，答案不會只是稍微有點偏差，而是變成一個完全不同的謎題，卻被自信地解出來。
一切都在你的瀏覽器裡執行
截圖從來不會被上傳。圖片會被畫到一塊畫布上，再從裡面讀出像素，接下來的每一步都在你自己分頁裡的那一組數字陣列上執行。沒有任何伺服器看得到這張圖，也沒有任何一份副本存在你的裝置以外的地方。
一張你從來沒有傳送出去的圖片，就不會有人需要儲存它，或向你保證已經刪除；而一條沒有任何網路傳輸的處理流程，能在遠低於一秒的時間內讀出一個棋盤。
它做的第一件事，是把圖片縮小，讓比較長的那一邊最多只有 900 像素。後面的步驟並不需要更多細節，因為目標是每一格取出一個代表色，而不是拍出一張銳利的照片，而且每個像素的運算量，會隨著縮放比例的平方下降。
第一步：找出棋盤
解題器一開始會先猜測頁面背景色。它會取樣圖片四邊各 7% 的邊框範圍，並取每個色彩通道的中位數，而且會先把過於鮮豔的像素從樣本裡剔除，這樣一個剛好切到角落的鮮豔橫幅，就不會把估計值拉偏。
接著每個像素都會依據它跟這個估計值的距離，被標記成背景或非背景，再逐列統計非背景像素的數量。這樣就能得到一條由上到下的密度曲線：空白邊界幾乎是零，棋盤範圍很高，標題列則介於兩者之間。連續高密度的列會成為候選區塊。格線在密度曲線上刻出的細微凹陷會被補平，因為一條一像素寬的格線不算是間隔，但棋盤上方真正的空白區域不會被補平，這樣才能把規則小標籤排除在候選範圍之外。
接下來才是真正關鍵的檢查：是不是正方形。每個候選區塊會沿著另一軸掃描，找出左右邊界，只有寬和高相差在大約三分之一以內、且至少涵蓋畫面 3% 的候選會被留下來。橫幅、標籤列和狀態列全都又寬又扁。在一張 Meowdoku 截圖裡，棋盤是唯一一個接近正方形的東西。
如果找不到任何接近正方形的區塊，解題器會假設你已經先裁好了棋盤，直接使用整張圖。這是一個不錯的失敗方式：它定位不出來的那張圖，通常本來就不太需要定位。
第二步：數出格數
知道棋盤在哪裡，並不代表知道它是 7×7 還是 9×9。為了判斷這件事，解題器會沿著棋盤框跨出 400 步，在每一步測量顏色跟前一步比起來變化了多少，並在另一軸上取 48 條平行線的平均值，這樣單獨一隻深色的貓才不會被誤判成一條邊界。格線的邊緣會呈現出規律的高峰。
它不是直接測量高峰之間的間距，而是去驗證各種假設。針對從 4 到 12 的每一個 N，它會算出這種格數下，N−1 條內部邊界應該落在哪裡，檢查每個位置附近是否有高峰，然後根據平均命中程度替這個假設打分數。最能解釋整條曲線的那個 N 就是答案。
兩個軸向會分別測量，再互相校對，因為真正的棋盤一定是正方形。如果水平方向算出 8、垂直方向算出 7，代表其中一邊漏看了一條不明顯的線，所以應該相信數字比較大的那一個。
第三步：沿著一個環取樣每一格，而不是取中心點
這一步不是那麼直覺。找到棋盤、數完格數之後，解題器需要每一格各取出一個顏色，最自然的做法似乎是讀取這一格正中央的像素。
但那正好是最錯的一個像素。格子的正中央，正是貓咪站的位置，也是被你標上 ✕ 的格子上，✕ 符號所在的位置。在一個已經解了一部分的棋盤上——而這正是你實際上會想尋求幫助的那種棋盤——取中心點會把一大堆格子誤讀成貓的顏色，還會憑空生出畫面上根本不存在的區域。
所以每一格改成在三個同心環上取樣：分別在距離中心 28%、36% 和 43% 的位置，每一圈各取十六個角度，一格總共四十八個樣本。這個環形範圍剛好落在格子邊界之內，所以不會取到格線，也剛好在圖示之外，所以不會被貓咪影響。這些樣本會取每個色彩通道的中位數，而不是平均數，這樣少數落在鋸齒邊緣或反光上的樣本，會被直接排除，而不是被混進整體結果裡。
第四步：把顏色聚成剛好 N 個區域
現在有 N×N 個顏色要分類成不同區域。這是一個分群問題，而分群問題通常特別麻煩的地方在於：你不知道該找幾個群集，而猜錯就會悄悄毀掉整個答案。
Meowdoku 剛好知道答案。規則已經把它定死了。一個 N×N 的棋盤，一定被切成剛好 N 個相連的區域，所以一個 9×9 棋盤就是九個，不會是八個，也不會是十個。就是這一個事實，把一個開放式的問題變成封閉式的問題，也就是 k 值已知的 k 平均演算法——這也是為什麼這一步很穩定，而前面兩步只能盡力而為。
還有兩個細節讓它保持穩定。起始的群集中心採用「每次選最遠的」方式：每一個新的中心，都是離目前所有已選中心最遠的顏色，這樣起始點才會分散在真正出現的色相上，而不是讓兩個中心搶著爭同一種淡黃色。而且因為這種選取方式是確定性的，不是隨機的，同一張截圖每次都會得到同一個棋盤。如果同一張圖上傳兩次，解題器卻給出不同答案，那還不如沒有這個功能。
區域編號之後會依照閱讀順序重新編排，所以左上角那一格所在的區域會排第一個。解題本身完全不依賴這個編號；棋盤只是照著一般人會用的方式編號而已。
第五步：求解，以及第二組解答代表什麼
有了區域編號的格子和棋盤大小，求解就是很直接的部分，跑的是遊戲產生棋盤時用的同一套限制條件解題器。有意思的決定是：它會要求找兩組解，而不是一組。
一個讀取正確的 Meowdoku 棋盤，一定恰好只有一個解，因為產生器在建立棋盤時就保證了這一點。所以如果找到兩組解，代表正在求解的棋盤，其實不是截圖裡的那個棋盤，某一格被分到錯誤的區域了。如果完全找不到解，代表另一個方向出了誤讀，讓限制條件互相矛盾。要求第二組答案，等於把求解結果變成對讀取品質的一種驗證。
哪裡會出錯，以及為什麼你可以手動塗改
第四步之前的每一步都是盡力而為，而且每一步都有可能出錯。以下是實際會遇到的情況：
- 壓縮過的截圖裡，兩個相近的色相。 嚴重的 JPEG 壓縮雜訊，可能會把兩個區域的顏色拉得太接近，讓 k 平均把它們合併，再把某個第三區域硬是切成兩半，好讓總數維持在 N。
- 拍螢幕的照片，而不是截圖。 斜角拍攝會讓格子間距變得不均勻，這會同時破壞格數計算和環形取樣的前提假設。
- 裁圖時留了一部分介面。 留在畫面裡的半個規則標籤，可能會讓棋盤框偏移幾個像素，靠近邊緣時，這點偏移就足以讓取樣環滑進隔壁那一格。
- 一個快解完的棋盤。 棋盤上的貓和 ✕ 越多，每一格被遮住的比例就越高。取樣環在這種情況下幫助很大，但也不是萬能的。
手動塗改工具是設計本身，不是備用方案
這正是為什麼每一個偵測到的格子，都可以用滑動的方式重新上色，也是為什麼解題器會拒絕執行，直到畫面上剛好出現 N 個不同的區域為止，並告訴你目前有幾個。這道防線能在上面提到的「合併再切開」這種錯誤，變成一個自信卻錯誤的答案之前，先把它攔下來。
棋盤畫回給你看的時候，用的是從你自己截圖裡取樣出來的顏色，而不是遊戲原本的調色盤，這樣你一眼就能檢查讀取結果對不對，而不是只能選擇相信它。如果某一格在我們畫面上看起來顏色不對，那它就是真的不對，滑一下就能修正。偵測負責處理繁瑣的九成多，剩下的判斷交給你。
在你自己的棋盤上試試看
拿一張你卡關的棋盤截圖，丟進解題器，看看它哪些格子會讀錯。錯讀的地方，幾乎都出現在這篇文章預測的那些位置。
解題器完全在你的瀏覽器裡執行。截圖只會在你的裝置上讀取，絕不會被上傳。