Backtrack & N Queen

[ এইখানের সব চরিত্রই কাল্পনিক , বাস্তবতার সাথে কাছে , উপরে , নিচে , দূরে কোন খানেই কোন মিল নাই । গল্পে তাই বাস্তবতার সাথে কোন মিল ,  কোন লজিক খুঁজে বেড়ানো  অমূলক । ]    

হাতে একটা DLSR আছে আর কোন মেয়ে পটবে না এমনটা হবে না । রেদোয়ান এরও তাই সখিনাকে পটাইতে টাইম লাগল না । স্বাধীনতার পাওয়া থেকে স্বাধীনতা রক্ষা করা কঠিন । এত এত কম্পিটিশন এর যুগে তাই গার্লফ্রেন্ড রক্ষা করা কঠিন । কত কত থ্রেড আনাচে কানাচে । শিশির ভাবুক ছেলে , মনে গভীরের আবেগ বুঝতে তাই দেড়ি হয়ে গেছিল । ভার্সিটির লিফটে মনের আদান প্রদান হইলেও কিঞ্চিৎ সংকোচের কারণে রেদোয়ান এর কাছে একটু পিছিয়ে ছিল । সখিনা আর রেদোয়ান ক্লাসমেট , শিশির তাদের সিনিয়র । নানা ছালচাতুরে রেদোয়ান শিশির কে ধোঁকা দিয়ে সখিনাকে আগলাইয়া রাখলেও বহুমুখী প্রতিভার অধিকারী শিশির যদি কোনভাবেই সখিনার কাছে মনের ভাব পৌঁছাইয়া দিতে পারে , অতি ভাল ফ্রেন্ড থেকে শুধু  ফ্রেন্ড  সম্পর্কে  সখিনা রেদোয়ানকে নামাইয়া নিয়া আসলেও আসতে পারে । তাই কোন ভাবেই রেদোয়ান শিশির এর  কোন প্রকার নোট , হৃদয় দিয়ে আঁকা ছবি সখিনার কাছে পৌঁছাতে দিতে পারে না । এমনেই সহপাঠী বান্ধবী মাত্রই সিনিয়র ভাইয়াদের প্রতি কিঞ্চিৎ দুর্বল থাকে তারপর যদি সিনিয়র বহুমুখী প্রতিভার অধিকারী হয় । বলা রাখা ভাল আমরা এমন একটা যুগের কথা বলতেছি এইযুগে  লিফট , হাতে DLSR থাকলেও মোবাইল ফোন নাই , এমনকি ফেসবুক ও নাই । এই যুগে ছেলে যতই আধুনিক হোক আশে-পাশে  জুনিওর ছেলে থাকলে সৎ সাহস নিয়ে কোন মেয়ের সাথে কথা বলতে সাহস করে না ।  

যেভাবেই হোক রেদোয়ানকে সখিনাকে রক্ষা করতে হবে যেকোন ধরণের আলাপ-চারিতা   শিশির এর কুনজর থেকে । রেদোয়ান ঠিক একটা N*N rectangle Grid কল্পনা করল সখিনার আসে-পাশে একদম দাবা ঘরের মত । এই ঘর গুলা যদি রেদোয়ান গার্ড দিয়ে রাখতে পারে তাহলে শিশির কখনই সখিনার ধারের কাছেও আসবে না ।  রেদোয়ান এর কিছু স্পেশাল ফ্রেন্ড আছে । যারা সব সময় ভাবেই রেদোয়ান এর লাইফে আসে শুধু দুইজন মানুষ , এক সখিনা আর সে । আর কেউ নাই , আর কেউ থাকবে তা ও কল্পনাও করতে পারে না । তারা আবার দাবা খেলার মন্ত্রীর মত গার্ড দিতে পারে । মানে কেউ কোন ঘরে থাকলে মন্ত্রী যেমন এট্যাক করে তেমন করে গার্ড দিয়ে রাখতে পারে সখিনাকে যেন শিশির কোন ভাবেই সখিনার কাছে আসতে না পারে । এমন কিছুটা 

 

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

সুপার বুড়া ভাইয়া মাহির খুবই গুরু গম্ভীর মানুষ । প্রোগ্রামিং ছাড়া কোন কথা বলেন না । সব কিছু শুনে অনেকক্ষণ চিন্তা ভাবনা করে বলল “ শুন রেদোয়ান তুমি যে প্রবলেম এ আছ , এইডা খুবই পুরাতন ক্যাসিক্যাল N Queen Problem , যা ১৮৫০ সালেই “Franz  Nauck” নামের এক ভদ্রলোক সমাধান দিয়ে গেছেন । এই সমাধান তোমাকে বুঝতে হবে , শুধু বুঝতে হবে না অন্তর দিয়া ফিল ও করতে হবে তাইলেই তুমি সখিনাকে শিশির এর কুনজর থেকে রক্ষা করতে পারবা ”  

আমরা যে যুগে আছি এইডা হইল ভাল যুগ , এইখানে মানুষ মনের মধ্যে ভয়-ভিতি নিয়ে প্রেম-পিরিতি করে কখন কে এসে প্রেমিকা  ভাগাইয়া নিয়া যায় । তাই যতই কঠিন হোক রেদোয়ানকে বুঝতে হবে N-Queen  প্রবলেম এর সমাধান , নিজের জন্য , নিজের অনাগত নাতি-নাতনীর জন্য যে তারা রেদোয়ানকে দাদু , সখিনাকে দিদা ডাকতে পারে ।

