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

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

数独规则要求数字只能使用一次：

规则 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;

Answer 2

接受的答案没有正确计算子网格，sgc和sgr在除法后也需要乘以3才能正确识别子网格顶点

public boolean isValidEntry(char[][] board, int row , int col,char val)
{
    for(int i = 0 ; i < 9 ;i++){
        if(board[row][i] == val)
            return false;
    }
    
    for(int j = 0 ; j < 9 ;j++){
        if(board[j][col] == val)
            return false;
    }
    
    int sgc = col / 3;   // in wich subgrid are we ?
    int sgr = row / 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 (board[(3*sgr) + i][(3*sgc) + j] == val)
                return false;

    }

    return true;
    
}

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

How do you find out in which sub-grid a 2D array element is located

c++

arrays

multidimensional-array