引言

今天繼續常春藤名校之一——康奈爾大學的FPGA課程ECE 5760典型案例分享：基于DE1-SOC開發板的FPGA數獨謎題求解器。

1. 項目概述

項目說明

介紹項目之前先介紹數獨游戲。

數獨游戲是一種廣受歡迎的數學游戲。在其基本且被廣泛認可的形式中，數獨包含一個 9 × 9 的網格，其中某些方格已填入數字。該游戲的目的是通過填入剩余的方格來完成網格，同時確保每一行、每一列以及九個 3 × 3 子網格都恰好包含數字 1 到 9 各一次。解決該游戲的訣竅在于利用網格中包含的數字作為線索來推導出可能的解。下圖是世界最難的數獨謎題之一示例。

它極具挑戰性，因為只有一種解法，而提供的線索非常有限。如果您感興趣，不妨嘗試自行解決這個謎題，并將結果與本文的FPGA實現結果進行對比。

該項目是在友晶DE1-SOC開發板實現數獨謎題求解器，用戶可以使用鼠標和鍵盤控制Sudoku網格。我們利用FPGA上的反向追蹤算法高效解決謎題。片上CPU在FPGA的幫助下，在VGA屏幕上顯示Sudoku網，用戶可以輸入數字并直觀地看到謎題。FPGA實時處理解題過程，更新網格并提供即時反饋。

求解器的速度取決于數獨謎題的難度和解的數量。對于一個簡單的數獨謎，求解者可以在幾百微秒內完成。然而，對于一個較難的謎題，或者如果第一個空格的解是一個較大的數字，可能需要大約10000微秒才能完成。

2. 反向追蹤算法

從第一個空格開始，依次測試從1到9的數字。如果一個數字滿足所有三個條件——這意味著它沒有出現在同一行、列或塊中——就將該數字放入該格中。然后繼續到下一個空格，并使用更新的Sudoku棋盤重復這個過程。繼續時可能會遇到一個在1到9之間的數字不匹配的格。當這種情況發生時就返回到之前的格并嘗試替代數字。鑒于一個Sudoku謎題只有一個解，系統將不斷拒絕無效解，直到找到一個符合所有條件的正確解。

3. 硬件設計

硬件設計分為四個模塊:控制單元、數獨寄存器、更新器和檢查器，如下圖所示。每個模塊具有不同的功能，并通過圖中指示的信號進行通信：

4. 軟件設計

該項目使用運行在HPS上的Linux操作系統來編譯和執行Sudoku謎題解法所必需的C程序。

C程序的主要目標包括:

在VGA顯示器上繪制數獨網格。

通過鼠標和鍵盤處理用戶的輸入和交互。

將數獨謎題數據發送到FPGA進行處理。

從FPGA接收解決方案并將其顯示在VGA上。

5. 源碼下載

https://github.com/dengyutu/CU-Project-FPGA-Sudoku-Solver