একটি সুডোকু থেকে একটি সংখ্যা মুছলে সেটা আরও কঠিন হয়ে উঠতে পারে। ভুল সংখ্যাটি মুছলে আপনি সুডোকুর একমাত্র উত্তরটাই নষ্ট করে দিতে পারেন। পূর্ণ একটা গ্রিড আর একেবারে ফাঁকা পাতার মাঝখানে আছে একটি কঠোর সীমা: ১৭টি শুরু-সূত্র। সুডোকু কেন এখানেই থামে?

উত্তরটা শুরু হয় এমন এক প্রশ্ন দিয়ে—যেটা সহজেই এড়িয়ে যাওয়া যায়: আপনার পাজল কি শুধু একটি সমাধান রাখে?

একটাই পূর্ণ গ্রিড, একটাই উত্তর

ক্লাসিক ৯×৯ সুডোকুতে, প্রতিটি সারি, কলাম এবং ৩×৩ বক্সে ১ থেকে ৯ সংখ্যাগুলো ঠিক একবার করে থাকতে হবে। এগুলোই নিকোলির প্রকাশিত স্ট্যান্ডার্ড নিয়ম-এ বলা হয়েছে। গ্রিডে আগেই ছাপা থাকে যে সংখ্যাগুলো, সেগুলোকে বলা হয় givens, বা সূত্র/ক্লু।

একটি পূর্ণ গ্রিড সব ওই নিয়ম মেনে চলতে পারে—তবুও ওই গ্রিডটি যে শুরু-সূত্রগুলো দিয়ে বানানো হয়েছে, সেগুলোর একটাই সম্ভাব্য উত্তর না-ও হতে পারে। যদি দুটি ভিন্ন পূর্ণতা ফিট করে, তাহলে খেলোয়াড় বুঝতে পারবে না—পাজলের নির্মাতা আসলে কোনটা চেয়েছিলেন।

সেজন্যই এককত্ব (uniqueness) গুরুত্বপূর্ণ। ঠিকভাবে তৈরি করা একটি ক্লাসিক সুডোকু আপনাকে এমন তথ্য দেয়, যাতে আপনি ঠিক একটি পূর্ণ গ্রিডই শনাক্ত করতে পারেন। আপনি যদি নিয়মগুলোতে নতুন হন, তাহলে আমাদের সুডোকু খেলার গাইড ভালো শুরু হবে।

দেখুন, একটি ক্লু কীভাবে সবকিছু বদলে দেয়

এখানে ইচ্ছাকৃতভাবে প্রায়-সম্পূর্ণ একটি পাজল আছে। একটি ডট চিহ্ন দেয় ফাঁকা সেল।

5 3 4 | 6 . 8 | 9 1 2
6 7 2 | 1 9 5 | 3 4 8
1 9 8 | 3 4 2 | 5 6 7
------+-------+------
8 5 9 | . . 1 | 4 2 3
4 2 6 | 8 5 3 | 7 9 1
7 1 3 | 9 2 4 | 8 5 6
------+-------+------
9 6 1 | 5 3 7 | 2 8 4
2 8 7 | 4 1 9 | 6 3 5
3 4 5 | 2 8 6 | 1 7 9

এটার আছে ৭৮টি ক্লু এবং একটিমাত্র সমাধান। উপরের সারিতে দরকার ৭। তারপর চতুর্থ সারিতে দরকার কলাম চার-এ ৭ এবং কলাম পাঁচ-এ ৬।

এখন প্রথম সারি, কলাম চার-এর ৬টা মুছে দিন। এতে চারটি সেল ফাঁকা হবে, এবং দুটি বিন্যাস কাজ করে:

সেলপূর্ণতা Aপূর্ণতা B
সারি 1, কলাম 467
সারি 1, কলাম 576
সারি 4, কলাম 476
সারি 4, কলাম 567

বাকি সব সংখ্যাই একই থাকে। দুটো বিন্যাসই প্রতিটি সারি, কলাম, বক্স, এবং বাকি সূত্র—সবকিছু মেনে চলে। এই চারটি সেল একটি আয়তক্ষেত্র তৈরি করে, যেখানে ৬ আর ৭ বদলানো গেলেও কোনো নিয়ম ভাঙে না। আমরা সমাধানের সংখ্যা যাচাই করেছি: প্রথম পাজলটিতে ঠিক একটি পূর্ণতা ছিল; মুছে ফেলার পর এতে ঠিক দুটি হলো।

একটি ক্লু মুছলে এমনটা হয় না যে, যে সমাধান আগে কাজ করেছিল সেটি আর কাজ করবে না—কারণ সেটা এখনও বাকি সব সূত্রই মেনে চলে। কিন্তু ক্লু মুছলে আরেকটি উত্তর “ঢুকে পড়তে” পারে। এমনকি এই পাজলেও, যেখানে আছে ৭৭টি given, সেটি দ্ব্যর্থক (ambiguous)—তাই শুধু ক্লুর সংখ্যা বেশি হলেই অনন্যতা নিশ্চিত হয় না।

কেন ১৭-ই ন্যূনতম

