2026年10月22日 星期四

在 ChatGPT Codex 中設定 Comfy MCP 

到 Codex 選 Setting -> Plugins -> Add MCP servers
各欄輸入如下

Mame (可自取): Comfy MCP
Type: STDIO

Command to launch (填入電腦裡安裝的 uvx 路徑):
C:\Users\HugoKuo\AppData\Local\Programs\Python\Python312\Scripts\uvx

Arguments (設定如下，配合 Command to launch 的設定等同於 Codex 會執行 uvx --with comfy-cli>=1.14.0 comfy-mcp):
--with
comfy-cli>=1.14.0
comfy-mcp

Environment variables (填入你 local 端 run 起來的 ComfyUI 端點) :
COMFY_LOCAL_URL = http://127.0.0.1:8188



張貼者： 於 沒有留言 :
標籤： , , ,

Ollama AI 筆記 - 整合 Ollama AI, Open Web UI, MCP, MCPO, Stable Difussion, ComfyUI, Docker Compose

------------------------- WSL 設定安裝 Nvidia Container Toolkit -----------

# Windows 可在 WSL 上安裝 Nvidia Container Toolkit 讓 Docker container 可以使用 GPU 加速，參考 ollama/ollama - Docker Image 的 Nvidia GPU 部份

#設定 Repository

curl -fsSL https://nvidia.github.io/libnvidia-container/gpgkey \
    | sudo gpg --dearmor -o /usr/share/keyrings/nvidia-container-toolkit-keyring.gpg
curl -s -L https://nvidia.github.io/libnvidia-container/stable/deb/nvidia-container-toolkit.list \
    | sed 's#deb https://#deb [signed-by=/usr/share/keyrings/nvidia-container-toolkit-keyring.gpg] https://#g' \
    | sudo tee /etc/apt/sources.list.d/nvidia-container-toolkit.list
sudo apt-get update

#安裝 Nvidia Container Toolkit

sudo apt-get install -y nvidia-container-toolkit

#安裝完 Nvidia Container Toolkit 後可能會需要重新啟動 Docker

service docker restart
//或
systemctl restart docker

-----------------------------------------------------------------------------------

#可用 Docker 安裝 Ollama，例如 Docker compose 如下範例，啟動方：
docker-compose.yml : 

volumes: 
    ollama-volume:
    open-webui-volume:
