引言

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

1. 項(xiàng)目概述

項(xiàng)目說(shuō)明

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

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

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

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

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

2. 反向追蹤算法

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

3. 硬件設(shè)計(jì)

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

4. 軟件設(shè)計(jì)

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

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

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

通過(guò)鼠標(biāo)和鍵盤(pán)處理用戶(hù)的輸入和交互。

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

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

5. 源碼下載

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