গ্যারি ম্যাকগুইয়ার, বাষ্টিয়ান টুগেমন, এবং জিল সিভারিও প্রমাণ করেছেন যে ১৬টি given থাকা কোনো ক্লাসিক ৯×৯ সুডোকুতে ঠিক একটিমাত্র সমাধান হতে পারে না। তাদের মূল গবেষণাপত্র বর্ণনা করে exhaustive কম্পিউটার সার্চের কথা। তাই ঠিকভাবে solvable ১৭-ক্লুর পাজল থাকে—অর্থাৎ ১৭-ই ন্যূনতম।

এটার মানে এই নয় যে ১৭টি সংখ্যার যে কোনো বিন্যাসই একটি বৈধ পাজল বানাবে। তাদের অবস্থান (positions) এবং মান (values) দুটোই গুরুত্বপূর্ণ। ফলাফলটি ক্লাসিক সুডোকুর ক্ষেত্রেও প্রযোজ্য; ভ্যারিয়েন্টে অতিরিক্ত নিয়ম থাকলে সমস্যা বদলে যায়।

১৬-কে বাদ দিলেই কীভাবে ছোট সংখ্যাগুলোকেও বাদ দেওয়া যায়? যদি কোনো ছোট পাজলে একটাই সমাধান থাকত, তাহলে আপনি সেই সমাধান থেকে সঠিক কিছু ক্লু যোগ করে সেটাকে ১৬ পর্যন্ত নিয়ে আসতে পারতেন। ক্লু যোগ করলে সেটার অনন্য উত্তর অক্ষুণ্ণ থাকত—যা ওই ফলাফলের সঙ্গে বিরোধ সৃষ্টি করে।

কীভাবে প্রমাণ করবেন যে এর চেয়ে ছোট পাজল নেই?

একটি ১৭-ক্লুর পাজল দেখালেই বোঝা যায় কী সম্ভব। কিন্তু ১৬ কাজ করতে পারে না—এটা প্রমাণ করতে হলে প্রতিটি সম্ভাবনাকে বাদ দিতে হয়।

গবেষকরা সমাপ্ত (completed) গ্রিডগুলোকে পদ্ধতিগতভাবে খুঁজেছিলেন, সমতুল্য (equivalent) গ্রিডের হিসাব রেখে। তাদের পদ্ধতিতে ব্যবহার হয়েছে unavoidable sets: সেলগুলোর এমন দল, যেখানে বিকল্প সমাধান ঠেকাতে সেখানে অবশ্যই একটি ক্লু থাকতে হবে। এরপর তারা hitting sets গণনার জন্য একটি কার্যকর অ্যালগরিদম তৈরি করেন—যেগুলো ওই দলগুলোর সঙ্গে ছেদ করে এমন নির্বাচন—এবং অনন্যতা যাচাই করতে সম্ভাব্য ক্লু-সেটগুলো পরীক্ষা করেন। পত্রটিতে পদ্ধতিটি ব্যাখ্যা করা আছে।

উপরে থাকা আয়তক্ষেত্রটা ধারণাটার ছোট একটি উদাহরণ। চারটি সেলই যদি ক্লু ছাড়া রাখেন, তাহলে দুটো বিন্যাসই টিকে থাকে। ওই সেলগুলোর অন্তত একটি ঠিক করে (ফিক্স করে) দিলে, আপনি ওই নির্দিষ্ট বদলাটাকে বন্ধ করে দেন। একটি দুর্বল/বিরল (sparse) পাজলে, অনেক রকম বিকল্প একসাথে বন্ধ করতে হয়।

ন্যূনতম ক্লু মানে সর্বোচ্চ কঠিন নয়

ক্লুর সংখ্যা বলে “কতটা তথ্য ছাপা আছে?” কিন্তু সেটা বলে না—পরের বার আপনি ঠিক কোন ধরনের সিদ্ধান্ত (deduction) টের পাবেন। কতগুলো given আছে তা বলে না যে পরের চালটা হবে সহজ একটা একক (obvious single) নাকি এমন কোনো প্যাটার্ন, যা আপনি আগে কখনও শিখেননি।

আরেকটা দরকারি পার্থক্য আছে: minimum আর minimal। minimum হলো ক্লাসিক সুডোকুতে সম্ভব সবচেয়ে ছোট ক্লু সংখ্যা। আর minimal পাজল হলো এমন, যেখানে কোনো given-ই সরালেই অনন্যতা হারায়। কোনো পাজলকে minimal বললে সেটাতে ১৭টি ক্লু আছে—এটা বলা হয় না।

আপনার পরের খেলায়, প্রতিটি বসানোর আগে সেটাকে ব্যাখ্যা করার চেষ্টা করুন: “এই বক্সে ৪ রাখার একটাই সম্ভব সেল এটা।” আপনি যদি এখনই কোনো চাল ব্যাখ্যা করতে না পারেন, তাহলে প্রার্থীগুলো (candidates) দেখুন বা আমাদের সুডোকু সমাধানের গাইড থেকে কোনো টেকনিক চেষ্টা করুন।

পরের বার যখন আপনি কোনো sparse সুডোকু দেখবেন, ক্লুগুলো গুনুন—তারপর দেখুন, প্রতিটি ক্লু কেন এত গুরুত্বপূর্ণ।

আলোচনায় যোগ দিন

মন্তব্য

0

কোনো ভাবনা জানান, প্রশ্ন করুন বা অন্য খেলোয়াড়কে সাহায্য করুন।

সাইন-ইন যাচাই করা হচ্ছে…

মন্তব্য লোড হচ্ছে…