services:
    #有設定 profile，啟動方式例如 docker compose --profile <profile name> up -d，
    #例 docker compose --profile service up -d
    ollama:
        image: curl -fsSL https://ollama.com/install.sh | sh:0.32.15
        container_name: ollama/ollama:0.32.15
        restart: unless-stopped
        profiles: [service]
        volumes:
            - ollama-volume:/root/.ollama
        ports:
            - "11434:11434"
        environment:
            #可依需求自行調整 OLLAMA_CONTEXT_LENGTH
            #太小可能會造成 context 被截斷 AI 無成正確回應，例如AI應該要找到並使用 MCP Tool 但卻回找不到 Tool 可用
            - OLLAMA_CONTEXT_LENGTH=8192
        #讓 container 使用 GPU，等同 docker run 的 --gpus=all 參數
        deploy:
            resources:
                reservations:
                    devices:
                        - driver: nvidia
                          count: all
                          capabilities: [gpu]
        logging:
            driver: "json-file"
            options:
                max-size: "1k"
                max-file: "3" 

    #除了直接用 CLI command, HTTP, Node JS, Python... 等使用 Ollama
    #也可撘配 Open Web UI 用瀏覽器使用 Ollama
    open-webui:
        image: ghcr.io/open-webui/open-webui:main
        container_name: open-webui
        restart: unless-stopped
        profiles: [service]
        ports:
            - "3001:8080"
        volumes:
            - open-webui-volume:/app/backend/data
        environment:            
            - OLLAMA_BASE_URL=http://ollama:11434
            # 如果 Ollama 是直接另外 run 在 host 宿主機上的話 
            #(如果沒有寫在 docker compose 裡所以得不到 ollama domain 的話)，
            # 也可設定 extra_hosts 然後設定 OLLAMA_BASE_URL 如下
            #- OLLAMA_BASE_URL=http://host.docker.internal:11434
        #extra_hosts:
        #    - "host.docker.internal:host-gateway"
        depends_on:
            - ollama
    
    # 使用 mcpo 將本地使用 stdio 的 mcp server 包成 Open Web UI 支援的 Open API endpoint
    mcp-server:
        image: ghcr.io/open-webui/mcpo:main
        container_name: mcp-server
        restart: unless-stopped
        ports:
            - "8000:8000"
        profiles: [service]
        volumes:
            - ./mcp-server:/mcp-server
        command:
            - --config
            - /mcp-server/config.json
              
    # ComfyUI 是底層使用 AI 繪圖 Stable Difussion 的一種介面實現
    comfyui:
        image: ghcr.io/lecode-official/comfyui-docker:0.6.3-comfyui-0.8.2-comfyui-manager-4.0.5-pytorch-2.9.1-cuda-12.6-cudnn-9
        container_name: comfyui
        restart: unless-stopped
        profiles: [service]
        ports:
            - "8188:8188"
        volumes:
            - ./comfyui/models:/opt/comfyui/models
            - ./comfyui/output:/opt/comfyui/output
            - ./comfyui/custom_nodes:/opt/comfyui/custom_nodes
            - ./comfyui/workflows:/opt/comfyui/user/default/workflows
        deploy:
            resources:
                reservations:
                    devices:
                        - driver: nvidia
                          count: all
                          capabilities: [gpu]
    
    #備分 docker volume 使可使用
    #可執行 sudo docker compose --profile backup_volume run --rm backup_volume
    backup_volume:
        image: alpine:3.23.3
        container_name: backup_volume
        profiles: [backup_volume]
        volumes:
            - ollama-volume:/usr/local/ollama-volume
            - open-webui-volume:/usr/local/open-webui-volume
            - ./backup_volume:/usr/local/backup_volume
        command:
            - sh
            - -c
            - |
                tar -cvf /usr/local/backup_volume/ollama-volume.tar -C /usr/local ollama-volume
                tar -cvf /usr/local/backup_volume/open-webui-volume.tar -C /usr/local open-webui-volume
    
    #還原備分 docker volume 使可使用
    #可執行 sudo docker compose --profile restore_volume run --rm restore_volume
    restore_volume:
        image: alpine:3.23.3
        container_name: restore_volume
        profiles: [restore_volume]
        volumes:
            - ollama-volume:/usr/local/ollama-volume
            - open-webui-volume:/usr/local/open-webui-volume
            - ./backup_volume:/usr/local/backup_volume
        command:
            - sh
            - -c
            - |
                tar -xvf /usr/local/backup_volume/ollama-volume.tar -C /usr/local
                tar -xvf /usr/local/backup_volume/open-webui-volume.tar -C /usr/local

/mcp-server/config.json (mcpo 的 mcp config，可以自行放入多個想要設定的 MCP server)，這裡的例子放了 fetch (可抓取網頁內容) 和 chrome-devtools (實際上可能 docker container 裡面還要裝 chrome 及一些設定才能使用)： 

{
  "mcpServers": {
	"fetch": {
	  "command": "uvx",
	  "args": ["mcp-server-fetch"]
	},	
    "chrome-devtools": {
      "command": "npx",
      "args": ["-y", "chrome-devtools-mcp@latest"]
    }
  }
}

--------------------  常用指令 ------------------
#進入 Ollama 互動介面 menu，畫面如下所示

ollama

Ollama 互動模式的選單畫面
跟 AI 問答的樣子：


#如果 Ollama 沒有被啟動，可用指令手動啟動
ollama serve

#下載安裝模型 model
#官方模型列表
ollama pull <model name>
#例如：
ollama pull gemma4:e4b

#模型下載列表
https://ollama.com/search

#運行模型 (模型沒下載會自行下載)，進行 chat
ollama run <model name>
#例如：
ollama run gemma4

#列出模型
ollama list

