Sudoku - 案例

講了一些Sudoku的目視法，尤其是所謂的二階、三階的應用。說實在，有時真的是可遇不可求。
剛好有範例，就展示一下。

上圖中，中中大方格，他交錯限制來源中，6只有兩個，而他的覆蓋點只有一個。所以，並不能取得唯一解。此時，千萬別放棄。他就是一個三階的應用。

1與2，就是一般限制式。可是，很幸運的是，交錯來源的交錯來源，可以讓已知變成第2層級。也就是3可以變成4。
但是這個結果，對於中中大方格並沒有幫助。可是，經由他在加上另一個左下大方格的交錯來源，使得已知層級又到第二，也就是5的地方。如此在加上原本的1與2就可以得到中中大方格的右上小方格就是6了。

同一個題目，右中大方格的右上小方格應該是什麼呢？

看下圖吧。

解了這個，其他的9就全解了。

Sudoku - 4

上一回有點算是補充加強說明。今天得把「目視法」做個了結。

其實，我們想盡辦法就是要讓限制條件達到兩橫兩縱，這樣子就可以取得唯一解。只可惜，天不從人願。往往交錯條件來源，也是個未知數。

但是，「未知」也有兩個層級。
1. 我知道她在哪個小方格。
2. 我知道她應該在哪一橫（縱）。

第1個層級當然是我們最終目標；第二層級卻可以讓我變成別人的限制條件。
現在的問題時，交錯來源就是不知道呀，所以才無法進階到第1層級呀。
別忘了，每個交錯來源也有交錯來源。而他的交錯來源，可以不需要讓他實踐第1層級，只要能實踐到第2層級，就可以讓他變成一個限制式，那覆蓋點的要求就可以降低了。也就是說，由交錯來源的交錯來源取得唯一解，這個就是轉折，就是我說的「階」。
下圖不屬於二階，但需用他來說明。對中間這個大方格而言，上中、下中、左中、右中就是他的交錯來源。其中右中同數字(此範例為5)尚不知，不過，根據基本條件，他一定會是在下橫，這樣子自然是一個限制式。因為是基本條件，還算是一階的部份。而且，實際情況，常常不是這麼剛好的啦。

現在，右中大方格的交錯來源變成了，右上、右下、左中、中中。注意，中中才是我們要去解決的問題，中間的紅5是答案，不是已知。
我們再來看下圖。注意，他與上圖示不同。

原本光看右中，若他的負責範圍並沒有覆蓋，而且也不知道同數字應該在哪裡，但是，經由他的交錯來源，可以限制他，雖然無法達到第1層級的正確答案，但是我知道，同數字應該一定會在下橫中。進而形成了限制式，也決定了中中這個大方格中的中中小方格的數字，在本例中為5。
這種特性者，稱之為二階限制式。
其實，這樣子的變形相當多。因為，每一個大方格都會有四個交錯來源。所以，二階也會有四個交錯來源。
哈～不想多寫了，如果有跟上，應該就知道什麼是三階了吧。
同一個情境，但是左中的5並不清楚，但是藉由他的交錯來源，可以定義出他不需是上橫，進而決定右中必須在下橫，那中中的大方格中的中中小方格就必須是多少了。

 留一個伏筆。原則上，大部分的入門、普通困難的用這個方法「眼睛」瞄一瞄應該就會有解。很快的補完後，接著就會用基本限制式把缺的補起來（因為，當已知數字很多時，用這方法不容易抓出縱橫的關係）

 也許我們就來試一下吧。仍然採用第一次抓取的題目。

中中大方格 看到他交錯來源1的話有四個，那他的右上那個就是1了。這個沒什麼技巧，眼睛掃描一下即可。
左下大方格中，其實也是交錯來源都有1。只是說，他已經有兩個很好的覆蓋點，兩縱也決定右下小方格為1。

來看2吧。

