如何使用c++在数独子网格上迭代？
如何使用c++在数独子网格上迭代？
提问于 2019-01-07 05:55:31
我试着做一个在线数独c++测试问题。
我需要确定9x9数独板是否有效。只有填充的单元格需要根据以下规则进行验证(有些单元格有“”。以表示未填写)：
- 每一行必须包含数字1-9，不重复。
- 每一列必须包含数字1-9，不重复.
- 网格的每个93x3子框必须包含数字1-9，不重复。
对于我的解决方案，我正在遍历每一行、每列和每一个子框网格。把这些数字加到地图上。看看地图上有没有副本。
我很确定我已经解决了1和2的标准问题，但我很难想象如何遍历子框3x3网格。所以我采用了some code found here，老实说，我仍然无法完全理解它。我认为这部分可能是造成问题的原因。
如何解决标准3？
示例输入，正确的答案应该返回False，但我的代码返回True：
[
[".",".","4",".",".",".","6","3","."],
[".",".",".",".",".",".",".",".","."],
["5",".",".",".",".",".",".","9","."],
[".",".",".","5","6",".",".",".","."],
["4",".","3",".",".",".",".",".","1"],
[".",".",".","7",".",".",".",".","."],
[".",".",".","5",".",".",".",".","."],
[".",".",".",".",".",".",".",".","."],
[".",".",".",".",".",".",".",".","."]
]我的(坏的)解决方案：
class Solution {
public:
bool isValidSudoku(vector<vector<char>>& board) {
//Iterate over each row
for (int x = 0; x < 9; x++) {
//Add row numbers to map
map<char, int> row_nums {};
for (int i = 0; i < 9; i++) {
if (board[x][i] != '.') {
row_nums[board[x][i]]++;
}
}
//Return false if duplicates found in row map
for (auto it = row_nums.begin(); it != row_nums.end(); ++it) {
if (it->second > 1) {
return false;
}
}
}
//Iterate over columns
for (int i = 0; i < 9; i++) {
//Add column numbers to map
map<char, int> col_nums {};
for (int y = 0; y < 9; y++) {
if (board[i][y] != '.') {
col_nums[board[i][y]]++;
}
}
//Return false if duplicates found in column map
for (auto it = col_nums.begin(); it != col_nums.end(); it++) {
if (it->second > 1) {
return false;
}
}
}
//Iterate over the 3x3 sub-boxes and add numbers to a map
//I think this is where I am stuck
for (int x = 0; x < 9; x++) {
for (int y = 0; y < 9; y++) {
map<char, int> box_nums {};
for (int bx = (x/3)*3; bx < (x/3)*3 + 3; bx++) {
for (int by = (y/3)*3; by < (y/3)*3 + 3; by++) {
if (board[bx][by] != '.') {
box_nums[board[bx][by]]++;
}
}
}
//Return false if duplicates found in column map
for (auto it = box_nums.begin(); it != box_nums.end(); it++) {
if (it->second > 1) {
return false;
}
}
}
}
//Else return true
return true;
}
};回答 2
Stack Overflow用户
回答已采纳
发布于 2019-01-07 07:08:48
您共享的示例是有效的Sudoku w.r.t子框。在列4中有一个问题，其中有两个5。列检查中的逻辑必须更改为迭代每一行，保持列的固定。
//Iterate over columns
for (int i = 0; i < 9; i++) {
//Add column numbers to map
map<char, int> col_nums {};
for (int y = 0; y < 9; y++) {
if (board[y][i] != '.') {
col_nums[board[y][i]]++;
}
}
//Return false if duplicates found in column map
for (auto it = col_nums.begin(); it != col_nums.end(); it++) {
if (it->second > 1) {
return false;
}
}
}这应该能解决你的问题。
不确定您的子框问题，但这里有另一种不执行(bx/3)*3等操作来获取子框的方法
for (int x = 0; x < 9; x+=3) {
for (int y = 0; y < 9; y+=3) {
map<char, int> box_nums{};
for (int bx = x; bx < x + 3; bx++) {
for (int by = y; by < y + 3; by++) {
if (board[bx][by] != '.') {
box_nums[board[bx][by]]++;
}
}
}
//Return false if duplicates found in column map
for (auto it = box_nums.begin(); it != box_nums.end(); it++) {
if (it->second > 1) {
return false;
}
}
}
}Stack Overflow用户
发布于 2019-01-07 14:23:45
首先，您不需要一个std::map，并使用第二个循环来验证是否有计数大于1，只需使用std::set，如果insert操作返回false，这意味着找到了重复。其次，您只需拥有3个std::set数组并一次迭代所有行和列，只需为每一项找到适当的std::set：
const size_t size = 9;
using cset = std::set<char>;
using sets = std::array<cset,size>;
sets columns, rows, squares;
for( size_t i = 0; i < size; ++i ) {
for( size_t j = 0; j < size; ++j ) {
char n = board[i][j];
if( not checkSet( columns[i], n ) ) return false;
if( not checkSet( rows[j], n ) ) return false;
if( not checkSet( squares[i/3 + j/3*3], n ) ) return false;
}
}
return true;其中checkSet()可以这么简单：
bool checkSet( cset &s, char n )
{
return s.insert( n ).second;
}注意:如果您关心效率，您应该使用std::array<bool,size>而不是std::set，将您的字符转换为数字0-8，并在该数组中使用它作为索引。
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/54069163
复制相关文章
相似问题
腾讯云开发者