#刪除模型
ollama rm <model name>

# 也可使用 http 呼叫，例如：

curl http://localhost:11434/api/generate -d '{
  "model": "gemma4",
  "prompt": "Why is the sky blue?",
  "stream": false
}'

# 也可使用 Node JS, Python Library 呼叫
# 以 Node JS 為例，先 npm install ollama 安裝 package 後，執行如下

一般的非 Streaming 回答：

import ollama from 'ollama'
//一般的非 Streaming 回答
const response = await ollama.chat({
  model: 'gemma4:e4b',
  messages: [{ role: 'user', content: 'Why is the sky blue?' }],
})
console.log(response.message.content);

Streaming 回答：

import ollama from 'ollama'
//Streaming 回答
const message = { role: 'user', content: 'Why is the sky blue?' }
const response = await ollama.chat({
  model: 'gemma4:e4b',
  messages: [message],
  stream: true,
})
for await (const part of response) {
  process.stdout.write(part.message.content)
}

---------------------------- 與 Open Web UI 的搭配使用 ------------------

參考上方的 docker-compose.yml ，
使用 docker compose up -d 指令把 Ollama 和 Open Web UI 啟動起來後，
就可以用瀏覽器用下面網址進到 Open Web UI 介面去使用 Ollama
http://localhost:3001


Open WebUI 的 num_ctx 會覆蓋掉 Ollama 自己設定的 OLLAMA_CONTEXT_LENGTH，可依需求到 Settings -> Models -> Advanced Params -> num_ctx (Ollama) 設定 context length 修改




---------------------------- Open Web UI 與 MCPO 搭配使用 ------------------
Open Web UI 支援 Open AI 型式去連接 MCP Server，
如果我們本地端的 MCP Server 是走 Stdio 的話，
可以使用 MCPO 去把本地 MCP Server 包裝成 Open API 型式，
使用方式可參考上述的 docker-compose.yml 和 /mcp-server/config.json，
啟動好 MCPO Server 後，我們就可以用
http://localhost:8000/docs
觀看 MCP 的 Open API document 文件。

Open Web UI 的部份則要如下設定使用 MCP tool (AI Model 也要支持使用 tool 才行，例如 gemma 就行)。
  1. Settings -> Models -> 選擇 Model -> Advance Params -> Function Calling 選 Native (雖然它寫 Default 是 Native，但實測發現要選 Native MCP tool 才會被使用，可能是 bug ?)。
  2. Settings 的 Tools 區塊 -> Integrations -> 在 External Tool Servers 按 + 號 (Add connection) 加入新的 MCP tool，Name 可自己取，url 填 MCP 的 endpoint，例如 http://mcp-server:8000/fetch
  3. Settings -> Models -> 選擇 Model -> Tools 按 Select Tool 勾選要用的 MCP tool
  4. 跟 AI聊天的地方就可以看到可用的 MCP Tool 顯示在 Avaliable Tools 了
  5. 以下是跟 AI 聊天時使用了 fetch 這個 MCP tool 的畫面
---------------------------- Open Web UI 與 ComfyUI 搭配使用以文生圖 ------------------
ComfyUI 是底層使用 Stable Difussion AI 繪圖的 UI 介面，
使用串接各種 Node 的 input/ouput 的 workflow 方式來使用 Stable Difussion 進行 AI 繪圖，
docker 的配置可參考上述的 docker-compose.yml，
啟動 docker container 後，
可用
http://localhost:8188
進入 ComfyUI 的介面如下，範例為最基礎的文生圖 flow：


 
#可下載繪圖 Model 的地方
Civitai (主要以AI繪圖為主) : https://civitai.com/
Hugging Face (不只AI繪圖，也有其他種類的 AI Model) : https://huggingface.co/

#可以安裝 ComfyUI Manager custom node，提供了更多更細的設定功能，
例如顯示各 node 的 id
ComfyUI Manager 的 Git: ComfyUI Manger Git 
安裝方式可到 ComfyUI 的 custom_nodes 資料夾執行以下 git clone 指令即可
git clone https://github.com/ltdrdata/ComfyUI-Manager comfyui-manager

