Two Dimensional Array Constraints: Sudoku

Question

I am attempting to solve Sudoku as a constraint satisfaction problem for a homework assignment. I have already constructed constraints for all the elements in a particular row being distinct, as well as for columns. I am trying to construct the constraints for the elements in a sub-region being distinct, and I'm running into some trouble.

The general idea behind my current algorithm is to add all of the variables that are in a sub-region (e.g. a 3x3 box for a 9x9 grid) into a list, and then permute all the values in that list to construct NotEqualConstraints between each variable. The code below works properly for the 1st subregion of a NxN grid, but I am not sure how I should change this to iterate through the rest of the entire grid.

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

Can anyone guide me in the right direction about how I can modify the code to hit each subregion and not just the top left one?

edit: I am also open to trying any algorithm that works, it is not necessary to add all of the values to an ArrayList for each sub-region. If you see a better way, please share insight

Answer 1

Here is the working solution I came up with, for those interested:

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

Answer 2

I'm not entirely certain what you're trying to do, but the below algorithm should give you every value you need. You can just ignore and/or remove the values you don't need. You could probably fill all your arrays appropriately at the point where you have all the numbers.

The words I use:

• square: a single square to put a number in.
• subregion: a group of squares, a 3x3 grid in the classic sudoku.
• puzzle: the whole thing, 3x3 subregions and 9x9 squares.

Code:

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

If you only need the top left squares per subregion, just remove the inner two loops:

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