Многопоточность полезна в любой ситуации, когда один поток должен ждать ресурс, а тем временем вы можете запустить другой поток. Это включает в себя поток, ожидающий запрос ввода-вывода или доступ к базе данных, в то время как другой поток продолжает работу ЦП.
Многопоточность также полезна , если , отдельные потоки могут быть распределены по разным процессорам (или ядрам), поскольку они затем работают по-настоящему параллельно, хотя им, как правило, придется обмениваться данными, поэтому все еще будут некоторые разногласия.
Я не вижу причин, по которым многопоточный решатель судоку был бы более эффективным, чем однопоточный, просто потому, что не нужно ждать ресурсов. Все будет сделано в памяти.
Но я помню некоторую домашнюю работу, которую я сделал в Uni, и она была также бесполезна (код на Фортране, чтобы увидеть, как глубоко проложился туннель, когда вы копали под углом 30 градусов на одну милю, затем 15 градусов на другую милю - да Я довольно старый :-). Суть в том, чтобы показать, что вы можете сделать это, а не то, что это полезно.
к алгоритму.
Я написал однопоточный решатель, который в основном выполнял серию правил на каждом проходе, чтобы попытаться заполнить другой квадрат. Примерное правило: если в строке 1 только один квадрат свободен, число видно из всех остальных чисел в строке 1.
Были одинаковые правила для всех строк, всех столбцов, всех мини-сеток 3х3. Существовали также правила, которые проверяли пересечение строк / столбцов (например, если данный квадрат мог содержать только 3 или 4 из-за строки и 4 или 7 из-за столбца, тогда это было 4). Были более сложные правила, которые я не буду здесь подробно описывать, но в основном они аналогичны тем, которые вы решаете вручную.
Я подозреваю, что у вас есть аналогичные правила в вашей реализации (поскольку, кроме грубой силы, я не могу придумать другого пути ее решения, и если вы использовали грубую силу, у вас нет надежды: -).
Что бы я предложил, это выделить каждое правило для потока и сделать так, чтобы они совместно использовали сетку. Каждый поток будет выполнять свое собственное правило и только это правило.
Обновление:
Джон, исходя из ваших правок:
[edit] Я забыл упомянуть, что количество используемых потоков указано в качестве аргумента программы, так что, насколько я могу судить, это никак не связано с состоянием головоломки ...
Кроме того, не может быть единственного решения - допустимым вводом может быть абсолютно пустая доска. Я должен сообщить мин (1000, количество решений) и отобразить одно из них (если оно существует)
Похоже, ваш учитель не хочет, чтобы вы делили на основе правил, а вместо этого - на точки разветвления (где могут применяться несколько правил).
Под этим я подразумеваю, что в любой точке решения, если есть два или более возможных шагов вперед, вы должны распределять каждую возможность в отдельном потоке (все еще используя ваши правила для эффективности, но одновременно проверяя каждую возможность). Это обеспечит вам лучший параллелизм (при условии, что потоки могут быть запущены на отдельных процессорах / ядрах), поскольку для платы не будет конкуренции; каждый поток получит свою собственную копию.
Кроме того, поскольку вы ограничиваете количество потоков, вам нужно будет поработать над магией пула потоков, чтобы добиться этого.
Я бы предложил иметь рабочую очередь и N потоков. Рабочая очередь изначально пуста, когда ваш основной поток запускает все рабочие потоки. Затем основной поток помещает начальное состояние головоломки в рабочую очередь.
Рабочие потоки просто ждут, когда в рабочую очередь будет помещено состояние, и один из них захватывает его для обработки. Рабочий поток - это ваш однопоточный решатель с одной небольшой модификацией: когда есть X возможностей для продвижения вперед (X> 1), ваш работник помещает X-1 из них обратно в рабочую очередь, а затем продолжает обрабатывать другую возможность.
Итак, допустим, есть только одно решение (правда, Судоку :-). Первый рабочий поток откажется от решения, не найдя вилок, и это будет точно так же, как в вашей текущей ситуации.
Но с двумя возможностями на 27-м ходу (скажем, 3 или 4 могут войти в верхнюю левую ячейку), ваш поток создаст другую доску с первой возможностью (поместите 3 в эту ячейку) и поместит ее в рабочую очередь. Затем он поместил бы 4 в своем собственном экземпляре и продолжил.
Другая нить возьмет доску с 3 в этой ячейке и продолжит. Таким образом, у вас одновременно работают два потока, которые обрабатывают две возможности.
Когда какой-либо поток решает, что его доска неразрешима, он выбрасывает его и возвращается в рабочую очередь для дополнительной работы.
Когда какой-либо поток решает, что его плата решена, он уведомляет основной поток, который может его сохранить, перезаписывая любое предыдущее решение (первое найденное - решение), или выбрасывает его, если у него уже есть решение (последнее найденное). это решение), тогда рабочий поток возвращается в рабочую очередь для дополнительной работы. В любом случае основной поток должен увеличить количество найденных решений.
Когда все потоки простаивают, а рабочая очередь пуста, main либо найдет, либо не найдет решение. Он также будет иметь количество решений.
Имейте в виду, что все коммуникации между рабочими и основным потоком должны быть взаимно переопределены (я предполагаю, что вы знаете это, основываясь на информации в вашем вопросе).