#可在設定中開啟各 node 的 id，之後方便跟 Open Web UI 整合，如下所示：

#將 ComfyUI 整合到 Open Web UI 的方式，
可參考 Open WebUI連接Stable Diffusion生成圖片，讓AI指揮AI繪圖 · Ivon的部落格
先在 ComfyUI 設計好繪圖的 flow，用 File -> Export (API) 把它導出成 API 用的 JSON 檔，
在 JSON 檔中可以看到各 ComfyUI node 的 id，如果有開啟如上述的 "顯示 node ID 的話"，
可以直接從 Flow Graph 中看到各 Node 的 ID。


到 Settings -> Images 把 Image Generation 的勾選打開，
Image Generation Engine 選 ComfyUI。

填入要用的 Model，必須是 ComfyUI 中有安裝的 Model，
不用是 ComfyUI Flow Graph 中使用的 Model，
所填的 Model 等下會帶入 ComfyUI flow 的 Load Checkpoint node 中。

填入 Image Size，例如 512x512。
填入 Steps，例如 20。
Base URL 填入 ComfyUI 的 endpoint，例如 http://comfyui:8188

按下 ComfyUI Workflow 的 Import 導入剛剛從 ComfyUI 導出的 JSON 檔。
在 ComfyUI Workflow Nodes 中填入各 Prompt 對應到 ComfyUI 中的 node ID，
各 Prompt 對應的 ComfyUI node 如下：
text : 就是 CLIP Text Encode (Prompt) node。
Model : 就是 Load Checkpoint node。
Width, Height : 就是 Empty Latent Image。
Steps, Seed ： 就是 KSampler

最後按下 Save 儲存設定，上述設定說明可參考下圖。



接著回到 Open Web UI 的聊天處，把 Image 勾選起來，
就可以在對話中開始要求 AI 生圖了，如下圖範例，Prompt 參考：
產生一張如下描述的圖片，請先將描述轉換成適合 Stable Difussion 的 英文 Prompt， 再用 Prompt 來產生圖片：
一隻狗在河裡遊泳




張貼者： 於 沒有留言 :
標籤： , , , , , , , ,

2026年8月1日 星期六

Rust 程式語言使用筆記

 Rust

說明文件:
https://rust-lang.tw/book-tw/ch01-01-installation.html

Windows 可到這安裝:
https://rust-lang.org/tools/install/

安裝後，可再自行設定客制的環境變數：

RUSTUP_HOME ：預設是   C:\Users\{userName}\.rustup，存放 Rustup 的 metadata 和 toolchains

CARGO_HOME ：預設是  C:\Users\{userName}\.cargo，是 Cargo home，Cargo, rustc, rustup 及一些其他 command 會放在這 %CARGO_HOME%\bin

IDE 可以用 Visual Studio Code + rust-analyzer plugin

-----------------------------------------------------------------------------

Rust 生態：

rustup ： 是一個用來負責安裝及管理 Rust 的工具
Cargo ：是一個 Rust 的建構系統與套件管理工具
Crates.io ： 是個讓 Rust 生態系統中的每個人都能發佈它們的開源 Rust 專案並讓其他人使用的地方 (類似 Java 的 Maven、Node.js 的 npm)

---------------- rustup 相關 --------------------------------------------------------------

#更新 Rust 版本
rustup update

#移除 Rust 及 rustup
rustup self uninstall

---------------- Rust 相關 --------------------------------------------------------------

#查看 Rust 版本
rustc --version

#編譯並建立執行檔 (如果在 Windows 中執行檔會是 .exe 檔)
rustc <filename>.rs

---------------- Cargo 相關 --------------------------------------------------------------

#查看 Cargo 版本
cargo --version

#建立 Cargo 專案
cargo new <專案名稱>

#編譯建立執行檔
#預設是 debug build，會將建立的執行檔 () 放至 <project folder>/target/debug/ 中
cargo build
#如果是要產生正式發佈用的執行檔，可以指定 --release，Cargo 會在編譯時最佳化編譯結果，產生的執行檔會放在 <project folder>/target/release 而不是 debug 資料夾 
cargo build --release

