Master Your Knowledge About N-Queen Problem (With Source Code)

N QUEEN প্রব্লেম হলো এমন একটি সমস্যা যেখানে N সংখ্যক QUEEN কে একটি (N X N) চেসবোর্ড এ এমনভাবে সাজানো যেন পরপর দুটি QUEEN এর মধ্যে ROW বরাবর , COLUMN বরাবর এবং DIAGONAL বরাবর কোনো সংঘর্ষ না বাঁধে|এই সমস্যাটি Backtracking কৌশল অবলম্বন করে সমাধান করা যায় |

Backtracking হলো এমন একটি কৌশল যা কতগুলো শর্ত মেনে একটি সমস্যার সন্তোষজনক সমাধান বের করে |

সহজ ভাষায়, Backtracking করে যখন কোনো সমাধান খোঁজা হয় তখন এটি কতগুলো শর্ত নিয়ে কাজ শুরু করে এবং যদি সেই শর্তগুলোর কোনো একটি, কোনো একটি নির্দিষ্ট জায়গায় এসে মিথ্যে হয় তাহলে, পিছনে ফিরে আবার শর্তমতো খোঁজার কাজ অব্যাহত রাখে |

N QUEEN এর N হচ্ছে এর QUEEN সংখ্যা | সধারনত, আমরা হিসেবে শুরু করি
N = 4 এর জন্য | অর্থাৎ, 4 টি QUEEN এর জন্য | কারণ,

N = 1 এর ক্ষেত্রে এটি একটি TRIVIAL SOLUTION দেয় |
N = 2 এর ক্ষেত্রে N — QUEEN সম্ভব নয় |
N = 4 এর জন্য একটি সমাধান হচ্ছে, (3 ,1 ,2 ,4 )

A 4-Queen Solution

একদম শুরু থেকে বিশ্লেষণ করা যাক,

ধরা যাক , N = 4 অর্থাৎ, QUEEN এর সংখ্যা 4 টি } তাহলে, সহজেই বলা যায় চেসবোর্ডটি 4X4 বিশিষ্ট | এখন, 1 থেকে 4 পর্যন্ত 4 ROW এবং 4 COLUMN বিশিষ্ট একটি চেসবোর্ড তৈরি করা হলো |

An empty chess-board for the implementation of 4-Queen

এখন, সাধারণ চিন্তা করলে যদি ধরা হয়, শুধুমাত্র প্রথম শর্তটি সত্য অর্থাৎ,

“একই ROW বরাবর দুটি QUEEN পরপর কখনো বসবে না”

কিন্তু, একই COLUMN বরাবর বসতে পারবে| তাহলে, ব্যাপারটি এমন দাঁড়ায়,

Applying only the row condition

এখন যদি ২য় শর্তটি প্রযোজ্য করা হয়, অর্থাৎ,

“একই COLUMN এ 2 টি QUEEN পরপর বসবে না|”

সেক্ষেত্রে, একটি পথে বাকি থেকে যায় এবং সেটি হলো QUEEN গুলোকে DIAGONAL এ পরপর বসানো| সেক্ষেত্রে,

Applying the column condition

কিন্তু, এভাবে করলে সমাধান এসে দাঁড়ায়, 4 ^ 4 = 256 সংখ্যক বার|
যা মোটেও একটি সন্তোষজনক সমাধান নয় |

এখন তৃতীয় শর্তটি প্রযোজ্য করা যাক,

“একই DIAGONAL বরাবর পরপর দুটি QUEEN বসবে না |”

তৃতীয় শর্তটি প্রযোজ্য করার সাথে সাথে N — QUEEN এর সমাধান এসে দাঁড়ায়
4 টি QUEEN (1 , 2 , 3 , 4 ) এর Permutation আকারে | অর্থাৎ, 4! = 24 সংখ্যক বার | এই 24 টি সমাধানের মধ্যে থেকে এমন দুটি সমাধান উঠে আসে যা উপরোক্ত এই তিনটি শর্ত পূরণ করে | সে দুটি সমাধান হলো,

2 possible solution of 4-Queen

এই 24 টি Permutation একটি Solution Tree / Permutation Tree গঠন করে | Sum Of Subset ব্যবহার করে এই ট্রি টি গঠন হয় |

Fig(2.6) — Solution State Tree Of 4 — Queen

এখানে প্রত্যেকটি Permutation এক একটি অবস্থা / STATE এবং তার থেকে মাত্র দুটি অবস্থা সত্য (সবুজ রং দিয়ে চিহ্নিত) |

এখন, পুরো কাজটি প্রথম থেকে শেষ পর্যন্ত কিভাবে হয় দেখা যাক |

বাখ্যা:-

প্রথমে, একটি সম্পূর্ণ খালি চেসবোর্ড এর সর্ব বাম থেকে কাজ শুরু করতে হবে | প্রত্যেকটি COLUMN এ আমরা একটি করে QUEEN বসাবো এবং যদি পর পর দুটিতে সংঘর্ষ বাঁধে তাহলে ওই একই COLUMN এ এমন একটি ROW খুঁজবো যেখানে সংঘর্ষ বাঁধে না |এমন ROW এবং COLUMN না থাকে তাহলে, Backtrack করবো এবং রিটার্ন করবো FALSE |

