數獨求解器與生成器（回溯算法實現）

摘要

本畢業設計旨在利用MATLAB技術實現一個基于回溯算法的數獨求解器與生成器。通過深入分析數獨游戲的規則和回溯算法的原理，設計并實現了數獨求解的核心算法，同時開發了數獨生成功能，能夠生成符合規則的有效數獨謎題。系統采用MATLAB圖形用戶界面（GUI）進行設計，提供了友好的交互界面，方便用戶輸入數獨謎題、求解數獨以及生成新的數獨謎題。經過測試，該系統能夠高效準確地求解和生成數獨，具有較高的實用性和穩定性。

關鍵詞

MATLAB；數獨；回溯算法；求解器；生成器

一、引言

1.1 研究背景與意義

數獨是一種基于邏輯的數字填充游戲，它要求玩家在一個9x9的網格中填入數字1到9，使得每一行、每一列以及每一個3x3的子網格內的數字都不重復。數獨游戲不僅能夠鍛煉玩家的邏輯思維能力，還具有一定的趣味性和挑戰性，因此受到了廣泛的喜愛。

隨著計算機技術的發展，利用計算機程序來求解和生成數獨謎題成為了一個熱門的研究方向。MATLAB作為一種強大的數學計算和可視化軟件，具有豐富的函數庫和便捷的編程環境，非常適合用于開發數獨求解器與生成器。通過實現這樣的系統，不僅可以加深對數獨游戲規則和算法原理的理解，還可以提高利用MATLAB進行算法開發和圖形界面設計的能力。

1.2 國內外研究現狀

目前，國內外已經有許多關于數獨求解算法的研究。常見的數獨求解算法包括回溯算法、唯一法、排除法等。其中，回溯算法是一種深度優先搜索策略，通過嘗試填充數字并在發現當前路徑不可能達到目標時撤銷之前的操作，具有實現簡單、通用性強的特點，被廣泛應用于數獨求解。

在數獨生成方面，也有一些研究提出了不同的生成方法，如基于隨機填充和回溯修正的方法、基于模板的方法等。這些方法能夠在一定程度上生成有效的數獨謎題，但在謎題的質量和生成效率方面還有待進一步提高。

1.3 研究目標與內容

本畢業設計的研究目標是利用MATLAB技術實現一個基于回溯算法的數獨求解器與生成器，具體研究內容包括：

分析數獨游戲的規則和回溯算法的原理，設計數獨求解的核心算法。
實現數獨生成功能，能夠生成符合規則的有效數獨謎題。
利用MATLAB的GUI功能設計用戶界面，提供友好的交互體驗。
對系統進行測試和優化，確保其能夠高效準確地求解和生成數獨。

二、相關理論與技術

2.1 數獨游戲規則

數獨游戲在一個9x9的網格中進行，該網格被劃分為9個3x3的子網格。游戲開始時，部分格子中已經填入了數字，玩家需要根據以下規則在空白格子中填入數字1到9：

每一行中的數字1到9不能重復。
每一列中的數字1到9不能重復。
每一個3x3的子網格中的數字1到9不能重復。

2.2 回溯算法原理

回溯算法是一種通過遞歸來遍歷問題所有可能狀態的算法。它采用試錯的方法，在問題空間樹中進行深度優先搜索，當找到一個解時，就返回上一步嘗試其他的可能，直到所有的可能性都被檢查過。

在數獨求解中，回溯算法的基本步驟如下：

從第一個空白格子開始，嘗試填入數字1到9。
對于每一個嘗試的數字，檢查是否滿足數獨的規則（即該數字在當前行、列和子網格中不重復）。
如果滿足規則，則遞歸地嘗試填充下一個空白格子。
如果在填充后續格子時發現無法滿足規則，則回溯到上一個格子，嘗試下一個數字。
如果所有數字都嘗試過且無法滿足規則，則說明當前路徑無解，返回上一層繼續嘗試。

2.3 MATLAB GUI設計基礎

