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

Некоторые общие моменты: я не бегаю процессы параллельно, если: 1) легко разделить проблему 2) Я знаю, что получу от этого выгоду - например, я не столкнусь с другим узким местом. Я полностью избегаю обмена изменяемыми значениями между потоками или минимизирую это. Некоторые люди достаточно умны, чтобы безопасно работать с мьютексами. Я не.

Вам нужно найти в своем алгоритме точки, которые создают естественные ветви или большие единицы работы. После того, как вы определили единицу для работы, вы помещаете ее в очередь, чтобы поток взял ее. Как банальный пример. 10 баз данных для обновления. Начать обновление async на всех 10 серверах. Подождите, пока все завершится. Я могу легко избежать совместного использования состояния между потоками / процессами, и может легко агрегировать результаты.

Что касается судоку, то на ум приходит эффективное решение судуко, которое должно сочетать 2-3 (или более) стратегии, которые никогда не выходят за пределы определенной глубины. Когда я занимаюсь судоку, очевидно, что в любой момент разные алгоритмы обеспечивают решение с наименьшей трудозатратностью. Вы можете просто задействовать несколько стратегий, позволить им исследовать до ограниченной глубины, дождаться отчета. Промыть, повторить. Это позволяет избежать «грубой силы» решения. У каждого алгоритма есть собственное пространство данных, но вы комбинируете ответы.

На сайте Sciam.com была статья об этом год или два назад, но похоже, что она не публичная.

Когда я занимаюсь судоку, очевидно, что в любой момент разные алгоритмы обеспечивают решение с наименьшей трудозатратностью. Вы можете просто задействовать несколько стратегий, позволить им исследовать до ограниченной глубины, дождаться отчета. Промыть, повторить. Это позволяет избежать «грубой силы» решения. У каждого алгоритма есть собственное пространство данных, но вы комбинируете ответы.

На сайте Sciam.com была статья об этом год или два назад, но похоже, что она не публичная.

Когда я занимаюсь судоку, очевидно, что в любой момент разные алгоритмы обеспечивают решение с наименьшей трудозатратностью. Вы можете просто задействовать несколько стратегий, позволить им исследовать до ограниченной глубины, дождаться отчета. Промыть, повторить. Это позволяет избежать «грубой силы» решения. У каждого алгоритма есть собственное пространство данных, но вы комбинируете ответы.

На сайте Sciam.com была статья об этом год или два назад, но похоже, что она не публичная.

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

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

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

Нужно ли использовать многопоточность или просто использовать многопоточность, чтобы вы могли научиться выполнять задание?

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

Вы сказали, что использовали обратное отслеживание для решения проблемы. Что вы можете сделать, так это разделить пространство поиска на два и обработать каждое пространство в потоке, тогда каждый поток будет делать то же самое, пока вы не достигнете последнего узла. Я нашел решение этой проблемы, которое можно найти на www2.cs.uregina.ca/~hmer200a, но с использованием одного потока, но механизм разделения пространства поиска существует с использованием ветвления и привязки.

Когда вы говорите все решения данной головоломки, вы имеете в виду последнее и единственное решение головоломки? Или различных способов достижения единого решения? Я понимал, что по определению у головоломки судоку может быть только одно решение ...

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

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

Here is a greedy brute-force single-threaded solver:

1. Select next empty cell. If no more empty cells, victory!
2. Possible cell value = 1
3. Check for invalid partial solution (duplicates in row, column or 3x3 block).
4. If partial solution is invalid, increment cell value and return to step 3. Otherwise, go to step 1.

If you look at the above outline, the combination of steps 2 and 3 are obvious candidates for multithreading. More ambitious solutions involve creating a recursive exploration that spawns tasks that are submitted to a thread pool.

EDIT to respond to this point: "I don't understand how you can find different solutions to the same problem at the same time without maintaining multiple copies of the puzzle."

You can't. That's the whole point. However, a concrete 9-thread example might make the benefits more clear:

1. Start with an example problem.
2. Find the first empty cell.
3. Create 9 threads, where each thread has its own copy of the problem with its own index as a candidate value in the empty cell.
4. Within each thread, run your original single-threaded algorithm on this thread-local modified copy of the problem.
5. If one of the threads finds an answer, stop all the other threads.

As you can imagine, each thread is now running a slightly smaller problem space and each thread has the potential to run on its own CPU core. With a single-threaded algorithm alone, you can't reap the benefits of a multi-core machine.

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

