Even the Odds!

Contest link: Intra AUST Preliminary Fall – 17
Problem name: Even the Odds!

Required knowledge: Modular arithmetic, big multiplication.

Editorial: Firstly, try reading this Modular Arithmetic or you can google about modular arithmatic and it’s properties. Now let’s analyze the problem.
Given and M, we need to find summation of first even numbers modulo and summation of first odd numbers modulo M.

We can observe that the first N odd numbers summation can be found by calculating N * N and first N even numbers summation can be found by calculating N * (N+1).
let, N = 4,

Odd : 1 + 3 + 5 + 7 = 16 = 4 * 4
Even : 2 + 4 + 6 + 8 = 20 = 4 * 5

As the modulo M is really big we can’t simply calculate ( (N % M) * ( (N+1)%M) )%M, because the N can be as large as 1018 – 1 and M can be 1018, then at the time of multiplying, it will overflow. How can we do this without overflow? We will simply use a divide and conquer technique to calculate N * N by adding N with N, N times, instead of multiplying them. Let N = 1018 – 1, M = 1018.

Now, from modular arithmatic we know that

– (a * b) % m = (( a%m ) * ( b%m ))%m
– (a + b) % m = (( a%m ) + ( b%m ))%m

Say, = 1018 and b = 10 and m = 1018 – 1.
So, ( (1018 – 1) %1018 ) * (1018 – 1) %1018 ) ) % 1018= ( (1018 – 1) * (1018 – 1) ) % 1018 = 0 ; here 
(1018 – 1) * (1018 – 1) will cause overflow.

