судоку на пролог слишком долго, чтобы решить

Question

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

Answer 1

Не видя кода, никто не может вам помочь, но вот некоторые общие советы, которые могут вам пригодиться.

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

Сокращение делает намного меньше, чем вы думаете. Это только полезно, если вы знаете, что ваше первое решение так же хорошо или лучше, чем остальное. Это совершает вы к первому предположению.

В такой проблеме, как судоку, очень легко наивно генерировать гораздо больше решений, чем вам нужно. Если вы просто выберите цифру, вы создадите 9^9 потенциальных решений для сетки 3x3, но вы уже знаете, что последовательность, подобная [9,9,9,9,9,9,9,9,9] бесполезен для вас. Большинство решений, которые вы создаете с этим подходом, будут бесполезны. Так что гораздо лучше просто попросить перестановку [1,2,3,4,5,6,7,8,9] - это на три порядка лучше! Но это получается с судоку, вы можете сделать еще лучше, потому что вы не захотите больше, чем некоторое количество 9 или 1 в том же ряду 9.

В этом свете должно быть ясно, что Общая идея «просто использовать разрез» немного напоминает передачу ребенку скальпеля или попросить хирурга использовать его для вырезания индейки в честь Дня благодарения. Это может быть отличный инструмент, но не в неправильных руках или за неправильную работу. Чтобы вам было хорошо, вам сначала нужно что-то узнать о том, какой порядок вы создаете потенциальными решениями. Если вы не создадите их в правильном порядке, это навредит вам. Это похоже на маркетинг. Вам нужны высококвалифицированные лидеры, но если вы выбросите все свои деньги за неправильные дорогие деньги, вы будете мертвы в воде.

Часто, если вы прослеживаете программу Prolog, вы можете понять, почему она тратит время на создание вещей неэффективно. Если вы когда-нибудь подумаете о себе, «он должен был уже отказаться!» то вы точно знаете, где положить разрез. Скорее всего, вы подумаете: «Почему вы так глупы, пытаетесь сделать это до этого?» Если вы обнаружите, что думаете об этом, формализуйте свою мысль. Вернитесь назад и напишите более умный генератор, и производительность вашего кода резко улучшится.

Анекдот из моего личного опыта. Сын друга пытался обыграть онлайн-игру. Для этого ему пришлось решить кучу анаграмм. Это очень утомительно для длинных слов. Я написал программу Prolog, которая использовала WordNet как свою базу данных. Я бы взял буквы и перепутал их, пока не нашел слово в базе данных, а затем распечатал его. Он работал на небольшие слова, скажем, на 5 букв, но это было просто больно медленно с 7 или 8. Прошло несколько лет, и я в душе, когда вдруг осознаю: я могу сделать индекс. Если я просто беру все слова в словаре и сортирую их символы, тогда я могу взять символы анаграммы, отсортировать их и найти все слова, которые соответствуют этому в индексе. Построение индекса требует времени, но не намного по сравнению с выполнением миллиардов перестановок, и я должен сделать это только один раз, чтобы обеспечить быстрый поиск.Первоначальная программа больше походила на Пролог, о котором мы мечтаем, и мастера могут писать, но второй из них позволил найти анаграммы огромных слов и читать было не намного сложнее (хотя и менее «декларативный»). Мораль этой истории заключается в том, что сокращение никогда не привлекло бы меня к этой реализации или к алгоритму, который выполнялся так же хорошо, как этот. Качество алгоритма все еще имеет значение.

Answer 2

Рассмотрите возможность использования ограничений конечного домена. Они доступны практически во всех современных системах Prolog и позволяют принимать декларативные формулировки многих комбинаторных проблем, в том числе Sudoku.

Если вы моделируете эту проблему с ограничениями конечного домена, вам не понадобится !/0 и все равно получите очень эффективное решение.

Из документации SWI-Пролога library(clpfd):

:- use_module(library(clpfd)). 

sudoku(Rows) :- 
     length(Rows, 9), maplist(length_(9), Rows), 
     append(Rows, Vs), Vs ins 1..9, 
     maplist(all_distinct, Rows), 
     transpose(Rows, Columns), 
     maplist(all_distinct, Columns), 
     Rows = [A,B,C,D,E,F,G,H,I], 
     blocks(A, B, C), blocks(D, E, F), blocks(G, H, I). 

length_(L, Ls) :- length(Ls, L). 

blocks([], [], []). 
blocks([A,B,C|Bs1], [D,E,F|Bs2], [G,H,I|Bs3]) :- 
     all_distinct([A,B,C,D,E,F,G,H,I]), 
     blocks(Bs1, Bs2, Bs3). 

problem(1, [[_,_,_,_,_,_,_,_,_], 
      [_,_,_,_,_,3,_,8,5], 
      [_,_,1,_,2,_,_,_,_], 
      [_,_,_,5,_,7,_,_,_], 
      [_,_,4,_,_,_,1,_,_], 
      [_,9,_,_,_,_,_,_,_], 
      [5,_,_,_,_,_,_,7,3], 
      [_,_,2,_,1,_,_,_,_], 
      [_,_,_,_,4,_,_,_,9]]). 

Пример запроса и его результат:

?- problem(1, Rows), sudoku(Rows), maplist(writeln, Rows). 
[9, 8, 7, 6, 5, 4, 3, 2, 1] 
[2, 4, 6, 1, 7, 3, 9, 8, 5] 
[3, 5, 1, 9, 2, 8, 7, 4, 6] 
[1, 2, 8, 5, 3, 7, 6, 9, 4] 
[6, 3, 4, 8, 9, 2, 1, 5, 7] 
[7, 9, 5, 4, 6, 1, 8, 3, 2] 
[5, 1, 9, 2, 8, 6, 4, 7, 3] 
[4, 7, 2, 3, 1, 9, 5, 6, 8] 
[8, 6, 3, 7, 4, 5, 2, 1, 9]