用哪种数据结构来表示数独谜题,并通过找出裸单/隐藏单来解决它
本文关键字:解决 隐藏 表示 数据结构 | 更新日期: 2023-09-27 18:18:41
我很犹豫应该用以下两种数据结构中的哪一种来表示数独板,以便使用裸单和隐藏单技术来解决它。
1。
//using bool array to store candidates of a cell.
int[,] board = new int[9,9];
bool[,] isFixed = new bool[9,9]; // determine cell is fixed.
bool[,,] candidates = new bool[9,9,9];
以这种方式,我们可以通过检查candidates[row, col, n]
是否为真或假来检查单元格(行,col)是否包含候选n
2。
int[,] board = new int[9,9];
bool[,] isFixed = new bool[9,9]; // determine cell is fixed.
bool[,] row = new bool[9,9]; //row(1,2) = true means number 2 was already appear (is solved or fixed) in 1st row
bool[,] col = new bool[9,9]; //col(1,2) = true means number 2 was already appear (is solved or fixed) in 1st col
bool[,] square3x3 = new bool[9,9]; //square3x3 (1,2) = true means number 2 was already appear (is solved or fixed) in 1st square3x3
通过这种方式,我们可以通过检查表达式row[r, n] && col[c, n] && square3x3[r/3 * 3 + c/3, n]
是否为真或假来检查单元格(r,c)是否包含候选n
当某个单元格用数字n求解时,在第一种方法中,我们必须更新该单元格的row, col, square3x3中所有3x9单元格的候选值,而在第二种方法中,我们只设置row[,n], col[,n]和square3x3[,n]为true。
但我不确定哪种方法适合和有效地找到裸单和隐藏单。
谁能给我一个算法来找到隐藏的单?
帮帮我,谢谢!
我个人不会使用一组必须保持同步的基本数组,而是使用Board类。
这将在内部有一个9x9的字段项数组,它将保存一个可选的(int?
)给定数字,一个可选的派生数字和一个候选列表(bool[9]
)。
该类将公开一些属性/方法来获取特定的单元格或行/列/块。
当我自己解决数独时,我只用了两个多维数组就成功了。
一个包含字段的当前状态(单元格是数字),另一个包含字段可能的下一个状态(单元格是数字数组)。
你可以从我的代码中得到一些想法(虽然是用Ruby写的)
https://github.com/stulentsev/sudoku-solver/blob/master/solver.rb