কম্পিউটার কিভাবে সুডোকু তৈরি করে: আপনার দৈনন্দিন পাজলের পেছনের অ্যালগরিদম

ইন্টারনেটের নিস্তব্ধ কোণায় বা বিশ্বজুড়ে সকালের সংবাদপত্রের পৃষ্ঠায় সুডোকুকে প্রায়শই এর প্রতারণাকারী সরলতার জন্য প্রশংসা করা হয়। এটি একজনকে বলে দেয় যে, এটি শুধুমাত্র সংখ্যার একটি সাধারণ খেলা মনে হলেও, 9x9 গ্রিডের নিচে যৌক্তিক জটিলতার একটি বিশাল মহাসাগর লুকিয়ে আছে। কিন্তু আপনি কি কখনো থেমে চিন্তা করেছেন যে এই গ্রিডগুলো আসলে কীভাবে অস্তিত্ব লাভ করে? যখন আপনি কোনো অ্যাপে "জেনারেট" বোতাম টিপেন বা স্থানীয় পাজল বইয়ের 12 নম্বর পৃষ্ঠায় ফ্লিপ করেন, তখন মেশিনের ভেতরটাতে আসলে কী ঘটে?

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

ভিত্তি: ল্যাটিন স্কোয়ার থেকে বৈধ গ্রিড পর্যন্ত

একটি সুডোকু গ্রিড একটি বৈধ পাজল হিসেবে অবস্থান না করা পর্যন্ত, একে প্রথমে খেলার মৌলিক নিয়মগুলো মেনে চলতে হবে। এর মূল ভিত্তিতে, একটি সম্পূর্ণ সুডোকু গ্রিড হলো একটি নির্দিষ্ট ধরনের ল্যাটিন স্কোয়ার (Latin Square)। একটি ল্যাটিন স্কোয়ার হলো একটি n×n বিন্যাস যেটি nটি ভিন্ন প্রতীক দিয়ে পূর্ণ, যার প্রতিটি প্রতীক প্রতিটি সারিতে ঠিক একবার এবং প্রতিটি কলামে ঠিক একবার ঘটে।

তবে, একটি সাধারণ ল্যাটিন স্কোয়ার সুডোকুর তৃতীয় নিয়মটির কথা বিবেচনা করে না: 3x3 সাবগ্রিড (যাকে প্রায়শই "বক্স" বা "এলাকা" বলা হয়)। একটি বৈধ সমাধানকৃত গ্রিড তৈরি করতে, একটি অ্যালগরিদম নিশ্চিত করতে হবে যে:

• প্রতিটি সারিতে 1 থেকে 9 পর্যন্ত সংখ্যাগুলো ঠিক একবার করে থাকতে হবে।
• প্রতিটি কলামে 1 থেকে 9 পর্যন্ত সংখ্যাগুলো ঠিক একবার করে থাকতে হবে।
• প্রতিটি 3x3 বক্সে 1 থেকে 9 পর্যন্ত সংখ্যাগুলো ঠিক একবার করে থাকতে হবে।

কম্পিউটার ব্যাকট্র্যাকিং অ্যালগরিদম বা পারমুটেশন পদ্ধতি ব্যবহার করে এই প্রাথমিক "সমধানকৃত" গ্রিডগুলো তৈরি করে। সাধারণত এই প্রক্রিয়াটি প্রথম সারি দিয়ে শুরু হয়, যা সংখ্যার যেকোনো একটি পারমুটেশন হতে পারে (যেমন: 1-2-3-4-5-6-7-8-9)। এরপর পূর্ববর্তী সারি বা কলামের সীমাবদ্ধতার সাথে দ্বন্দ্ব না করে এমন বৈধ পারমুটেশন খুঁজে পরবর্তী সারিগুলো পূর্ণ করা হয়। একটি সম্পূর্ণ গ্রিড তৈরি হলে, এটি এর থেকে উদ্ভূত সকল ভবিষ্যতের পাজলের জন্য "সমাধানের ক্যানভাস" হিসেবে কাজ করে।

পাজল তৈরির শিল্পকলা: অপসারণ প্রক্রিয়া

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

জেনারেশন প্রক্রিয়াটি সাধারণত এই ধাপগুলো অনুসরণ করে:

