二维数组限制：数独

Question

我正在尝试将数独问题作为约束满足问题来解决，这是一项家庭作业。我已经为特定行和列的所有元素构建了互不相同的约束条件。我正在尝试构建子区域中元素互不相同的约束条件，并遇到一些麻烦。

我目前算法的基本思想是将所有位于子区域（例如9x9网格中的3x3框）中的变量添加到列表中，并对该列表中的所有值进行排列以构建每个变量之间的不等式约束。下面的代码适用于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中不是必须的。如果您知道更好的方法，请分享您的见解。

- Ben Siver

---

阿，你有什么问题，我的小伙子？ - Bojangles

给定的代码迭代通过网格左上角开始的第一个子区域，但不是网格的每个子区域。 - Ben Siver

这只是简单的算术，没有更多了。如果你在纸上计算出来，你会立即看到算法。 - Hovercraft Full Of Eels

我已经在纸上努力解决了一段时间，这对我来说并不是那么容易:/ - Ben Siver

Answer 1

对于那些感兴趣的人，以下是我想出来的可行解决方案：

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);
            }
    }   
}

- Ben Siver

Answer 2

我不确定你想要做什么，但以下算法应该能给您所需的每个值。您可以忽略或删除您不需要的值。您可能可以在拥有所有数字的那一点上适当地填充所有数组。

我使用的单词：

• 方格：一个单独的方格来放置数字。
• 子区域：一组方格，一个 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++;
    }
}

如果您只需要每个子区域的左上角方块，只需删除内部两个循环即可：

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++;
    }
}

- Aberrant

Answer 3

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);
           }
        }
    }
}

- ratchet freak

---

由于某种奇怪的原因，您正在将start1初始化为其本身，而没有对start1进行任何初始化。同样的情况也适用于start2。因此，您无法编译上述代码片段。 - Keen Sage

谢谢您的快速回复。我不确定您的算法是否正确，因为我测试了它，并没有识别出除第一个子区域之外的所有子区域都有重复数字的情况。请注意，我已更改start1和start2的初始化值为0。 - Ben Siver

Answer 4

我不完全理解你想做什么，但如果你想解决这个谜题，你只需要一个递归方法，它会填入数字直到填满整个网格并且谜题是有效的。这是我为 futoshiki 谜题求解器提供的解决方案（类似于数独）。

- Giannis

---

我正在将这个谜题作为一个约束满足问题来解决。一旦约束条件确定下来（我卡住的步骤），我有一个比暴力搜索更高效的算法来解决这个谜题。 - Ben Siver

根据帖子明确说明是CSP问题，因此应该进行Downvote。显而易见的解决方案是递归，因为CSP将需要27*9！约600万个不同的约束条件... - Per Alexandersson

你是如何推理出这个数字的呢？9x9的限制数应该是810个，4x4的限制数应该是56个。 - Ben Siver