0

好吧，我正在处理数独求解算法和生成问题，但仍停留在相当简单的任务上。我已经检查了一个数字是否真的适合按行和按列的位置。但让我抓狂的是块检查，即数字是否真的适合 3x3 块。

它必须足够简单，但我无法真正找到解决方案。简而言之，我想知道矩阵中某个位置所属的 3x3 块。以下是一些断言案例。块号、行号和列号索引从 0 开始。

assert("x( 0, 8 ) === 2"); 
assert("x( 8, 8 ) === 8"); 
assert("x( 3, 3 ) === 4"); 
assert("x( 3, 7 ) === 5"); 
assert("x( 7, 1 ) === 6");

x( i , j )返回块号，其中i= row 和j= col。

4

2 回答 2

5

不就是：

block = 3 * (i / 3) + (j / 3)

（假设整数运算）。

我会编写一个支票，像这样（在伪 C++ 中）

// row = row to check
// col = column to check
// checkNum = number we are thinking of inserting
bool check(int row, int col, int checkNum)
{
    int blockRow = 3 * (row/3);
    int blockCol = 3 * (col/3);
    for(int i = 0 ; i < 9 ; i++)
    {
        if(grid[row][i] == checkNum) return false; // number exists in the row.
        if(grid[i][col] == checkNum) return false; // number exists in the col.
        if(grid[blockRow + i/3][blockCol + i%3] == checkNum) return false; // number exists in the block.
    }
    return true;
}
于 2012-12-24T16:04:16.337 回答
1

这是javascript中的数独求解器。取自我创建的DSSudokuSolver。CleanElements 函数的功能与您要求的类似。

CleanElements = function(comp_ary, Qsudoku){
    for(i=0; i<9; i++){
        for(j=0; j<9; j++){
            /*if(Qsudoku[i][j] != ""){
                comp_ary[i][j]=[];
            }*/
            for(k=0; k<9; k++){
                i_index = comp_ary[i][k].indexOf(Qsudoku[i][j]);
                if(i_index != -1){
                    comp_ary[i][k].splice(i_index, 1);
                }
                j_index = comp_ary[k][j].indexOf(Qsudoku[i][j]);
                if(j_index != -1){
                    comp_ary[k][j].splice(j_index, 1);
                }
            }
            if(i < 3){
                i_min = 0;
                i_max = 2;
            }
            else if(i < 6){
                i_min = 3;
                i_max = 5;
            }
            else{
                i_min = 6;
                i_max = 8;
            }

            if(j < 3){
                j_min = 0;
                j_max = 2;
            }
            else if(j < 6){
                j_min = 3;
                j_max = 5;
            }
            else{
                j_min = 6;
                j_max = 8;
            }

            for(i_box=i_min; i_box<=i_max; i_box++){
                for(j_box=j_min; j_box<=j_max; j_box++){
                    index = comp_ary[i_box][j_box].indexOf(Qsudoku[i][j]);
                    if(index != -1){
                        comp_ary[i_box][j_box].splice(index, 1);
                    }
                }
            }
        }
    }
    return comp_ary;
}

FindElements = function(comp_ary, Qsudoku){
    for(i=0; i<9; i++){
        for(j=0; j<9; j++){
            if(comp_ary[i][j].length == 1){
                if (Qsudoku[i][j] == ""){
                    Qsudoku[i][j] = comp_ary[i][j][0];
                    comp_ary[i][j] = [];
                }
            }
        }
    }
    return Qsudoku;
}

IsThereNullElement = function(Qsudoku){
    for(i=0; i<9; i++){
        for(j=0; j<9; j++){
            if(Qsudoku[i][j] == ""){
                return false;
            }
        }
    }
    return true;
}

InitEmptyArray = function(){
    empty_ary = Array();
    for(i=0; i<9; i++){
        empty_ary[i] = Array();
        for(j=0; j<9; j++){
            empty_ary[i][j] = Array();
            for(k=0; k<9; k++){
                empty_ary[i][j][k] = (k+1).toString();
            }
        }
    }
    return empty_ary;
}

DSSolve = function(Qsudoku){
    comp_ary = InitEmptyArray(); //Complementary Array
    window.comp_ary_old = comp_ary;
    IterationMax = 5000;

    while(true){
        IterationMax -= 1;
        comp_ary = CleanElements(comp_ary, Qsudoku);
        console.log(comp_ary);

        if(window.comp_ary_old == comp_ary){
            //implement this.
        }
        else{
            window.comp_ary_old = comp_ary;
        }

        Qsudoku = FindElements(comp_ary, Qsudoku);
        //console.log(Qsudoku);

        if(IsThereNullElement(Qsudoku)){
            return Qsudoku;
        }

        if(IterationMax == 0){
            return null;
        }
    }
}
于 2012-12-24T16:10:21.680 回答