But,(((1018 – 1)%1018) + ((1018 – 1)%1018) + ….

We can easily add (1018 – 1 + 1018 – 1) and then mod it with 1018. We will do this 1018 times, and by using modulo operation each time, there won’t be any overflow.
As 1018 is also a very big number, we can do this is O (log10(N)) times with folowing divide and conquer algorithm.

We will use this bigmul function to calculate ( a * b ) % c. We will simply add the number a, b times each with modulo operation. As the range is too big, we can’t simply use loop, so we will use this recursion technique of calculating big multiplication in logN time.


Cool Magic Square Trick

Today I will talk about a very exciting and cool trick regarding magic square. Once you learn this trick, everybody will definitely acknowledge you as a great math magician 😉
Let’s get started then,
First choose a participant. Ask him/her to select a 2 digit number between 22 and 99. Suppose he choses the number 50. Now I will construct a 4×4 magic square with different unique numbers and make him/her believe that I’m the greatest math magician 😀
I will now take a pen and paper, draw a 4×4 grid and fill up the grid with some random numbers like this :
Well see, every number is random and unique. If you calculate the sum of every column or every row, even the diagonals, you will see the sum is 50 ! And that is your chosen number. If you take the sum of the numbers of the 4 corners, it will be 50 ( 30+7+4+9 = 50 ).
if you take any 4 square inside the grid, the summation of numbers there will be 50. Don’t believe? Check yourself 😛
Ok, but the trick doesn’t end here actually. If you take any 9 square (3×3) and take the summation of 4 corners for that square, the sum will also be 50 !
Check the red colored tiles and see the magic yourself. Cool , right? And I can do this all
day with different numbers 😉
And even this is also possible:
The red and blue tiles sum is also 50! Well there are 28 different combinations where we can get the desired value.
Okay, let’s reveal the trick behind the scene. First think of your magic square like this in your mind:
These four blocks are our magic blocks that will determine the outcome. Remember this by heart and randomly place numbers to other 12 blocks to confuse your partner. But you aren’t doing it randomly, are you? 😉 The greater the magician, the innocent he looks, so you have to be really smart and innocent to pull this off 😛
Well, just fill the 12 blocks like this each and everytime:
Capture.JPGYou can remember this through some practice of course. Well it is essential for every magician to practice, so it’s alright for you to do so. Look we didn’t fill up the A, B, C, D blocks. We only placed the numbers from 1 to 12 here. And remember, everytime these 12 numbers have to be placed like this exactly. Now we will fill up the 4 magic blocks with four different magic numbers. How we will generate these magic numbers? Here is the answer:
A : Subtract 20 from the given number. The number given was 50. So I get 50 – 20 = 30 for the block A.
B : 
Subtract 1 from A, so we get 30 – 1 = 29.
C : Add 2 with A, so we get 30 + 2 = 32 for C.
D : Add 1 with A, so we get 30 + 1 = 31 for D.
Thank you for reading this. Hope you enjoyed all.

Magic Square Part – 2

আগের পর্ব ঃ part – 1

জোড় সংখ্যক গ্রিডের ম্যাজিক স্কয়ার সমাধান ( Solving Even-Numbered Magic Square )

প্রথমে আমরা সহজভাবে দেখি। আমরা এখন যেটি দেখবো সেটি হল ডাবল-জোড় সংখ্যক গ্রিড এর জন্য। ডাবল-জোড় কি? ( Doubly Even ) ডাবল-জোড় হল, যে জোড় গ্রিড ভাঙলে আবার জোড় গ্রিড পাওয়া যায়। যেমন ঃ ৪, ৮, ১৬… আবার, ৬, ১২, ১৪… এসব হবে সিঙ্গেল-জোড় গ্রিড এর মেথড এ। আমরা পরে আলোচনা করবো এটি নিয়ে। আপাতত ডাবল-জোড় দেখি।

প্রথমেই আমরা ম্যাজিক কন্সটেন্ট বের করি। ধরি গ্রিড 4×4,
সুতরাং, [  4 * ( 42 + 1 ) ] / 2 = [ 4 * 17 ] / 2 = 34

প্রথম ধাপ ঃ গ্রিড এর ৪ টি কোনাতে আমরা N/4 সাইজের ঘর মার্ক করে রাখবো।
4×4 এর জন্য মার্ক করা ঘরের সাইজ ঃ 1×1
8×8 এর জন্য মার্ক করা ঘরের সাইজ ঃ 2×2
12×12 এর জন্য মার্ক করা ঘরের সাইজ ঃ 3×3
1.JPGদ্বিতীয় ধাপঃ এবার আমরা মাঝাখানের ঘরগুলি, যেগুলি চার কোনার সাথে কানেক্টেড আছে, তাদের মার্ক করবো এভাবে ঃ 1.JPG
তৃতীয় ধাপঃ এবার আমরা মার্ক করা ঘরগুলিতে সংখ্যা বসাতে থাকবো। যে যেই ঘরে বসবে ( ১ থেকে শুরু করে ) তাকে সেই ঘরে বসিয়ে দিবো এভাবে ঃ
1চতুর্থ ধাপঃ এবার আমরা যেসব ঘর মার্ক করা নেই, সেগুলোতে বাকি সংখ্যাগুলি বসিয়ে দিবো রিভার্স অর্ডার এঃ
আমরা হিসাব করে দেখবো যে, সকল সারি, কলাম, কর্ণ বরাবর যোগফল ৩৪ হচ্ছে ( ম্যাজিক কন্সটেন্ট )।
একটি ৮x৮ এর জন্য দেখা যাক –>
1.JPG এখানে ম্যাজিক কন্সটেন্ট ঃ ২৬০

এবার আমরা দেখবো সিঙ্গেল-জোড় সংখ্যার জন্য। ( Single-Even ) সিঙ্গেল-জোড় হল এমন সংখ্যার গ্রিড যা ২ দিয়ে বিভাজ্য কিন্তু ৪ দিয়ে নয়। প্রথম সিংগেল-জোড় হল ৬x৬, কারন ২x২ ম্যাজিক স্কয়ার সম্ভব নয়।আমরা এখন এরকম গ্রিড এর জন্য দেখবো কিভাবে মানগুলি বসাতে হবে।
ম্যাজিক কন্সটেন্ট, c = [  6*( 6*6+1 ) ] / 2 = 222/2 = 111
প্রথমে আমরা ৬x৬ গ্রিড টিকে এভাবে চারভাগে চাগ করবো। এবার আমরা এই চার ব্লকে আমাদের নাম্বারগুলি বসাবো এভাবেঃ A ব্লকের রেঞ্জ হবে ১-৯, B ব্লকের রেঞ্জ হবে ১৯-২৭, C হবে ২৮-৩৬ এবং D হবে ১০-১৮। এরপরে আমরা ৩x৩ যেভাবে সল্ভ করেছি, সেইভাবে মানগুলি বসাবো।
এবার আমরা প্রতি ব্লকের জন্য মানগুলি বসাবো। প্রতি ব্লকের ১, ১০, ১৯, ২৭ এগুলোকে ১ ধরে আমরা আমাদের ৩x৩ ম্যাজিক স্কয়ার কমপ্লিট করবো। মান বসানোর সময় আমরা শুধুমাত্র ৩x৩ গ্রিডই বিবেচনা করবো।
আমাদের কাজ এখনও শেষ হয়নি। সিঙ্গেল-জোড় এর ক্ষেত্রে এই পার্টটি গুরুত্বপুর্ণ। আমরা কয়েকটি ঘর মার্ক করবো এবং কিছু ঘরের সাথে এক্সচেঞ্জ করবো এভাবেঃ
মার্ক করা ঘরগুলি আমরা এক্সচেঞ্জ করবো, তাহলেই আমাদের কাজ শেষ।
1.JPGএভাবে সবসময়, A এবং C ব্লকের মাঝে এক্সচেঞ্জ করতে হবে।
৬ এর থেকে বড় গ্রিড এর জন্য আমাদের A,C ছাড়াও B,D এর মাঝেও এক্সট্রা এক্সচেঞ্জ করতে হবে সেইম ১-১ মেথড এ, নিচের ছবিটি দেখলে আশা করি বুঝা যাবে ঃ
১৪x১৪ ঃ এক্সচেঞ্জ এর আগে।

১৪x১৪ ঃ এক্সচেঞ্জ এর পরে।

এবার একটি মজার ট্রিক ঃ magic square trick

Magic Square Part – 1

ম্যাজিক স্কয়ার কি? ( What is Magic Square? )

একটি  N x N ২ডি গ্রিড এ 1 থেকে N পর্যন্ত সংখাগুলোকে প্রতিটি কেবলমাত্র একবার ব্যবহার করে এমনভাবে সাজাতে হবে, যাতে ঐ গ্রিড এর প্রতিটি সারি, কলাম এবং কর্ণ গুলির যোগফল সমান হয়। এখন এরকম অনেকরকম সাজানো যেতে পারে, আমাদের এমন একটি স্টেট বের করতে হবে, যেটায় এই যোগফল সবচেয়ে কম হয়।

ম্যাজিক কন্সটেন্ট ( Magic Constant )

ম্যাজিক কন্সটেন্ট হল সেই সর্বনিম্ন সংখ্যা যেটা আমাদের গ্রিড এর জন্য বের করতে হবে। এখন গ্রিড N x N হলে,
ম্যাজিক কন্সটেন্ট, c = N * [ ( N2 + 1 ) / 2 ]
সুতরাং, N = 3 হলে, c = 3 * [  ( 9 + 1 ) / 2 ] = 3 * [ 10 / 2 ] = 3 * 5 = 15
কাজেই সব সারি, কলাম, কর্ণ এর যোগফল অবশ্যই ১৫ হতে হবে।

বেজোড় সংখ্যক গ্রিডের ম্যাজিক স্কয়ার সমাধান ( Solving Odd-Numbered Magic Square )

 প্রথম ধাপ ঃ গ্রিড এর প্রথম সারির একদম মাঝের কলামে ১ বসাই।

আমরা একটি 3 x 3 গ্রিড এর জন্য করবো। 7 x 7 এর জন্য 4th কলামে আমরা 1 বসাবো, এরকমভাবে।
বেজোড় সারি-কলামের ক্ষেত্রে আমরা সবসময় এভাবে শুরু করবো।
দ্বিতীয় ধাপঃ আমরা সবসময় sequencially ১ থেকে n পর্যন্ত বসাবো। এখন, ১ বসানোর পরে আমরা একবার কলাম, একবার সারি, এভাবে ধাপে ধাপে সিরিয়ালি বসাবো। নিচের উদাহরন দেখলে বিষয়টা বুঝা যাবেঃ
২ আমরা এভাবে বসাবো। ১ এর ঠিক পরের কলাম এবং সবার শেষের সারিতে ২ বসবে। এরপরে আমরা বাকি সংখ্যাগুলি ২ এর পরের কলাম, এবং আগের সারিতে, এভাবে বসাবো। অর্থাৎ আমরা নিচ থেকে উপরে উঠবো। এখন কথা হচ্ছে, ২ এর পরে আর কলাম নেই, এটা একটি ব্যাতিক্রম। এরকম ৩ ধরনের ক্ষেত্র আছে, যেগুলি একটু খেয়াল করলে আমরা সহজে হ্যান্ডেল করতে পারবো।
প্রথম ব্যাতিক্রমঃ আমরা এখন হিসাব অনুযায়ী ৩ নং কলাম এবং ২ নং সারিতে যাবো। কিন্তু আমাদের এটি গ্রিড এর বাইরে, কাজেই আমাদের ঐ সারিতে থাকবো ঠিকই, কিন্তু ডান দিকে না গিয়ে আমরা একদম সবচেয়ে বামদিকের ঘরে বসাবো।

ছবি দেখে আমরা বুঝতে পারবো ব্যাপারটা। ৩ এর জন্য ঘর গ্রিড এ নাই, কাজেই আমরা ২ নং সারিতে থাকবো ঠিকই, কিন্তু, একদম বামে চলে যাবো, আসলে ব্যাপারটা ঠিক বামে না, আমাদের যে দিকে যাবার কথা, তার বিপরীত দিকে যাবো। কাজেই কলাম ১ এ চলে আসলাম।
দ্বিতীয় ব্যাতিক্রমঃ
এখন আমাদের ৪ বসানোর জন্য আবার ঝামেলায় পরে গেলাম। আমাদের উপরের সারিতে এবং পরের কলামে যাওয়ার কথা, কিন্তু সেখানে আগে থেকেই ১ আমরা লিখে রেখেছি। এরকম অবস্থা হলে সেটি হল দ্বিতীয় ব্যাতিক্রম। এজন্য আমরা যেখানে বর্তমানে আছি, তার ঠিক নিচের সারিতে পরের মান বসাবো, এক্ষেত্রে কলাম একই থাকবে। অর্থাৎ ৪ কে আমরা ৩ এর নিচে বসাবো এভাবে ঃ
এখন আমরা দেখতে পাচ্ছি আমাদের মূল যেভাবে বসানোর কথা ছিল, আমরা সেরকম পথ পেয়ে গেছি 😀 । কাজেই আমরা ৪ থেকে উপরের সারি, পরের কলাম, এভাবে বাকি সংখ্যাগুলি বসাতে থাকবো যতক্ষন কোন ব্যাতিক্রম না পাই। অর্থাৎ ঃ
5এখন আমরা ৭ বসানোর জন্য দেখি যে একটি ব্যাতিক্রম হয়ে গেছে। হিসাব অনুযায়ী গ্রিডের বাইরে চলে যায়, এখন আমাদের এটা ১ নং ব্যাতিক্রমের মধ্যে পরে, কিন্তু যেহেতু, ৬ এর নিচে খালি একটি ঘর আছে, কাজেই, এটি আসলে ২ নং ব্যাতিক্রম। তাই আমরা ৬ এর ঠিক নিচে ৭ কে বসাবো এভাবে ঃ

এখন আমরা খেয়াল করলে দেখবো এখানে আসলে ১ নং ব্যাতিক্রমটি হয়েছে, কারন ৭ এর নিচে ঘর ফাঁকা নেই, আবার গ্রিড এর বাইরেও চলে যাচ্ছে। তাই আমরা উপরের সারির সবচেয়ে বামদিকে পরের সংখ্যাকে বসাবো এভাবে ঃ

তৃতীয় ব্যাতিক্রমঃ এখন আমরা আসি ৩ নং ব্যাতিক্রম এ। এটি আসলে এমনিতেই বুঝা যায়, আমাদের হিসাবে এখন যাওয়ার কথা উপরে, কিন্তু গ্রিড এর বাইরে হওয়াতে আমরা দেখবো ৮ এর নিচে ফাঁকা ঘর আছে কিনা, ফাঁকা নেই, কাজেই হিসাব মত আমাদের সবচেয়ে বামের ঘরে ব্যাতিক্রম ১ অনুযায়ী মান বসানোর কথা, কিন্তু এটিও গ্রিড এর বাইরে  -_- । এটিই আমাদের ৩নং ব্যাতিক্রম। এক্ষেত্রে আমাদের ঠিক পরের কলামের নিচ থেকে যে ঘর ফাঁকা পাবো, সেখানে মান বসায়ে দিবো।

সারি, কলাম, কর্ণ সকল ক্ষেত্রে যোগফল ১৫ এসেছে, কাজেই আমাদের উদ্দেশ্য সফল। এভাবে আমরা যেকোন বেজোর সংখ্যক গ্রিড এর জন্য ম্যাজিক স্কয়ার বানাতে পারবো।
 ** ৭ এর জন্য আমরা একটি ম্যাজিক স্কয়ার দেখি ঃ
এক্ষেত্রে ম্যাজিক কন্সটেন্ট, c = 175
আমরা ঠিক 3×3 এর মত করে 7×7 গ্রিডটি সাজালাম। এখন সারি, কলাম, কর্ণ সব যোগ করে আমরা ১৭৫ পাবো 🙂
ইটারেশন গুলিতে বুঝতে সমস্যা হলে, হাতে কলমে এভাবে একটি করলেই আশা করি সবাই বুঝে যাবে।

এখন আমাদের লাগবে জোড় সংখ্যক গ্রিডের জন্য সমাধান। আমাদের প্রথমে ১ টি জিনিস দেখা লাগবে আগে, আমরা প্রথমে দেখবো যে গ্রিডটি কে ভাঙলে যে গ্রিড পাওয়া যায়, সেগুলি জোড় নাকি বেজোড়। ২ টির ভিন্নতার কারনে ভিন্ন ভিন্ন মান আসবে। আমরা ২ টির জন্যই দেখবো এখানে ঃ part – 2

A* Search Algorithm for N-Puzzle

আমরা A* সার্চ দিয়ে ৮-পাযল প্রব্লেমটি সল্ভ করার চেষ্টা করবো। শুরুতে একটি স্ট্রাকচার এ আমরা আমাদের স্টেট সেইভ রাখার জন্য স্ট্রিং, পাথ সেইভ রাখার জন্য আরেকটি স্ট্রিং, হিউরিস্টিক, ডেপথ এসব সেইভের জন্য ইন্টিজার। তাহলে স্ট্রাকচার এমন দাঁড়ায় ঃ
struct puzzle {
string state, path;
int heuristic, depth, f;
আমরা f এর মাঝে depth + heuristic সেইভ রাখবো প্রতিটি স্টেট এর জন্য। এখন আমাদের কাজ হচ্ছে একটি প্রায়োরিটি কিউ নেয়া। প্রায়োরিটি কিউ তে আমরা f এর মান অনুসারে নোড ইনসার্ট করবো। তাহলে যার f এর মান কম, সেটি আমরা আগে প্রসেস করবো।

আমরা ইনিশয়াল এ আমাদের স্টেট এর পাথ এর জন্য “0” পুশ করতে পারি path স্ট্রিং এ, depth হবে 0 এবং f এর মান হবে, depth + heuristic = ( হিউরিস্টিক হিসাব করে যত হয়, আমরা তা বসাবো )।
চাইল্ড নোড জেনারেট এর পরে, চাইল্ড এর ক্ষেত্রে depth = parent.depth + 1 এবং path এর ক্ষেত্রে আমরা যদি UP ,মুভ দেয়ার ফলে চাইল্ডটি পেয়ে থাকি, তাহলে path = parent.path + “U” এভাবে পুশ করে দিবো।
আমরা যদি আমাদের ফাইনাল স্টেট পেয়ে যাই, তাহলে আমরা path স্ট্রিংটি রিটার্ন করে দিবো, এবং এই path থেকে পরবর্তীতে আমরা ইনিশিয়াল থেকে ফাইনাল স্টেট এর গ্রিড ও প্রিন্ট করতে পারবো।

২ টি ভেক্টর নিবো open এবং close নামের। open এর কাজ হচ্ছে, আমরা যেসব নোড এখনও এক্সপান্ড করিনি, সেগুলি রাখবো। আর close এর মাঝে আমরা, যেসব নোড এর এক্সপান্ড হয়ে গেছে,সেগুলো রাখবো।open, close এর কাজ হল, অপ্রয়োজনীয় নোড নিয়ে আমাদের মাথা ব্যথা আর করা লাগবেনা। আমরা প্যারেন্ট নোড থেকে চাইল্ড বানানোর পর দেখবো যে, এই চাইল্ড আগে থেকেই open এর মাঝে আছে কিনা, যদি থাকে, এবং ঐ open এর চাইল্ড যদি আমাদের এখন পাওয়া চাইল্ড এর চেয়ে ভালো অথবা সমান হয়, তাহলে আমরা এখনকার চাইল্ড আর নোড এ পুশ করবোনা। একই কাজ আমরা close এর খেত্রেও করবো।
আর এরকম কিছু না হলে আমরা সেটি কিউ তে পুশ করবো। এভাবে কাজ চলতে থাকবে, এবং আমরা আমাদের ফাইনাল স্টেট পেলে ব্রেক করে দিবো আর পাথ এর স্ট্রিংটি থেকে আমরা ইনিশিয়াল থেকে সহজেই পাথ ও প্রিন্ট করতে পারবো।

psudocode :  A* search
path_finding : Path

N Puzzle Problem – part 3

আগের পর্ব এখানে ঃ part – 1 , part – 2

মেমরি স্পেস ( Memory Space )

আমরা আমাদের মেমরি স্পেস কমানোর জন্য স্ট্রাকচারকে একটু মডিফাই করতে পারি। আমরা একটি স্ট্রিং এর মধ্যে আমাদের প্রতি স্টেট এর প্রয়োজনীয় সব জিনিস সেইভ রাখতে পারি। 


যেমন চিত্রের পাযলটির জন্য আমরা ২ডি অ্যাারে তে ভ্যালুগুলি না রেখে একটি স্ট্রিং এ এভাবে রাখতে পারি ঃ string a = “123046758” । এর মাধ্যমে আমরা পরে এটিকে ইচ্ছা করলে ২ডি গ্রিড এ কনভার্ট করে আমাদের কাজ করতে পারি। এখন আমরা আমাদের প্যারেন্ট ও এভাবে স্ট্রিং এর শেষে অ্যাড করে দিতে পারি। যেমন ঃ a = “123046758L” , এর মানে হচ্ছে এই স্টেট টি Left মুভ দেয়ার পরে আমরা পেয়েছি। আর আমাদের বাকি হিউরিস্টিক ভ্যালু সেইভ। এটাও আমরা একই ভাবে করতে পারি। ব্যাপারটা তোমাদের উপর ছেড়ে দিলাম। এখন আমরা একটি ম্যাপ রাখবো এরকম ঃ map < string, bool > visited;
এই ম্যাপ এর কাজ হচ্ছে আমাদের স্টেট গুলি চেক এ রাখা। মানে একই স্টেট এ যেনো আমরা আবার ফিরে না আশি। এর একটি সুবিধা হল আমাদের অপ্রয়োজনীয় বারতি স্টেট সেইভ রাখা লাগবেনা। আমরা একবার ভিজিটেড কোন স্টেট আবার পেয়েছি কিনা, এটা ম্যাপ এর মাধ্যমে এভাবে চেক করতে পারবো। আরো একটি কাজ আমরা করবো যে, যদি unsolvable state কখনো চলে আসে, তাহলে আমরা তাকে মার্ক করে রাখবো যে এটি বাজে স্টেট, এখানে আসলে সামনে আর একে এক্সপান্ড এর কোন প্রয়োজন নেই। আর আমরা কিউ তে একের বেশি স্টেট কখনো রাখছি না, কাজেই আমাদের মেমরি বেড়ে গিয়ে রান টাইম এরর খাওয়ার সম্ভাবনা কম।

টাইম কমপ্লেক্সিটি ( Time Complexity )

বি এফ এস, ডি এফ এস এর জন্য আমাদের টাইম কমপ্লেক্সিটি হবে O ( b) । এখানে,
b = branching factor ( একটি নোড থেকে সর্বোচ্চ যে কয়টি চাইল্ড নোড জেনারেট হতে পারে, আমাদের পাযল এর ক্ষেত্রে সর্বোচ্চ ৪ টি হতে পারে {উপরে, নিচে, ডানে, বামে} )।
d = depth ( আমাদের নোড জেনারেটের সর্বোচ্চ লেভেল, )


ইটারেটিভ ডিপেনিং সার্চ এর জন্য হবে O ( bd ), O ( b) এর পরিবর্তে। অর্থাৎ আমরা ডি এফ এস মত এগিয়ে যাবো এবং যখন দরকার হবে তখন আমরা নতুন চাইল্ড তৈরী করবো।

A* সার্চ সম্পর্কে জানার জন্য এখানে দেখতে পারো ঃ A* search

N Puzzle Problem – part 2

আগের পর্ব এখানে ঃ part – 1

আগের পর্বে আমরা পাযল এর solvable state নিয়ে কথা বলেছি। এখন আমরা দেখবো কিভাবে আগালে আমরা সহজে পাযল প্রব্লেম সল্ভ করতে পারি।


ছবিটি হল একটি ৮-পাযল এর স্টেট কিভাবে জেনারেট হবে তার একটি স্যাম্পল।

ডি এফ এস ( Depth First Search )

আমরা এটি সল্ভ এর জন্য প্রথমেই ভাবতে পারি ডি এফ এস (Depth_First_Search) এর কথা। এরজন্য আমরা একেকটি স্টেট থেকে সবচেয়ে ডীপ এ যাওয়ার চেষ্টা করবো। যদি আর কোন স্টেট এ না যেতে পারি, তাহলে আবার রিকার্সিভলি ব্যাক করে ফিরে আসবো। কিন্তু এর একটি বড় সমস্যা হল, আমাদের এই নোড জেনারেট এর ব্যাপারটি আমাদের ফাইনাল স্টেট থেকে অনেক অনেক দূরে নিয়ে যেতে পারে, যার কারনে আমরা এক্সপেক্টেড সলুশন পাবোতো নাই, উলটো আমাদের প্রোগ্রাম মেমরি ধারন করতে না পারার কারনে ক্র্যাশ করার সল্ভাবনা অনেক বেশি। কাজেই ডি এফ এস নরমালি করতে গেলে আমাদের জন্য তা সুবিধার হবেনা।

বি এফ এস ( Breadth First Search )

আমরা বি এফ এস এর মাধ্যমেও কাজ করতে গেলে সেইম আগের মতন প্রবলেম এ পরবো। অর্থাৎ BFS & DFS সেইম টাইপ নোড জেনারেট করবে। আমাদের তাই কিছু ট্রিক কাজে লাগাতে হবে যাতে অপটিমাল সলুশন পাওয়া যায়।

যাদের বি এফ এস, ডি এফ এস সম্পর্কে জানা নেই, তারা শাফায়েত ভাই এর ব্লগ থেকে দেখে নিতে পারো।
বি এফ এস
ডি এফ এস
একটি ছোট উদাহরন দেই। ধরি আমি পিযা ডেলিভারি দিবো একটি ১০ তলা বিল্ডিং এ। বিল্ডিং এর প্রতি তলায় আবার ১০ টি করে রুম আছে। একদিন কোন এক কারনে এলাকার মেয়র ঘোষনা দিল যে আজকে এই বিল্ডিং এর সবাইকে পিযা খাওয়ানো হবে । পুরো বিল্ডিং এ পিযা সার্ভের দায়িত্ব পরলো আমার ঘাড়ে -_- । এখন আমার কাছে ২ টি অপশন আছে। আমি প্রথেম ১ তলার সব রুম এ পিযা ডেলিভারি দিলাম, এরপরে ২ তলার সব রুম, এরপরে ৩ তলা… এভাবে ১০ তলা পর্যন্ত ডেলিভারি শেষ করলাম। আরেক কাজ করতে পারি যে, আমি প্রথমে ১ তলার একটি রুম এ পিযা দিয়ে ২ তলায় চলে গেলাম, সেখানের হাতের সবচেয়ে কাছের রুম এ পিযা দিয়ে আবার ৩ তলায়… এভাবে ১০ তলায় দেয়ার পরে আবার ১ তলায় নেমে পরর রুম থেকে একই ভাবে ডেলিভারি শুরু করলাম। এই ২ কাজের মধ্যে প্রথমটি হচ্ছে বি এফ এস, এবং পরেরটি হল ডি এফ এস। আশা করি কোনরকম আইডিয়া তোমরা পেয়েছো।

এখন আমরা কাজের কথায় আসি। আমরা ৮-পাযল সল্ভের ক্ষেত্রে আমাদের জন্য reachable state হল 9! / 2 = 1,81,440। এই ব্যাপারটি কিভাবে আসলো তা এখানে আলোচনা করছিনা। ১৫-পাযল এর জন্য এই মান 16! / 2 = 10,461,394,944,000 । বুঝতেই পারছো, ৮-পাযল শুধুমাত্র ব্রুটফোর্স দিয়ে করা গেলেও, ১৫ এর ক্ষেত্রে এটি সম্ভব না। এজন্য আমাদের লাগবে A* ( এ স্টার ) সার্চ বা ইটারেটিভ ডিপেনিং সার্চ ( Iterative Deepening A* Search or IDA* search )।
আমরা এখানে ডি এফ এস, বি এফ এস স্টাইল এর কাজ করবো, কিন্তু একটু আলাদাভাবে। আমরা একটি ফাংশন নিবো
f  ( n ) = g ( n ) + h ( n ), যেখানে,
f  ( n ) = n তম স্টেট এর ভ্যালু ( cost ) ।
g ( n ) = ইনিশিয়াল স্টেট থেকে  n তম স্টেট পর্যন্ত দূরত্ব।
h ( n ) = হিউরিস্টিক জেনারেশন এর জন্য একটি ফাংশন।
হিউরিস্টিক হল এমন একটি টেকনিক, যা আমাদের অপটিমাল সলুশন খুঁজে বের করতে সাহায্য করে। আমাদের পাযল সল্ভিং এর ক্ষেত্রে A* সার্চে আমরা এই হিউরিস্টিক ব্যবহার করবো। সহজ কথায়, এটি সিম্পল একটি ভ্যালু যা প্রতিটি স্টেট এর জন্য বের করে আমরা আমাদের সুবিধামত সামনে এগিয়ে যাবো।
ছবিটিতে আমরা দেখতে পাচ্ছি যে, ইনিশিয়াল স্টেট থেকে ৪ টি নতুন স্টেট জেনারেট হয়েছে। আমরা A* সার্রচের জন্য এই প্রতিটি চাইল্ড স্টেট এর হিউরিস্টিক ভ্যালু বের করবো। এরমধ্যে যেই ভ্যালু সবার চেয়ে কম, আমরা সেই চাইল্ড কে পরবর্তী স্টেট এর জন্য এক্সপান্ড ( Expand or Branching; creating next child for further calculation ) করবো।


হিউরিস্টিক ব্যবহারের সুবিধা ঃ

অপটিমাল সলুশন সহজে স্বল্প সময়ের মধ্যে বের করে নিয়ে আসা যায়,  এবং অপ্রয়োজনীয় নোড মেরে ফেলে ( removal of unnecessary nodes )।


এখন আমরা আলোচনা করবো কোডিং নিয়ে। প্রথমেই আমরা ইনিশিয়াল স্টেট থেকে নোড এক্সপান্ড করবো। এখন যেকোন একটি হিউরিস্টিক ফাংশন আমরা ব্যবহার করবো। ইনিশিয়াল স্টেট এ g ( n ) = 0। এই স্টেট এর জন্য আমরা h ( n ) , f ( n ) বের করবো। আমরা এই প্যারেন্ট কে এক্সপান্ড করে কতগুলি চাইল্ড নোড পাবো। এবার কাজ হচ্ছে প্রতিটি চাইল্ড নোড এর জন্য আমরা f ( n ) বের করবো। এবং এর মধ্যে সবচেয়ে কম যার মান, আমরা সেটি নিয়ে সামনে এগিয়ে যাবো। এই সামনে এগিয়ে যাওয়ার মানে হচ্ছে একটি কিউ তে আমরা স্টেট গুলি জমা রাখবো। এখন আমরা এভাবে একটি স্ট্রাকচার ডিক্লার করতে পারি–>
struct node
int grid [ N ] [ N ] ;            // 2D grid to save the state
int h_val;                            // heuristic value of the state
char parent ;                     // parent =  { ‘U’, ‘D’, ‘L’, ‘R’ }
এখানে grid ২ডি অ্যাারেতে আমরা আমাদের পাযল এর স্টেট এর ভ্যালুগুলি রাখবো। h_val এর মাঝে থাকবে এই গ্রিড এর জন্য জেনারেট করা হিউরিস্টিক ভ্যালু। parent ভ্যারিয়েবল এর মাঝে আমরা প্যারেন্ট স্টেট থেকে কোন মুভ এ এই স্টেট এ এসেছি সেটি সেভ রাখবো। (এ ব্যাপারটি আমাদের জানা থাকলে ব্যাকট্র্যাক এর ক্ষেত্রে সুবিধা হবে)
এখন আমাদের একটি কিউ লাগবে যেখানে এই নোডগুলি রাখবো আমরা। শুরুতে আমরা কিউ তে আমাদের ইনিশিয়াল স্টেট এর যে পাযল দেয়া আছে তা রাখবো। এরপরে আমরা কিউ থেকে এই নোড পপ করে এর চাইল্ড জেনারেট করবো। এখন চাইল্ড জেনারেট এর সাথে সাথে আমরা প্রত্যেক চাইল্ডের হিউরিস্টিক ও জেনারেট করবো। এরপরে আমরা এই হিউরিস্টিক এর মধ্যে যার মান কম, সেই চাইল্ডকে কিউ তে পুশ করবো। এখন নরমাল বি এফ এস এ আমরা কিন্তু সব চাইল্ড ই পুশ করতাম। এখানেও তা করা যাবে, কিন্তু ১৫-পাযল এর ক্ষেত্রে খুব কষ্টকর হবে ব্যাপারগুলি ঠিকমত হিসাব নিকাশ করা। কারন, মেমরি, টাইম কমপ্লেক্সিটি এর ব্যাপারগুলি আমাদের মাথায় রাখা লাগবে। আর যেহেতু আমরা A* সার্চ ব্যবহার করছি, আমাদের অপ্রয়োজনীয় চাইল্ড নোড জেনারেট না করাই উত্তম। যখন দরকার হবে আমরা তখন জেনারেট করবো। নিচের ছবিটি খেয়াল করি ঃ 


ইনিশিয়াল স্টেট টি থেকে আমরা ৩ টি চাইল্ড নোড পেলাম। এদের f ( n ) বের করলাম। এবং এরমধ্যে সবচেয়ে কম যার মান, তাকে আমরা পরবর্তীতে কিউ তে পুশ করবো। এখন যেহেতু আমরা কিউ তে বাকি ২ টি নোড পুশ করছিনা, কাজেই আমাদের মেমরি স্পেস এক্ষেত্রে অনেক বেঁচে যাবে। কিউ তে চাইল্ড নোডটি পুশ এর সময় আমরা parent ভ্যারিয়েবল এর মধ্যে ‘L’ ক্যারেক্টারটি রাখবো, কারন 4 কে Left এ নেয়ার মাধ্যমে আমরা এই চাইল্ড নোডটি পেয়েছি। আমরা বলেছিলাম যে আমাদের এই ভ্যারিয়েবল এর মান ব্যাকট্র্যাকিং এর কাজে লাগবে। আমরা সেটি এখন আলোচনা করবো। আশা করি, এ পর্যন্ত সবকিছু বুঝে গেছো। এখন ধরি আমাদের প্যারেন্ট নোডের f এর মান এর চেয়ে প্রতিটি চাইল্ড নোডের f এর মান বেশি আসলো। এখন আমরা যেই চাইল্ড ই নেই না কেনো, ব্যাপারটি কিন্তু আসলে খারাপ হবে, কারন কম f এর মান থেকে আমরা আবার বেশি মানের দিকে আগাচ্ছি। আমাদের মেইন টার্গেট হচ্ছে যত কম মুভ এ পাযল সল্ভ করা যাএ, অর্থাৎ আমাদের f এর মান কমাতে হবে। এখন যদি এরকম অবস্থা হয়, তখন আমাদের সেই চাইল্ড নোড থেকে আবার প্যারেন্ট এ ব্যাক করতে হবে।
এখন আমাদের কাছে তো বর্তমান নোড ছাড়া আর কোন নোড নেই, তাহলে কিভাবে প্যারেন্ট এ ব্যাক করবো? এরজন্য আমাদের তখন দেখতে হবে parent ভ্যারিয়েবল এর মধ্যে কি আছে।যা থাকবে তার বিপরীত স্টেট দিয়ে ব্যাক মুভ করলে আমরা আমাদের প্যারেন্টকে আবার পাবো। মানে যদি ভ্যারিয়েবল এ থাকে ‘L’, তাহলে আমাদের ‘Right’ মুভ করতে হবে আগের স্টেট পাওয়ার জন্য। এখন আগের স্টেট পাবার পরে আবার আমরা সব চাইল্ড জেনারেট করবো। এখন যেই চাইল্ড আগে নিয়েছিলাম, সেটি না নিয়ে, তার ঠিক পরের হিউরিস্টিক মান অনুযায়ী আমরা চাইল্ড নিবো।


ধরি আমাদের ইনিশিয়াল স্টেট এ f = 45। এর ৩ টি চাইল্ড জেনারেট করি।


৩ টি চাইল্ডের মধ্যে f = 42 আমরা সিলেক্ট করবো এবং একে কিউ তে পুশ করে এক্সপান্ড করবো।


এখন খেয়াল করে দেখি যে, আমরা নতুন যে ৩ টি চাইল্ড পেলাম, তাদের প্রত্যেকের  f এর মান প্যারেন্ট এর f এর মান থেকে বেশি। কাজেই আমাদের এই নোড এক্সপান্ড করা আসলে ঠিক হয়নি। তাই আমাদের ব্যাকট্র্যাক করতে হবে।


ব্যাকট্র্যাক করে আগের অবস্থায় ফিরে আসলাম। এখন আমরা নিবো f = 43  কারন, আগের f এর মানের ঠিক পরবর্তী মান এটি।


এবার আমরা এই নোডকে এক্সপান্ড করে নতুন চাইল্ড পেলাম, যার মধ্যে একটির f এর মান 41, যা আগের তুলনায় ভালো মান আমাদের প্রব্লেম সল্ভিং এর জন্য। তাই আমরা এখন এটি নিয়ে কাজ করবো।

এই ছিল আসলে ব্যাসিক কোডিং এর হিন্টস। একেকজনের কোডিং স্টাইল অনুযায়ী কোডের আইডিয়া চেঞ্জ হবে, আরো বেটার আইডিয়া আসবে। পরবর্তী পর্বে আমরা দেখবো এই সার্চিং এর মধ্যে কিছু অপটিমাইজেশন আনা যায় কিনা।

পরবর্তী পর্ব : part – 3