数独小解
source link: https://blog.csdn.net/tkokof1/article/details/84872398
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
本文简述了一种关于数独游戏的程序解法
数独游戏相信大家都有所耳闻,规则上非常简明:
在 9 x 9 的数格中(由 9 个 3 x 3 的九宫格组成)会预先给定不少于(>=)17个数字,你需要在满足以下条件的情况下补完其余数格中的数字:
- 每一行的数字不重复
- 每一列的数字不重复
- 每个 3 x 3 九宫格中的数字不重复
这里有个示例:
使用程序求解数独的一种简单方法便是穷举(搜索),较粗糙的一种方式就是枚举 9 x 9 数格中所有的数字组合(为每个数格指定 1 ~ 9 之间的某个数字),只是这种搜索方式的解空间较大,实际运用中需要进行剪枝,剪枝的思路其实也很朴素,依据数独中相关数字不可重复的3条规则即可:
按照空白数格顺序进行深度优先搜索,对于每个空白数格生成候选数字列表(即满足规则下可能填入该空白数格的数字列表),然后依次填入可能的候选数字,并在下一个空白数格处继续进行相同的深度优先搜索,如果成功则找到答案,否则返回失败.
(可以使用启发式算法优化,譬如按候选数字列表最短的空白数格顺序进行搜索(实际测试中因为工程原因其实比顺序搜索方法更慢))
下面是使用 Lua 实现的示例程序:
function get_sudoku_row_and_col(data)
local row = #data
local col = data[1] and #data[1] or 0
return row, col
end
function print_sudoku(data)
local row, col = get_sudoku_row_and_col(data)
for i = 1, row do
local str_buffer = {}
for j = 1, col do
table.insert(str_buffer, data[i][j])
end
print(table.concat(str_buffer, ", "))
end
print()
end
function check_sudoku_row(data, row_index)
local row, col = get_sudoku_row_and_col(data)
local sum = 1
for i = 1, col do
sum = sum | (1 << (data[row_index][i]))
end
return sum == 0x3FF
end
function check_sudoku_col(data, col_index)
local row, col = get_sudoku_row_and_col(data)
local sum = 1
for i = 1, row do
sum = sum | (1 << (data[i][col_index]))
end
return sum == 0x3FF
end
function check_sudoku_square(data, row_index, col_index)
local row, col = get_sudoku_row_and_col(data)
local sum = 1
for i = row_index, row_index + 2 do
for j = col_index, col_index + 2 do
sum = sum | (1 << (data[i][j]))
end
end
return sum == 0x3FF
end
function check_sudoku(data)
local row, col = get_sudoku_row_and_col(data)
-- check row
for i = 1, row do
if not check_sudoku_row(data, i) then
return false
end
end
-- check col
for i = 1, col do
if not check_sudoku_col(data, i) then
return false
end
end
-- check square
for i = 1, row // 3 do
local row_index = (i - 1) * 3 + 1
for j = 1, col // 3 do
local col_inex = (j - 1) * 3 + 1
if not check_sudoku_square(data, row_index, col_inex) then
return false
end
end
end
return true
end
function apply_sudoku(data, delta)
local row, col = delta.row, delta.col
if data[row] and data[row][col] then
data[row][col] = delta.val
end
end
function revert_sudoku(data, delta)
local row, col = delta.row, delta.col
if data[row] and data[row][col] then
data[row][col] = 0
end
end
function get_pending_list(data, row, col)
if data[row] and data[row][col] then
if data[row][col] == 0 then
-- only empty pos has pending list
local pending_list = { true, true, true, true, true, true, true, true, true }
local data_row, data_col = get_sudoku_row_and_col(data)
-- check row
for i = 1, data_col do
pending_list[data[row][i]] = false
end
-- check col
for i = 1, data_row do
pending_list[data[i][col]] = false
end
-- check square
local square_row = (row - 1) // 3 * 3 + 1 -- or math.ceil(row / 3) * 3 - 2
local square_col = (col - 1) // 3 * 3 + 1 -- or math.ceil(col / 3) * 3 - 2
for i = square_row, square_row + 2 do
for j = square_col, square_col + 2 do
pending_list[data[i][j]] = false
end
end
-- gen pending list number
local pending_list_num = {}
for i = 1, #pending_list do
if pending_list[i] then
table.insert(pending_list_num, i)
end
end
return pending_list_num
end
end
end
function get_next_search_pos(data, row, col)
-- now we just search in order
local data_row, data_col = get_sudoku_row_and_col(data)
-- top right part
for j = col, data_col do
if data[row][j] == 0 then
return row, j
end
end
-- rest part
for i = row + 1, data_row do
for j = 1, data_col do
if data[i][j] == 0 then
return i, j
end
end
end
end
function search_sudoku_recur(data, row, col)
row, col = get_next_search_pos(data, row, col)
if row and col then
local pending_list = get_pending_list(data, row, col)
if pending_list and #pending_list > 0 then
for i = 1, #pending_list do
apply_sudoku(data, { row = row, col = col, val = pending_list[i] })
local val = search_sudoku_recur(data, row, col)
if val then
return true
else
revert_sudoku(data, { row = row, col = col, val = pending_list[i] })
end
end
-- all pending list is not valid
return false
else
-- no valid pending list
return false
end
else
-- all data filled
if check_sudoku(data) then
-- valid data
return true
else
-- invalid data
return false
end
end
end
function search_sudoku(data)
return search_sudoku_recur(data, 1, 1)
end
示例程序并不简短,但是理解起来并不困难,要点如下:
- 数独的数格表示使用了"二维数组"
- 函数 check_sudoku 用以检查数格中的数字是否满足数独条件
- 函数 search_sudoku 实现了上述的深度优先搜索方法
下图是号称世界上迄今难度最大的数独游戏,有兴趣的朋友可以试下:
Recommend
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK