數獨看起來複雜,生成演算法的核心卻很樸素:對每一格列出所有合法候選數字,隨機挑一個填進去;填到無解就整盤重來。以下用不到兩百行 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";
}
目前的演算法是「填滿 + 檢查 + 重來」,屬於暴力法,運氣不好時會連續失敗多次。若要更穩定,可改用回溯法:遇到無合法候選的格子就退回上一格換一個數字,而不是整盤作廢。
另外,這裡產生的是「完整解答」而非「謎題」。真正的數獨遊戲還需要挖洞:從完整盤面中依序移除數字,每次移除後檢查是否仍存在唯一解,直到挖到目標難度為止。唯一解驗證通常需要搭配求解器來跑。