Многопоточный алгоритм решения судоку?

Question

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

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

Буду признателен, если кто-нибудь даст мне несколько начальных советов по алгоритму (пожалуйста, без кода ...)

---

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

Кроме того, не может быть единственного решения - допустимым входным значением может быть абсолютно пустая доска. Я должен сообщить min(1000, number of solutions) и отобразить один из них (если он существует)

Answer 1

Просто примечание. На самом деле я реализовал оптимизированный решатель судоку и изучил многопоточность, но две вещи остановили меня.

Во-первых, простые накладные расходы на запуск потока заняли 0,5 миллисекунды, а полное разрешение - от 1 до 3 миллисекунд (я использовал Java, другие языки или среды могут давать другие результаты).

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

Answer 2

У меня есть идея, которая довольно забавная ... сделайте это с моделью актера! Я бы сказал, используя Erlang .. Как? Вы начинаете с оригинальной доски, и ..

• 1) сначала пустую ячейку создайте 9 детей с разным номером, затем совершите самоубийство
• 2) каждый ребенок проверяет, является ли он недействительным, если это так, он совершает самоубийство, иначе
  • если есть пустая ячейка, перейдите к 1)
  • если завершено, этот актер является решением

Очевидно, что каждый выживший актер является решением проблемы =)

Answer 3

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