右中大方格很幸運一橫一縱，再加上三個覆蓋點，當可以確定小格子中右中一定是2。
左下大方格也是可以一眼看穿。
至於中中大方格，只有右中與左中，需要兩個覆蓋點，可惜，目前只知道一個右上那個1的已知點。看起來無法找出無一解。
但是，注意，他的上中交錯來源，卻因為他的右上大方格的關係，讓我確信上中的大方格，其2一定是在中縱，進而對中中這個大方格多了一個限制式，那就可以篤定的說，左上那個小格就會是2了。
再補一個例子。注意看左下這個大方格，是不是只剩一個未知呢？不是可以大方的填入3。

接著他又可以造成左上大方格中的右下小方格，取得唯一解3。然後，又可以造成右上大方格中的右上小方格為一解為3。接著又可以決定右下大方格中的左上小方格又是唯一解3。

就是這樣子，瞄過來，瞄過去，再配合原始限制條件，很快地就可以把數字一一填上去。

 順序：綠色─〉藍色─〉黃色─〉橘色。這樣3又完成了。

4的部份則有兩個仍無法確定。顏色順序同前。

6的部份，顏色順序同前。
這個完成後，右中與下中的大方格中，右回到基本限制式。

然後，引發後續幾個回到基本限制式。

接著7也可以處理完。

有回到基本限制式。
如此循環，很快地就可以把所有數字填入。
後續就省略了吧。

當然，對於進階、專家級的題目光靠這個有時可能不足。但，大原則是不變的。

Sudoku - 3

有了一階限制式的基礎之後，我們再來更進階的應用。
上回有提到邊際效益的問題今天再來把這多說明一點。

所謂的邊際效益，就是限制式與覆蓋點的關係。
就是說一個限制條件（某數字已知在某橫軸或縱軸上，就是一個限制條件）到底能夠為另一個大方格覆蓋多少小方格。
回想之前，要決定每一個大方格中的小方格，如果有四個限制式的話（橫軸，縱軸各二），那一定可以確認其唯一值。
回到最基本的遊戲規則，要決定大方格中的某一小方格，那就表示其他的8個方格必須已知（覆蓋，對這個方法而言，我不需要知道他是什麼，只需要知道他有沒有被覆蓋）。反過來說，要決定一個大方格中的小方格，就會有8個未知。如果這8個未知都有人覆蓋，那又回到基本條件。有點繞口令。只是想表達，限制式與覆蓋能夠搭配好，就能得到唯一值。

 下圖中，少了一個限制式，但是剛好他「負責範圍」有人幫忙覆蓋的話，那表示這個限制式的意義還是有的。

 這個「負責範圍」，會有邊際效益的問題。看圖可以知道，大方格中的四個角落的小方格，基本上可以被橫或縱給限制住。同時有縱與橫，那就太浪費了。
所以，同時是兩個橫，或同時是兩個縱那是最理想的事情了。

同為縱

一橫一縱

所以，當我們用「眼力」來找的時候，他的順序性應該是
1. 最理想狀態，當然是兩橫兩縱。0個負責範圍覆蓋點。
2. 兩橫(縱)一縱(橫)，外加1個負責範圍覆蓋點。
3. 兩橫(縱)，外加兩個負責範圍覆蓋點。
4. 一橫一縱，外加三個負責範圍覆蓋點。
5. 一橫(縱)，外加五個負責範圍覆蓋點。
6. 縱橫都沒有，外加八個負責範圍覆蓋點。

等等，要求的覆蓋點增加太快了吧，是的，這就是他的數學特性。
（其實，誰說Sudoku一定得9X9呢）

反過來說，接著要努力的就是如何降低覆蓋點的要求。
如何能夠增加限制式（多知一個橫，或多知一個縱），既使我不知道他正確的答案是什麼。

Sudoku - 2

知道Sudoku規則後，當然可以按照其規則來把剩下的數字填入。等等，若是這樣子的話，要填一個數字，就得知道其他8個是什麼數字。這樣子對於要用「視力」的方式，似乎不太好。當然希望能一眼望去，用最少數字下決定，不是很好嗎？這就是我開始想聊聊的方法。

限制式