MATLAB提供了圖形用戶界面（GUI）設計工具，允許用戶通過拖放組件的方式快速創建交互式界面。GUI主要由各種控件（如按鈕、文本框、編輯框等）和回調函數組成。回調函數是當用戶與控件進行交互時自動調用的函數，用于實現相應的功能。

三、系統設計

3.1 系統總體架構

本系統主要由數獨求解模塊、數獨生成模塊和用戶界面模塊三部分組成。數獨求解模塊負責根據輸入的數獨謎題，利用回溯算法求解出完整的數獨解；數獨生成模塊負責生成符合規則的有效數獨謎題；用戶界面模塊提供友好的交互界面，方便用戶輸入數獨謎題、求解數獨以及生成新的數獨謎題。

3.2 數獨求解模塊設計

3.2.1 算法流程

初始化：讀取輸入的數獨謎題，將其存儲為一個9x9的矩陣。
尋找空白格子：遍歷矩陣，找到第一個值為0的格子（表示空白格子）。
嘗試填充數字：從1到9依次嘗試在該空白格子中填入數字。
檢查合法性：對于每一個嘗試的數字，檢查是否滿足數獨的規則（即該數字在當前行、列和子網格中不重復）。
遞歸求解：如果滿足規則，則遞歸地調用求解函數，嘗試填充下一個空白格子。
回溯：如果在填充后續格子時發現無法滿足規則，則回溯到上一個格子，嘗試下一個數字。
返回結果：如果所有空白格子都被成功填充，則返回求解后的數獨矩陣；如果所有數字都嘗試過且無法滿足規則，則返回空矩陣表示無解。

3.2.2 代碼實現

function solved_sudoku = solve_sudoku(sudoku)% 尋找空白格子[row, col] = find_empty_cell(sudoku);% 如果沒有空白格子，說明數獨已解if isempty(row)solved_sudoku = sudoku;return;end% 嘗試填充數字1到9for num = 1:9if is_valid(sudoku, row, col, num)sudoku(row, col) = num;% 遞歸求解solved_sudoku = solve_sudoku(sudoku);% 如果求解成功，返回結果if ~isempty(solved_sudoku)return;end% 回溯，撤銷當前填充sudoku(row, col) = 0;endend% 所有數字都嘗試過且無法滿足規則，返回空矩陣solved_sudoku = [];
endfunction [row, col] = find_empty_cell(sudoku)% 尋找值為0的格子（空白格子）[row, col] = find(sudoku == 0, 1);
endfunction valid = is_valid(sudoku, row, col, num)% 檢查行是否重復if any(sudoku(row, :) == num)valid = false;return;end% 檢查列是否重復if any(sudoku(:, col) == num)valid = false;return;end% 檢查3x3子網格是否重復start_row = 3 * floor((row - 1) / 3) + 1;start_col = 3 * floor((col - 1) / 3) + 1;sub_grid = sudoku(start_row:start_row+2, start_col:start_col+2);if any(sub_grid(:) == num)valid = false;return;endvalid = true;
end

3.3 數獨生成模塊設計

3.3.1 算法流程

初始化：創建一個全0的9x9矩陣，表示空白數獨。
填充數字：利用回溯算法在空白數獨中隨機填充數字，確保每一步填充都滿足數獨的規則。
挖空處理：在填充完整的數獨中隨機選擇一定數量的格子，將其值設為0，生成數獨謎題。
檢查唯一解：確保生成的數獨謎題有且僅有一個解，如果有多解，則重新進行挖空處理。

3.3.2 代碼實現

