c++ - 您如何找出二维数组元素位于哪个子网格中

Question

这里是 C++ 初学者。我目前正在尝试制作一个数独解决程序，所以我必须检查它所在的 9x9 框中是否存在一个值。

这是我检查元素是否遵循规则的代码:

//constants for rows and columns of the sudoku puzzle, can be changed
const int ROWS = 9;
const int COLS = 9;

bool follows_rule(int grid[ROWS][COLS], int rowIndex, int colIndex, int value){


    for (int i = 0; i < COLS; i++){ 
        if (grid[rowIndex][i] == value) //check if there are any other values on the same column
            return false;
        if (grid[i][colIndex] == value) //or the same row
            return false;
    }
    //to-do: check if another equal value exists in the 9x9 box
    return true;
}

//returns true if another element has the same value as "value", false otherwise
bool exists_in_2d_array(int grid[ROWS][COLS], int value){
    for (int x = 0; x < ROWS / 3; x++)
    {
        for (int y = 0; y < COLS / 3; y++)
        {
            if (grid[x][y] == value)
            {
                return true;
            }
        }
    }
    return false;
}

我的想法是找出当前元素的坐标指向哪个 9x9 框，然后将该 9x9 网格放入另一个二维数组中，并检查该元素的值是否存在于网格中的其他位置。不过，我真的不知道该怎么做。

Answer 1

SUDOKU 规则要求数字只能使用一次:

• 规则 1:在每一行
• 规则 2:在每一列中
• 规则 3:在 9x9 网格的每个 3x3 子网格中

函数 follows_rule() 检查给定的网格位置，是否允许该值。目前它只检查规则 1 和 2。我建议你为规则 3 使用以下代码:

bool follows_rule(int grid[ROWS][COLS], int rowIndex, int colIndex, int value){
    for (int i = 0; i < COLS; i++){
        if (grid[rowIndex][i] == value)
            return false;
        if (grid[i][colIndex] == value) // ATTENTION THIS IS OK BECAUSE ROWS==COLS !!
            return false;
    }
    // Check if another equal value exists in the 3x3 box 
    int sgc = (colIndex / 3) * 3;   // in wich subgrid are we ?
    int sgr = (rowIndex / 3) * 3; 
    // check all the elements of the 3x3 grid startic at sgr, sgc
    for (int i = 0; i < 3; i++)
        for (int j = 0; j < 3; j++)
            if (grid[sgr + i][sgc + j] == value)
                return false; 
    return true;
}

您可以使用以下代码测试 3x3 验证:

int sudoku[ROWS][COLS] = {
        { 1, 0, 0, 0, 0, 0, 0, 8, 0 },
        { 0, 0, 2, 0, 0, 0, 0, 0, 0 },
        { 0, 3, 0, 0, 0, 0, 0, 0, 0 },
        { 0, 0, 0, 1, 3, 0, 0, 0, 0 },
        { 0, 0, 0, 0, 0, 5, 0, 0, 0 },
        { 0, 0, 0, 0, 8, 0, 0, 0, 0 },
        { 0, 0, 0, 0, 0, 0, 0, 0, 0 },
        { 0, 0, 0, 0, 0, 0, 0, 0, 0 },
        { 0, 0, 0, 0, 0, 0, 0, 0, 0 }
};

if (follows_rule(sudoku, 1, 0, 1) == false
    && follows_rule(sudoku, 1, 0, 4) == true
    && follows_rule(sudoku, 5, 5, 8) == false
    && follows_rule(sudoku, 5, 5, 1) == false
    && follows_rule(sudoku, 5, 5, 7) == true)
    cout << "Test ok !" << endl; 
else cout << "Tests failed" << endl;