1. একটি সমাধানকৃত গ্রিড নির্বাচন করুন: আনুমানিক 6.67 × 10^21 সংখ্যক সম্ভাব্য বৈধ সুডোকু গ্রিডের মধ্যে একটি বেছে নিন।
2. পুনরাবৃত্তিমূলকভাবে অঙ্ক অপসারণ করুন: কম্পিউটার সাধারণত এলোমেলো অবস্থান দিয়ে শুরু করে সংখ্যাগুলো একটু করে অপসারণ করা শুরু করে।
3. অদ্বিতীয়তা যাচাই করুন: প্রতিটি অপসারণের পর, অ্যালগরিদম আংশিকভাবে পূর্ণ গ্রিডটি সমাধান করার চেষ্টা করে। যদি পাজলের একাধিক সমাধান থাকে, তবে অপসৃত সংখ্যাটি ফিরিয়ে দেওয়া হয়। এটি অত্যন্ত গুরুত্বপূর্ণ; একটি ভালো সুডোকুর ঠিক একটিই অনন্য সমাধান থাকতে হবে।
4. সম্পন্ন হওয়া পর্যন্ত পুনরাবৃত্তি করুন: প্রক্রিয়াটি তখনও চালু থাকে যতক্ষণ না কাঙ্ক্ষিত সংখ্যক সংকেত (clues) বাকি থাকে, যা সাধারণ কঠিনতার স্তরের জন্য সাধারণত ২৫ থেকে ৩৫ এর মধ্যে হয়, যেখানে ১৭ হলো প্রমাণিত গাণিতিক ন্যূনতম সংখ্যা।

সুডোকুতে একটি অনন্য সমাধান নিশ্চিত করতে প্রয়োজনীয় সংকেতের ন্যূনতম সংখ্যা হলো ১৭। যদিও ৮০টির বেশি সংকেত সহ পাজল থাকা সম্ভব (যা প্রায়শই তুচ্ছ বা "সহজ" হিসেবে বিবেচিত হয়), ভালোভাবে নকশাকৃত পাজলগুলো সাধারণত ধারাবাহিক যৌক্তিক অনুমানের প্রয়োজন এমন একটি ভারসাম্য বজায় রাখে।

চ্যালেঞ্জ রেটিং অ্যালগরিদম

আপনি হতে পারেন আশ্চর্য কিভাবে একটি কম্পিউটার জানে যে একটি পাজল "সহজ", "মাঝারি" নাকি "বিশেষজ্ঞ"। চমকপ্রদ বিষয় হলো, বেশিরভাগ মানক জেনারেটর কঠিনতা রেটিং মূল প্রসেসিং সময়ের ওপর নির্ভর করে না। এর বদলে, তারা যৌক্তিক কৌশলের শ্রেণিবিন্যাসের ওপর নির্ভর করে।

প্রধান পদ্ধতিটির মধ্যে রয়েছে গ্রিডের মধ্য দিয়ে অগ্রগতির জন্য প্রয়োজনীয় যৌক্তিক ধাপগুলোকে শ্রেণীবদ্ধ করা। অ্যালগরিদম কৌশলগুলোর একটি হায়ারার্চি ব্যবহার করে পাজলটি সমাধান করার চেষ্টা করে:

1. নেকেড সিঙ্গেলস (Naked Singles): এমন সেল যেগুলোতে মাত্র একটি সম্ভাব্য প্রার্থী রয়েছে।
2. হিডেন সিঙ্গেলস (Hidden Singles): এমন সেল যেখানে একটি সংখ্যা নির্দিষ্ট কোনো সারি, কলাম বা বক্সের মধ্যে শুধুমাত্র একটি স্থানে রাখা যেতে পারে।
3. পেয়ার এবং ট্রিপলস: এমন প্যাটার্ন খোঁজা যেখানে দুটি বা তিনটি সেলে একই দুটি প্রার্থী শেয়ার করা থাকে।
4. এক্স-উইংস এবং সফডিশ (X-Wings and Swordfish): একাধিক সারি ও কলাম জড়িত উন্নত যৌক্তিক অনুমান।

যদি একটি পাজল সম্পূর্ণভাবে বেসিক স্ক্যানিং (নেকেড/হিডেন সিঙ্গেলস) ব্যবহার করে সমাধান করা যায়, তবে এটি সাধারণত "সহজ" হিসেবে শ্রেণীবদ্ধ করা হয়। যেহেতু খেলোয়াড়কে প্যাটার্ন রিকগনিশন বা ফরওয়ার্ড-লুকিং লজিক প্রয়োগ করতে হবে, তাই কঠিনতার রেটিং বৃদ্ধি পায়। এটাই হলো কারণ কখনো কখনো একটি মাত্র সংখ্যা অপসারণ বা যোগ করা পাজলের শ্রেণীকে স্থানান্তরিত করতে পারে—এটি জটিলতর যৌক্তিক ধাপ ব্যবহারের জন্য বাধ্য করতে পারে।

মানক সুডোকুর বাইরে: অ্যালগরিদমিক সামঞ্জস্য