function generated_sudoku = generate_sudoku()% 初始化空白數獨sudoku = zeros(9, 9);% 利用回溯算法填充數字sudoku = fill_sudoku(sudoku);% 挖空處理num_holes = 40; % 設置挖空的格子數量indices = randperm(81);for i = 1:num_holesrow = ceil(indices(i) / 9);col = mod(indices(i), 9);if col == 0col = 9;endsudoku(row, col) = 0;end% 檢查唯一解solutions = 0;temp_sudoku = sudoku;% 使用匿名函數簡化回調count_solutions = @(~) (solutions = solutions + 1; false);% 修改solve_sudoku以支持計數function solved = count_solve_wrapper(s)nonlocal solutions[row, col] = find_empty_cell(s);if isempty(row)solutions = solutions + 1;solved = false; % 阻止進一步遞歸return;endfor num = 1:9if is_valid(s, row, col, num)s(row, col) = num;if count_solve_wrapper(s)solved = false;return;ends(row, col) = 0;endendsolved = false;endcount_solve_wrapper(temp_sudoku);% 如果有多解，重新生成while solutions ~= 1sudoku = zeros(9, 9);sudoku = fill_sudoku(sudoku);num_holes = 40;indices = randperm(81);for i = 1:num_holesrow = ceil(indices(i) / 9);col = mod(indices(i), 9);if col == 0col = 9;endsudoku(row, col) = 0;endsolutions = 0;temp_sudoku = sudoku;count_solve_wrapper(temp_sudoku);endgenerated_sudoku = sudoku;
endfunction sudoku = fill_sudoku(sudoku)% 利用回溯算法填充數字[row, col] = find_empty_cell(sudoku);if isempty(row)return;endfor num = 1:9if is_valid(sudoku, row, col, num)sudoku(row, col) = num;sudoku = fill_sudoku(sudoku);if ~isempty(find_empty_cell(sudoku))continue;endendend
end

3.4 用戶界面模塊設計

3.4.1 界面布局

用戶界面采用MATLAB的GUI設計工具創建，主要包括以下組件：

一個9x9的編輯框矩陣，用于輸入和顯示數獨謎題和解。
三個按鈕，分別用于求解數獨、生成數獨和清空數獨。

3.4.2 回調函數實現

function sudoku_gui()% 創建主窗口f = figure('Name', '數獨求解器與生成器', 'NumberTitle', 'off', 'MenuBar', 'none',...'ToolBar', 'none', 'Position', [200, 200, 450, 500]);% 創建數獨面板sudoku_panel = uipanel('Title', '數獨', 'Position', [0.05, 0.3, 0.9, 0.6], 'Parent', f);% 創建按鈕面板button_panel = uipanel('Title', '操作', 'Position', [0.05, 0.05, 0.9, 0.2], 'Parent', f);% 創建數獨編輯框矩陣cells = zeros(9, 9);for i = 1:9for j = 1:9cells(i, j) = uicontrol('Style', 'edit', 'String', '', 'Position',...[50 * (j - 1) + 10, 50 * (9 - i) + 10, 40, 40],...'HorizontalAlignment', 'center', 'FontSize', 16, 'Enable', 'on',...'BackgroundColor', 'white', 'Parent', sudoku_panel);endend% 創建求解按鈕uicontrol('Style', 'pushbutton', 'String', '求解數獨', 'Position', [20, 20, 100, 30],...'Callback', @(src, event) solve_button_callback(cells), 'Parent', button_panel);% 創建生成按鈕uicontrol('Style', 'pushbutton', 'String', '生成數獨', 'Position', [140, 20, 100, 30],...'Callback', @(src, event) generate_button_callback(cells), 'Parent', button_panel);% 創建清空按鈕uicontrol('Style', 'pushbutton', 'String', '清空數獨', 'Position', [260, 20, 100, 30],...'Callback', @(src, event) clear_button_callback(cells), 'Parent', button_panel);
endfunction solve_button_callback(cells)% 讀取數獨編輯框中的數獨矩陣sudoku = read_sudoku(cells);% 求解數獨solved_sudoku = solve_sudoku(sudoku);% 如果求解成功，將結果填入數獨編輯框if ~isempty(solved_sudoku)fill_sudoku(cells, solved_sudoku);elseerrordlg('該數獨無解！', '錯誤');end
endfunction generate_button_callback(cells)% 生成數獨generated_sudoku = generate_sudoku();% 將生成的數獨填入數獨編輯框fill_sudoku(cells, generated_sudoku);
endfunction clear_button_callback(cells)% 清空數獨編輯框for i = 1:9for j = 1:9set(cells(i, j), 'String', '', 'Enable', 'on');endend
endfunction sudoku = read_sudoku(cells)% 讀取數獨編輯框中的數獨矩陣sudoku = zeros(9, 9);for i = 1:9for j = 1:9str = get(cells(i, j), 'String');if ~isempty(str)sudoku(i, j) = str2double(str);endendend
endfunction fill_sudoku(cells, sudoku)% 將數獨矩陣填入數獨編輯框for i = 1:9for j = 1:9if sudoku(i, j) > 0set(cells(i, j), 'String', num2str(sudoku(i, j)), 'Enable', 'off');elseset(cells(i, j), 'String', '', 'Enable', 'on');endendend
end