限制式可以分成好幾階。所謂的「階」是指要轉折幾次。
先來看看通則。
每一個小方格內的可填入的數字，將受限於其兩個縱軸與兩個橫軸之限制。
中間大方格的中間小方格，之所以必須填入5，是因為他的左右兩個縱軸出現了5。上下橫軸中出現了5。中間那個空格只好是5了。

這樣子，我們是不是只要發現在題目中，縱軸，橫軸都分別出現同一個數字時，那他們交錯下的那個大方格裡的小方格，就得跟他的數字一樣了。而且是，只要有出現即可。不在乎是哪一個，因為這是基本限制條件，在同一個橫軸或縱軸都只能出現一次。如下圖。

若有四個已知數字來決定時，我稱之為一階限制式。
當然，事與願違。不可能剛好四個都有，那就得看其變形。
也就是看交錯大方格內，其他未知的方格中是否為其他已知數字來覆蓋。如下圖中，因為下橫軸沒有5，但是卻在他的下方那個小方格有其他非5的數字（X可以為其他非5的數字）這樣子的話，也是滿足了限制式。

相同的道理，再少一個已知呢。這時候就得小心，會發生「已知數字的邊際效益」的問題。
上圖中，已知少了橫軸。接下來少了橫軸與少了縱軸，所衍生的邊際效益是不一樣的。
再少另一個橫軸，只需多加一個已知。如下圖。

如果少的卻是縱軸呢？也就是說，限制式剩一個橫軸與一個縱軸，那就變成需要三個已知。如下圖。

不過，也別太緊張，如果無法確認，也就是說，應該要三個已知，卻只有兩個已知，那表示這個5還不能確定。（可以出現在兩個地方）那沒關係，就先去看別的格子就好。
只要能確認是唯一的，就可以放上正確的數字。

這都可以用眼睛瞄一瞄就可以知道。

如果真的遇到下列情形時，有沒有辦法解決呢？這時候就要來看二階限制式了。

也就是多一道程序。既使我不知道他會填入哪一個，但我知道一定要填入這一排（這一列）。相對地，不就是多了一條限制式了嗎？
留到下回分解。

上圖是上次剪下來的題目。
這是入門級題目，所以有很多數字足夠用今天的技術。
看看中間大方格中，若要填入1的話，是不是他另外兩個縱軸與兩個橫軸都有1了，那也只剩下右上角可以放1了。是不是，眼睛瞄一瞄就可以了。
左下角大方格中，要放1，不也是嗎？
那右中大方格中要放2的話，已知三個2，但是另外一個幸運地被其他數字覆蓋了。是不是只能在上中那個小方格填入2呢？
這樣子，霹哩趴啦就可以填入一堆了。
這個是入門題目，進階一點的空格會更多，但是，掌握交錯限制式，就可以填入不少數字。
但是，

Sudoku - 1

個人是蠻喜歡玩Sudoku的。他是個遊戲，也是個數學。我只想整理整理想法而已。
首先得先要有Sudoku的題目。目前有很多來源，隨便用Google搜尋就可以找到一堆。手機上當然也有。這就不去討論了。

先來看規則。

他是在一個9x9的方格中，再分隔成3X3有9個大方格。也就是每一個大方格裡又有九個小方格。這個小方格裡，可放1~9的某一個數字。

他有三個基本限制式
1. 每一橫軸有9個小方格，可任意放1~9之數字，但不可重複。

2. 每一縱軸有9個小方格，可任意放1~9之數字，但不可重複。

3. 在大方格中的9個小方格內，可任意放1~9數字，但不可重複。

經由這三個基本條件的要求下，需要再多一個神奇45。也就是當數字皆填滿時，橫軸、縱軸，與大方格的總和都必須同時滿足數字相加為45。

但是，Sudoku的題目，就是挖空了一些小方格，讓你去填入1~9數字並滿足上述條件。
洞挖的越多，那每個小方格的可能解，就會多個讓你無法決定。此時，也是解題的樂趣。
下圖就是抓取google應用程式的其中一個題目。

他的數學要求就是45。真正的重點在於演算法。但是，若從遊戲的角度，就別鬧了。
後續，就先從遊戲的角度來聊聊光用眼力就可以進行解題的技巧。