Введение
Итак, это продолжение моих попыток в новый алгоритм решения Судоку. Начало было тут, на текущий мой взгляд довольно глупое и неудачное.
Как известно, задача заполнения Судоку имеет большого родственника в виде задачи заполнения латинского квадрата. Если мы имеем некий латинский квадрат с аналогичным размером и наполнением, что и поле Судоку - то во множестве его решений будет и решение этого Судоку.
Для тех, кто немного "не в теме":
Лати́нский квадра́т n-го порядка — таблица L=(lij) размеров n × n, заполненная n элементами множества M таким образом, что в каждой строке и в каждом столбце таблицы каждый элемент из M встречается в точности один раз
Поэтому имеет смысл для начала придумать алгоритм заполнения латинского квадрата, дабы потом попытаться адаптировать это дело под Судоку. На этом я и решил остановиться.
Как известно, это тоже NP-полная задача, которая вряд ли может быть решена за полиноминальное время. Найденное мной решение, разумеется, скорее подтверждает этот тезис, но, быть может, оно не самое бесперспективное.
Код можно глянуть тут. Java, стримы, лямды и вот это вот все.
Итак, теперь можно перейти к рассмотрению самого решения.
Начало
Наша задача звучит так: дана квадратная матрица целых чисел с порядком N; каждый элемент матрицы - число от 1 до N. Необходимо найти все варианты ее заполнения по правилам латинского квадрата до определенного лимита.
Задача ясна, начнем с интерфейса для класса, который будет отвечать за данную логику.
LatinSquare
package com.smolka.latin.square;
import java.util.List;
public interface LatinSquare {
boolean check(Integer[][] square);
Integer[][] getFirstVariant(Integer[][] square);
List<Integer[][]> getVariantsWithLimit(Integer[][] square, int limit);
}
Метод check проверяет, заполнена ли матрица по правилам латинского квадрата и пригодится нам в тестах. getFirstVariant получает первое попавшееся решение - пусть будет, getVariantsWithLimit получает все решения до определенного лимита. Для каждого метода мы передаем square - т.е. наше поле, которое может как иметь некоторое предзаполнение (главное - валидное), так и не иметь его вовсе.
Полная реализация этого класса имеет такой вид - для тех, кому уже интересно глянуть.
LatinSquareImpl
package com.smolka.latin.square.impl;
import com.smolka.latin.square.LatinSquare;
import org.apache.commons.lang3.tuple.Pair;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;
import java.util.List;
import java.util.Map;
import java.util.Set;
import java.util.stream.Collectors;
import java.util.stream.IntStream;
public class LatinSquareImpl implements LatinSquare {
@Override
public boolean check(Integer[][] square) {
Set<Integer> allElements = IntStream.range(1, square.length + 1).boxed().collect(Collectors.toSet());
if (isInvalid(square, allElements)) {
return false;
}
for (int row = 0; row < square.length; row++) {
Set<Integer> elements = getSetOfNotNullElementsByRow(row, square);
if (elements.size() != allElements.size()) {
return false;
}
}
for (int column = 0; column < square.length; column++) {
Set<Integer> elements = getSetOfNotNullElementsByColumn(column, square);
if (elements.size() != allElements.size()) {
return false;
}
}
return true;
}
@Override
public Integer[][] getFirstVariant(Integer[][] square) {
Set<Integer> allElements = IntStream.range(1, square.length + 1).boxed().collect(Collectors.toSet());
if (isInvalid(square, allElements)) {
throw new RuntimeException("Square is invalid");
}
SelectionMatrix<Integer> selectionMatrix = new SelectionMatrix<>(square, allElements, Integer.class);
Step step = findingStep(new Step(selectionMatrix, 1));
if (!step.isLast()) {
return null;
}
return step.getResult().getFirst();
}
@Override
public List<Integer[][]> getVariantsWithLimit(Integer[][] square, int limit) {
Set<Integer> allElements = IntStream.range(1, square.length + 1).boxed().collect(Collectors.toSet());
if (isInvalid(square, allElements)) {
throw new RuntimeException("Square is invalid");
}
SelectionMatrix<Integer> selectionMatrix = new SelectionMatrix<>(square, allElements, Integer.class);
Step resultStep = findingStep(new Step(selectionMatrix, limit));
return resultStep.getResult();
}
private Step findingStep(Step step) {
if (step.isLast()) {
return step;
}
SelectionMatrix<Integer> currentSelectionMatrix = step.getCurrentMatrix();
Pair<Integer, List<SelectionMatrixElement<Integer>>> minRowPair = currentSelectionMatrix.getUnfilledRowAndIndexWithMinimumVariants();
Integer rowIndex = minRowPair.getKey();
List<SelectionMatrixElement<Integer>> row = minRowPair.getValue();
if (rowIndex == null) {
step.addToResult(currentSelectionMatrix);
return step;
}
Map<Integer, Set<Integer>> variantsMap = new HashMap<>();
for (int i = 0; i < row.size(); i++) {
SelectionMatrixElement<Integer> element = row.get(i);
variantsMap.put(i, element.getVariants());
}
VariantsFinder<Integer, Integer> variantsFinder = new VariantsFinder<>();
variantsFinder.findVariantsWithCallback(variantsMap, (newVariant) -> {
SelectionMatrix<Integer> copySelectionMatrix = currentSelectionMatrix.getCopy();
boolean validity = copySelectionMatrix.setRowToMatrixAndReturnValidity(rowIndex, newVariant);
if (!validity) {
return step.isLast();
}
Step newStep = step.newStep(copySelectionMatrix);
Step result = findingStep(newStep);
return result.isLast();
});
return step;
}
private boolean isInvalid(Integer[][] square, Set<Integer> allElements) {
if (square.length == 0) {
return true;
}
for (Integer[] row : square) {
if (row.length != square.length) {
return true;
}
for (Integer element : row) {
if (element == null) {
continue;
}
if (!allElements.contains(element)) {
return true;
}
}
}
for (int row = 0; row < square.length; row++) {
int count = getNotNullElementsCountByRow(row, square);
Set<Integer> notNullElementsSet = getSetOfNotNullElementsByRow(row, square);
if (count != notNullElementsSet.size()) {
return true;
}
}
for (int column = 0; column < square.length; column++) {
int count = getNotNullElementsCountByColumn(column, square);
Set<Integer> notNullElementsSet = getSetOfNotNullElementsByColumn(column, square);
if (count != notNullElementsSet.size()) {
return true;
}
}
return false;
}
private int getNotNullElementsCountByColumn(int column, Integer[][] square) {
int counter = 0;
for (Integer[] element : square) {
if (element[column] != null) {
counter++;
}
}
return counter;
}
private int getNotNullElementsCountByRow(int row, Integer[][] square) {
int counter = 0;
for (int column = 0; column < square.length; column++) {
if (square[row][column] != null) {
counter++;
}
}
return counter;
}
private Set<Integer> getSetOfNotNullElementsByColumn(int column, Integer[][] square) {
Set<Integer> result = new HashSet<>();
for (Integer[] element : square) {
if (element[column] != null) {
result.add(element[column]);
}
}
return result;
}
private Set<Integer> getSetOfNotNullElementsByRow(int row, Integer[][] square) {
Set<Integer> result = new HashSet<>();
for (int column = 0; column < square.length; column++) {
if (square[row][column] != null) {
result.add(square[row][column]);
}
}
return result;
}
private static class Step {
private final SelectionMatrix<Integer> currentSelectionMatrix;
private final int limit;
private final List<Integer[][]> result;
public Step(SelectionMatrix<Integer> currentSelectionMatrix, int limit) {
this.currentSelectionMatrix = currentSelectionMatrix;
this.limit = limit;
this.result = new ArrayList<>();
}
private Step(SelectionMatrix<Integer> currentSelectionMatrix, int limit, List<Integer[][]> result) {
this.currentSelectionMatrix = currentSelectionMatrix;
this.limit = limit;
this.result = result;
}
public void addToResult(SelectionMatrix<Integer> selectionMatrix) {
result.add(selectionMatrix.toArray());
}
public Step newStep(SelectionMatrix<Integer> newSelectionMatrix) {
return new Step(newSelectionMatrix, limit, result);
}
public boolean isLast() {
return result.size() >= limit;
}
public SelectionMatrix<Integer> getCurrentMatrix() {
return currentSelectionMatrix;
}
public List<Integer[][]> getResult() {
return result;
}
}
}
По ходу статьи станет ясней, что здесь происходит.
Начало алгоритма. Инициализация матрицы подбора. Корректировка
Теперь немного о самом алгоритме.
Общая идея такова: алгоритм подбирает строки для квадрата до тех пор, пока полностью не заполнит квадрат. Делает он это исходя из всех допустимых вариантов каждой ячейки квадрата. Если количество допустимых вариантов для ячейки равняется 1 - то это уже заполненная ячейка, в моей терминологии имеющая сильный вариант. Все множество допустимых вариантов для ячейки вычисляется, как (A \ B) \ C, где A - множество всех возможных значений, B - множество всех сильных вариантов по строке элемента, C - множество всех сильных вариантов по столбцу элемента. Ну а операция \ - это разница между двумя множествами.
Проще говоря, если исходная матрица у нас имеет такой вид:
1 |
2 |
3 |
4 |
5 |
null |
4 |
null |
null |
null |
null |
null |
null |
5 |
null |
2 |
null |
null |
null |
null |
3 |
null |
null |
null |
null |
То допустимые варианты для незаполненных ячеек должны иметь такой вид:
1 |
2 |
3 |
4 |
5 |
(5) |
4 |
(1,2) |
(1,2,3) |
(1,2,3) |
(4) |
(1,3) |
(1,2) |
5 |
(1,2,3) |
2 |
(1,3,5) |
(1,4,5) |
(1,3) |
(1,3,4) |
3 |
(1,5) |
(1,2,4,5) |
(1,2) |
(1,2,4) |
Не забываем, что ячейки 1.0 и 2.0 (строка-столбец, счет с нуля) тоже являются сильными вариантами, соответственно, тоже должны быть учтены.
Ну а при инициализации на основе полностью пустого квадрата все будет скучней: каждый элемент будет представлять из себя множество всех возможных значений.
Этот формат уже не соответствует исходному полю, представленному в виде двумерного массива целых чисел. Соответственно, уже на этом этапе напрашивается отдельная сущность, которую я назвал матрицей подбора. Под нее я завел отдельный класс, в котором происходит относительно много интересного. Вот сразу его код.
SelectionMatrix
package com.smolka.latin.square.impl;
import org.apache.commons.lang3.tuple.Pair;
import java.lang.reflect.Array;
import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Map;
import java.util.Objects;
import java.util.Set;
import java.util.stream.Collectors;
public class SelectionMatrix<T> {
private final List<List<SelectionMatrixElement<T>>> matrix;
private final Set<Integer> unfilledRows;
private final Set<T> allElements;
private final int size;
private final Class<T> clazz;
private SelectionMatrix(List<List<SelectionMatrixElement<T>>> matrix,
Set<T> allElements,
Set<Integer> unfilledRows,
int size,
Class<T> clazz) {
this.matrix = matrix;
this.allElements = allElements;
this.unfilledRows = unfilledRows;
this.size = size;
this.clazz = clazz;
}
public SelectionMatrix(T[][] field,
Set<T> allElements,
Class<T> clazz) {
this.clazz = clazz;
if (field.length == 0) {
throw new RuntimeException("Field is empty");
}
for (T[] row : field) {
if (row.length != field.length) {
throw new RuntimeException("Field is not matrix");
}
}
this.size = field.length;
this.matrix = new ArrayList<>();
this.allElements = allElements;
this.unfilledRows = new HashSet<>();
for (int row = 0; row < field.length; row++) {
List<SelectionMatrixElement<T>> rowMatrix = new ArrayList<>();
matrix.add(rowMatrix);
for (int column = 0; column < field[row].length; column++) {
if (field[row][column] == null) {
rowMatrix.add(new SelectionMatrixElement<>(row, column));
} else {
if (!allElements.contains(field[row][column])) {
throw new RuntimeException(String.format("Matrix contains unknown element %s", field[row][column]));
}
rowMatrix.add(new SelectionMatrixElement<>(row, column, new HashSet<>(Set.of(field[row][column]))));
}
}
}
for (int rowIndex = 0; rowIndex < matrix.size(); rowIndex++) {
List<SelectionMatrixElement<T>> row = matrix.get(rowIndex);
for (SelectionMatrixElement<T> elem : row) {
if (!elem.isStrong()) {
unfilledRows.add(rowIndex);
break;
}
}
}
prepareMatrix();
}
public T[][] toArray() {
if (!isFilled()) {
throw new RuntimeException("Attempt to create an array from unfilled matrix");
}
@SuppressWarnings("unchecked")
T[][] result = (T[][]) Array.newInstance(clazz, size, size);;
for (int row = 0; row < size; row++) {
for (int column = 0; column < size; column++) {
result[row][column] = getElement(row, column).getStrongValue();
}
}
return result;
}
public SelectionMatrixElement<T> getElement(int row, int column) {
return matrix.get(row).get(column);
}
public boolean isFilled() {
return unfilledRows.isEmpty();
}
public Pair<Integer, List<SelectionMatrixElement<T>>> getUnfilledRowAndIndexWithMinimumVariants() {
if (unfilledRows.isEmpty()) {
return Pair.of(null, null);
}
int resultIndex = unfilledRows.stream().findFirst().orElseThrow();
int min = Integer.MAX_VALUE;
for (int unfilledRowIndex : unfilledRows) {
int allVariantsSize = matrix.get(unfilledRowIndex)
.stream()
.map(SelectionMatrixElement::getVariantsSize)
.reduce(Integer::sum)
.orElseThrow();
int avgSize = (allVariantsSize / size);
if (avgSize < min) {
resultIndex = unfilledRowIndex;
min = avgSize;
}
}
return Pair.of(resultIndex, matrix.get(resultIndex));
}
public SelectionMatrix<T> getCopy() {
List<List<SelectionMatrixElement<T>>> newMatrix = new ArrayList<>();
Set<Integer> unfilledRows = new HashSet<>(this.unfilledRows);
for (List<SelectionMatrixElement<T>> row : matrix) {
List<SelectionMatrixElement<T>> newRow = new ArrayList<>();
newMatrix.add(newRow);
for (SelectionMatrixElement<T> selectionMatrixElement : row) {
newRow.add(selectionMatrixElement.copy());
}
}
return new SelectionMatrix<>(newMatrix, allElements, unfilledRows, size, clazz);
}
public boolean setRowToMatrixAndReturnValidity(int rowIndex, Map<Integer, T> rowToSet) {
if (unfilledRows.isEmpty()) {
throw new RuntimeException("Attempt to set row for empty matrix");
}
if (rowToSet.size() == size) {
unfilledRows.remove(rowIndex);
}
List<SelectionMatrixElement<T>> rowInMatrix = matrix.get(rowIndex);
List<RowInfo<T>> unfilledMatrix = getUnfilledRowsInOrder();
for (int valueIndex = 0; valueIndex < rowToSet.size(); valueIndex++) {
T value = rowToSet.get(valueIndex);
rowInMatrix.get(valueIndex).resetVariants(value);
for (RowInfo<T> unfilledRow : unfilledMatrix) {
int unfilledRowIndex = unfilledRow.rowIndex();
if (unfilledRowIndex == rowIndex) {
continue;
}
List<SelectionMatrixElement<T>> unfilledRowValues = unfilledRow.rowValues();
unfilledRowValues.get(valueIndex).removeVariant(value);
}
}
return correctUnfilledPartAndReturnValidity();
}
private boolean correctUnfilledPartAndReturnValidity() {
List<RowInfo<T>> unfilledMatrix = getUnfilledRowsInOrder();
boolean wasChanges;
do {
SubSegmentValidityResult rowProcessResult = postProcessRowsSubSegmentsAndReturnValidity(unfilledMatrix);
if (!rowProcessResult.isValid()) {
return false;
}
wasChanges = rowProcessResult.wasChanges();
SubSegmentValidityResult columnProcessResult = postProcessColumnsSubSegmentsAndReturnValidity(unfilledMatrix);
if (!columnProcessResult.isValid()) {
return false;
}
if (columnProcessResult.wasChanges()) {
wasChanges = true;
}
} while (wasChanges);
for (RowInfo<T> unfilledRow : unfilledMatrix) {
boolean reallyUnfilled = unfilledRow.rowValues().stream().anyMatch(e -> !e.isStrong());
if (!reallyUnfilled) {
unfilledRows.remove(unfilledRow.rowIndex());
}
}
return true;
}
private SubSegmentValidityResult postProcessColumnsSubSegmentsAndReturnValidity(List<RowInfo<T>> matrix) {
boolean wasChanges = false;
for (int columnIndex = 0; columnIndex < size; columnIndex++) {
List<SelectionMatrixElement<T>> column = new ArrayList<>();
for (RowInfo<T> row : matrix) {
column.add(row.rowValues().get(columnIndex));
}
SubSegmentValidityResult processResult = postProcessSubSegmentAndReturnValidity(column);
if (!processResult.isValid) {
return new SubSegmentValidityResult(false, false);
}
if (processResult.wasChanges) {
wasChanges = true;
}
}
return new SubSegmentValidityResult(true, wasChanges);
}
private SubSegmentValidityResult postProcessRowsSubSegmentsAndReturnValidity(List<RowInfo<T>> matrix) {
boolean wasChanges = false;
for (RowInfo<T> row : matrix) {
SubSegmentValidityResult processResult = postProcessSubSegmentAndReturnValidity(row.rowValues());
if (!processResult.isValid) {
return new SubSegmentValidityResult(false, false);
}
if (processResult.wasChanges) {
wasChanges = true;
}
}
return new SubSegmentValidityResult(true, wasChanges);
}
private SubSegmentValidityResult postProcessSubSegmentAndReturnValidity(List<SelectionMatrixElement<T>> subSegment) {
SubSegmentVariantsOccurrenceInfo<T> subSegmentVariantsOccurrenceInfo = new SubSegmentVariantsOccurrenceInfo<>();
for (int index = 0; index < subSegment.size(); index++) {
subSegmentVariantsOccurrenceInfo.putOccurrenceInfo(subSegment.get(index).getVariants(), index);
}
if (subSegmentVariantsOccurrenceInfo.hasError()) {
return new SubSegmentValidityResult(false, false);
}
Map<Set<T>, Set<Integer>> variantsWithSizeOccurrenceEquality = subSegmentVariantsOccurrenceInfo.getVariantsWithSizeOccurrenceEquality();
boolean wasChanges = false;
for (Map.Entry<Set<T>, Set<Integer>> variantWithSizeOccurrenceEqualityEntry : variantsWithSizeOccurrenceEquality.entrySet()) {
Set<T> variant = variantWithSizeOccurrenceEqualityEntry.getKey();
Set<Integer> onIndexes = variantWithSizeOccurrenceEqualityEntry.getValue();
for (int otherIndex = 0; otherIndex < subSegment.size(); otherIndex++) {
if (onIndexes.contains(otherIndex)) {
continue;
}
SelectionMatrixElement<T> otherElement = subSegment.get(otherIndex);
if (otherElement.removeVariants(variant)) {
wasChanges = true;
}
}
}
if (wasChanges) {
SubSegmentValidityResult newResult = postProcessSubSegmentAndReturnValidity(subSegment);
if (!newResult.isValid()) {
return new SubSegmentValidityResult(false, false);
}
return new SubSegmentValidityResult(true, wasChanges);
}
return new SubSegmentValidityResult(true, wasChanges);
}
private List<RowInfo<T>> getUnfilledRowsInOrder() {
List<RowInfo<T>> result = new ArrayList<>();
List<Integer> unfilledRowsIndicesInOrder = unfilledRows.stream().sorted().toList();
for (Integer unfilledRowIndex : unfilledRowsIndicesInOrder) {
result.add(new RowInfo<>(unfilledRowIndex, matrix.get(unfilledRowIndex)));
}
return result;
}
private void prepareMatrix() {
for (int row = 0; row < matrix.size(); row++) {
List<SelectionMatrixElement<T>> emptyElementsByRow = getEmptyElementsByRow(row, matrix);
for (SelectionMatrixElement<T> emptyElementInRow : emptyElementsByRow) {
List<SelectionMatrixElement<T>> constraints = getStrongElementsByElementSegment(emptyElementInRow, matrix);
Set<T> valuesFromConstraints = constraints.stream().map(SelectionMatrixElement::getStrongValue).collect(Collectors.toSet());
Set<T> newVariants = new HashSet<>(allElements);
newVariants.removeAll(valuesFromConstraints);
if (newVariants.isEmpty()) {
throw new RuntimeException("Matrix is invalid");
}
emptyElementInRow.resetVariants(newVariants);
}
}
if (!correctUnfilledPartAndReturnValidity()) {
throw new RuntimeException("Matrix is invalid");
}
}
private List<SelectionMatrixElement<T>> getStrongElementsByElementSegment(SelectionMatrixElement<T> element, List<List<SelectionMatrixElement<T>>> matrix) {
List<SelectionMatrixElement<T>> result = new ArrayList<>();
int row = element.getRow();
int column = element.getColumn();
for (int rowIndex = 0; rowIndex < matrix.size(); rowIndex++) {
if (rowIndex == row) {
continue;
}
SelectionMatrixElement<T> matrixElem = matrix.get(rowIndex).get(column);
if (matrixElem.isStrong()) {
result.add(matrixElem);
}
}
for (int columnIndex = 0; columnIndex < matrix.size(); columnIndex++) {
if (columnIndex == column) {
continue;
}
SelectionMatrixElement<T> matrixElem = matrix.get(row).get(columnIndex);
if (matrixElem.isStrong()) {
result.add(matrixElem);
}
}
return result;
}
private List<SelectionMatrixElement<T>> getEmptyElementsByRow(int row, List<List<SelectionMatrixElement<T>>> matrix) {
List<SelectionMatrixElement<T>> result = new ArrayList<>();
for (int column = 0; column < matrix.size(); column++) {
if (matrix.get(row).get(column).isEmpty()) {
result.add(matrix.get(row).get(column));
}
}
return result;
}
private record RowInfo<T>(
int rowIndex,
List<SelectionMatrixElement<T>> rowValues
) {
@Override
public boolean equals(Object o) {
if (o == null || getClass() != o.getClass()) return false;
RowInfo<?> rowInfo = (RowInfo<?>) o;
return rowIndex == rowInfo.rowIndex && Objects.equals(rowValues, rowInfo.rowValues);
}
@Override
public int hashCode() {
return Objects.hash(rowIndex, rowValues);
}
}
private record SubSegmentValidityResult(
boolean isValid,
boolean wasChanges
) {
@Override
public boolean equals(Object o) {
if (o == null || getClass() != o.getClass()) return false;
SubSegmentValidityResult that = (SubSegmentValidityResult) o;
return isValid == that.isValid && wasChanges == that.wasChanges;
}
@Override
public int hashCode() {
return Objects.hash(isValid, wasChanges);
}
}
}
SelectionMatrixElement
package com.smolka.latin.square.impl;
import java.util.HashSet;
import java.util.Objects;
import java.util.Set;
import java.util.stream.Collectors;
public class SelectionMatrixElement<T> {
private final int row;
private final int column;
private final Set<T> variants;
public SelectionMatrixElement(int row, int column) {
this.row = row;
this.column = column;
this.variants = new HashSet<>();
}
public SelectionMatrixElement(int row, int column, Set<T> variants) {
this.row = row;
this.column = column;
this.variants = variants;
}
public int getVariantsSize() {
return variants.size();
}
public Set<T> getVariants() {
return variants;
}
public int getRow() {
return row;
}
public int getColumn() {
return column;
}
public SelectionMatrixElement<T> copy() {
return new SelectionMatrixElement<>(row, column, new HashSet<>(variants));
}
public boolean removeVariants(Set<T> variants) {
return this.variants.removeAll(variants);
}
public void removeVariant(T variant) {
this.variants.remove(variant);
}
public boolean isStrong() {
return variants.size() == 1;
}
public T getStrongValue() {
if (!isStrong()) {
throw new RuntimeException("Attempt to unboxing non-strong element");
}
return variants.stream().findFirst().orElseThrow();
}
public void resetVariants(T variant) {
this.variants.clear();
this.variants.add(variant);
}
public void resetVariants(Set<T> variants) {
this.variants.clear();
this.variants.addAll(variants);
}
public boolean isEmpty() {
return variants.isEmpty();
}
@Override
public boolean equals(Object o) {
if (o == null || getClass() != o.getClass()) return false;
SelectionMatrixElement<?> that = (SelectionMatrixElement<?>) o;
return row == that.row && column == that.column;
}
@Override
public int hashCode() {
return Objects.hash(row, column);
}
@Override
public String toString() {
return "(" + this.variants.stream().map(Objects::toString).collect(Collectors.joining(", ")) + ")";
}
}
Инициализируется эта матрица (если мы не создаем ее копию) через конструктор SelectionMatrix(T[][] field, Set<T> allElements, Class<T> clazz).
Здесь field - это наша матрица, allElements - все элементы, которыми она должна быть заполнена (в случае целых чисел - ряд от 1 до N), clazz - класс элементов (Integer в случае целых чисел).
Логика инициализации следующая:
Для начала - базовая валидация. Проверяем, не пустое ли поле и является ли оно квадратной матрицей. По образу field мы инициализируем matrix - List List-ов, где "внешний" List - это строка, а элементы "внутреннего" List-а - это элементы матрицы подбора, т.е. все столбцы по отношению к строке. Если элемент поля null - то и соответствующий элемент матрицы подбора до поры будет пустым, иначе создаем элемент с "сильным" (т.е. единственным) вариантом. Затем построчно проверяем, есть ли незаполненные варианты, и если они есть - запоминаем строку, как незаполненную.
Ремарка: информация о незаполненных строках - важная, и в последующих подборах будет обновляться.
Далее уже интересней - нам надо подготовить матрицу подбора, заполнив пустые элементы "слабыми" вариантами. Для начала мы пробегаемся по каждому пустому элементу и подтягиваем множество всех "сильных" вариантов, входящих в его сегмент (строка + столбец). Множество, полученное из разницы между allElements и этим множеством и есть заполнение для этого элемента. Если в процессе какой-то элемент ничем не заполнился - то с матрицей что-то не так, прокидываем ошибку.
С этим процессом есть как минимум одна проблема: по ходу дела будут появляться новые и новые "сильные" элементы. Хорошо, если они в самом начале обработки строки, но если где-нибудь в середине - то нам надо корректировать все предыдущие элементы, содержащие такой же вариант (т.к. он уже считается невозможным). И все это надо делать циклично, т.к. такая корректировка одного варианта может породить новый "сильный" вариант с надобностью нового прохода.
Появляется следующая идея, которая будет использоваться не только в валидации. Корректировка.
Отдельно по каждому подсегменту (т.е. строка или столбец) мы получаем статистику встречаемости тех или иных комбинаций. Если встречаемость определенной комбинации превышает ее размерность - это говорит нам об ошибке. Если же встречаемость комбинации равна ее размерности - это говорит нам о том, что элементы этой комбинации возможно распределить только на тех местах, на которых стоит эта комбинация. Из остальных комбинаций в подсегменте необходимо убрать элементы из этой комбинации. Процесс повторяется циклично, если были изменения - то проходим через процесс еще раз, до тех пор, пока перестанут появляться новые и новые изменения. Если в процессе какая-то строка полностью заполнена - запоминаем это.
Эта идея выродилась в следующий класс и следующие методы.
SubSegmentVariantsOccurrenceInfo
package com.smolka.latin.square.impl;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;
public class SubSegmentVariantsOccurrenceInfo<T> {
private final Map<Set<T>, Set<Integer>> variantsOccurrenceInfo;
public SubSegmentVariantsOccurrenceInfo() {
this.variantsOccurrenceInfo = new HashMap<>();
}
public void putOccurrenceInfo(Set<T> variants, Integer index) {
variantsOccurrenceInfo.putIfAbsent(variants, new HashSet<>());
variantsOccurrenceInfo.get(variants).add(index);
}
public boolean hasError() {
for (Map.Entry<Set<T>, Set<Integer>> variantOccurrenceEntry : variantsOccurrenceInfo.entrySet()) {
Set<T> variant = variantOccurrenceEntry.getKey();
Set<Integer> indices = variantOccurrenceEntry.getValue();
if (variant.size() < indices.size()) {
return true;
}
}
return false;
}
public Map<Set<T>, Set<Integer>> getVariantsWithSizeOccurrenceEquality() {
Map<Set<T>, Set<Integer>> result = new HashMap<>();
for (Map.Entry<Set<T>, Set<Integer>> variantOccurrenceEntry : variantsOccurrenceInfo.entrySet()) {
Set<T> variant = variantOccurrenceEntry.getKey();
Set<Integer> indices = variantOccurrenceEntry.getValue();
if (variant.size() == indices.size()) {
result.put(variant, indices);
}
}
return result;
}
}
методы в SelectionMatrix
...
private boolean correctUnfilledPartAndReturnValidity() {
List<RowInfo<T>> unfilledMatrix = getUnfilledRowsInOrder();
boolean wasChanges;
do {
SubSegmentValidityResult rowProcessResult = postProcessRowsSubSegmentsAndReturnValidity(unfilledMatrix);
if (!rowProcessResult.isValid()) {
return false;
}
wasChanges = rowProcessResult.wasChanges();
SubSegmentValidityResult columnProcessResult = postProcessColumnsSubSegmentsAndReturnValidity(unfilledMatrix);
if (!columnProcessResult.isValid()) {
return false;
}
if (columnProcessResult.wasChanges()) {
wasChanges = true;
}
} while (wasChanges);
for (RowInfo<T> unfilledRow : unfilledMatrix) {
boolean reallyUnfilled = unfilledRow.rowValues().stream().anyMatch(e -> !e.isStrong());
if (!reallyUnfilled) {
unfilledRows.remove(unfilledRow.rowIndex());
}
}
return true;
}
...
private List<RowInfo<T>> getUnfilledRowsInOrder() {
List<RowInfo<T>> result = new ArrayList<>();
List<Integer> unfilledRowsIndicesInOrder = unfilledRows.stream().sorted().toList();
for (Integer unfilledRowIndex : unfilledRowsIndicesInOrder) {
result.add(new RowInfo<>(unfilledRowIndex, matrix.get(unfilledRowIndex)));
}
return result;
}
...
private SubSegmentValidityResult postProcessColumnsSubSegmentsAndReturnValidity(List<RowInfo<T>> matrix) {
boolean wasChanges = false;
for (int columnIndex = 0; columnIndex < size; columnIndex++) {
List<SelectionMatrixElement<T>> column = new ArrayList<>();
for (RowInfo<T> row : matrix) {
column.add(row.rowValues().get(columnIndex));
}
SubSegmentValidityResult processResult = postProcessSubSegmentAndReturnValidity(column);
if (!processResult.isValid) {
return new SubSegmentValidityResult(false, false);
}
if (processResult.wasChanges) {
wasChanges = true;
}
}
return new SubSegmentValidityResult(true, wasChanges);
}
...
private SubSegmentValidityResult postProcessRowsSubSegmentsAndReturnValidity(List<RowInfo<T>> matrix) {
boolean wasChanges = false;
for (RowInfo<T> row : matrix) {
SubSegmentValidityResult processResult = postProcessSubSegmentAndReturnValidity(row.rowValues());
if (!processResult.isValid) {
return new SubSegmentValidityResult(false, false);
}
if (processResult.wasChanges) {
wasChanges = true;
}
}
return new SubSegmentValidityResult(true, wasChanges);
}
...
private SubSegmentValidityResult postProcessSubSegmentAndReturnValidity(List<SelectionMatrixElement<T>> subSegment) {
SubSegmentVariantsOccurrenceInfo<T> subSegmentVariantsOccurrenceInfo = new SubSegmentVariantsOccurrenceInfo<>();
for (int index = 0; index < subSegment.size(); index++) {
subSegmentVariantsOccurrenceInfo.putOccurrenceInfo(subSegment.get(index).getVariants(), index);
}
if (subSegmentVariantsOccurrenceInfo.hasError()) {
return new SubSegmentValidityResult(false, false);
}
Map<Set<T>, Set<Integer>> variantsWithSizeOccurrenceEquality = subSegmentVariantsOccurrenceInfo.getVariantsWithSizeOccurrenceEquality();
boolean wasChanges = false;
for (Map.Entry<Set<T>, Set<Integer>> variantWithSizeOccurrenceEqualityEntry : variantsWithSizeOccurrenceEquality.entrySet()) {
Set<T> variant = variantWithSizeOccurrenceEqualityEntry.getKey();
Set<Integer> onIndexes = variantWithSizeOccurrenceEqualityEntry.getValue();
for (int otherIndex = 0; otherIndex < subSegment.size(); otherIndex++) {
if (onIndexes.contains(otherIndex)) {
continue;
}
SelectionMatrixElement<T> otherElement = subSegment.get(otherIndex);
if (otherElement.removeVariants(variant)) {
wasChanges = true;
}
}
}
if (wasChanges) {
SubSegmentValidityResult newResult = postProcessSubSegmentAndReturnValidity(subSegment);
if (!newResult.isValid()) {
return new SubSegmentValidityResult(false, false);
}
return new SubSegmentValidityResult(true, wasChanges);
}
return new SubSegmentValidityResult(true, wasChanges);
}
...
private record RowInfo<T>(
int rowIndex,
List<SelectionMatrixElement<T>> rowValues
) {
@Override
public boolean equals(Object o) {
if (o == null || getClass() != o.getClass()) return false;
RowInfo<?> rowInfo = (RowInfo<?>) o;
return rowIndex == rowInfo.rowIndex && Objects.equals(rowValues, rowInfo.rowValues);
}
@Override
public int hashCode() {
return Objects.hash(rowIndex, rowValues);
}
}
...
private record SubSegmentValidityResult(
boolean isValid,
boolean wasChanges
) {
@Override
public boolean equals(Object o) {
if (o == null || getClass() != o.getClass()) return false;
SubSegmentValidityResult that = (SubSegmentValidityResult) o;
return isValid == that.isValid && wasChanges == that.wasChanges;
}
@Override
public int hashCode() {
return Objects.hash(isValid, wasChanges);
}
}Ключевой метод - correctUnfilledPartAndReturnValidity, который и проделывает всю эту работу с незаполненными строками матрицы, возвращая false, если в процессе вышли на ошибку (встречаемость > размерности).
При инициализации если correctUnfilledPartAndReturnValidity вернул false - мы можем прокидывать исключение. Этот метод будет использоваться не только в валидации, но об этом позже.
В остальном же по прохождению начальной инициализации и корректировки на поле такого вида, например
{ 1, 2, 3 },
{ null, null, null },
{ null, 1, null }мы сразу получаем заполненную матрицу подбора вида
{ 1, 2, 3 },
{ 2, 3, 1 },
{ 3, 1, 2 }И даже никаких действий больше не нужно. Довольно неплохо для начала.
Дем дальш.
Генерируем варианты строк. Подстановка и ее последствия. Сборка решений
Второй большой и финальный шаг ведет нас в два класса - возвращаемся в LatinSquareImpl + смотрим на VariantsFinder. Его код без методов-для-галочки прикладываю.
VariantsFinder без лишнего
package com.smolka.latin.square.impl;
import org.apache.commons.lang3.tuple.Pair;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;
import java.util.List;
import java.util.Map;
import java.util.Set;
import java.util.function.Function;
public class VariantsFinder<K, V> {
...
public void findVariantsWithCallback(Map<K, Set<V>> keyValuesMap, Function<Map<K, V>, Boolean> callbackFunction) {
List<Pair<K, Set<V>>> content = keyValuesMap.entrySet().stream()
.map(es -> Pair.of(es.getKey(), es.getValue()))
.toList();
findCartesianProductWithoutDupesWithCallback(content, 0, new HashMap<>(), callbackFunction);
}
...
private boolean findCartesianProductWithoutDupesWithCallback(List<Pair<K, Set<V>>> content, int index, Map<K, V> current, Function<Map<K, V>, Boolean> callbackFunction) {
if (index == content.size()) {
Set<V> values = new HashSet<>(current.values());
if (values.size() == content.size()) {
return callbackFunction.apply(new HashMap<>(current));
}
return false;
}
Set<V> addedValuesSet = new HashSet<>(current.values());
for (int i = index + 1; i < content.size(); i++) {
if (addedValuesSet.containsAll(content.get(i).getValue())) {
return false;
}
}
Pair<K, Set<V>> currentPair = content.get(index);
K key = currentPair.getKey();
Set<V> values = currentPair.getValue();
for (V value : values) {
if (addedValuesSet.contains(value)) {
continue;
}
current.put(key, value);
if (findCartesianProductWithoutDupesWithCallback(content, index + 1, current, callbackFunction)) {
return true;
}
current.remove(key);
}
return false;
}
}
В чем суть шага?
мы обрабатываем незаполненные строки, начиная с тех, что в среднем содержат меньше всего вариантов (вычисляется как общее количество всех вариантов, деленное на размер строки).
выбираем из этого множества определенную строку и начинаем подбирать под нее варианты.
все варианты строки - по факту просто декартово произведение из элементов строки, только каждый элемент произведения не должен содержать повторов.
как только нам удалось подобрать вариант строки - мы создаем копию текущей матрицы подбора и вставляем эту строку в матрицу.
процесс подстановки и проверки выглядит так: сетаем в соответствующую строку матрицы подбора "сильные" варианты на соответствующие места. Идем "вниз" по колонкам остальных строк, удаляя "сильный" вариант из элементов соотв. столбца. Вызываем метод correctUnfilledPartAndReturnValidity, возвращаем его результат наружу - строка "не встала", если был возвращен false.
зарываемся глубже в рекурсию, если строка "встала".
если незаполненных строк больше не осталось - значит, матрица подбора успешно заполнена; переводим ее в понятный массив, запоминаем массив в результате, спускаемся по стеку рекурсии вниз.
процесс продолжается либо до тех пор, пока не закончатся все варианты строк, либо по достижению лимита собранных решений.
В LatinSquareImpl за это отвечает следующий метод:
findingStep
private Step findingStep(Step step) {
if (step.isLast()) {
return step;
}
SelectionMatrix<Integer> currentSelectionMatrix = step.getCurrentMatrix();
Pair<Integer, List<SelectionMatrixElement<Integer>>> minRowPair = currentSelectionMatrix.getUnfilledRowAndIndexWithMinimumVariants();
Integer rowIndex = minRowPair.getKey();
List<SelectionMatrixElement<Integer>> row = minRowPair.getValue();
if (rowIndex == null) {
step.addToResult(currentSelectionMatrix);
return step;
}
Map<Integer, Set<Integer>> variantsMap = new HashMap<>();
for (int i = 0; i < row.size(); i++) {
SelectionMatrixElement<Integer> element = row.get(i);
variantsMap.put(i, element.getVariants());
}
VariantsFinder<Integer, Integer> variantsFinder = new VariantsFinder<>();
variantsFinder.findVariantsWithCallback(variantsMap, (newVariant) -> {
SelectionMatrix<Integer> copySelectionMatrix = currentSelectionMatrix.getCopy();
boolean validity = copySelectionMatrix.setRowToMatrixAndReturnValidity(rowIndex, newVariant);
if (!validity) {
return step.isLast();
}
Step newStep = step.newStep(copySelectionMatrix);
Step result = findingStep(newStep);
return result.isLast();
});
return step;
}
...
private static class Step {
private final SelectionMatrix<Integer> currentSelectionMatrix;
private final int limit;
private final List<Integer[][]> result;
public Step(SelectionMatrix<Integer> currentSelectionMatrix, int limit) {
this.currentSelectionMatrix = currentSelectionMatrix;
this.limit = limit;
this.result = new ArrayList<>();
}
private Step(SelectionMatrix<Integer> currentSelectionMatrix, int limit, List<Integer[][]> result) {
this.currentSelectionMatrix = currentSelectionMatrix;
this.limit = limit;
this.result = result;
}
public void addToResult(SelectionMatrix<Integer> selectionMatrix) {
result.add(selectionMatrix.toArray());
}
public Step newStep(SelectionMatrix<Integer> newSelectionMatrix) {
return new Step(newSelectionMatrix, limit, result);
}
public boolean isLast() {
return result.size() >= limit;
}
public SelectionMatrix<Integer> getCurrentMatrix() {
return currentSelectionMatrix;
}
public List<Integer[][]> getResult() {
return result;
}
}Собственно, именно этот метод и используют методы getFirstVariant и getVariantsWithLimit.
getFirstVariant и getVariantsWithLimit
@Override
public Integer[][] getFirstVariant(Integer[][] square) {
Set<Integer> allElements = IntStream.range(1, square.length + 1).boxed().collect(Collectors.toSet());
if (isInvalid(square, allElements)) {
throw new RuntimeException("Square is invalid");
}
SelectionMatrix<Integer> selectionMatrix = new SelectionMatrix<>(square, allElements, Integer.class);
Step step = findingStep(new Step(selectionMatrix, 1));
if (!step.isLast()) {
return null;
}
return step.getResult().getFirst();
}
@Override
public List<Integer[][]> getVariantsWithLimit(Integer[][] square, int limit) {
Set<Integer> allElements = IntStream.range(1, square.length + 1).boxed().collect(Collectors.toSet());
if (isInvalid(square, allElements)) {
throw new RuntimeException("Square is invalid");
}
SelectionMatrix<Integer> selectionMatrix = new SelectionMatrix<>(square, allElements, Integer.class);
Step resultStep = findingStep(new Step(selectionMatrix, limit));
return resultStep.getResult();
}В общем-то это и есть конец работы алгоритма. Можно подводить итог.
Результаты
Результаты алгоритма пока такие:
Он работает. Уже хорошо.
Для несложных вариантов решение находится за считанные миллисекунды.
Для незаполненного квадрата 9x9 миллион решений подбирает за 20 секунд.
Для незаполненного квадрата 9x9 10 миллионов решений подбирает за время в пределах 3-4 минут.
Для незаполненного квадрата 40x40 повисает надолго.
Тесты выглядят следующим образом.
Тесты
package com.smolka;
import com.smolka.latin.square.impl.LatinSquareImpl;
import org.junit.Test;
import java.util.HashSet;
import java.util.List;
import java.util.Set;
public class LatinSquareTest {
@Test
public void test_checkNegative() {
Integer[][] field = {
{ 1, 2, 3 },
{ 1, 3, 2 },
{ 2, 1, 3 }
};
LatinSquareImpl latinSquare = new LatinSquareImpl();
assert !latinSquare.check(field);
}
@Test
public void test_checkPositive() {
Integer[][] field = {
{ 1, 2, 3 },
{ 3, 1, 2 },
{ 2, 3, 1 }
};
LatinSquareImpl latinSquare = new LatinSquareImpl();
assert latinSquare.check(field);
}
@Test
public void test_findingMillionVariants() {
Integer[][] field = {
{ null, null, null, null, null, null, null, null, null },
{ null, null, null, null, null, null, null, null, null },
{ null, null, null, null, null, null, null, null, null },
{ null, null, null, null, null, null, null, null, null },
{ null, null, null, null, null, null, null, null, null },
{ null, null, null, null, null, null, null, null, null },
{ null, null, null, null, null, null, null, null, null },
{ null, null, null, null, null, null, null, null, null },
{ null, null, null, null, null, null, null, null, null },
};
LatinSquareImpl latinSquare = new LatinSquareImpl();
int limit = 1000000;
List<Integer[][]> result = latinSquare.getVariantsWithLimit(field, limit);
for (Integer[][] variantInResult : result) {
assert latinSquare.check(variantInResult);
}
assert result.size() == limit;
Set<Integer[][]> setForDupesCheck = new HashSet<>(result);
assert setForDupesCheck.size() == result.size();
}
@Test
public void test_findingFirstEverest() {
Integer[][] field = {
{ 8, null, null, null, null, null, null, null, null },
{ null, null, 3, 6, null, null, null, null, null },
{ null, 7, null, null, 9, null, 2, null, null },
{ null, 5, null, null, null, 7, null, null, null },
{ null, null, null, null, 4, 5, 7, null, null },
{ null, null, null, 1, null, null, null, 3, null },
{ null, null, 1, null, null, null, null, 6, 8 },
{ null, null, 8, 5, null, null, null, 1, null },
{ null, 9, null, null, null, null, 4, null, null },
};
LatinSquareImpl latinSquare = new LatinSquareImpl();
Integer[][] result = latinSquare.getFirstVariant(field);
assert result != null;
assert latinSquare.check(result);
}
@Test
public void test_findingTwoSimple() {
Integer[][] field = {
{ 1, 2, 3, 4, 5 },
{ null, 4, null, null, null },
{ null, null, null, 5, null },
{ 2, null, null, null, null },
{ 3, null, null, null, null }
};
int limit = 2;
LatinSquareImpl latinSquare = new LatinSquareImpl();
List<Integer[][]> result = latinSquare.getVariantsWithLimit(field, limit);
for (Integer[][] variantInResult : result) {
assert latinSquare.check(variantInResult);
}
assert result.size() == limit;
Set<Integer[][]> setForDupesCheck = new HashSet<>(result);
assert setForDupesCheck.size() == result.size();
}
@Test
public void test_findingFirstSimple() {
Integer[][] field = {
{ 1, 2, 3, 4, 5 },
{ null, 4, null, null, null },
{ null, null, null, 5, null },
{ 2, null, null, null, null },
{ 3, null, null, null, null }
};
LatinSquareImpl latinSquare = new LatinSquareImpl();
Integer[][] result = latinSquare.getFirstVariant(field);
assert result != null;
assert latinSquare.check(result);
}
@Test
public void test_findingFirstSimple2() {
Integer[][] field = {
{ 1, 2, 3 },
{ null, null, null },
{ null, 1, null }
};
LatinSquareImpl latinSquare = new LatinSquareImpl();
Integer[][] result = latinSquare.getFirstVariant(field);
assert result != null;
assert latinSquare.check(result);
}
}
Конечно, время наверняка зависит и от вычислительной мощности конкретной машины (а она у меня довольно неплохая), поэтому может варьироваться.
Сложность алгоритма - открытый вопрос. Понятно, что не полином, но точную оценку дать пока не пытался.
Какую ключевую проблему я вижу: в какой-то момент при подборе даже варианта одной строки алгоритм зарывается в бесперспективное пространство, эдакую "пустыню", из которой выходить придется довольно долго. Это очень ярко проявляет себя на пустом квадрате 40-го порядка, когда после подбора 8-10 строк алгоритм в VariantsFinder начинает очень долго искать вариант следующей строки.
Для выявления таких ситуаций даже был сделан специальный кусок кода в VariantsFinder.findCartesianProductWithoutDupesWithCallback
Set<V> addedValuesSet = new HashSet<>(current.values());
for (int i = index + 1; i < content.size(); i++) {
if (addedValuesSet.containsAll(content.get(i).getValue())) {
return false;
}
}Если получится хотя бы гулять в поисках варианта строки таким образом, чтобы никогда в это место не заходило - это уже будет весьма неплохо.
Каким образом при подборе строки смотреть далеко наперед и предыугадывать такие ситуации, при том задешево и не зарываясь в похожие по сложности процессы - пока не знаю. Были мысли "танцевать" от выявленных в матрице комбинаций с частотой, равной размерности. При первом же их появлении смотреть, что следует из них всех, и если из этого "следствия" мы не можем в дальнейшем заполнить квадрат - то откидываем подобранную строку, как невалидную. Но идея пока неясная и перспективы туманные.
В целом получается как-то так. Делитесь впечатлениями и опытом (если был похожий), критикуйте и прочее-прочее) Код, как я и говорил, можно посмотреть здесь.
Всем добра и всем дзякую!
andy_p
Поскольку латинский квадрат NP-полная задача, то и решать ее надо соответствующими методами, в данном случае с помощью SAT солвера.
igorsmolkako Автор
Да, в моем тоже может быть в каком-то виде утилизированно.
igorsmolkako Автор
Если я правильно помню любую NP можно свести к SAT.
wataru
Не обязательно. Конкретная задача позволяет использовать всякие особеннсти и получать более быстрое решение.