В основном вы хотите разделить возможное состояние решения на несколько подпространств, которые являются как можно более независимыми (чтобы избежать тратить слишком много ресурсов на накладные расходы на создание потоков), и все же «соответствовать» вашему алгоритму (чтобы фактически получить выгоду от наличия нескольких потоков).

Depending on how you coded your single threaded solver, you might be able to re-use the logic. You can code a multi-threaded solver to start each thread using a different set of strategies to solve the puzzle.

Using those different strategies, your multi-threaded solver may find the total set of solutions in less time than your single threaded solver (keep in mind though that a true Sudoku puzzle only has one solution...you're not the only one who had to deal with that god awful game in class)

Multi-threading is useful in any situation where a single thread has to wait for a resource and you can run another thread in the meantime. This includes a thread waiting for an I/O request or database access while another thread continues with CPU work.

Multi-threading is also useful if the individual threads can be farmed out to diffent CPUs (or cores) as they then run truly concurrently, although they'll generally have to share data so there'll still be some contention.

I can't see any reason why a multi-threaded Sudoku solver would be more efficient than a single-threaded one, simply because there's no waiting for resources. Everything will be done in memory.

But I remember some of the homework I did at Uni, and it was similarly useless (Fortran code to see how deep a tunnel got when you dug down at 30 degrees for one mile then 15 degrees for another mile - yes, I'm pretty old :-). The point is to show you can do it, not that it's useful.

On to the algorithm.

I wrote a single threaded solver which basically ran a series of rules in each pass to try and populate another square. A sample rule was: if row 1 only has one square free, the number is evident from all the other numbers in row 1.

There were similar rules for all rows, all columns, all 3x3 mini-grids. There were also rules which checked row/column intersects (e.g. if a given square could only contain 3 or 4 due to the row and 4 or 7 due to the column, then it was 4). There were more complex rules I won't detail here but they're basically the same way you solve it manually.

I suspect you have similar rules in your implementation (since other than brute force, I can think of no other way to solve it, and if you've used brute force, there's no hope for you :-).

What I would suggest is to allocate each rule to a thread and have them share the grid. Each thread would do it's own rule and only that rule.

Update:

Jon, based on your edit:

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

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

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

Под этим я подразумеваю, что в любой момент решения, если есть два или более возможных шага вперед, вы должны выделить каждую возможность отдельному потоку (все еще используя свои правила для эффективности, но одновременно проверяя каждая возможность). Это даст вам лучший параллелизм (при условии, что потоки могут выполняться на отдельных процессорах / ядрах), поскольку не будет конкуренции за плату; каждый поток получит свою собственную копию.

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

Я бы посоветовал иметь рабочая очередь и N потоков. Очередь работ изначально пуста, когда ваш основной поток запускает все рабочие потоки. Затем основной поток помещает начальное состояние головоломки в рабочую очередь.

Рабочие потоки просто ждут, пока состояние будет помещено в рабочую очередь, и один из них захватывает его для обработки. Рабочий поток - это ваш однопоточный решатель с одной небольшой модификацией: когда есть X возможностей двигаться вперед (X> 1), ваш рабочий помещает X-1 из них обратно в рабочую очередь, а затем продолжает обрабатывать другую возможность.

Итак, допустим, есть только одно решение (истинная судоку :-). Первый рабочий поток уничтожит решение, не найдя никаких вилок, и это будет точно так же, как в вашей текущей ситуации.

Но с двумя возможностями на 27-м ходу (скажем, 3 или 4 могут попасть в верхнюю левую ячейку), ваш поток создаст еще одну доску с первой возможностью (поместите 3 в эту ячейку) и поместит ее в рабочую очередь. Затем он поместит 4 в свою собственную копию и продолжит.

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

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

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

Когда все потоки простаивают, а рабочая очередь пуста, у основного потока либо будет, либо не будет решения. У него также будет количество решений.

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

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

Когда все потоки простаивают, а рабочая очередь пуста, у основного потока либо будет, либо не будет решения. У него также будет количество решений.

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

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

Когда все потоки простаивают, а рабочая очередь пуста, у основного потока либо будет, либо не будет решения. У него также будет количество решений.

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

Когда все потоки простаивают и рабочая очередь пуста, main либо будет, либо не иметь решения. У него также будет количество решений.

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

Когда все потоки простаивают и рабочая очередь пуста, main либо будет, либо не иметь решения. У него также будет количество решений.

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

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

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

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

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

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

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