数独小解
本文簡述了一種關(guān)于數(shù)獨(dú)游戲的程序解法
數(shù)獨(dú)游戲相信大家都有所耳聞,規(guī)則上非常簡明:
在 9 x 9 的數(shù)格中(由 9 個(gè) 3 x 3 的九宮格組成)會(huì)預(yù)先給定不少于(>=)17個(gè)數(shù)字,你需要在滿足以下條件的情況下補(bǔ)完其余數(shù)格中的數(shù)字:
這里有個(gè)示例:
使用程序求解數(shù)獨(dú)的一種簡單方法便是窮舉(搜索),較粗糙的一種方式就是枚舉 9 x 9 數(shù)格中所有的數(shù)字組合(為每個(gè)數(shù)格指定 1 ~ 9 之間的某個(gè)數(shù)字),只是這種搜索方式的解空間較大,實(shí)際運(yùn)用中需要進(jìn)行剪枝,剪枝的思路其實(shí)也很樸素,依據(jù)數(shù)獨(dú)中相關(guān)數(shù)字不可重復(fù)的3條規(guī)則即可:
按照空白數(shù)格順序進(jìn)行深度優(yōu)先搜索,對(duì)于每個(gè)空白數(shù)格生成候選數(shù)字列表(即滿足規(guī)則下可能填入該空白數(shù)格的數(shù)字列表),然后依次填入可能的候選數(shù)字,并在下一個(gè)空白數(shù)格處繼續(xù)進(jìn)行相同的深度優(yōu)先搜索,如果成功則找到答案,否則返回失敗.
(可以使用啟發(fā)式算法優(yōu)化,譬如按候選數(shù)字列表最短的空白數(shù)格順序進(jìn)行搜索(實(shí)際測(cè)試中因?yàn)楣こ淘蚱鋵?shí)比順序搜索方法更慢))
下面是使用 Lua 實(shí)現(xiàn)的示例程序:
function get_sudoku_row_and_col(data)local row = #datalocal col = data[1] and #data[1] or 0return row, col endfunction print_sudoku(data)local row, col = get_sudoku_row_and_col(data)for i = 1, row dolocal str_buffer = {}for j = 1, col dotable.insert(str_buffer, data[i][j])endprint(table.concat(str_buffer, ", "))endprint() endfunction check_sudoku_row(data, row_index)local row, col = get_sudoku_row_and_col(data)local sum = 1for i = 1, col dosum = sum | (1 << (data[row_index][i]))endreturn sum == 0x3FF endfunction check_sudoku_col(data, col_index)local row, col = get_sudoku_row_and_col(data)local sum = 1for i = 1, row dosum = sum | (1 << (data[i][col_index]))endreturn sum == 0x3FF endfunction check_sudoku_square(data, row_index, col_index)local row, col = get_sudoku_row_and_col(data)local sum = 1for i = row_index, row_index + 2 dofor j = col_index, col_index + 2 dosum = sum | (1 << (data[i][j]))endendreturn sum == 0x3FF endfunction check_sudoku(data)local row, col = get_sudoku_row_and_col(data)-- check rowfor i = 1, row doif not check_sudoku_row(data, i) thenreturn falseendend-- check colfor i = 1, col doif not check_sudoku_col(data, i) thenreturn falseendend-- check squarefor i = 1, row // 3 dolocal row_index = (i - 1) * 3 + 1for j = 1, col // 3 dolocal col_inex = (j - 1) * 3 + 1if not check_sudoku_square(data, row_index, col_inex) thenreturn falseendendendreturn true endfunction apply_sudoku(data, delta)local row, col = delta.row, delta.colif data[row] and data[row][col] thendata[row][col] = delta.valend endfunction revert_sudoku(data, delta)local row, col = delta.row, delta.colif data[row] and data[row][col] thendata[row][col] = 0end endfunction get_pending_list(data, row, col)if data[row] and data[row][col] thenif data[row][col] == 0 then-- only empty pos has pending listlocal pending_list = { true, true, true, true, true, true, true, true, true }local data_row, data_col = get_sudoku_row_and_col(data)-- check rowfor i = 1, data_col dopending_list[data[row][i]] = falseend-- check colfor i = 1, data_row dopending_list[data[i][col]] = falseend-- check squarelocal square_row = (row - 1) // 3 * 3 + 1 -- or math.ceil(row / 3) * 3 - 2local square_col = (col - 1) // 3 * 3 + 1 -- or math.ceil(col / 3) * 3 - 2for i = square_row, square_row + 2 dofor j = square_col, square_col + 2 dopending_list[data[i][j]] = falseendend-- gen pending list numberlocal pending_list_num = {}for i = 1, #pending_list doif pending_list[i] thentable.insert(pending_list_num, i)endendreturn pending_list_numendend endfunction get_next_search_pos(data, row, col)-- now we just search in orderlocal data_row, data_col = get_sudoku_row_and_col(data)-- top right partfor j = col, data_col doif data[row][j] == 0 thenreturn row, jendend-- rest partfor i = row + 1, data_row dofor j = 1, data_col doif data[i][j] == 0 thenreturn i, jendendend endfunction search_sudoku_recur(data, row, col)row, col = get_next_search_pos(data, row, col)if row and col thenlocal pending_list = get_pending_list(data, row, col)if pending_list and #pending_list > 0 thenfor i = 1, #pending_list doapply_sudoku(data, { row = row, col = col, val = pending_list[i] })local val = search_sudoku_recur(data, row, col)if val thenreturn trueelserevert_sudoku(data, { row = row, col = col, val = pending_list[i] })endend-- all pending list is not validreturn falseelse-- no valid pending listreturn falseendelse-- all data filledif check_sudoku(data) then-- valid datareturn trueelse-- invalid datareturn falseendend endfunction search_sudoku(data)return search_sudoku_recur(data, 1, 1) end示例程序并不簡短,但是理解起來并不困難,要點(diǎn)如下:
- 數(shù)獨(dú)的數(shù)格表示使用了"二維數(shù)組"
- 函數(shù) check_sudoku 用以檢查數(shù)格中的數(shù)字是否滿足數(shù)獨(dú)條件
- 函數(shù) search_sudoku 實(shí)現(xiàn)了上述的深度優(yōu)先搜索方法
下圖是號(hào)稱世界上迄今難度最大的數(shù)獨(dú)游戲,有興趣的朋友可以試下:
參考資料
總結(jié)
