গণিত ইশকুল | সুডোকু সমাধানের যত অ্যালগরিদম

প্রথম আলোকে নির্ভরযোগ্য সূত্র হিসেবে পেতে হলেএখানে ক্লিক করুন

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

প্রচলিত অ্যালগরিদমগুলোর মধ্যে একটি হলো ব্যাকট্র্যাকিং। এটি মূলত ব্রুট ফোর্স বা অনুমানমূলক অনুসন্ধান প্রক্রিয়া। এ প্রক্রিয়ায় যেভাবে কাজ হয় সেটি হলো, এটি প্রথম ফাঁকা ঘরে 1 বসায় এবং পরবর্তী ঘরে যায়। পরবর্তী ঘরে গিয়ে 1 বসায়। যদি দেখা যায় যে 1 সেখানে হতে পারে না, তাহলে সেখানে 2 বসানো হয়। এভাবে কোনো কারণে যদি কোনো ঘরে 1 থেকে 9 পর্যন্ত কোনো সংখ্যাই না হয়, তাহলে সেই ঘর ফাঁকা রেখে এটি আবার পূর্ববর্তী ঘরে গিয়ে বসানো মান থেকে ১ বৃদ্ধি করবে। এভাবে যতক্ষণ পর্যন্ত ৮১টি ঘরই সঠিক মান দ্বারা পূর্ণ হচ্ছে ততক্ষণ প্রক্রিয়াটি চলবে। এই পদ্ধতির সুবিধাগুলো হলো, এই পদ্ধতিতে সাধারণত সমাধান আসা নিশ্চিত। আবার সুডোকুর কাঠিন্যের সঙ্গে এই পদ্ধতির কোনো সম্পর্কে নেই। কারণ, এটি যুক্তি দিয়ে সুডোকু সমাধান করে না। এই অ্যালগরিদম অন্যান্য অ্যালগরিদমের তুলনায় সহজ, যার জন্য এটি অধিকাংশ ক্ষেত্রেই ব্যবহৃত হয়। তবে এই অ্যালগরিদমের একটি সমস্যা হচ্ছে অনেক ক্ষেত্রে এই পদ্ধতিতে সমাধান আসতে অনেক বেশি সময় লেগে যেতে পারে। কারণ, অনেক ক্ষেত্রে এই প্রক্রিয়া ৯ লাখ বার পর্যন্ত চলতে পারে।

পরবর্তী যে অ্যালগরিদম রয়েছে, তা হলো, স্টোকাস্টিক অনুসন্ধান বা অপ্টিমাইজেশন পদ্ধতি। এই পদ্ধতির সঙ্গে ব্যাকট্র্যাকিংয়ের তফাতের জায়গাটি হচ্ছে, ব্যাকট্র্যাকিংয়ে যেমন ১ থেকে সংখ্যা বসানো শুরু হয়, এই পদ্ধতিতে সেটি হয় না। বরং এই পদ্ধতিতে ফাঁকা ঘরগুলোতে দৈবভাবে সংখ্যা বসানো হয়। এখন এই পদ্ধতি মূলত ভুলের সংখ্যাটি গণনা করে। দৈবভাবে সংখ্যা বসানোর পর যতগুলো ভুল থাকে, এটি সেটি গণনা করে। তারপর বিভিন্ন উপায়ে সংখ্যাগুলোকে অদলবদল করা হয়। কাঠিন্য ও সীমাবদ্ধতা বিবেচনায় অদল বদলের প্রক্রিয়াটি এক্ষেত্রে ব্যাখ্যা করা হলো না। এভাবে অদলবদল করার পর আবার ভুলের সংখ্যা গণনা করা হয়। এভাবে যতক্ষণ না পর্যন্ত ভুলের সংখ্যা শূন্য হয়, ততক্ষণ পর্যন্ত প্রক্রিয়াটি চলতে থাকে। এ প্রক্রিয়া অন্য প্রক্রিয়ার চেয়ে তুলনামূলকভাবে দ্রুত। বিশেষত এই ধরনের অ্যালগরিদমগুলো সমস্যার যৌক্তিক

সমাধান না থাকলেও সমাধান বের করতে সক্ষম। যার কারণে দ্রুত বিভিন্ন সুডোকুর সমাধান করা যায়। অপর দিকে যুক্তি খাটিয়ে বের করতে হয়, এমন অ্যালগরিদমের তুলনায় এটি মন্থর।

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

আজকের পর্বেও একটি সুডোকু পাঠকের সমাধানের জন্য দেয়া হল। আশা করি, পাঠক তা সমাধান করতে সক্ষম হবেন।