Two dimensional limitations of the array: sudoku

Question

I am trying to solve Sudoku as a problem of satisfying the constraints for a homework job. I have already created restrictions for all elements of a single row, as well as columns. I am trying to build constraints for elements in a separate area, and I am facing some problems.

The general idea of ​​my current algorithm is to add to the list all the variables that are in the subregion (for example, a 3x3 field for a 9x9 grid), and then rearrange all the values ​​in this list to build NotEqualConstraints between each variable. The code below works correctly for the 1st sub-region of the NxN grid, but I'm not sure how to change this to iterate over the rest of the 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 someone lead me in the right direction about how I can change the code to get into each subregion, and not just the upper left?

edit: I can also try any algorithm that works, there is no need to add all the values ​​to the ArrayList for each subregion. If you see a better way, please read the understanding.

Answer 1

Here is a working solution that I came across 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 quite sure what you are trying to do, but the algorithm below should give you everything you need. You can simply ignore and / or delete values ​​that you do not need. Perhaps you could fill all your arrays appropriately in the place where you have all the numbers.

Words I use:

• square: one square to enter a number.
• subregion: group of squares, 3x3 grid in classic sudoku.
• puzzle: all this, 3x3 subregion and 9x9 squares.

the 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 row (subRegionRow) //The subregion column (subRegionColumn) //The subregion index (subRegionIndex) //The square row within the puzzle (squareRowInPuzzle) //The square column within the puzzle (squareColumnInPuzzle) //The square index within the puzzle (squareIndexInPuzzle) //The square row within the subregion (squareRowInSubRegion) //The square column within the subregion (squareColumnInSubRegion) //The square 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 for each 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 row (subRegionRow) //The subregion column (subRegionColumn) //The subregion index (subRegionIndex) //The square row within the puzzle (squareRowInPuzzle) //The square column within the puzzle (squareColumnInPuzzle) //The square index within the puzzle (squareIndexInPuzzle) //The square row within the subregion (always 0) //The square column within the subregion (always 0) //The square index within the subregion (always 0) //You'll get this once for all squares, add the code to do something with it here. subRegionIndex++; } } 

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

Answer 4

I don’t quite understand what you are trying to do, but if you are trying to solve the riddle, you only need a recursive method that will put the numbers until it fills the entire grid and the puzzle is not valid. It was my solution to solve futoshiki puzzle (similar to sudoku)