Я недавно сделал решатель судоку на Java с использованием обратного отслеживания.
Возможно ли, учитывая решения, сформулировать проблему или загадку?
ИЗМЕНИТЬ
Чтобы сформулировать исходную головоломку, есть ли способ добиться этого?
и дополнительный вопрос,
учитывая загадку и решения.
Если я смогу решить головоломку, используя решения (результат - головоломки)
и в то же время может решать решения с помощью головоломки (результат - решения)
У кого номер больше?
головоломки? или решения?
Можно сформулировать одно из множества возможных исходных состояний.
Если больше нельзя удалить числа, вы достигли одного из исходных состояний головоломки.
Если вы выбрали числа, которые вы удаляете случайным образом (шаг 2), вы можете выполнить это несколько раз и получить разные отправные точки, которые приведут к одной и той же финальной головоломке.
Создать головоломку из решения очень просто. Вы просто применяете шаги решения в обратном направлении.
Например, если строка содержит 8 цифр, вы можете заполнить 9-ю. Если вы сделаете это в обратном порядке, если строка содержит 9 цифр, вы можете удалить одну. Это приведет к очень скучной головоломке, но все же верной (действительная головоломка - это головоломка с одним решением).
Чем сложнее будут шаги, которые вы сделаете, тем сложнее будет головоломка. Фактически, перебор головоломки - самая сложная стратегия, ее выполнение в обратном порядке, вероятно, сводится к случайному удалению цифры и проверке грубой силы, есть ли еще только одно уникальное решение. Обратите внимание, что вам не нужно решать всю головоломку: достаточно доказать, что есть только один способ добавить удаленную цифру обратно в головоломку.
Что касается второй части вашего вопроса: это немного похоже на математический вопрос, но позвольте мне ответить:
Хорошая головоломка имеет только одно решение. Поскольку существует несколько головоломок, которые дают одно и то же решение (например, существует 81 способ заполнить 80 из 81 квадрата, каждый из которых дает одно и то же решение из другой головоломки), можно сказать, что головоломок намного больше, чем решений.
Если вы также разрешите головоломки с несколькими решениями, это изменится. Для каждой головоломки должно быть одно или несколько решений, но все эти решения также принадлежат этой головоломке, поэтому количество решений для головоломок равно количеству головоломок для решений. Недействительные головоломки не меняют этого: поскольку они принадлежат к 0 решениям, вам не нужны дополнительные головоломки, принадлежащие этим решениям.
Пс. Также тривиально создавать головоломки, если они не должны быть однозначно решаемыми: просто удалите случайным образом несколько цифр, и все готово.
Если я могу решить головоломку, используя решения (результат - головоломки), и в то же время могу решать решения, используя головоломку (результат - это решения)
У кого номер больше?
головоломки? или решения?
Нет однозначного ответа.
Каждое решение содержит ровно 2 81 соответствующих головоломки, включая тривиальную. Не у всех из них есть уникальное решение, но у многих есть. Следовательно, если выбранный набор решений содержит только один элемент, то максимальный набор головоломок, которые в совокупности соответствуют набору решений, значительно больше.
С другой стороны, полностью пустая головоломка дает 6670903752021072936960 решений. Есть много пар таких, которые используют только пустую сетку в качестве общей головоломки. Таким образом, если выбранный набор головоломок включает только пустую сетку, то набор соответствующих решений значительно больше.
