Real-World Constraint Solving উদাহরণ

Constraint solving হল এমন একটি প্রযুক্তি যা ব্যবহার করে নির্দিষ্ট শর্ত বা constraints এর উপর ভিত্তি করে সমস্যার সমাধান করা হয়। প্রোলগের মাধ্যমে, আপনি constraint satisfaction problems (CSP) সমাধান করতে পারেন, যেখানে বিভিন্ন শর্ত বা সীমাবদ্ধতা থাকে এবং আপনাকে এগুলির মধ্যে সেরা সমাধান খুঁজে বের করতে হয়।

নিচে আমরা real-world constraint solving এর জন্য প্রোলগে কিছু উদাহরণ দেখব।

উদাহরণ ১: Scheduling Problem

Scheduling সমস্যা একটি ক্লাসিক **constraint satisfaction problem (CSP)**। উদাহরণস্বরূপ, একটি স্কুলের পরীক্ষার সময়সূচী নির্ধারণ করতে হবে যাতে একই সময়ে একই শিক্ষক অথবা একই কক্ষে দুটি পরীক্ষা না হয়।

প্রথমে Constraints নির্ধারণ করা যাক:

• একই সময়ে একই শিক্ষক দুটি পরীক্ষায় থাকতে পারবেন না।
• একই সময়ে একই কক্ষে দুটি পরীক্ষা নেওয়া যাবে না।
• প্রতিটি পরীক্ষার জন্য নির্দিষ্ট কক্ষে একটি নির্দিষ্ট সময়ের মধ্যে থাকতে হবে।

প্রোলগে এর সমাধান:

% Define the subjects
subject(math).
subject(science).
subject(english).

% Define the rooms
room(room1).
room(room2).

% Define the time slots
time_slot(t1).
time_slot(t2).

% Define the teachers for each subject
teacher(math, teacher1).
teacher(science, teacher2).
teacher(english, teacher3).

% Define the constraints
schedule(Subject, Room, Time) :-
    subject(Subject),
    room(Room),
    time_slot(Time),
    teacher(Subject, Teacher),
    not(conflict(Teacher, Time)),
    not(conflict_room(Room, Time)).

% Define conflict constraints
conflict(Teacher, Time) :-
    schedule(_, _, Time), 
    teacher(_, Teacher).

conflict_room(Room, Time) :-
    schedule(_, Room, Time).

এখানে, schedule/3 একটি subject, room, এবং time slot এর জন্য constraint satisfaction নির্ধারণ করছে। আমরা conflict/2 এবং conflict_room/2 দিয়ে শর্ত নির্ধারণ করেছি যে একি সময়ে একই শিক্ষক এবং একই কক্ষে দুটি পরীক্ষা চলতে পারে না।

কোয়ারি:

?- schedule(math, room1, t1).

এটি math পরীক্ষার জন্য room1 এবং t1 সময়ে একটি পরীক্ষা নির্ধারণ করবে যদি সেখানে কোনো conflict না থাকে। যদি কোনো কনফ্লিক্ট না থাকে, তাহলে এটি সমাধান প্রদান করবে।

উদাহরণ ২: Sudoku Puzzle

Sudoku একটি জনপ্রিয় constraint satisfaction problem। এখানে ৯x৯ গ্রিডে কিছু সংখ্যার মধ্যে সীমাবদ্ধতা থাকে:

• প্রতিটি সারিতে ১ থেকে ৯ পর্যন্ত সমস্ত সংখ্যাগুলি একবার মাত্র থাকতে হবে।
• প্রতিটি কলামে ১ থেকে ৯ পর্যন্ত সমস্ত সংখ্যাগুলি একবার মাত্র থাকতে হবে।
• প্রতিটি ৩x৩ ব্লকে ১ থেকে ৯ পর্যন্ত সমস্ত সংখ্যাগুলি একবার মাত্র থাকতে হবে।

প্রোলগে এর সমাধান:

