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= 行と= 列のブロック番号を返しますj。

4

2 に答える 2

5

Isn't it just: 

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

(assumes integer operations).

I would code a check, something like this (in pseudo 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 に答える