সুডোকু জেনারেশনের নীতিমালাগুলো কেবল ক্লাসিক 9x9 গ্রিড পর্যন্ত সীমাবদ্ধ নয়। আধুনিক লজিক পাজল অ্যাপ এবং ওয়েবসাইটগুলো ইউনিক টুইস্ট সহ ভ্যারিয়েন্ট তৈরি করতে এই একই অ্যালগরিদমিক ফ্রেমওয়ার্ক ব্যবহার করে। উদাহরণ স্বরূপ, একটি কিলার সুডোকু (Killer Sudoku) তৈরি করার জন্য একটি মানক বৈধ গ্রিড তৈরি করতে হয় এবং তারপর সেটিকে "কাগ" বা "খাঁচা"-তে বিভক্ত করতে হয় যেখানে সংখ্যাগুলোর যোগফল একটি লক্ষ্য সংখ্যার সাথে মিলবে। এখানে জেনারেশন আরও জটিল কারণ কাগের সীমাবদ্ধতাগুলো অবশ্যই অন্তর্নিহিত গ্রিড সংখ্যার সাথে সামঞ্জস্যপূর্ণ হতে হবে।

এছাড়াও, ক্যালকুডোকু (Calcudoku) (যাকে কেনকেন নামেও পরিচিত) জেনারেশনের জন্য খাঁচায় গাণিতিক অপারেটর নির্ধারণ করতে হয় এবং নিশ্চিত করতে হবে যে ফলাফলগত গাণিতিক সমীকরণের গ্রিডের মধ্যে অনন্য সমাধান রয়েছে। এই ভ্যারিয়েন্টগুলোর প্রায়শই কাস্টম অ্যালগরিদমের প্রয়োজন হয় কারণ সীমাবদ্ধতাগুলো শুধুমাত্র অবস্থানগত নয়, বরং গাণিতিকও।

অ্যান্টি-সিমেট্রি এবং ইকুইভালেন্স ক্লাস

বৈচিত্র্য নিশ্চিত করার জন্য, কম্পিউটারগুলো বিরলভাবে একই গ্রিড দুবার ব্যবহার করে। তবে বেশিরভাগ প্রয়োগের জন্য ৬ কোটি কোটি অনন্য গ্রিড তৈরি করা অপ্রয়োজনীয়। এর বদলে, জেনারেটরগুলো সিমেট্রি এবং ইকুইভালেন্স ক্লাস (equivalence classes) ব্যবহার করে।

সুডোকু গ্রিডগুলোর বেশ কিছু রূপান্তর রয়েছে যা তাদের মৌলিক "যুক্তিকে" পরিবর্তন করে না। এর মধ্যে রয়েছে:

• অঙ্কের পারমুটেশন (Digit Permutation): সব ১ কে ২ দিয়ে, সব ২ কে ৩ দিয়ে প্রতিস্থাপন করা ইত্যাদি। পাজলটি গঠনগতভাবে অভিন্ন থাকে।
• সারি/কলাম বিনিময় (Row/Column Swapping): একই ব্যান্ডের মধ্যে পুরো সারিগুলো বিনিময় করা (যেমন: সারি ১ এবং সারি ২ বিনিময়) অথবা তিনটি সারির পুরো ব্যান্ড বিনিময় করা।
• ঘূর্ণন ও প্রতিফলন (Rotation and Reflection): গ্রিডটি অনুভূমিক বা উল্লম্বভাবে ঘোরানো, অথবা ৯০ ডিগ্রিতে ঘোরানো।

এই সিমেট্রিগুলোর বোঝাপড়া থাকলে, একটি জেনারেটর "মাষ্টার" গ্রিড বেছে নিয়ে দৃশ্যমানভাবে ভিন্ন কিন্তু যৌক্তিকভাবে সমতুল্য হাজার হাজার পাজল তৈরি করতে পারে। এটি অ্যাপগুলোকে ট্রিলিয়নগুলোর অনন্য অন্তর্নিহিত সমাধানের প্রয়োজন ছাড়াই হাজার হাজার নতুন দেখতে পাজল অফার করতে সাহায্য করে।

এটি আপনার জন্য কেন গুরুত্বপূর্ণ

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

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

তাই, পরের বার আপনি যখন একটি চূড়ান্ত অঙ্ক পূর্ণ করেন এবং "সাফল্য" বার্তাটি চেক করেন, তখন মনে রাখবেন সেই মুহূর্তটিকে সম্ভব করার জন্য কয়েক সেকেন্ডে কত কোটি গণনা হয়েছে। এটি কেবল একটি খেলা নয়; এটি সবাইকে সহজলভ্য করা কম্পিউটেশনাল যুক্তির এক অসাধারণ achievement।