#編譯並執行專案執行檔 (也可自己用 command line 手動執行，只是要自己指定執行檔位置)，如果程式碼沒有改變，cargo run 不會重新執行 build
cargo run

#檢查程式碼，可用來確保程式碼會不會通過編譯，但不會產生執行檔
cargo check

#加入要依賴的 Crates
cargo add <crates名稱>[@<版本號>]
#範例：
cargo add rand
cargo add rand@0.8.5

 #建構所有本地端依賴函式庫的技術文件，並在你的瀏覽器中開啟
cargo doc --open

------------ 語法特色 -------------------

# 變數的 shadowing
# 變數可以遮蔽上一個同名變數，直到離開作用域，例：

fn main() {
    let number = "123";
    // u32 型別的 number 遮蔽(shadow) 了 &str 的 number
    let number: u32 = number.parse()
                            .expect("不是個數字");

    println!("這是個 {number}"); // 這是個 123
}

# tuple
# tuple 可存放多個不同型別的變數，例：

//tuple 例子
//也可以不特別寫出型別宣告 : (u32, &str, f64)
let tuple: (u32, &str, f64) = (3, "abc", 1.2);
println!("{}", tuple.1); // abc
let (_x, _y, z) = tuple;
println!("{z}") // 1.2

# statement (陳述式) 和 expression (表達式)，參考
#statement： 不會回傳值。
#expression ：會回傳值，不用分號結尾。
#例 ：
let x = 1 + 3; 是個 statement，其中 1 + 3 是個 expression
let x = {
    let y = 1 + 3;
    y
}
其中 y 是 expression，會回傳 y 的值給 x

# function 的定義、回傳值方式
# 用 fn 定義 function，用 -> 定前回傳型別
# 可以用 return xxx; 的 statement 提前回傳值，
# 或是在最後一行用 expression 表示回傳 

fn main() {
    println!("{}", add(1, 5)); // 6
    println!("{}", add(0, 0)); // 0
}

fn add(x:u32, y:u32) -> u32 {
    if x == 0 && y == 0 {
        //此為用 statement 回傳值
        return 0;
    }

    //此為用 expression 回傳值
    x + y
}

#enumeration
#可用 match 處理 enumeration 的各變體 (variants)

use std::cmp::Ordering;

fn main() {
    let x = 1;
    let y = 2;
    //使用 match 處理 cmp() 回傳的 enumeration
    match x.cmp(&y) {
        Ordering::Less => println!("less"),
        Ordering::Equal => print!("equal"),
        Ordering::Greater => print!("greater")
    };

    //處理 enumeration 並回傳值的例子
    let number = "123abc";
    let number: u32 = match number
                           .parse() {
        Ok(num) => num,
        Err(_) => {
            println!("無法轉成數字");
            0
        }
    };
    println!("{number}");          
}
張貼者： 於 沒有留言 :
標籤：

TiddlyWiki 筆記

------------------- Macro 相關 ------------------
#Macro 呼叫

#簡寫，但 param 只能用純文字，無法使用 text reference 或 transclude
<<my-procedure param="This is the parameter value">>

#完整寫法 參考
<$transclude $variable="macroName" parameterName="parameterValue"/>
#範例，以 list-tagged-draggable Macro 為例：
 <$transclude $variable="list-tagged-draggable" tag={{!!title}}/>

------------------- Filter 相關 ------------------
參考
#使用方式
#多個 step 可用 +, - 連接
#step 的使用方式
# 純文字可用 [parameter]
[operator:suffix[parameter]] 
#範例：
[tag[xxxTag]]

# text reference 可用 {text reference}
[operator:suffix{text reference}]
#範例：
[tag{!!title}]