四、系統測試與優化

4.1 系統測試

為了驗證系統的正確性和穩定性，我們進行了以下測試：

功能測試：分別測試數獨求解、生成和清空功能，確保各項功能能夠正常實現。
邊界測試：測試輸入極端情況的數獨謎題，如全空白數獨、全填充數獨等，檢查系統是否能夠正確處理。
性能測試：測試系統在不同復雜度數獨謎題下的求解和生成時間，評估系統的性能。

4.2 系統優化

根據測試結果，我們對系統進行了以下優化：

算法優化：對回溯算法進行優化，減少不必要的遞歸調用和重復計算，提高求解效率。
界面優化：優化用戶界面布局，提高界面的美觀性和易用性。
錯誤處理優化：增加錯誤處理機制，對用戶輸入的非法數獨謎題進行提示和處理，提高系統的魯棒性。

五、結論與展望

5.1 結論

本畢業設計成功利用MATLAB技術實現了一個基于回溯算法的數獨求解器與生成器。通過深入分析數獨游戲規則和回溯算法原理，設計并實現了數獨求解和生成的核心算法，同時利用MATLAB的GUI功能設計了友好的用戶界面。經過測試和優化，系統能夠高效準確地求解和生成數獨，具有較高的實用性和穩定性。

5.2 展望

雖然本系統已經實現了基本的功能，但仍有進一步改進和擴展的空間。未來的研究可以從以下幾個方面展開：

算法改進：研究更高效的數獨求解算法，如舞蹈鏈算法等，進一步提高求解效率。
功能擴展：增加數獨謎題的難度分級功能，根據用戶的需求生成不同難度的數獨謎題；增加數獨解題提示功能，幫助用戶更好地理解和解決數獨謎題。
多平臺支持：將系統移植到其他平臺，如Web平臺或移動平臺，擴大系統的使用范圍。

