如何使用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;
}
};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提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/54069163
复制相关文章
相似问题
腾讯云开发者
