引言

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

1. 項(xiàng)目概述

項(xiàng)目說明

介紹項(xiàng)目之前先介紹數(shù)獨(dú)游戲。

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

它極具挑戰(zhàn)性，因?yàn)橹挥幸环N解法，而提供的線索非常有限。如果您感興趣，不妨嘗試自行解決這個謎題，并將結(jié)果與本文的FPGA實(shí)現(xiàn)結(jié)果進(jìn)行對比。

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

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

2. 反向追蹤算法

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

3. 硬件設(shè)計

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

4. 軟件設(shè)計

該項(xiàng)目使用運(yùn)行在HPS上的Linux操作系統(tǒng)來編譯和執(zhí)行Sudoku謎題解法所必需的C程序。

C程序的主要目標(biāo)包括:

在VGA顯示器上繪制數(shù)獨(dú)網(wǎng)格。

通過鼠標(biāo)和鍵盤處理用戶的輸入和交互。

將數(shù)獨(dú)謎題數(shù)據(jù)發(fā)送到FPGA進(jìn)行處理。

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

5. 源碼下載

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