N Queen Problem কি ?

N Queen problem হল একটা N*N দাবা বোর্ডে কত ভাবে N টা queen বসানো যায় যাতে তারা একজন অপরজনকে কোন ভাবে এট্যাক না করে । N Queen problem এর solution এর মাধ্যমে আমরা খুব সহজেই যত কম্বিনেশন আছে তা পেয়ে যেতে পারি । 

Solution :  

Queen যেভাবে এট্যাক করে তাতে প্রতিটা Row এবং column এ মাত্র একজন করে queen  বসতে পারে এবং সাথে সাথে আমাদের চেক করে রাখতে হবে diagonal ভাবে কোন Queen আবার যে ঘরে এই Queen টা কে বসাতে চাচ্ছি তাতে  এট্যাক করে   বসে আছে কিনা । কাজটা আমরা খুব সহজেই backtrack দিয়ে করে ফেলতে পারি । আমরা জানি সব Row তে শুধু মাত্রই একটা করে Queen থাকবে এবং সিরিয়ালই যদি আমরা Queen বসাতে থাকি তাহলে আমাদের শুধু বের করতে হবে কোন Queen কোন কলামে আছে যাতে diagonally ও অন্য কোন Queen যেখানে আমরা এই Queenটা বাসাতে চাচ্ছি তাকে এট্যাক করছে না মানে এইখানে আমরা Queen বসাতে পারি ।

একটা জিনিস খেয়াল করি , যখন আমরা কোন Queen বসাই তখন শুধু এইটা চেক করলেই আগের বসানো কোন Queen এর সাথে এখন যে প্লেস এ Queenটা আমরা বসাতে চাচ্ছি তা conflict করছে কিনা মানে এই পজিশন previous বসানো কোন Queen already attack করে রেখেছে কিনা । এইখানে column এর চেক এর পার্টটা অনেক ইজি কিন্তু diagonally part টা একটু tricky . একটা জিনিস খেয়াল করলে দেখা যাবে যে সব কলাম বাম থেকে নিচের ডান দিকে যায় তাদের row আর column এর বিয়োগ ফল একই হয় এবং যে সব কলাম ডান থেকে নিচের বাম দিকে যায় তাদের row এবং column এর যোগফল একই হয় , মানে একটা Queen এর জন্য কলাম সাপেক্ষে দুইটা আলাদা ভাল্যু আছে যেইটা তারা স্টোর করে রাখে যা তাদের অন্য Queen থেকে different করে ।  কোডটা দেখি

	const int MX = 100 ;
	int queen[ MX ] ; // queen[i] for ith row queen
	int column[ MX ] , diagonal1[ MX + MX ] , diagonal2[ MX + MX ] ; // always double from column
	int total ; // It will determine the total number of solution
	// call with nqueen( 1 , 8 ) for 8 queen problem
	// make sure column [ MX ] , diagonal1[ MX + MX ] , diagonal2[ MX + MX ] are all initially 0
	int nqueen( int now , int n )
	{
	if( now == n + 1 ) // complete
	{
	total += 1 ; // count total unique solution
	printf(" ( row , column ) " );
	for ( int i = 1 ; i <= n ; i++ )
	{
	printf("(%d , %d) " , i , queen[i] );
	}
	printf("\n");
	return ;
	}
	for ( int i = 1 ; i <= n ; i++ )
	{
	if( column[i] || diagonal1[ i + now ] || diagonal2[ n + i - now ] ) continue ;
	// As i - now can be negative thats why we are adding n
	queen[ now ] = i ; // position of column
	column[i] = diagonal1 [ i + now ] = diagonal2 [ n + now - i ] = 1 ;
	nqueen( now + 1 , n );
	column[i] = diagonal1 [ i + now ] = diagonal2 [ n + now - i ] = 0 ;
	}
	}

view raw N Queen.cpp hosted with ❤ by GitHub

এইখানে আমরা global variable column[] , diagonal1[] , diagonal2[] এর মাধ্যমে কোনটা কোনটা নেওয়া হইছে একটা সল্যুশন এর জন্য তা দেখানো হয়েছে । যখন কোন একটা কল হয় তার আগে আমরা এদের ১ করে দিচ্ছি মানে তাদের নেওয়া শেষ , যতক্ষণ পর্যন্ত না recursion কলটা ফেরত আসতেছে ততক্ষণ তারা ১ থাকবে মানে বুক থাকবে । এইভাবে all solution পাওয়া যায় ।

সারাংশ : 

অতপর আমরা এইটা বুঝতে পারি যে যদি আমাদের গার্লফ্রেন্ড রক্ষা করে রাখতে হয় অবশ্যই আমাদের backtrack এর এপ্লিকেশন N Queen সম্পর্কে ক্লিয়ার ধারণা রাখতে হবে নাহলে যুগ যুগান্তর ধরে শিশির এর মত সুযোগ সন্ধানীরা তাদের ভাগাইয়া নিয়া যাবে । UVA 750 প্রবলেমটা এখন তাই করা উচিত সবার ।