% Define the Sudoku grid as a list of lists (9x9 grid)
sudoku([ [1, _, _, _, 2, _, _, _, 3],
         [_, _, _, 1, _, 3, 5, _, _],
         [_, _, _, 4, _, _, _, 6, 7],
         [_, _, 2, _, 7, _, _, _, 5],
         [3, _, _, _, _, _, _, _, 6],
         [7, 8, _, 9, _, _, _, _, _],
         [6, _, _, _, _, 1, _, 4, _],
         [_, 9, 6, _, _, 5, _, _, _],
         [9, _, 4, 6, _, _, 7, 3, _] ]).
         
% Define the constraint that each row must have unique numbers from 1 to 9
valid_row(Row) :- fd_all_different(Row).

% Define the constraint that each column must have unique numbers from 1 to 9
valid_column(Grid, ColumnIndex) :-
    findall(Value, nth1(RowIndex, Grid, Row), nth1(ColumnIndex, Row, Value)).

% Define the constraint that each 3x3 sub-grid must have unique numbers from 1 to 9
valid_subgrid(Grid) :-
    subgrid(Grid), % Add the 3x3 grid constraint here.
    fd_all_different(Grid).

% Apply these constraints to the full sudoku grid.
solve_sudoku(Grid) :-
    sudoku(Grid),
    maplist(valid_row, Grid),
    maplist(valid_column, Grid),
    maplist(valid_subgrid, Grid),
    fd_labeling(Grid).

এখানে, fd_all_different/1 হল প্রোলগের constraint logic programming (CLP) লাইব্রেরির একটি ফাংশন যা নিশ্চিত করে যে একটি row, column অথবা subgrid এর সকল সংখ্যা ভিন্ন হবে। এছাড়া, fd_labeling/1 ফাংশনটি সঠিক grid configuration বের করতে সাহায্য করে।

উদাহরণ ৩: N-Queens Problem

N-Queens সমস্যা একটি জনপ্রিয় কনস্ট্রেইন্ট স্যটিসফেকশন সমস্যা যেখানে N সংখ্যক রাণীকে একটি N x N chessboard এ এমনভাবে বসাতে হয় যে তারা একে অপরকে আক্রমণ না করে। অর্থাৎ, কোনো দুটি রাণী একই সারি, কলাম বা ডায়াগনালে থাকতে পারবে না।

প্রোলগে এর সমাধান:

n_queens(N, Solution) :-
    length(Solution, N), % List to hold the positions of queens
    valid_queens(Solution, N), % Validate queens placement
    place_queens(Solution, N).

% Ensure that queens don't attack each other
valid_queens([], _).
valid_queens([Head|Tail], N) :-
    valid_queen(Head, Tail, N),
    valid_queens(Tail, N).

valid_queen(_, [], _).
valid_queen(X, [Y|Rest], N) :-
    X =\= Y, % No queens in the same row
    abs(X - Y) =\= abs(length([Y|Rest]) - N), % No queens in the same diagonal
    valid_queen(X, Rest, N).

% Place queens
place_queens(Solution, N) :-
    fd_all_different(Solution),
    fd_labeling(Solution).

এখানে valid_queens/2 এবং valid_queen/3 প্রেডিকেটগুলি নিশ্চিত করে যে কোন দুটি রাণী একই সারি বা ডায়াগনালে নেই। আমরা fd_all_different/1 ব্যবহার করছি যাতে N সংখ্যক রাণী একে অপরের সাথে সাংঘর্ষিক না হয়।

Conclusion

Real-world constraint solving এ প্রোলগ অত্যন্ত শক্তিশালী একটি টুল। এটি constraint logic programming (CLP) এর সাহায্যে constraint satisfaction problems (CSP) সমাধান করতে সক্ষম। উদাহরণস্বরূপ, Scheduling, Sudoku, এবং N-Queens সমস্যাগুলিতে প্রোলগ ব্যবহার করে আমরা বিভিন্ন ধরনের সীমাবদ্ধতা (constraints) প্রয়োগ করতে পারি এবং সেগুলির মধ্যে একটি valid solution খুঁজে বের করতে পারি।