Блог

Я пытаюсь решить судоку как проблему удовлетворения ограничений для домашнего задания. Я уже построил ограничения для всех элементов в определенной строке, которые различаются, а также для столбцов. Я пытаюсь создать ограничения для отдельных элементов в субрегионе, и у меня возникают некоторые проблемы.

Общая идея моего текущего алгоритма состоит в том, чтобы добавить все переменные, которые находятся в субрегионе (например, поле 3×3 для сетки 9×9), в список, а затем переставить все значения в этом списке, чтобы построить NotEqualConstraints между каждой переменной. Приведенный ниже код работает правильно для 1-го субрегиона сетки 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 для каждого субрегиона. Если вы видите лучший способ, пожалуйста, поделитесь информацией

Вот рабочее решение, которое я придумал, для тех, кто заинтересован:

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

Я не совсем уверен, что вы пытаетесь сделать, но приведенный ниже алгоритм должен дать вам все необходимые значения. Вы можете просто игнорировать и / или удалять ненужные вам значения. Вероятно, вы могли бы соответствующим образом заполнить все свои массивы в точке, где у вас есть все числа.

Слова, которые я использую:

• квадрат: один квадрат для ввода числа.
• субрегион: группа квадратов, сетка 3×3 в классическом судоку.
• головоломка: все это, 3×3 подобластей и 9×9 квадратов.

Код:

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

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

Я не совсем понял, что вы пытаетесь сделать, но если вы пытаетесь решить головоломку, вам просто нужен рекурсивный метод, который будет вводить числа до тех пор, пока он не заполнит всю сетку, и головоломка будет действительной.Это было мое решение для решателя головоломок futoshiki (аналогично sudoku)