Введение
Как известно, нахождение оптимального алгоритма решения любой NP-полной задачи — это цель амбициозная, пахнущая славой и неплохими деньгами. Как раз к таким задачам относится Судоку, и как раз своим решением этой головоломки я горел последний месяц. На данный момент сделана (по ощущениям) лишь половина дела, и хоть результаты и вышли интересными (по крайней мере для меня-любимого) — дело еще далеко до завершения, т.к. в определенном моменте настал «творческий тупик». Впрочем, надеюсь, что он пройдет и на свет появится по крайней мере какое-то новое любопытное решение. Пока что лишь поделюсь своими первыми наработками в этом направлении. Пока что они не вполне вылизаны + написаны на Java, перевод на какой-нибудь более простой для восприятия язык планируется лишь с окончательной победой на Java. Потому если не перевариваете Java и всякие там стримы — лучше не стоит.
Пишу статью в том числе и для себя, чтобы подвести предварительные итоги этой кампании и подумать о дальнейших шагах. Ну, может, кому-то тоже будет интересно.
Шаг 0. С чего начинаем
Начать следует с общей сути алгоритма. Это не совсем обычный перебор вслепую или в полу-слепую. По результатам работы готовой части алгоритма мы получаем такие «кусочки» этой головоломки, которые по отдельности гарантированно не нарушают правила поля, и нашей задачей лишь остается выбрать правильные кусочки и собрать из них правильный паззл.
Начинается все с подбора «опорных» точек для анализа.
Нам не нужно подбирать варианты исходя из каждой точки поля — достаточно будет выявить ограниченный набор точек и найти все не нарушающие правила поля варианты исходя из них. Варианты в данном случае — это заполнение других точек относительно опорной, которые входят в ту же строку, тот же столбец и тот же квадрат (образуют сегмент в моей терминологии).
При идеальном распределении каждая «опорная точка» — это новый квадрат и новая строка/столбец. Идеальный случай выглядит как-то так.
При поле:
опорными точками будут позиции 0.0, 1.3, 2.1, 3.2 (счет с нуля).
Понятно, что так получится не всегда, но в любом случае таким образом мы стремимся к минимизации опорных точек, а значит и минимизации дальнейших сравнений — и это при полном покрытии нашего поля.
О том, как выглядит подбор этих опорных точек в коде — немного ниже; технически подбор опорных точек — это не первый шаг, хотя логически он напрашивается первым.
Шаг 1. Обозначаем основные классы и формируем мапу потенциалов.
Определимся, какие сущности в форме классов нам пригодятся в дальнейшем.
Position — позиция в поле. Ничего интересного, row да column — индексы с нуля.
PositionPotential — название тоже говорит само за себя, потенциал позиции. Важная мета-информация, получаемая на первом этапе анализа исходного поля. Включает в себя possibleNumbers — возможные значения в этой позиции исходя из того, как заполнены связанные строка/столбец/квадрат (из примера выше для 0.0 это будет 2,3,4 — 1 исключаем, т.к. она уже находится внизу по строке 0); squareIndex — индекс квадрата поля (для 2.1, скажем, этот индекс будет 2); segmentInfo — информация о сегменте данной позиции, самые важные данные здесь — это segmentPositions (для 2.1, например, это будут 0.1, 1.1, 2.0, 2.2, 2.3, 3.1, т.е. свободные точки, связанные с этой по сегменту).
Cell — позиция в ассоциации с числом. position, number — атрибуты. Если number пустое — поле не заполнено.
Sudoku и имплементация SudokuImpl — класс, отвечающий за поиск решения. В нем и будет происходить вся основная логика. Получает на вход n — размерность квадратов и матрицу field — наше игровое поле.
В коде все это выглядеть будет так.
Структуры
Position
public record Position( int row, int column ) { // опустим детали... }SegmentInfo
import java.util.HashSet; import java.util.Objects; import java.util.Set; public record SegmentInfo(Position startingPoint, Set<Integer> possibleNumbers, Set<Position> segmentPositions) { // опустим детали... }PositionPotential
import java.util.HashSet; import java.util.Set; public class PositionPotential { private final Set<Integer> possibleNumbers; private SegmentInfo segmentInfo; private int squareIndex; public PositionPotential(int possibleNumber) { Set<Integer> setWithSingleNumber = new HashSet<>(); setWithSingleNumber.add(possibleNumber); this.possibleNumbers = setWithSingleNumber; } public PositionPotential(Set<Integer> possibleNumbers, int squareIndex) { this.possibleNumbers = possibleNumbers; this.squareIndex = squareIndex; } public PositionPotential(Set<Integer> possibleNumbers, SegmentInfo segmentInfo, int squareIndex) { this.possibleNumbers = possibleNumbers; this.segmentInfo = segmentInfo; this.squareIndex = squareIndex; } // опустим прочие детали... }Cell
public record Cell( Position position, Integer number ) { public boolean isEmpty() { return number == null; } // опустим прочие детали... }Интерфейс центрального класса
public interface Sudoku { int[][] getVariant(); boolean checkVariant(int[][] variant); }С основными сущностями определились. Теперь давайте получим из нашей матрицы field все ячейки — пустые и заполненные — и по ним сформируем мапу из свободных позиций и потенциалов. Подробно останавливаться на этом процессе вряд ли есть смысл, он не сложный и второстепенный — можно будет посмотреть в полном коде. Главное, что на выходе мы получаем вот такую вот информацию.
Set<Cell> cells = getCells(this.field); Map<Position, PositionPotential> positionPotentialMap = createNewPotentialMapForCells(cells);Теперь, исходя из нее, можно получить и «опорные» точки для анализа.
Алгоритм выглядит вот так.
Возможно, кривовато, но вроде работает
private Set<Position> getPositionsForAnalyze(Map<Position, PositionPotential> positionPotentialMap) { Set<Position> result = new HashSet<>(); // получаем все свободные строки Set<Integer> rowsToFeel = positionPotentialMap.keySet().stream().map(Position::row).collect(Collectors.toSet()); // т.к. мы будем проводить манипуляции с мапой, которые не должны отразиться на изначальном объекте - получаем ее копию Map<Position, PositionPotential> positionPositionPotentialCopy = copyOfPotentialMap(positionPotentialMap); for (int row : rowsToFeel) { // получаем первую позицию с данной строкой; если таковых нет - доудалялись. придется восстанавливать мапу, откинув только уже выбранные опорные точки. Position firstPositionWithRow = positionPositionPotentialCopy.keySet().stream().filter(p -> p.row() == row).findFirst().orElse(null); if (firstPositionWithRow == null) { positionPositionPotentialCopy = copyOfPotentialMap(positionPotentialMap); for (Position position : result) { positionPositionPotentialCopy.remove(position); } firstPositionWithRow = positionPositionPotentialCopy.keySet().stream().filter(p -> p.row() == row).findFirst().orElseThrow(); } // добавляем в результат первую позицию по строке result.add(firstPositionWithRow); Set<Position> positionsToDelete = new HashSet<>(); positionsToDelete.add(firstPositionWithRow); int squareOfPosition = positionPositionPotentialCopy.get(firstPositionWithRow).getSquareIndex(); // все связанные по квадрату, столбцу или строке позиции убираем из рассмотрения - пока не расставим все точки либо пока не останется места для распределения на следующие строки Position finalFirstPositionWithRow = firstPositionWithRow; Set<Position> connectedPositions = positionPositionPotentialCopy.entrySet().stream().filter(es -> { Position position = es.getKey(); PositionPotential positionPotential = es.getValue(); return position.row() == finalFirstPositionWithRow.row() || position.column() == finalFirstPositionWithRow.column() || positionPotential.getSquareIndex() == squareOfPosition; }).map(Map.Entry::getKey).collect(Collectors.toSet()); // удаляем positionsToDelete.addAll(connectedPositions); for (Position positionToDelete : positionsToDelete) { positionPositionPotentialCopy.remove(positionToDelete); } } return result; }Set<Position> positionsToAnalyze = getPositionsForAnalyze(positionPotentialMap);Итак, «опорные точки» у нас есть. Дальше можно приступать к валидации и анализу возможных вариантов по каждой точке.
Шаг 2. Валидация, подбор вариантов
Определимся с необходимыми структурами здесь.
PossibleNumbersValidationResult — результат валидации всех возможных чисел в опорной точке. Содержит информацию, по какой позиции результат; валидно/не валидно (если невалидно — то решения в целом не существует, ибо как минимум одну ячейку мы заполнить уже не можем); результаты валидации с подобранными вариантами — для каждой возможной цифери.
PossibleNumberValidationResult — результат валидации конкретного числа в опорной точке. Опять же, для какой позиции результат; по какой цифери; валидно/не валидно (если не валидно — ветки с этим числом в опорной точке в принципе не имеет смысла подбирать). И коллекция из SegmentValidBatch, о нем ниже.
CellsVariant — вариант заполнения какого-то фрагмента поля (строки, столбца, квадрата). По сути просто коллекция заполненных Cell, связанная с типом ROW, COLUMN или SQUARE.
SegmentValidBatch — вариант, как заполнить сегмент (включая опорную точку). Имеет три CellsVariant — строка, столбец, квадрат.
Как выглядит в коде.
Собсна, вот
PossibleNumbersValidationResult
public record PossibleNumbersValidationResult( Position forPosition, boolean isValid, Map<Integer, PossibleNumberValidationResult> validationResultByNumber ) { //... опустим детали }PossibleNumberValidationResult
public record PossibleNumberValidationResult( Position forPosition, int number, boolean isValid, List<SegmentValidBatch> segmentValidBatches ) { //... опустим детали }CellsVariant
public class CellsVariant { private final Set<Cell> cells; private UUID batchUUID; private final UUID uuid; private final SubSegmentType type; // опустим детали... }Итак, мы берем некую опорную точку и идем ее валидировать. Результаты мы собираем в лист. То, что мы получим — это на данный момент и есть тот максимум, что пока можно извлечь из алгоритма (как все это соотносить — отдельный вопрос, пока актуальный).
List<PossibleNumbersValidationResult> possibleNumbersValidationResults = new ArrayList<>(); for (Position position : positionsToAnalyze) { PossibleNumbersValidationResult possibleNumbersValidationResult = possibleNumbersValidation(position, positionPotentialMap); possibleNumbersValidationResults.add(possibleNumbersValidationResult); }Метод possibleNumbersValidation
possibleNumbersValidation
private PossibleNumbersValidationResult possibleNumbersValidation(Position position, Map<Position, PositionPotential> positionPotentialMap) { PositionPotential potential = positionPotentialMap.get(position); Set<Integer> possibleNumbers = potential.getPossibleNumbers(); // получаем сегмент нашей позиции Map<Position, PositionPotential> positionSegment = getSegment(position, positionPotentialMap); // получаем позиции, сгруппированные по строке опорной позиции - т.е. по сути столбец сегмента Map<Position, PositionPotential> positionsByRow = positionSegment.entrySet().stream().filter(p -> Objects.equals(p.getKey().row(), position.row())).collect(Collectors.toMap(Map.Entry::getKey, Map.Entry::getValue)); // получаем позиции, сгруппированные по столбцу опорной позиции - т.е. по сути строку сегмента Map<Position, PositionPotential> positionsByColumn = positionSegment.entrySet().stream().filter(p -> Objects.equals(p.getKey().column(), position.column())).collect(Collectors.toMap(Map.Entry::getKey, Map.Entry::getValue)); // получаем позиции, сгруппированные по квадрату опорной позиции - из них потом мы уберем те позиции, которые пересекаются со строкой и столбцом Map<Position, PositionPotential> positionsBySquare = positionSegment.entrySet().stream().filter(p -> p.getValue().getSquareIndex() == potential.getSquareIndex()).collect(Collectors.toMap(Map.Entry::getKey, Map.Entry::getValue)); boolean isValid = false; Map<Integer, PossibleNumberValidationResult> possibleNumberValidationResultMap = new HashMap<>(); // пробегаемся for (int possibleNumber : possibleNumbers) { PossibleNumberValidationResult possibleNumberValidationResult = possibleNumberValidation(position, possibleNumber, positionsByRow, positionsByColumn, positionsBySquare); possibleNumberValidationResultMap.put(possibleNumber, possibleNumberValidationResult); // если хотя бы одна возможная цифра валидна - в целом результат валиден if (possibleNumberValidationResult.isValid()) { isValid = true; } } return new PossibleNumbersValidationResult(position, isValid, possibleNumberValidationResultMap); }Метод possibleNumberValidation выглядит немного страшновато и о нем чуть ниже. Пока остановлюсь на том, что внутри него используется метод validateSubSegmentAfterDeletion — он призван валидировать мапу-подсегмент (строка, столбец, квадрат), из которого мы удалили рассматриваемое число.
Этот метод — так сказать, самая мякотка, выполняет работу по валидации и возвращает нам все возможные валидные варианты заполнения, когда в опорной точке стоит рассматриваемое число.
Начнем с него и продолжим идти вглубь.
Работает валидация в два этапа:
-
смотрит на встречаемость той или иной комбинации в подсегменте. Если ее частота превышает ее размерность — мы не сможем заполнить подсегмент. Невалидно.
-
смотрим на комбинации из одной цифры. Если таковые есть — запоминаем их, как обязательные варианты для заполнения той или иной позиции. Вычеркиваем число из других позиций. Делаем это циклично, пока ситуация «есть позиции с единственным вариантом в подсегменте» сохраняется, т.к. может быть «цепная реакция». Если что-то по итогу оказалось пустым — подсегмент на рассматриваемом числе в опорной позиции невалиден.
А затем мы уже строим возможные варианты для остальных позиций, с учетом единственно-возможных вариантов.
Как выглядит код.
С комментариями
private SubSegmentFillingResult validateSubSegmentAfterDeletion(Map<Position, PositionPotential> subSegment, Position forPosition, int number, SubSegmentType subSegmentType) { // результат с возможными заполнениями подсегмента. инициализируем его переданным типом. SubSegmentFillingResult result = new SubSegmentFillingResult(subSegmentType); // если подсегмент изначально пуст и в анализе, получается, не нуждается - просто вернем true if (subSegment.isEmpty()) { result.setValid(true); return result; } // заводим коллекцию, в которой будут складываться ячейки с единственно возможным заполнением Set<Cell> mandatoryCells = new HashSet<>(); // мапа, в которой будет вестись статистика: сколько раз та или иная комбинация встречается на протяжении подсегмента. пригодится. Map<Set<Integer>, Integer> combinationCount = new HashMap<>(); // мапа, в которой мы держим позиции, соотнесенные с единственно возможным вариантом заполнения. пригодится для формирования mandatoryCells. Map<Position, Integer> singleElementsMap = new HashMap<>(); Map<Position, PositionPotential> copyOfSegment = copyOfPotentialMap(subSegment); for (Map.Entry<Position, PositionPotential> segmentEntry : copyOfSegment.entrySet()) { Position position = segmentEntry.getKey(); PositionPotential positionPotential = segmentEntry.getValue(); // ведем статистику встречаемости Set<Integer> possibleNumbers = positionPotential.getPossibleNumbers(); combinationCount.putIfAbsent(possibleNumbers, 0); combinationCount.put(possibleNumbers, combinationCount.get(possibleNumbers) + 1); // если возможно только одно число - заполняем мапу singleElementsMap if (possibleNumbers.size() == 1) { singleElementsMap.put(position, possibleNumbers.stream().findFirst().orElseThrow()); } } // если встречается хоть одна комбинация, частота которой превышает ее размерность - это значит, что заполнить подсегмент мы уже не можем. вердикт - невалидно. for (Map.Entry<Set<Integer>, Integer> combinationCountEntry : combinationCount.entrySet()) { Set<Integer> combination = combinationCountEntry.getKey(); Integer count = combinationCountEntry.getValue(); if (count > combination.size()) { result.setValid(false); return result; } } do { // здесь мы делаем манипуляции с мапой singleElementsMap, т.е. с позициями, которые имеют только один вариант для заполнения. // формируем по ним mandatoryCells, а так же убираем "заполненные" этим числом позиции из анализа + убираем из остальных позиций это число, как возможное // т.к. операция может вызвать "цепную реакцию" - делаем это все в цикле. Set<Integer> singleElementsSet = new HashSet<>(singleElementsMap.values()); for (Map.Entry<Position, Integer> singeElementEntry : singleElementsMap.entrySet()) { Position position = singeElementEntry.getKey(); Integer mandatoryNumber = singeElementEntry.getValue(); mandatoryCells.add(new Cell(position, mandatoryNumber)); copyOfSegment.remove(position); } if (copyOfSegment.isEmpty()) { break; } for (PositionPotential potential : copyOfSegment.values()) { potential.removePossibleNumbers(singleElementsSet); if (potential.getPossibleNumbers().isEmpty()) { // если по итогу манипуляции мы не можем заполнить какую-то позицию - то это тоже нездоровая ситуация. вердикт - невалидно. result.setValid(false); return result; } } singleElementsMap = copyOfSegment.entrySet() .stream() .filter(e -> e.getValue().getPossibleNumbers().size() == 1) .collect(Collectors.toMap(Map.Entry::getKey, v -> v.getValue().getPossibleNumbers().stream().findFirst().orElseThrow())); } while (!singleElementsMap.isEmpty()); // проваливаемся в метод, строящий возможные варианты заполнения с опорной точкой и валидируемым числом, учитывая mandatoryCells NumberSequenceVariant<Position> numberSequenceVariants = getMainVariantForSubSegment(copyOfSegment, mandatoryCells, forPosition, number); result.setNumberSequenceVariant(numberSequenceVariants); if (numberSequenceVariants.isEnd()) { result.setValid(false); return result; } result.setValid(true); return result; }Теперь — к методам getMainVariantForSubSegment, getVariantOnRootNumberForSubSegment и франкенштейну NumberSequenceVariant.
Метод getMainVariantForSubSegment ничего особо интересного не представляет — это просто предбанник для второго метода, который снова обогатит нам подсегмент mandatoryCells (примечание: я не до конца понимаю, зачем сделал такую свистопляску с перегонкой в Cell в предыдущем методе и обратно в Map здесь, но по крайней мере сигнатура метода выглядит как-то понаглядней, что ли…); возьмет первую позицию из подсегмента и создаст по ее возможным циферям «корневой» NumberSequenceVariant, и будет раскручивать дальнеший поиск вариантов посредством вызова второго метода.
С комментариями
private NumberSequenceVariant<Position> getMainVariantForSubSegment(Map<Position, PositionPotential> subSegment, Set<Cell> mandatoryCells, Position forPosition, int number) { // инициализация "корня" NumberSequenceVariant<Position> numberSequenceVariant = new NumberSequenceVariant<>(number, forPosition); List<NumberSequenceVariant<Position>> resultsByPossibleNumbersInFirstPositionInSubSegment = new ArrayList<>(); Map<Position, PositionPotential> subSegmentCopy = copyOfPotentialMap(subSegment); // возвращаем mandatoryCell на свои места for (Cell mandatoryCell : mandatoryCells) { subSegmentCopy.put(mandatoryCell.position(), new PositionPotential(mandatoryCell.number())); } Position firstPosition = subSegmentCopy.keySet().stream().findFirst().orElseThrow(); Set<Integer> possibleNumbersForFirstPosition = subSegmentCopy.values().stream().findFirst().map(PositionPotential::getPossibleNumbers).orElseThrow(); // если подсегмент только из одной позиции - просто добавляем в последовательность возможные цифры из первой позиции, и уходим; дальнейшие действия ни к чему. if (subSegmentCopy.size() == 1) { for (int possibleNumber : possibleNumbersForFirstPosition) { resultsByPossibleNumbersInFirstPositionInSubSegment.add(new NumberSequenceVariant<>(possibleNumber, firstPosition)); } numberSequenceVariant.justAddNewVariantsToBranches(resultsByPossibleNumbersInFirstPositionInSubSegment); return numberSequenceVariant; } // оно нам ни к чему в дальнейшем разборе... subSegmentCopy.remove(firstPosition); // пробегаемся по возможным цифрам для первой позиции, по каждой получаем варианты for (int possibleNumber : possibleNumbersForFirstPosition) { NumberSequenceVariant<Position> variant = getVariantOnRootNumberForSubSegment(possibleNumber, firstPosition, subSegmentCopy); // если метод вернул null - значит, путной цепочки собрать не вышло. увы. null-ы нам не нужны. if (variant != null) { resultsByPossibleNumbersInFirstPositionInSubSegment.add(variant); } } // добавляем результаты по цифрам для первой позиции в корень и возвращаем его numberSequenceVariant.justAddNewVariantsToBranches(resultsByPossibleNumbersInFirstPositionInSubSegment); return numberSequenceVariant; }Перед тем, как двигаться дальше к getVariantOnRootNumberForSubSegment — немного остановимся на франкенштейнах.
Первый из них — NumberSequenceVariant. Что‑то вроде дерева, только стремное, как из фильма «Сонная лощина». Суть его в том, что каждый «узел» ассоциирован с определенной позицией — это раз; последовательность «вниз» из чисел и позиций образует ветку — это два; в каждой ветке число не может повторяться — это три; есть функциональность для удаления веток ниже определенной размерности — это нам пригодится и это четыре; есть возможность из веток получить внятные коллекции элементов — это пять. Решение словно бы немного попахивает, но работает и, возможно, работает правильно. Порефакторить бы, но трогать уже даже немного боязно 🙂
А вот и оно, родимое, полный код этого костыльного ужаса
public class NumberSequenceVariant<KEY> { private final int number; private final KEY key; private final List<NumberSequenceVariant<KEY>> branches = new ArrayList<>(); public NumberSequenceVariant(int number, KEY key) { this.number = number; this.key = key; } public boolean isEnd() { return branches.isEmpty(); } public void justAddNewVariantsToBranches(List<NumberSequenceVariant<KEY>> newVariants) { branches.addAll(newVariants); } public void justAddWithIgnoringSame(int number, KEY key) { if (number == this.number) { return; } branches.add(new NumberSequenceVariant<>(number, key)); } public boolean addVariantToEndOfPathWithIgnoringSame(int number, KEY keyOfVariant, Set<KEY> passedPath) { if (number == this.number) { return false; } Set<KEY> pathWithoutCurrentPosition = new HashSet<>(passedPath); boolean wasDeletedInPath = pathWithoutCurrentPosition.remove(key); if (!wasDeletedInPath) { return false; } if (pathWithoutCurrentPosition.isEmpty()) { branches.add(new NumberSequenceVariant<>(number, keyOfVariant)); return true; } boolean wasAdding = false; for (NumberSequenceVariant<KEY> child : branches) { if (child.addVariantToEndOfPathWithIgnoringSame(number, keyOfVariant, pathWithoutCurrentPosition)) { wasAdding = true; } } return wasAdding; } /** * Удаление всех веток, размер которых не соответствует. */ public void removeAllBranchesWithSizeLessThan(int size) { if (size == 1 || isEnd()) { return; } Set<NumberSequenceVariant<KEY>> toDelete = new HashSet<>(); for (NumberSequenceVariant<KEY> branch : branches) { int counter = 1; boolean result = branch.removeRecursion(size, counter); if (!result) { toDelete.add(branch); } } branches.removeAll(toDelete); } public Set<Set<Pair<KEY, Integer>>> getKeyValuePairs() { Set<Set<Pair<KEY, Integer>>> result = new HashSet<>(); Pair<KEY, Integer> currentCell = Pair.of(key, number); for (NumberSequenceVariant<KEY> branch : branches) { if (branch.isEnd()) { Set<Pair<KEY, Integer>> singleSet = new HashSet<>(); singleSet.add(Pair.of(branch.key, branch.number)); singleSet.add(currentCell); result.add(singleSet); continue; } Set<Set<Pair<KEY, Integer>>> resultsFromBranch = branch.getKeyValuePairs(); for (Set<Pair<KEY, Integer>> resultFromBranch : resultsFromBranch) { Set<Pair<KEY, Integer>> appendedWithCurrentCell = new HashSet<>(resultFromBranch); appendedWithCurrentCell.add(currentCell); result.add(appendedWithCurrentCell); } } if (result.isEmpty()) { Set<Pair<KEY, Integer>> singleSet = new HashSet<>(); singleSet.add(Pair.of(key, number)); result.add(singleSet); } return result; } private boolean removeRecursion(int size, int counter) { counter++; if (isEnd()) { return counter >= size; } boolean result = false; Set<NumberSequenceVariant<KEY>> toDelete = new HashSet<>(); for (NumberSequenceVariant<KEY> branch : branches) { result = branch.removeRecursion(size, counter); if (!result) { toDelete.add(branch); } } branches.removeAll(toDelete); return !isEnd(); } @Override public boolean equals(Object o) { if (o == null || getClass() != o.getClass()) return false; NumberSequenceVariant<KEY> that = (NumberSequenceVariant) o; return number == that.number && Objects.equals(key, that.key); } @Override public int hashCode() { return Objects.hash(number, key); } }Второе — это VariantSelectionElementChain.
Для чего он нужен?
Алгоритм подбора вариантов заполнения сводится к такому:
убираем из всех позиций «корневое» число (т.е. число из первой позиции, с которым мы определились в предыдущем методе). Допустим, у нас вышло как-то так:
позиция x1.y1: {2, 3}
позиция x2.y2: {1}
позиция x3.y3: {4}
позиция x4.y4: {3, 4}
Сортируем по размерности, x2.y2 и x3.y3 у нас выносятся на самый верх.
Элементы внутри тоже на всякий случай сортируем (правда, я уже забыл, в чем была моя задумка, виноват :)).
Берем первый элемент из этой цепочки. Добавляем его возможные цифры в результирующий NumberSequenceVariant, можно без каких-либо проверок и условий, просто записываем в конец.
Далее начинаем проходить циклом по другим вариантам.
Идем попарно, берем левое и правое; если правое состоит из одного элемента — пытаемся добавить в дерево, и если попытка была неудачной — сразу бросаем это дело, т.к. тут уже явный тупик (каким-то образом прокрались два одинаковых единственно-возможных варианта); если же нет — пробегаемся по каждой цифре из правого. Если левое включает в себя цифру из правого и левое состоит из 1 элемента — мы сразу отбрасываем такой вариант; если нет — пытаемся добавить число в дерево; если была хотя бы одна успешная попытка добавления — то продолжаем процесс; если не было ни одной — то это тупик.
Ну и да, по тому, по какой ветви распределять цифры — будет отвечать переменная passedPath, коллекция позиций (я на всякий случай поясню: passedPath — «пройденный путь» xD). Та самая, что принимается в качестве аргумента в addVariantToEndOfPathWithIgnoringSame. Мы дополняем ее пройденной позицией в конце добавления либо единственно возможного варианта, либо любого из не-единственных. Да, тут получается некоторый рассинхрон между ветками, которые постоянно дополняются и ветками, в которых ничего не залилось… но последние ветки-неудачники нам и не нужны, мы их все равно потом «обрезаем».
Собственно, VariantSelectionElementChain нужен лишь для организации этой цепочки.
Код VariantSelectionElementChain.
Тута
public class VariantSelectionElementChain implements Comparable<VariantSelectionElementChain> { private final Position position; private final List<Integer> sortedPossibleNumbers; public VariantSelectionElementChain(Position position, PositionPotential positionPotential, int excludeNumber) { this.position = position; PositionPotential potentialCopy = positionPotential.safeCopy(); this.sortedPossibleNumbers = potentialCopy.getPossibleNumbers().stream().filter(n -> n != excludeNumber).sorted().toList(); } @Override public int compareTo(VariantSelectionElementChain o) { int first = sortedPossibleNumbers.size(); int second = o.sortedPossibleNumbers.size(); return Integer.compare(first, second); } public Position getPosition() { return position; } public List<Integer> getSortedPossibleNumbers() { return sortedPossibleNumbers; } }И код самого метода.
Еще один страх божий, на этот раз без комментариев — описание алгоритма вроде и так понятное
private NumberSequenceVariant<Position> getVariantOnRootNumberForSubSegment(int number, Position position, Map<Position, PositionPotential> subSegment) { Set<Position> passedPath = new HashSet<>(); NumberSequenceVariant<Position> result = new NumberSequenceVariant<>(number, position); passedPath.add(position); List<VariantSelectionElementChain> variantSelectionChain = subSegment.entrySet() .stream() .map(es -> new VariantSelectionElementChain(es.getKey(), es.getValue(), number)) .sorted() .toList(); VariantSelectionElementChain firstElement = variantSelectionChain.stream().findFirst().orElseThrow(); for (int possibleNumberInFirstElement : firstElement.getSortedPossibleNumbers()) { result.justAddWithIgnoringSame(possibleNumberInFirstElement, firstElement.getPosition()); } if (result.isEnd()) { return null; } if (variantSelectionChain.size() == 1) { return result; } passedPath.add(firstElement.getPosition()); for (int i = 0; i < variantSelectionChain.size() - 1; i++) { VariantSelectionElementChain leftElement = variantSelectionChain.get(i); VariantSelectionElementChain rightElement = variantSelectionChain.get(i + 1); Position rightElementPosition = rightElement.getPosition(); List<Integer> numbersForLeft = leftElement.getSortedPossibleNumbers(); List<Integer> numbersForRight = rightElement.getSortedPossibleNumbers(); boolean wasAdding = false; if (numbersForRight.size() == 1) { wasAdding = result.addVariantToEndOfPathWithIgnoringSame(numbersForRight.stream().findFirst().orElseThrow(), rightElementPosition, passedPath); if (!wasAdding) { break; } passedPath.add(rightElementPosition); continue; } for (int numberInRight : numbersForRight) { if ((numbersForLeft.contains(numberInRight) && numbersForLeft.size() == 1)) { continue; } if (result.addVariantToEndOfPathWithIgnoringSame(numberInRight, rightElementPosition, passedPath)) { wasAdding = true; } } if (!wasAdding) { break; } passedPath.add(rightElementPosition); } result.removeAllBranchesWithSizeLessThan(subSegment.size() + 1); if (result.isEnd()) { return null; } return result; }После всей этой истории на выходе мы получаем SubSegmentFillingResult, который держит информацию о том, валиден/невалиден ли подсегмент (будет невалидным и в случае отсутствия вариантов); заполненный экземпляр NumberSequenceVariant и тип подсегмента.
Шаг 3. Дальнейший подбор вариантов
Таким образом мы получаем провалидированные подсегменты. Теперь возвращаемся к методу possibleNumberValidation. Как я и говорил, код у него страшноватый и связанный с тем, как мы в итоге соотносим подсегменты друг с другом, группируя их в валидные «батчи».
А вот и он
private PossibleNumberValidationResult possibleNumberValidation(Position forPosition, int number, Map<Position, PositionPotential> positionsByRow, Map<Position, PositionPotential> positionsByColumn, Map<Position, PositionPotential> positionsBySquare) { Map<Position, PositionPotential> positionsByRowCopyWithoutNumber = copyOfPotentialMap(positionsByRow).entrySet().stream().peek(e -> e.getValue().removePossibleNumber(number)).collect(Collectors.toMap(Map.Entry::getKey, Map.Entry::getValue)); Map<Position, PositionPotential> positionsByColumnCopyWithoutNumber = copyOfPotentialMap(positionsByColumn).entrySet().stream().peek(e -> e.getValue().removePossibleNumber(number)).collect(Collectors.toMap(Map.Entry::getKey, Map.Entry::getValue)); Map<Position, PositionPotential> positionsBySquareCopyWithoutNumber = copyOfPotentialMap(positionsBySquare).entrySet().stream().peek(e -> e.getValue().removePossibleNumber(number)).collect(Collectors.toMap(Map.Entry::getKey, Map.Entry::getValue)); Set<Position> positionsIntersectionsWithSquare = new HashSet<>(); for (Position positionInRow : positionsByRowCopyWithoutNumber.keySet()) { if (positionsBySquareCopyWithoutNumber.remove(positionInRow) != null) { positionsIntersectionsWithSquare.add(positionInRow); } } for (Position positionInColumn : positionsByColumnCopyWithoutNumber.keySet()) { if (positionsBySquareCopyWithoutNumber.remove(positionInColumn) != null) { positionsIntersectionsWithSquare.add(positionInColumn); } } SubSegmentFillingResult columnSubSegmentFillingResult = new SubSegmentFillingResult(SubSegmentType.COLUMN); columnSubSegmentFillingResult.setValid(true); if (!positionsByRowCopyWithoutNumber.isEmpty()) { columnSubSegmentFillingResult = validateSubSegmentAfterDeletion(positionsByRowCopyWithoutNumber, forPosition, number, SubSegmentType.COLUMN); } if (!columnSubSegmentFillingResult.isValid()) { return new PossibleNumberValidationResult(forPosition, number, false, null); } SubSegmentFillingResult rowSubSegmentFillingResult = new SubSegmentFillingResult(SubSegmentType.ROW); rowSubSegmentFillingResult.setValid(true); if (!positionsByColumnCopyWithoutNumber.isEmpty()) { rowSubSegmentFillingResult = validateSubSegmentAfterDeletion(positionsByColumnCopyWithoutNumber, forPosition, number, SubSegmentType.ROW); } if (!rowSubSegmentFillingResult.isValid()) { return new PossibleNumberValidationResult(forPosition, number, false, null); } SubSegmentFillingResult squareSubSegmentFillingResult = new SubSegmentFillingResult(SubSegmentType.SQUARE); squareSubSegmentFillingResult.setValid(true); if (!positionsBySquareCopyWithoutNumber.isEmpty()) { squareSubSegmentFillingResult = validateSubSegmentAfterDeletion(positionsBySquareCopyWithoutNumber, forPosition, number, SubSegmentType.SQUARE); } if (!squareSubSegmentFillingResult.isValid()) { return new PossibleNumberValidationResult(forPosition, number, false, null); } if (squareSubSegmentFillingResult.variantsAreEmpty() || columnSubSegmentFillingResult.variantsAreEmpty() || rowSubSegmentFillingResult.variantsAreEmpty()) { if (squareSubSegmentFillingResult.variantsAreEmpty() && columnSubSegmentFillingResult.variantsAreEmpty() && rowSubSegmentFillingResult.variantsAreEmpty()) { return new PossibleNumberValidationResult(forPosition, number, true, null); } if (squareSubSegmentFillingResult.variantsAreEmpty()) { if (!rowSubSegmentFillingResult.variantsAreEmpty() && !columnSubSegmentFillingResult.variantsAreEmpty()) { List<SegmentValidBatch> validBatches = getValidBatchesForColumnAndRow(columnSubSegmentFillingResult, rowSubSegmentFillingResult, positionsIntersectionsWithSquare); if (validBatches.isEmpty()) { return new PossibleNumberValidationResult(forPosition, number, false, null); } return new PossibleNumberValidationResult(forPosition, number, true, validBatches); } if (!rowSubSegmentFillingResult.variantsAreEmpty()) { List<SegmentValidBatch> validBatches = getValidBatchesForColumnOrRow(columnSubSegmentFillingResult); if (validBatches.isEmpty()) { return new PossibleNumberValidationResult(forPosition, number, false, null); } return new PossibleNumberValidationResult(forPosition, number, true, validBatches); } List<SegmentValidBatch> validBatches = getValidBatchesForColumnOrRow(columnSubSegmentFillingResult); if (validBatches.isEmpty()) { return new PossibleNumberValidationResult(forPosition, number, false, null); } return new PossibleNumberValidationResult(forPosition, number, true, validBatches); } if (!rowSubSegmentFillingResult.variantsAreEmpty()) { List<SegmentValidBatch> validBatches = getValidBatchesForColumnOrRowAndSquare(columnSubSegmentFillingResult, squareSubSegmentFillingResult, positionsIntersectionsWithSquare); if (validBatches.isEmpty()) { return new PossibleNumberValidationResult(forPosition, number, false, null); } return new PossibleNumberValidationResult(forPosition, number, true, validBatches); } List<SegmentValidBatch> validBatches = getValidBatchesForColumnOrRowAndSquare(columnSubSegmentFillingResult, squareSubSegmentFillingResult, positionsIntersectionsWithSquare); if (validBatches.isEmpty()) { return new PossibleNumberValidationResult(forPosition, number, false, null); } return new PossibleNumberValidationResult(forPosition, number, true, validBatches); } List<SegmentValidBatch> validBatches = getValidBatchesForColumnRowAndSquare(columnSubSegmentFillingResult, rowSubSegmentFillingResult, squareSubSegmentFillingResult, positionsIntersectionsWithSquare); if (validBatches.isEmpty()) { return new PossibleNumberValidationResult(forPosition, number, false, null); } return new PossibleNumberValidationResult(forPosition, number, true, validBatches); }Для начала — о positionsIntersectionsWithSquare. Ни для кого не секрет, что квадрат отчасти имеет пересечения со строкой и столбцом у сегмента. Нам ни к чему проверять эти пересечения в рамках проверки квадрата и строить варианты с ними — зачем, когда это будет происходить в рамках проверки столбца и строки? Потому мы исключаем их из подсегмента квадрата и анализируем только те ячейки, которые пересекаться не будут. Однако при соотнесении строки, столбца и квадрата нам нужно будет эти пересечения учитывать. Потому запоминаем их на будущее.
Далее — получаем результат для столбца, строки, квадрата. Затем идет большущий блок, где мы будем соотносить варианты столбца, строки, квадрата друг с другом. Если, например, не заполнен квадрат — соотносим строку и столбец. Если не заполнена строка либо столбец — соотносим оставшееся с квадратом. Заполнено все — соотносим строку, столбец, квадрат. И так далее. Каждый раз логика будет немного отличаться. Все эти методы по соотнесению привожу ниже.
Разные варианты соотнесения
private List<SegmentValidBatch> getValidBatchesForColumnOrRow(SubSegmentFillingResult subSegmentFillingResult) { List<SegmentValidBatch> result = new ArrayList<>(); Set<CellsVariant> subSegmentVariants = variantsToCells(subSegmentFillingResult); if (Objects.equals(subSegmentFillingResult.getType(), SubSegmentType.ROW)) { for (CellsVariant subSegmentVariant : subSegmentVariants) { result.add(new SegmentValidBatch(null, subSegmentVariant, null)); } } else if (Objects.equals(subSegmentFillingResult.getType(), SubSegmentType.COLUMN)) { for (CellsVariant subSegmentVariant : subSegmentVariants) { result.add(new SegmentValidBatch(subSegmentVariant, null, null)); } } else { throw new RuntimeException("Wrong type"); } return result; } private List<SegmentValidBatch> getValidBatchesForColumnAndRow(SubSegmentFillingResult columnSubSegmentFillingResult, SubSegmentFillingResult rowSubSegmentFillingResult, Set<Position> positionsIntersectionsWithSquare) { List<SegmentValidBatch> result = new ArrayList<>(); if (!Objects.equals(columnSubSegmentFillingResult.getType(), SubSegmentType.COLUMN) || !Objects.equals(rowSubSegmentFillingResult.getType(), SubSegmentType.ROW)) { throw new RuntimeException("Wrong type"); } Set<CellsVariant> columnSubSegmentVariants = variantsToCells(columnSubSegmentFillingResult); Set<CellsVariant> rowSubSegmentVariants = variantsToCells(rowSubSegmentFillingResult); for (CellsVariant columnSubSegmentVariant : columnSubSegmentVariants) { Set<Integer> intersectionsWithSquareForColumn = columnSubSegmentVariant.getCells().stream().filter(cell -> positionsIntersectionsWithSquare.contains(cell.position())).map(Cell::number).collect(Collectors.toSet()); for (CellsVariant rowSubSegmentVariant : rowSubSegmentVariants) { Set<Integer> intersectionsWithSquareForRow = rowSubSegmentVariant.getCells().stream().filter(cell -> positionsIntersectionsWithSquare.contains(cell.position())).map(Cell::number).collect(Collectors.toSet()); intersectionsWithSquareForRow.retainAll(intersectionsWithSquareForColumn); if (!intersectionsWithSquareForRow.isEmpty()) { continue; } result.add(new SegmentValidBatch(columnSubSegmentVariant, rowSubSegmentVariant, null)); } } return result; } private List<SegmentValidBatch> getValidBatchesForColumnOrRowAndSquare(SubSegmentFillingResult subSegmentFillingResult, SubSegmentFillingResult squareSubSegmentFillingResult, Set<Position> positionsIntersectionsWithSquare) { // todo тут подумать еще раз, что если будет слепое пятно в виде строки/столбца, который заполнен и пересечения мы не учитываем с ним. не должны ли possibleNumbers для столбцов и строк быть еще и пересечением с квадраотом??? List<SegmentValidBatch> result = new ArrayList<>(); Set<CellsVariant> subSegmentVariants = variantsToCells(subSegmentFillingResult); Set<CellsVariant> squareSubSegmentVariants = variantsToCells(squareSubSegmentFillingResult); if (!Objects.equals(subSegmentFillingResult.getType(), SubSegmentType.COLUMN) && !Objects.equals(subSegmentFillingResult.getType(), SubSegmentType.ROW)) { throw new RuntimeException("Wrong type"); } if (!Objects.equals(squareSubSegmentFillingResult.getType(), SubSegmentType.SQUARE)) { throw new RuntimeException("Wrong type"); } boolean isRow = subSegmentFillingResult.getType() == SubSegmentType.ROW; for (CellsVariant subSegmentVariant : subSegmentVariants) { Set<Integer> intersectionsWithSquare = subSegmentVariant.getCells().stream().filter(cell -> positionsIntersectionsWithSquare.contains(cell.position())).map(Cell::number).collect(Collectors.toSet()); for (CellsVariant squareSubSegmentVariant : squareSubSegmentVariants) { boolean hasDupes = squareSubSegmentVariant.getCells().stream().map(Cell::number).anyMatch(intersectionsWithSquare::contains); if (hasDupes) { continue; } if (isRow) { result.add(new SegmentValidBatch(null, squareSubSegmentVariant, squareSubSegmentVariant)); continue; } result.add(new SegmentValidBatch(squareSubSegmentVariant, null, squareSubSegmentVariant)); } } return result; } private List<SegmentValidBatch> getValidBatchesForColumnRowAndSquare(SubSegmentFillingResult columnSubSegmentFillingResult, SubSegmentFillingResult rowSubSegmentFillingResult, SubSegmentFillingResult squareSubSegmentFillingResult, Set<Position> positionsIntersectionsWithSquare) { List<SegmentValidBatch> result = new ArrayList<>(); Set<CellsVariant> columnSubSegmentVariants = variantsToCells(columnSubSegmentFillingResult); Set<CellsVariant> rowSubSegmentVariants = variantsToCells(rowSubSegmentFillingResult); Set<CellsVariant> squareSubSegmentVariants = variantsToCells(squareSubSegmentFillingResult); if (!Objects.equals(columnSubSegmentFillingResult.getType(), SubSegmentType.COLUMN) || !Objects.equals(rowSubSegmentFillingResult.getType(), SubSegmentType.ROW)) { throw new RuntimeException("Wrong type"); } if (!Objects.equals(squareSubSegmentFillingResult.getType(), SubSegmentType.SQUARE)) { throw new RuntimeException("Wrong type"); } for (CellsVariant columnSubSegmentVariant : columnSubSegmentVariants) { Set<Integer> intersectionsWithSquareByColumn = columnSubSegmentVariant.getCells().stream().filter(cell -> positionsIntersectionsWithSquare.contains(cell.position())).map(Cell::number).collect(Collectors.toSet()); for (CellsVariant rowSubSegmentVariant : rowSubSegmentVariants) { Set<Integer> intersectionsWithSquareByRow = rowSubSegmentVariant.getCells().stream().filter(cell -> positionsIntersectionsWithSquare.contains(cell.position())).map(Cell::number).collect(Collectors.toSet()); Set<Integer> intersectionsByRowAndColumn = new HashSet<>(intersectionsWithSquareByRow); intersectionsByRowAndColumn.retainAll(intersectionsWithSquareByColumn); if (!intersectionsByRowAndColumn.isEmpty()) { continue; } for (CellsVariant squareSubSegmentVariant : squareSubSegmentVariants) { Set<Integer> intersectedNumbersInRowColumnForSquare = new HashSet<>(intersectionsWithSquareByColumn); intersectedNumbersInRowColumnForSquare.addAll(intersectionsWithSquareByRow); boolean hasDupesForSquare = squareSubSegmentVariant.getCells().stream().map(Cell::number).anyMatch(intersectedNumbersInRowColumnForSquare::contains); if (hasDupesForSquare) { continue; } result.add(new SegmentValidBatch(columnSubSegmentVariant, rowSubSegmentVariant, squareSubSegmentVariant)); } } } return result; } private Set<CellsVariant> variantsToCells(SubSegmentFillingResult fillingResult) { return fillingResult.getNumberSequenceVariant().getKeyValuePairs().stream().map( setOfPairs -> setOfPairs.stream().map(pair -> new Cell(pair.getKey(), pair.getValue())).collect(Collectors.toSet()) ).map(r -> new CellsVariant(r, fillingResult.getType())).collect(Collectors.toSet()); }С possibleNumberValidation, похоже, разобрались!
Что имеем?
После всех манипуляций на выходе в PossibleNumbersValidationResult мы имеем информацию о том, применима ли конкретная цифра в конкретной «опорной» позиции — и все SegmentValidBatch под нее, т.е объединения валидной строки, столбца, квадрата, которые вместе образуют валидный сегмент (включая и цифру в «опорной» позиции теперь).
Как я и говорил: мы получили кучу больших и полноценных кусков паззла. Осталось только как-то быстро и безболезненно собрать их воедино.
Я проверял подбор на том же «Эвересте» от безумного финского математика Арто Инкала. Для каждой опорной позиции этих самых кусочков оказывалось впечатляюще много (собственно поэтому я и не привожу результаты работы программы). Всего, насколько я помню, их оказалось около 80 тысяч. Но что обнадеживает — для каждой позиции есть и единственно верный вариант заполнения среди кучи мусора. Значит, что-то отдаленно похожее на решение все же вырисовывается.
Конечно, я пытался соотносить все это дело. В тупую прямым перебором — такой вариант меня не очень привлекает, потому были какие-то небезынтересные, но бесполезные свистопляски с Index-ами и прочим, о чем я пока рассказывать не стану: в любом случае при сборке возможных вариантов прога зависает так, что у меня в какой-то момент лопается терпение и я заканчиваю мучения идеи.
Возможно, можно будет как-то совместить мои задумки по «индекам» и алгоритм X, скажем… но это мысли вслух.
В любом случае, промежуточный результат моих изысканий такой. Надеюсь, мне хватит энергии и фантазии их продолжить.
Буду рад, если у кого-нибудь появятся дельные идеи, как что-либо улучшить/обыграть. Адекватная критика, разумеется, тоже приветствуется.
Полный код проекта с недоделанным куском Index-а тоже прилагаю в публичном репе с неработающим пока тестом. Надеюсь, все нецензурные комментарии я оттуда поубирал…
Всем дзякую! Возможно, кому-то покажется интересным.
ссылка на оригинал статьи https://habr.com/ru/articles/878124/
Добавить комментарий