在友晶DE1-SOC開發(fā)板實現(xiàn)數(shù)獨謎題求解器

引言

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

1. 項目概述

項目說明

介紹項目之前先介紹數(shù)獨游戲。

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

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

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

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

2. 反向追蹤算法

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

3. 硬件設計

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