DIV CSS 佈局教程網

用 JavaScript 生成數獨謎題:以「候選數剔除法」打造九宮格
編輯:關於JavaScript     

數獨看起來複雜,生成演算法的核心卻很樸素:對每一格列出所有合法候選數字,隨機挑一個填進去;填到無解就整盤重來。以下用不到兩百行 JavaScript 完成一個可點擊重新生成的數獨盤面。

頁面骨架

<p><input value="Get New SuDoKu" type="button" onclick="onLoadTable()" id="refreshButton" /></p>
<table border="1" style="border-color: Red;" id="mainTable">
<tbody></tbody>
</table>

主流程:生成、驗證、渲染

這裡最值得注意的是外層的 do...while。因為隨機填法有可能走入死路,所以必須用「生成→檢查→不合格就重來」的迴圈確保輸出的盤面完整合法。

var sudokuArray = [[],[],[],[],[],[],[],[],[],[]];

function onLoadTable()
{
    do
    {
        sudokuArray = getNewArray();
        sudokuArray = getSudokuArray(sudokuArray);
    }
    while(!checkArray(sudokuArray))

    var table = document.getElementById("mainTable");
    table.removeChild(table.firstChild);
    for (var i = 0; i < 9; i++)
    {
        table.insertRow(i);
        for (var j = 0; j < 9; j++)
        {
            table.rows[i].insertCell(j);
            table.rows[i].cells[j].innerHTML = sudokuArray[i][j];
            setStyle(i, j, table.rows[i].cells[j]);
        }
    }
}

填值:逐格挑選候選數

function getSudokuArray(filledArray)
{
    for (var i = 0; i < 9; i++)
    {
        for (var j = 0; j < 9; j++)
        {
            var tempArray = getAvaildableArray(i, j, filledArray);
            if (tempArray.length > 0)
            {
                filledArray[i][j] =
                    tempArray[Math.round(Math.random() * (tempArray.length - 1))];
            }
        }
    }
    return filledArray;
}

驗證:有沒有空格

function checkArray(array)
{
    for (var i = 0; i < 9; i++)
        for (var j = 0; j < 9; j++)
            if (array[i][j] == undefined) return false;
    return true;
}

核心:計算合法候選數

這是整個演算法最關鍵的一段。做法是先準備 [1..9],再把「同一列已用過」、「同一行已用過」、「同一宮已用過」的數字標成 NaN,最後剩下的就是候選集。

function getAvaildableArray(rowIndex, cellIndex, array)
{
    var availdableArray = [1,2,3,4,5,6,7,8,9];

    for (var n = 0; n < 9; n++)
    {
        if (!isNaN(array[rowIndex][n]) && array[rowIndex][n] != undefined)
            availdableArray[array[rowIndex][n] - 1] = NaN;
        if (!isNaN(array[n][cellIndex]) && array[n][cellIndex] != undefined)
            availdableArray[array[n][cellIndex] - 1] = NaN;
    }

    var rowStartIndex = Math.floor(rowIndex / 3);
    var cellStartIndex = Math.floor(cellIndex / 3);
    for (var x = rowStartIndex * 3; x < rowStartIndex + 3; x++)
    {
        for (var y = cellStartIndex * 3; y < cellStartIndex + 3; y++)
        {
            if (!isNaN(array[x][y]) || array[x][y] != undefined)
                availdableArray[array[x][y] - 1] = NaN;
        }
    }

    var returnArray = [];
    for (var m = 0; m < 9; m++)
        if (!isNaN(availdableArray[m])) returnArray.push(availdableArray[m]);
    return returnArray;
}

function getNewArray()
{
    return [[],[],[],[],[],[],[],[],[],[]];
}

樣式:讓宮線更醒目

數獨的視覺重點在 3×3 的宮格分隔。透過取模運算判斷邊界,就能為特定邊框上色。

function setStyle(rowIndex, cellIndex, cell)
{
    cell.height = "20";
    cell.width = "20";
    if (cellIndex % 3 == 2) cell.style.borderRightColor = "red";
    if (cellIndex % 3 == 0) cell.style.borderLeftColor  = "red";
    if (rowIndex % 3 == 2)  cell.style.borderBottomColor = "red";
    if (rowIndex % 3 == 0)  cell.style.borderTopColor    = "red";
}

這個版本的改進空間

目前的演算法是「填滿 + 檢查 + 重來」,屬於暴力法,運氣不好時會連續失敗多次。若要更穩定,可改用回溯法:遇到無合法候選的格子就退回上一格換一個數字,而不是整盤作廢。

另外,這裡產生的是「完整解答」而非「謎題」。真正的數獨遊戲還需要挖洞:從完整盤面中依序移除數字,每次移除後檢查是否仍存在唯一解,直到挖到目標難度為止。唯一解驗證通常需要搭配求解器來跑。

XML學習教程| jQuery入門知識| AJAX入門| Dreamweaver教程| Fireworks入門知識| SEO技巧| SEO優化集錦|
Copyright © DIV+CSS佈局教程網 All Rights Reserved