ধরি, 4 টি QUEEN (Q1 ,Q2 ,Q3 ,Q4 )
সর্বপ্রথম (Q1) চেসবোর্ড এর (1,1) পসিশনে বসানো হলো |
তারপর, (Q2) কে অর্থাৎ ২য় QUEEN কে চেসবোর্ড এর (1,2) পসিশন এ বসানো হলো| কি দেখা যাচ্ছে ?

Step 1

দুটি QUEEN পর পর একই DIAGONAL এ অর্থাৎ, এদের মধ্যে সংঘর্ষ হচ্ছে | তাই ওই একই ROW এর পরবর্তী পসিশন (1,3) এ রাখতে হবে | দেখা যাচ্ছে এবার (Q1) এবং (Q2) এর মধ্যে সংঘর্ষ নেই | তাই, আমরা সামনে এগোতে পারি |

Step 2

কিন্তু, পরবর্তীতে, লক্ষ্য করলে দেখা যায় (Q3) কে কোনো পসিশন এ বসানো যাচ্ছেনা |
( ‘X’ দিয়ে সেটি বুঝানো হয়েছে )|

Step 3

তাই Backtrack করে (Q2) কে আরেক ঘর এগিয়ে (1,4) পসিশনে রাখবো | সেক্ষেত্রে,

(Q3) এর জন্য একটি গ্রহণযোগ্য জায়গা তৈরি হয় সেটি হচ্ছে (3,2) |

কিন্তু, এবার আরেকটি সমস্যা সামনে আসবে | (Q4) কে রাখার জন্য কোনো গ্রহণযোগ্য জায়গা নেই|( ‘X’ দিয়ে সেটি বুঝানো হয়েছে )

এখন, আবার Backtrack করে (Q3) এর কাছে যাবো কিন্তু (Q3) কে (3,3) এবং (3,4) কোনো পসিশনেই রাখা সম্ভব নয় | Backtrack করার জন্য চলে গেলাম (Q2) এর কাছে | কিন্তু, (Q2) কে সড়ানোর মতো আর কোনো জায়গা নেই | তাই, Backtrack করার জন্য আবার সবার উপরে (Q1) এর কাছে চলে যেতে হবে | এবং (Q1) কে (1, 2) পসিশন এ রাখতে হবে |

Step 6

এখন, (Q2) কে আবার (2,4) এ রাখবো | তার কারণ হচ্ছে, (2,1),(2,2) এবং (2,3) কোনোটিই তার জন্য গ্রহণযোগ্য জায়গা নয় | ( ‘X’ দিয়ে সেটি বুঝানো হয়েছে ) | (Q3) বসবে (3,1) পসিশন এ এবং এবার দেখা যাচ্ছে, (Q4) এর জন্য একটি গ্রহণযোগ্য জায়গা চেসবোর্ড এ তৈরি হয়েছে | সেটি হলো, (4,3) | এ ক্ষেত্রেও বলে দিতে চাই যে, (Q4) কে (4,1) এবং (4,2) পসিশন এ বসানো সম্ভব নয় | ( ‘X’ দিয়ে সেটি বুঝানো হয়েছে )

Step 7

Step 8

অর্থাৎ একটি সমাধান খুঁজে পাওয়া গেলো এবং সেটি হচ্ছে, (2,4,1,3)
আরেকটি সমাধান পেতে হলে এই একই কাজ করে যেতে হবে এবং সমাধান পাওয়া যাবে (3,1,4,2)
(এসো নিজে করি)
(2,4,1,3) এর Solution Space Tree হবে,

Partly solution state tree of 4- Queen

Draw the remaining part in your way.

Source Code :

ROW & COLUMN CHECK :

সোর্স কোড লেখার সময় যে কথাটি সবার প্রথমে চিন্তায় আসবে সেটি হলো আমি কিভাবে ROW ,COLUMN এবং Diagonal চেকগুলো করবো ? আসলেই তো? কিভাবে করবো ? প্রথম থেকে পড়ে আসলে অনেকেই হয়তো সেই উত্তর এর অনেকটাই খুঁজে পেতে সক্ষম হয়েছ | কিভাবে ?
এসো এবার বিস্তারিত বলা যাক |

মনে আছে সেই Permutation এর কথা ? যেখানে 4 QUEEN এর প্রত্যেকটি শর্ত মেনে ২৪টি এমন অবস্থা/STATE তৈরি হয়েছিল যার থেকে মাত্র ২টি গ্রহণযোগ্য সমাধান পাওয়া গিয়েছিলো|
এখন প্রশ্ন আসতে পারে, কেনোই বা আমরা Permutation করবো ? কারণ, আমরা জানি, N সংখ্যক নম্বর এর Permutation করা হলে, N! সংখ্যক Permutation বের হয় | যেমন,

