6

宿題の制約充足問題として数独を解こうとしています。特定の行のすべての要素と列の制約をすでに作成しました。サブリージョン内の要素の制約を明確に構築しようとしていますが、問題が発生しています。

現在のアルゴリズムの背後にある一般的な考え方は、サブ領域(9x9グリッドの場合は3x3ボックスなど)にあるすべての変数をリストに追加し、そのリスト内のすべての値を並べ替えて、各変数間にNotEqualConstraintsを作成することです。 。以下のコードは、NxNグリッドの最初のサブリージョンで正しく機能しますが、グリッド全体の残りの部分を反復処理するためにこれをどのように変更すればよいかわかりません。

int incSize = (int)Math.sqrt(svars.length);

ArrayList<Variable> subBox = new ArrayList<Variable>();

for (int ind = 0; ind < incSize; ind++) {
for (int ind2 = 0; ind2 < incSize; ind2++) {
    subBox.add(svars[ind][ind2]);
    }
}

for (int i = 0; i < subBox.size(); i++) {
for (int j = i + 1; j < subBox.size(); j++) {
   NotEqualConstraint row = new NotEqualConstraint(subBox.get(i), subBox.get(j));
   constraints.add(row);
   }
}

左上のサブリージョンだけでなく、各サブリージョンにヒットするようにコードを変更する方法について、誰かが正しい方向に私を導くことができますか?

編集:私はまた、機能するアルゴリズムを試すこともできます。各サブ領域のArrayListにすべての値を追加する必要はありません。より良い方法を見つけたら、洞察を共有してください

4

4 に答える 4

3

興味のある人のために、私が思いついた実用的なソリューションは次のとおりです。

for (int ofs = 0; ofs < svars.length; ofs++) {
    int col = (ofs % incSize) * incSize;
    int row = ((int)(ofs / incSize)) * incSize;

    ArrayList<Variable> subBox = new ArrayList<Variable>();
    for (int ind = row; ind < row+incSize; ind++) {
        for (int ind2 = col; ind2 < col+incSize; ind2++) {
            subBox.add(svars[ind][ind2]);
        }
    }
    for (int i = 0; i < subBox.size(); i++) {
            for (int j = i + 1; j < subBox.size(); j++) {
               NotEqualConstraint c = new NotEqualConstraint(subBox.get(i), subBox.get(j));
               constraints.add(c);
            }
    }   
}
于 2011-10-14T01:24:13.317 に答える
1

あなたが何をしようとしているのか完全にはわかりませんが、以下のアルゴリズムはあなたが必要とするすべての価値をあなたに与えるはずです。不要な値は無視したり削除したりできます。おそらく、すべての数値が得られた時点で、すべての配列を適切に埋めることができます。

私が使う言葉:

  • 正方形:数値を入れる単一の正方形。
  • サブリージョン:正方形のグループ、古典的な数独の3x3グリッド。
  • パズル:全体、3x3のサブリージョンと9x9の正方形。

コード:

//You should have these values at this point:
int subRegionWidth = something; //amount of horizontal squares in a subregion
int subRegionHeight = something; //amount of vertical squares in a subregion
int amountOfHorizontalSubRegions = something; //amount of subRegion columns next to each other
int amountOfVerticalSubRegions = something; //amount of subregion rows on top of each other

//Doesn't change, so calculated once in advance:
int squaresPerPuzzleRow = subRegionWidth*amountOfHorizontalSubRegions;

//Variables to use inside the loop:
int subRegionIndex = 0;
int squareColumnInPuzzle;
int squareRowInPuzzle;
int squareIndexInPuzzle;
int squareIndexInSubRegion;

for(int subRegionRow=0; subRegionRow<amountOfVerticalSubRegions;subRegionRow++)
{
    for(int subRegionColumn=0; subRegionColumn<amountOfHorizontalSubRegions;subRegionColumn++)
    {
        for(int squareRowInRegion=0; squareRowInRegion<subRegionHeight; squareRowInRegion++)
        {
            for(int squareColumnInRegion=0; squareColumnInRegion<subRegionWidth; squareColumnInRegion++)
            {
                squareColumnInPuzzle = subRegionColumn*subRegionWidth + squareColumnInRegion;
                squareRowInPuzzle = subRegionRow*subRegionHeight + squareRowInRegion;
                squareIndexInPuzzle = squareRowInPuzzle*squaresPerPuzzleRow + squareColumnInPuzzle;
                squareIndexInSubRegion = squareRowInRegion*subRegionWidth + squareColumnInRegion;

                //You now have all the information of a square:

                //The subregion's row (subRegionRow)
                //The subregion's column (subRegionColumn)
                //The subregion's index (subRegionIndex)
                //The square's row within the puzzle (squareRowInPuzzle)
                //The square's column within the puzzle (squareColumnInPuzzle)
                //The square's index within the puzzle (squareIndexInPuzzle)
                //The square's row within the subregion (squareRowInSubRegion)
                //The square's column within the subregion (squareColumnInSubRegion)
                //The square's index within the subregion (squareIndexInSubRegion)

                //You'll get this once for all squares, add the code to do something with it here.
            }
        }
        subRegionIndex++;
    }
}

サブリージョンごとに左上の正方形のみが必要な場合は、内側の2つのループを削除するだけです。

for(int subRegionRow=0; subRegionRow<amountOfVerticalSubRegions;subRegionRow++)
{
    for(int subRegionColumn=0; subRegionColumn<amountOfHorizontalSubRegions;subRegionColumn++)
    {
        squareColumnInPuzzle = subRegionColumn*subRegionWidth;
        squareRowInPuzzle = subRegionRow*subRegionHeight;
        squareIndexInPuzzle = squareRowInPuzzle*squaresPerPuzzleRow + squareColumnInPuzzle;

        //You now have all the information of a top left square:

        //The subregion's row (subRegionRow)
        //The subregion's column (subRegionColumn)
        //The subregion's index (subRegionIndex)
        //The square's row within the puzzle (squareRowInPuzzle)
        //The square's column within the puzzle (squareColumnInPuzzle)
        //The square's index within the puzzle (squareIndexInPuzzle)
        //The square's row within the subregion (always 0)
        //The square's column within the subregion (always 0)
        //The square's index within the subregion (always 0)

        //You'll get this once for all squares, add the code to do something with it here.

        subRegionIndex++;
    }
}
于 2011-10-20T10:42:26.770 に答える
0
for (int start1 = start1; start1 < svars.length/incSize; start1 ++) {
    for (int start2 = start2; start2 < svars.length/incSize; start2++) {//iterate through all subsets
        ArrayList<Variable> subBox = new ArrayList<Variable>();

        for (int ind = start1*incSize; ind < incSize; ind++) {
            for (int ind2 = start2*incSize; ind2 < incSize; ind2++) {
                 subBox.add(svars[ind][ind2]);
            }
        }

       for (int i = 0; i < subBox.size(); i++) {
        for (int j = i + 1; j < subBox.size(); j++) {
           NotEqualConstraint row = new NotEqualConstraint(subBox.get(i), subBox.get(j));
           constraints.add(row);
           }
        }
    }
}
于 2011-10-09T22:23:25.733 に答える
-2

私はあなたが何をしようとしているのか完全には理解していませんでしたが、パズルを解こうとしているのなら、それがすべてのグリッドを埋めてパズルが有効になるまで数字を入れる再帰的な方法が必要です。それが不等式の私の解決策でしたパズルソルバー(数独に似ています)

于 2011-10-11T17:43:59.843 に答える