Правила гри

Digitsum(Dl, D2, C2, D, C, Digs2, Digs).

Suml(Nl, N2, N, Cl, C2, Digsl, Digs2),

Sum1(Nl, N2, N,

0, 0, %Обидві цифри переносу, справа і зліва, равні 0

[0,1,2,3,4,5,6,7,6,9], _). % Доступними є всі цифри

suml([], [], [], 0, 0, Digits, Digits).

suml([D1|N1], [D2|N2], [D|N], Cl, C, Digsl, Digs):-

digitsum(Dl, D2, Cl, D, C, Digsl, Digs):-

del_var(Dl,Digsl,Digs2), % Вибір доступної цифри для Dl

del_var(D2,Digs2,Digs3), % Вибір доступної цифри для D2

del_var(D,Digs3,Digs), %Вибір доступної цифри для D

S is Dl + D2 + Cl,

D is S mod 10, % Залишок

С is Sdiv10. % Цілочисельне ділення

del_var(A,L,L):-nonvar(A),!. %Змінна А вже конкретизована

del_var[A,[A|L],L). % Видалити голову списку

del_var[A,[B|L],[B|Ll]):-

del_var(A,L,LI). % Видалити елемент з хвоста списку

% Деякі ребуси

puzzlel([D,O,N,A,L,D], [G,E,R,A,L,D],[R,O,B,E,R,T]).

puzzle2([O, S, E, N, D], [O, M, O, R, E], [M, O, N, E, Y]).

Іноді рішення подібних задач можна спростити, вказавши, як додаткове обмеження, цифрове значення однієї з букв (наприклад, повідомивши, що D дорівнює 5). Задачу, представлену у такій формі, можна повідомити системі Prolog з використанням відношення suml у такий спосіб:

?- suml([5,О,N,A,L,5],[G,E,R,A,L,5],

[R,O,B,E,R,T],0,0,[0,1,2,3,4,6,7,8,9], _).

Варто зазначити, що в обох випадках є лише по одному рішень, інакше кажучи, існує єдиний спосіб заміни букв цифрами.

13. Ігрові програми. Гра "бики й корови" (видатний розум)

Розробка ігрових програм є розвагою, а також гарним способом показу того, як використати Пролог для створення неелементарних програм. В ігрових програмах описується стратегія, що приводить до виграшу гри.

Грають двоє. Кожний задумує й записує таємне 4-значне число з неповторюваними цифрами. Гравець, що починає гру по жеребі, робить спробу відгадати число. Спроба - це 4-значне число з неповторюваними цифрами, повідомлюване супротивнику. Супротивник у відповідь повідомляє, скільки цифр вгадано без збігу з їхніми позиціями в таємному числі і скільки вгадано аж до позиції в таємному числі. Наприклад:

Задумано таємне число "3219".

Спроба номер: "2310".

Результат: дві "корови" (цифри: "2" і "3" - вгадані на невірних позиціях) і один "бик" (одна цифра "1" вгадана аж до позиції).

Свої спроби гравці роблять по черзі. Перемагає той, хто вгадає число першим. Код угаданий, якщо число биків дорівнює N. У загальному випадку кількість варіантів для k-значного числа в N-річній системі числення без повторень, дорівнює числу розміщень:

У класичному випадку гри із чотирма не повторюваними цифрами для відгадування будь-якого номера потрібно не більше семи ходів. Середня мінімальна довжина гри становить 26274/5040=5.2131 спроби.

Існує дуже простий алгоритм цієї гри: вводиться деякий порядок на множині припустимих правилами гіпотез; висування чергових припущень ураховує накопичену до цього моменту інформацію, і так доти, поки секретний код не буде розкритий.

Людині нелегко застосувати стратегію, використовувану в алгоритмі, оскільки це вимагатиме значної розрахункової роботи. З іншого боку недетермінований вибір Прологу, моделюємий пошуком з поверненнями, є ідеальним для реалізації саме такого алгоритму.

Програма "Бики й Корови"

master_mind (Code): -%Чистка, гіпотеза, перевірка, повідомлення

cleanup, guess (Code), check (Code), announce.

% Гіпотеза. Запитуюча процедура guess діє як генератор, використає процедуру selects(Xs Ys) для недетермінованого вибору списку Хs з елементів списку Ys. Відповідно до правил гри, Хs обмежується чотирма різними десятковими цифрами, у той час як список Ys містить 10 десяткових цифр.

guess(Code):-

Code=[X1,X2,X3,X4],selects(Code,[1,2,3,4,5,6,7,8,9,0]).

% предикат selects - це по суті "генератор" можливих рішень, у даному випадку генератор можливих комбінацій загаданого числа; зі списку можливих варіантів (цифри від 0 до 9), він генерує всі можливі варіанти цих цифр, розташовуючи їх у %список заданої довжини

selects([],Ys):-!.
selects([X|Xs],Ys):-select(X,Ys,Ys1),selects(Xs,Ys1).
select(X,[X|Xs],Xs).
select(X,[Y|Ys],[Y|Zs]):- select(X,Ys,Zs).

% Згенеровані можливі значення числа повинні бути перевірені на те, що ці варіанти не оброблені раніше, і, найголовніше, що

враховані всі уведені раніше відповіді про корів і биків.

% Для цього правило inconsistent перевіряє на точний збіг і загальні члени. Точний збіг - це кількість однакових цифр на своїх місцях, тобто биків. Загальні члени - це однакові цифри, але не на своїх місцях, тобто корови

% Перевірка гіпотези: чи нема протиріччя та питання

check(Guess):-not inconsistent(Guess),ask(Guess).

% Запит: B – бики, С – корови. Перевірка відповідності чисел

inconsistent(Guess):-query(OldGuess,B,C),

Дата добавления: 2014-01-04