代码之家 › 专栏 › 技术社区 › TinyTiger

如何使用C++对数独子网格进行迭代?

c++

TinyTiger · 技术社区 · 7 年前

我正在尝试做一个在线数独C++测试题。

我需要确定9x9数独板是否有效。只有已填充的单元格需要根据以下规则进行验证(某些单元格有“.”表示未填充):

每行必须包含数字1-9,不得重复。
每列必须包含数字1-9,不得重复。
网格的9个3x3子框中的每个子框必须包含数字1-9,不能重复。

对于我的解决方案,我将遍历每一行、每一列和每一个子框网格。把这些数字加到地图上。并检查地图是否有任何副本。

我很确定我有标准 1 和 2 解决了,但我无法想象如何循环通过子框3x3网格。所以我适应了 some code found here 说实话,我还是不能完全清醒。我认为那部分可能是造成问题的原因。

如何解决标准3?

示例输入,正确的答案应返回假,但我的代码返回真:

[
[".",".","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 回复 | 直到 7 年前

Wander3r 7 年前

您共享的示例是有效的数独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;
            }
        }
    }
}

Slava 7 年前

首先,你不需要 std::map 并使用第二个循环来验证是否有任何计数大于1,只需使用 std::set 如果insert操作返回false,则表示发现了重复项。第二,你可以有3个数组 STD::设置 一次遍历所有行和列,只需找到合适的 STD::设置 每个项目:

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::设置 ,将字符转换为数字0-8,并将其用作该数组中的索引。