import React, { useState, useEffect } from 'react';
import { RefreshCw, Play, Eraser, Gauge } from 'lucide-react';const SudokuSolverGenerator = () => {const [board, setBoard] = useState(Array(9).fill().map(() => Array(9).fill(0)));const [initialBoard, setInitialBoard] = useState(Array(9).fill().map(() => Array(9).fill(0)));const [selectedCell, setSelectedCell] = useState(null);const [isSolving, setIsSolving] = useState(false);const [difficulty, setDifficulty] = useState('medium');const [message, setMessage] = useState('生成一個新的數獨謎題');// 檢查數字是否有效const isValid = (board, row, col, num) => {// 檢查行for (let x = 0; x < 9; x++) {if (board[row][x] === num) return false;}// 檢查列for (let x = 0; x < 9; x++) {if (board[x][col] === num) return false;}// 檢查3x3宮格const startRow = row - row % 3;const startCol = col - col % 3;for (let i = 0; i < 3; i++) {for (let j = 0; j < 3; j++) {if (board[i + startRow][j + startCol] === num) return false;}}return true;};// 回溯算法求解數獨const solveSudoku = (board) => {for (let row = 0; row < 9; row++) {for (let col = 0; col < 9; col++) {if (board[row][col] === 0) {for (let num = 1; num <= 9; num++) {if (isValid(board, row, col, num)) {board[row][col] = num;if (solveSudoku(board)) {return true;}board[row][col] = 0;}}return false;}}}return true;};// 生成有效數獨謎題const generatePuzzle = (difficultyLevel) => {setIsSolving(true);setMessage('生成中...');// 創建一個完全解決的數獨板const solvedBoard = Array(9).fill().map(() => Array(9).fill(0));// 填充對角線上的3x3方塊（更容易求解）for (let box = 0; box < 9; box += 3) {fillDiagonalBox(solvedBoard, box);}// 解決數獨solveSudoku(solvedBoard);// 根據難度挖空const puzzle = JSON.parse(JSON.stringify(solvedBoard));const cellsToRemove = getCellsToRemoveCount(difficultyLevel);let removed = 0;while (removed < cellsToRemove) {const row = Math.floor(Math.random() * 9);const col = Math.floor(Math.random() * 9);if (puzzle[row][col] !== 0) {const temp = puzzle[row][col];puzzle[row][col] = 0;// 驗證謎題是否仍然有唯一解const copy = JSON.parse(JSON.stringify(puzzle));const solutions = countSolutions(copy);if (solutions === 1) {removed++;} else {puzzle[row][col] = temp;}}}setBoard(JSON.parse(JSON.stringify(puzzle)));setInitialBoard(JSON.parse(JSON.stringify(puzzle)));setIsSolving(false);setMessage(`已生成${getDifficultyName(difficultyLevel)}難度謎題`);};// 填充對角線上的3x3方塊const fillDiagonalBox = (board, boxStart) => {for (let i = 0; i < 3; i++) {for (let j = 0; j < 3; j++) {let num;do {num = Math.floor(Math.random() * 9) + 1;} while (!isValid(board, boxStart + i, boxStart + j, num));board[boxStart + i][boxStart + j] = num;}}};// 計算謎題應挖空的單元格數量const getCellsToRemoveCount = (level) => {switch (level) {case 'easy': return 40;case 'medium': return 50;case 'hard': return 60;default: return 50;}};// 獲取難度名稱const getDifficultyName = (level) => {switch (level) {case 'easy': return '簡單';case 'medium': return '中等';case 'hard': return '困難';default: return '中等';}};// 計算解決方案數量（用于驗證唯一解）const countSolutions = (board) => {let solutions = 0;const solve = (b) => {for (let row = 0; row < 9; row++) {for (let col = 0; col < 9; col++) {if (b[row][col] === 0) {for (let num = 1; num <= 9; num++) {if (isValid(b, row, col, num)) {b[row][col] = num;solve(b);b[row][col] = 0;if (solutions > 1) return; // 超過1個解直接返回}}return;}}}solutions++;};solve(board);return solutions;};// 處理數字輸入const handleNumberInput = (num) => {if (isSolving || !selectedCell) return;const [row, col] = selectedCell;const newBoard = [...board];// 只能修改初始為0的單元格if (initialBoard[row][col] === 0) {newBoard[row][col] = num;setBoard(newBoard);}};// 清除單元格const clearCell = () => {if (isSolving || !selectedCell) return;const [row, col] = selectedCell;const newBoard = [...board];if (initialBoard[row][col] === 0) {newBoard[row][col] = 0;setBoard(newBoard);}};// 解決當前數獨const solveCurrent = () => {setIsSolving(true);setMessage('求解中...');const copy = JSON.parse(JSON.stringify(board));const solved = solveSudoku(copy);if (solved) {setBoard(copy);setMessage('求解成功！');} else {setMessage('無解！請檢查輸入是否正確');}setIsSolving(false);};// 初始化生成謎題useEffect(() => {generatePuzzle(difficulty);}, []);return (<div className="max-w-4xl mx-auto p-6 bg-gradient-to-br from-blue-50 to-indigo-100 min-h-screen"><div className="bg-white rounded-2xl shadow-xl p-8"><h1 className="text-3xl font-bold text-center mb-2 text-indigo-800">數獨求解器與生成器</h1><p className="text-center text-gray-600 mb-8">使用回溯算法實現</p><div className="flex flex-col md:flex-row gap-8">{/* 數獨棋盤 */}<div className="flex-1"><div className="bg-gray-100 p-4 rounded-xl inline-block"><div className="grid grid-cols-9 gap-0 border-2 border-gray-800">{board.map((row, rowIndex) => (row.map((cell, colIndex) => {const isSelected = selectedCell && selectedCell[0] === rowIndex && selectedCell[1] === colIndex;const isInitial = initialBoard[rowIndex][colIndex] !== 0;const isHighlighted = (rowIndex === selectedCell?.[0] || colIndex === selectedCell?.[1]) && selectedCell && !isInitial;return (<div key={`${rowIndex}-${colIndex}`}onClick={() => !isInitial && setSelectedCell([rowIndex, colIndex])}className={`w-10 h-10 flex items-center justify-center text-xl font-semiboldborder border-gray-300${rowIndex % 3 === 2 && rowIndex !== 8 ? 'border-b-2 border-gray-800' : ''}${colIndex % 3 === 2 && colIndex !== 8 ? 'border-r-2 border-gray-800' : ''}${isSelected ? 'bg-indigo-200' : ''}${isHighlighted ? 'bg-indigo-100' : ''}${isInitial ? 'text-indigo-800' : 'text-gray-800 hover:bg-gray-200 cursor-pointer'}`}>{cell !== 0 ? cell : ''}</div>);})))}</div></div></div>{/* 控制面板 */}<div className="w-full md:w-64 space-y-6"><div className="bg-indigo-50 p-5 rounded-xl shadow-sm"><h3 className="font-semibold text-indigo-800 mb-3 flex items-center gap-2"><Gauge size={18} /> 難度選擇</h3><div className="space-y-2">{['easy', 'medium', 'hard'].map((level) => (<buttonkey={level}onClick={() => {setDifficulty(level);generatePuzzle(level);}}className={`w-full py-2 px-3 rounded-lg text-sm font-medium transition-all ${difficulty === level ? 'bg-indigo-600 text-white shadow-md' : 'bg-white text-indigo-700 hover:bg-indigo-100'}`}>{getDifficultyName(level)}</button>))}</div></div><div className="bg-indigo-50 p-5 rounded-xl shadow-sm"><h3 className="font-semibold text-indigo-800 mb-3">數字輸入</h3><div className="grid grid-cols-3 gap-2">{[1, 2, 3, 4, 5, 6, 7, 8, 9].map((num) => (<buttonkey={num}onClick={() => handleNumberInput(num)}className="w-full py-3 bg-white hover:bg-indigo-100 text-indigo-800 font-bold rounded-lg shadow-sm transition-all hover:scale-105">{num}</button>))}</div></div><div className="space-y-3"><buttononClick={clearCell}disabled={isSolving || !selectedCell}className={`w-full py-3 px-4 rounded-lg font-medium flex items-center justify-center gap-2 transition-all ${isSolving || !selectedCell ? 'bg-gray-200 text-gray-500 cursor-not-allowed' : 'bg-white hover:bg-gray-100 text-indigo-800 shadow-sm'}`}><Eraser size={18} /> 清除</button><buttononClick={solveCurrent}disabled={isSolving}className={`w-full py-3 px-4 rounded-lg font-medium flex items-center justify-center gap-2 transition-all ${isSolving ? 'bg-indigo-400 text-white cursor-not-allowed' : 'bg-indigo-600 hover:bg-indigo-700 text-white shadow-md'}`}><Play size={18} /> 求解</button><buttononClick={() => generatePuzzle(difficulty)}disabled={isSolving}className={`w-full py-3 px-4 rounded-lg font-medium flex items-center justify-center gap-2 transition-all ${isSolving ? 'bg-indigo-400 text-white cursor-not-allowed' : 'bg-indigo-600 hover:bg-indigo-700 text-white shadow-md'}`}><RefreshCw size={18} /> 新謎題</button></div><div className="bg-indigo-50 p-4 rounded-xl text-center"><p className={`font-medium ${message.includes('成功') ? 'text-green-700' : message.includes('無解') ? 'text-red-700' : 'text-indigo-800'}`}>{message}</p></div></div></div><div className="mt-8 text-center text-sm text-gray-500"><p>算法說明：使用回溯算法生成和求解數獨謎題</p><p className="mt-1">初始數字無法修改，空白單元格可自由填寫</p></div></div></div>);
};export default SudokuSolverGenerator;