# variable 可用 <variable>
[operator:suffix<variable>
#範例：
[tag<currentTiddler>]

------------------- 實作範例筆記 ------------------
# 在 Tiddler 中建立名為 task-end-date 的 field，用 datetime format: YYYYMMDDhhmmss 儲存，
然後再用 $list widget 將這些 Tiddler 以 task-end-date field 由新到舊排序。
#雖然 sort filter 是把 task-end-date 當成文字來排，但 datetime format 被當成文字排也符合照日期排序

<$list filter="[tag{!!title}sort[task-end-date]reverse[]]">
   <div style="margin-bottom:6px;">
      <span style="color:#888;">
        <$view field="task-end-date" format="date" template="YYYY-0MM-0DD"/>
      </span>
      &nbsp;
      <$link to=<<currentTiddler>>/>
   </div>
</$list>

張貼者： 於 沒有留言 :
標籤：

2026年6月20日 星期六

數獨求解 Java 實現三部曲 - 第三部 - 數獨求解器的 Java 實現

數獨求解 Java 實現三部曲：

  1. 數獨求解 Java 實現三部曲 - 第一部 - 精確覆蓋問題 (Exact cover) 與 X演算法 (AlgorithmX)
  2. 數獨求解 Java 實現三部曲 - 第二部 -  舞蹈鏈 (Dancing Links) (DLX)  - 可用來解數獨、8皇后問題(8 Queens, Puzzle) 等問題
  3. 數獨求解 Java 實現三部曲 - 第三部 -  數獨求解器的 Java 實現

經過上次兩篇文章後，我們知道了如何使用 AlgorithmX 來解 Exact cover 問題，並也知道了如何使用 DLX 的方式用程式實作解法後，今天我們要開始把學到的方法用來解數獨問題。

首先我們要把數獨問題轉成 Exact cover 問題，
只要得到了對應數獨的 Exact cover 矩陣後就可以用解 Exact cover 的方式來解數獨。

數獨的規則有四個約束 (constraint) 如下：

  1. 相同的格子 (cell) 只能有一個數字，例如一個 cell 如果是 1 就不能是 2~9 其他數字。
  2. 相同的 row 中相同的數字只能有一個，例如 row 1 上只能有一個 1、只能有一個 2 等。
  3. 相同的 column 中相同的數字只能有一個，例如 column 1 上只能有一個 1、只能有一個 2 等。
  4. 相同的宮 (box, 九宮格) 中相同的數字只能有一個，例如 box 1 上只能有一個 1、只能有一個 2 等。

為了簡化及方便討論，我們這裡先用 4x4 的數獨來討論，之後 9x9 的數獨原理也是一樣的。

4x4 的數獨如下所示，從左到右從上到下我們把各 cell 標上所在的 (row, column)：

(0, 0) (0, 1) (0, 2) (0, 3)
(1, 0) (1, 1) (1, 2) (1, 3)
(2, 0) (2, 1) (2, 2) (2, 3)
(3, 0) (3, 1) (3, 2) (3, 3)

我們把所有 cell 的可能 (可能是 1, 2, 3, 或 4) 和對應的約束關係寫成 exact cover 的矩陣如下，如果符合約束條件的話用 1 表示，不符合就不寫

(0, 0) 有一個數字 (0, 1) 有一個數字 (0, 2) 有一個數字 (0, 3) 有一個數字 (1, 0) 有一個數字 (1, 1) 有一個數字 (1, 2) 有一個數字 (1, 3) 有一個數字 (2, 0) 有一個數字 (2, 1) 有一個數字 (2, 2) 有一個數字 (2, 3) 有一個數字 (3, 0) 有一個數字 (3, 1) 有一個數字 (3, 2) 有一個數字 (3, 3) 有一個數字 row 0 有數字 1 row 0 有數字 2 row 0 有數字 3 row 0 有數字 4 row 1 有數字 1 row 1 有數字 2 row 1 有數字 3 row 1 有數字 4 row 2 有數字 1 row 2 有數字 2 row 2 有數字 3 row 2 有數字 4 row 3 有數字 1 row 3 有數字 2 row 3 有數字 3 row 3 有數字 4 column 0 有數字 1 column 0 有數字 2 column 0 有數字 3 column 0 有數字 4 column 1 有數字 1 column 1 有數字 2 column 1 有數字 3 column 1 有數字 4 column 2 有數字 1 column 2 有數字 2 column 2 有數字 3 column 2 有數字 4 column 3 有數字 1 column 3 有數字 2 column 3 有數字 3 column 3 有數字 4 box 0 有數字 1 box 0 有數字 2 box 0 有數字 3 box 0 有數字 4 box 1 有數字 1 box 1 有數字 2 box 1 有數字 3 box 1 有數字 4 box 2 有數字 1 box 2 有數字 2 box 2 有數字 3 box 2 有數字 4 box 3 有數字 1 box 3 有數字 2 box 3 有數字 3 box 3 有數字 4
(0, 0) 填 1 1 1 1 1
(0, 0) 填 2 1 1 1 1
(0, 0) 填 3 1 1 1 1
(0, 0) 填 4 1 1 1 1
(0, 1) 填 1 1 1 1 1
(0, 1) 填 2 1 1 1 1
(0, 1) 填 3 1 1 1 1
(0, 1) 填 4 1 1 1 1
(0, 2) 填 1 1 1 1 1
(0, 2) 填 2 1 1 1 1
(0, 2) 填 3 1 1 1 1
(0, 2) 填 4 1 1 1 1
(0, 3) 填 1 1 1 1 1
(0, 3) 填 2 1 1 1 1
(0, 3) 填 3 1 1 1 1
(0, 3) 填 4 1 1 1 1
(1, 0) 填 1 1 1 1 1
(1, 0) 填 2 1 1 1 1
(1, 0) 填 3 1 1 1 1
(1, 0) 填 4 1 1 1 1
(1, 1) 填 1 1 1 1 1
(1, 1) 填 2 1 1 1 1
(1, 1) 填 3 1 1 1 1
(1, 1) 填 4 1 1 1 1
(1, 2) 填 1 1 1 1 1
(1, 2) 填 2 1 1 1 1
(1, 2) 填 3 1 1 1 1
(1, 2) 填 4 1 1 1 1
(1, 3) 填 1 1 1 1 1
(1, 3) 填 2 1 1 1 1
(1, 3) 填 3 1 1 1 1
(1, 3) 填 4 1 1 1 1
(2, 0) 填 1 1 1 1
(2, 0) 填 2 1 1 1
(2, 0) 填 3 1 1 1
(2, 0) 填 4 1 1 1
(2, 1) 填 1 1 1 1
(2, 1) 填 2 1 1 1
(2, 1) 填 3 1 1 1
(2, 1) 填 4 1 1 1
(2, 2) 填 1 1 1 1
(2, 2) 填 2 1 1 1
(2, 2) 填 3 1 1 1
(2, 2) 填 4 1 1 1
(2, 3) 填 1 1 1 1
(2, 3) 填 2 1 1 1
(2, 3) 填 3 1 1 1
(2, 3) 填 4 1 1 1
(3, 0) 填 1 1 1 1
(3, 0) 填 2 1 1 1
(3, 0) 填 3 1 1 1
(3, 0) 填 4 1 1 1
(3, 1) 填 1 1 1 1
(3, 1) 填 2 1 1 1
(3, 1) 填 3 1 1 1
(3, 1) 填 4 1 1 1
(3, 2) 填 1 1 1 1
(3, 2) 填 2 1 1 1
(3, 2) 填 3 1 1 1
(3, 2) 填 4 1 1 1
(3, 3) 填 1 1 1 1
(3, 3) 填 2 1 1 1
(3, 3) 填 3 1 1 1
(3, 3) 填 4 1 1 1

寫出數獨對應 Exact cover 的 Algorithm X 用矩陣後，
就可以套用之前講過的 Dancing Links 求解法求出數獨的答案，
際際上一則數獨會有一些格子已經有填好的數子，而一個已有填好數字的格子不可能會再是其他數字了，
所以上述的矩陣可以先拿掉某些不可能的 row，
例如 (1, 1) 如果已經填好是 1 了，那我們就不需要 (1, 1) 填 2、(1, 1) 填 3 等的 row。

如上所述，我們可以用一樣的方法推導出一個 9X9 的數獨，各個格字是什麼數字時，轉成 Algorithm X 矩陣的 row 的公式如下：

private int[] getDancingLinksRow(int row, int col, int number) {
	    int[] algorithmXRow = new int[9 * 9 * 4]; //4 個約束，各約束有 9 個 column

	    //一個格字 (cell) 需有一個數字
	    int cellConstraint = row * 9 + col;
	    
	    //一個 row 需有一個 1, 2, 3, 4, 5, 6, 7, 8, 9
	    int rowConstraint = 9 * 9 + row * 9 + (number - 1);
	    
	    //一個 column 需有一個 1, 2, 3, 4, 5, 6, 7, 8, 9
	    int colConstraint = 2 * 9 * 9 + col * 9 + (number - 1);
	    
	    //一個 box 需有一個 1, 2, 3, 4, 5, 6, 7, 8, 9
	    int boxConstraint = 3 * 9 * 9 + ((row / 3) * 3 + (col / 3)) * 9 + (number - 1);

	    algorithmXRow[cellConstraint] = 1;
	    algorithmXRow[rowConstraint] = 1;
	    algorithmXRow[colConstraint] = 1;
	    algorithmXRow[boxConstraint] = 1;

	    return algorithmXRow;
	}

有了 getDancingLinksRow() 後，我們就能把一個 9x9 的數獨盤面轉成完整的 Algorithm X 矩陣了，如下： 

//將 int[][] board : 數獨的盤面 轉換成 Exact cover 問題的 Algorithm X 矩陣
	private int[][] buildSudokuDancingLinksMatrix(int[][] board) {
	    List<int[]> rows = new ArrayList<>();

	    for (int row = 0; row < board.length; row++) {
	        for (int col = 0; col < board[0].length; col++) {

	            if (board[row][col] != 0) {// 如果數獨的某一格已經有一個數字
	                int num = board[row][col];
	                rows.add(getDancingLinksRow(row, col, num));
	            } else {
	                	// 如果數獨的某一格還沒有數字，就產生對應 1~9 各種可能的 Algorithm X 矩陣 row
	                for (int num = 1; num <= 9; num++) {
	                    rows.add(getDancingLinksRow(row, col, num));
	                }
	            }
	        }
	    }

	    return rows.toArray(new int[0][0]);
	}

有了 Algorithm X 矩陣後，就可以用之前介紹的方式找出 Exact Cover 的解，
再把被選為答案的一組 Algorithm X 中的 row 子集
轉換成對應數獨的哪一個格子要填哪一個數字就可以了。

下面分享一下我的實作專案，裡面包括了三種數獨的求解實作，
分別是：

  1. 最簡單的 Backtracking 深度查詢遞迴演算法，效能最差，重試錯率很高。
  2. 用 Java 物件的方式實作 Dancing links，效能較差，且因為物件、鏈結等處理成本，有時花的時間會比 Backtracking 的時間還久。
  3. 用陣列 (pure int array) 的方式實作 Dancing links，效能較好，當數獨盤面的解很多時 (例如數獨一開始的已填好數字很少，存在很多個可能的解答盤面時)，效能比用物件方式實作快很多。

以以下數獨盤面為例，有 8008 個解答：

9 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
0 0 0 8 0 0 6 0 0
0 7 8 0 0 6 0 0 0
0 2 0 0 0 0 0 9 0
0 0 0 5 0 0 4 3 0
0 0 6 0 0 3 2 0 0
0 1 0 0 9 4 0 0 0
0 0 0 0 0 0 0 0 8
  1. Backtracking ： 耗時 20578 ms。
  2. 用 Java 物件的方式實作 Dancing links : 耗時 41717 ms。
  3. 用陣列 (pure int array) 的方式實作 Dancing links ：耗時 277 ms。

源碼分享：

數獨(Sudoku)解答器.zip

張貼者： 於 沒有留言 :
標籤： , , , ,
訂閱： 文章 ( Atom )