Defective Chess Board Problem

Defective Chess Board Problem কি, Problem টা solve করার উপায় নিচের দুইটি link দেখে আসলেই আশা করি clear হয়ে যাবে। 

লিঙ্ক ১

লিঙ্ক ২  (tutorial টা সম্পূর্ণ দেখবো, কোন অংশ skip করব না)

এখন কথা হচ্ছে এটা code এ রূপান্তর করবো কিভাবে?!  তো এর জন্য কিছু Prerequisite আছে , সেগুলো হলঃ

১) স্থানাঙ্ক জ্যামিতি এর উপর ধারণা থাকা

২) Recursion এর উপর ধারণা থাকা

যাইহোক...এখন এটা সল্ভ করার উপায়টা দেখি। এটা আমরা চারটা step এ সল্ভ করবো।  কোড implement এর মূল অংশ শুরু হবে tutorial এর ৭ মিনিট ৪৫ সেকেন্ড এর পরের ব্যাখ্যা থেকে। এখানে আমরা দুইটা condition খেয়াল রাখবো-

a) কোন Quadrant এ Defect point পেলে ঐ Quadrant এর start point টা আবার call করতে থাকবো যে পর্যন্ত না board এর size = 1 হয়। Board এর size 1 হলেই recursion function value return করা শুরু করবে।

b) যে Quadrant এ defect point পাব না ঐ Quadrant এর start point এ একটা defect point বসাবো। যেহেতু এখানে এখন একটা defect point যুক্ত হইল তাই condition 'a' এখানে repeat হবে।

Recursion function -  

TileBoard(int Start_x, int Start_y, int x, int y, int Size)

এখানে Start_x এবং Start_y কোন Quadrant এর start point এর পজিশন, x এবং y হচ্ছে defect point এর পজিশন, Size chess board এর size.

Step 1: 1st Quadrant (top left) এর জন্য-

if (x<Start_x+s && y<Start_y+s)  ///condition 'a'
        TileBoard(Start_x, Start_y, x, y, s);
    else
    {
        b[Start_x+s-1][Start_y+s-1] = t; ///condition 'b'
        TileBoard(Start_x, Start_y, Start_x+s-1, Start_y+s-1, s); ///repeat of condition 'a'
    }

Step 2: 2nd Quadrant (top right) এর জন্য-

if (x<Start_x+s && y>=Start_y+s)  ///condition 'a'
        TileBoard(Start_x, Start_y+s, x, y, s);
    else
    {
        b[Start_x+s-1][Start_y+s] = t; ///condition 'b'
        TileBoard(Start_x, Start_y+s, Start_x+s-1, Start_y+s, s);
    }

Step 3: 3rd Quadrant (bottom left) এর জন্য-

 if (x>=Start_x+s && y<Start_y+s)  ///condition 'a'
        TileBoard(Start_x+s, Start_y, x, y, s);
    else
    {
        b[Start_x+s][Start_y+s-1] = t; ///condition 'b'
        TileBoard(Start_x+s, Start_y, Start_x+s, Start_y+s-1, s);
    }

Step 4: 4th Quadrant (bottom right) এর জন্য-

 

 if (x>=Start_x+s && y>=Start_y+s)  ///condition 'a'
        TileBoard(Start_x+s, Start_y+s, x, y, s);
    else
    {
        b[Start_x+s][Start_y+s] = t; ///condition 'b'
        TileBoard(Start_x+s, Start_y+s, Start_x+s, Start_y+s, s);
    }

আশাকরি কোডটা কিভাবে করতে হবে এটা অনেকটাই clear হয়েছে। তাই নিজে নিজে চেষ্টা করবো কোডটা লিখার।

তারপরও সমস্যা হলে নিচের লিঙ্কে কোড দেওয়া হল...

The Code (in C++) 

Happy Coding!!! :)