(1,2,3,4) এই 4 টি নম্বর এর Permutation করা হলে 4!=24 টি Permutation সম্ভব এবং এই ২৪টির প্রত্যেকটি একে ওপরের চেয়ে আলাদা বা ভিন্ন|

1234 1243 1324 1342…1432…2413…3142… 4123 4132 4213 4231…4312

এই যে 24 তীর প্রত্যেকটি একে ওপরের চেয়ে ভিন্ন তার অর্থ কি দাঁড়াচ্ছে জানো?
ধরো, এই Permutation গুলোর মধ্যে যেকোনো একটি তুমি চেসবোর্ড এ বসাবে | মনে করো 1234 নিলাম| বসিয়ে দেখো তো | আবার 4132 চেসবোর্ড এ বসাও| এভাবে অন্যগুলো দিয়েও টেস্ট করে দেখতে পারো |

Permutation Check

একটি জিনিস খেয়াল করেছো ? প্রতিবারই একই ROW এবং COLUMN এ কোনো QUEEN বসছে না| এবং Permutation এ ( 1134 ,1244 ) বলে কিছু নেই | অর্থাৎ আমরা যদি N সংখ্যক QUEEN এর Permutation বের করতে পারি তাহলেই ROW এবং COLUMN চেক করা হয়ে যাবে | সেই কাজটি আমরা করবো (next_permutation) নামের একটি c++ ফাঙ্কশন দিয়ে |

DIAGONAL CHECK :

Diagonal চেক বলতে আমরা দুটি জিনিসকে বুঝি |
একটি Left to Right Diagonal এবং আরেকটি Right to Left Diagonal |

Right to Left Diagonal :

একটি অবস্থা বিবেচনা করা যাক | মনে করি, একটি 4 X 4 চেসবোর্ড এ (1,4) এবং (3,2) পসিশন এ দুটি Queen বসানো | দুটি Queen কি একটি আরেকটির সঙ্গে সংঘর্ষে জড়াচ্ছে ? হাঁ | কিন্তু, এখন আসল প্রশ্ন হলো কিভাবে টেস্ট হবে ? দেখোতো, এর মাঝে কোনো ভাবে আমরা একটি সূত্র বানাতে পারি কিনা ? (1 , 4 ) এর 1 হচ্ছে একটি One Dimentional Array এর ইনডেক্স নম্বর এবং 4 হচ্ছে ওই Array এর 1 নম্বর ইনডেক্স এর মান অর্থাৎ Array[i] = 4 ( i = 1 ) | ঠিক একই ভাবে, (3 , 2 ) এর 3 হচ্ছে Array এর ইনডেক্স নম্বর এবং 2 হচ্ছে ওই Array এর 3 নম্বর ইনডেক্স এর মান অর্থাৎ Array[j] = 2 ( j = 3 ) | তাহলে সূত্র হবে,

i — j == Array[j] — Array[i] => 1–3 == 2–4 => -2 == -2

সাজিয়ে লিখলে,

i — Array[j] == j — Array[i] => 1–2 == 3–4 => -1 == -1

রিটার্ন করবে False|

অর্থাৎ ইন্ডেক্সগুলোর বিয়োগফল এবং তাদের মানের বিয়োগফল সমান হলে বুঝতে হবে Right To Left Diagonal এ দুটি Queen একে ওপরের সাথে সংঘর্ষে আছে |

Right to Left Diagonal Check

Left To Right Diagonal :

আরেকটি অবস্থা বিবেচনা করা যাক, (1 , 2 ) এবং (3 , 4 ) |
যেখানে, (1 , 2 ) এর 1 হচ্ছে একটি One Dimentional Array এর ইনডেক্স নম্বর এবং 2 হচ্ছে ওই Array এর 1 নম্বর ইনডেক্স এর মান অর্থাৎ Array[i] = 2 ( i = 1 ) | ঠিক একই ভাবে, (3 , 4 ) এর 3 হচ্ছে Array এর ইনডেক্স নম্বর এবং 4 হচ্ছে ওই Array এর 3 নম্বর ইনডেক্স এর মান অর্থাৎ Array[j] = 4 ( j = 3 ) | তাহলে উপরের সূত্রটি যদি প্রয়োগ করা হয় তাহলে সেটি False রিটার্ন করবে না | এবার সূত্রটি একটু ঘুরিয়ে লিখলে দেখা যাক কি হয় |

i — j == Array[i] — Array[j] => 1–3 == 2–4 => -2 == -2

সাজিয়ে লিখলে,

i + Array[j] == j + Array[i] => 1 + 4 == 3 + 2 => 5 == 5

রিটার্ন করবে False |

অর্থাৎ ইন্ডেক্সগুলোর বিয়োগফল এবং তাদের মানের বিয়োগফল সমান হলে বুঝতে হবে Left to Right Diagonal এ দুটি Queen একে ওপরের সাথে সংঘর্ষে আছে |

উল্লেখ যে, Right To Left Diagonal হলে Array [j] — Array [i] হবে | এবং Left to Right Diagonal হলে Array [i] — Array [j] হবে |

Left to Right Diagonal Check

N-Queen Source Code