全國中小學科展

依全國中小學科展屆次查詢

依相關評語查詢

解開點線面 - 用SAT Solver解開Flow Free遊戲

科展類別

全國中小學科展作品

屆次

第59屆--民國108年

科別

生活與應用科學(一)科

得獎情形

探究精神獎

學校名稱

新竹縣立成功國民中學

指導老師

吳宗倫;謝東育

作者

黃仲璿;林立宸

關鍵字

可滿足性問題,布林運算,程式

摘要或動機

我們研究了Flow Free遊戲的特徵後,發現他與另一個遊戲——數獨在規則上有許多相似處。於是我們先轉而研究網路上已經有多種解法的數獨遊戲,嘗試將那些方法套用於Flow Free去解。經過多次嘗試,我們發現一種邏輯簡單且可行的方法 — SAT Solver。SAT Solver (Boolean Satisfiability Problem Solver或作Propositional Satisfiability Problem Solver)最大的特色是需要使用Boolean Variable,也就是一切條件都必須轉換成是非題。「這一格是哪一個顏色?」變成了「這一格是不是顏色一?是不是顏色二?是不是顏色三?...」。經過研究,我們得到一個結論 : 如果一個問題沒有步驟性(上一步驟不影響下一步的答案)且所有條件都能以是非條件式表示,就可以用SAT Solver解開。

解開點線面 - 用SAT Solver解開Flow Free遊戲

Adobe Reader(Pdf)檔案