ایک گرڈ کے روشن ہونے کے طریقوں کا شمار

چار کی انچاسویں طاقت

Conduit میں ہر ٹائل کی چار ممکنہ سمتیں ہوتی ہیں، یعنی اپنی جگہ سے صفر، ایک، دو یا تین چوتھائی چکر گھمائی ہوئی۔ ¹ روزانہ کے گرڈ کے انچاس خانوں میں سے ہر ایک کو ان چار میں سے ایک آزاد انتخاب دیجیے، تو بورڈ کی الگ الگ حالتوں کی تعداد 4⁴⁹ بنتی ہے۔ پورا لکھا جائے تو یہ 316,912,650,057,057,350,374,175,801,344 ہے، یعنی تین سو آکٹیلین سے زیادہ ترتیبیں، جن میں سے کھیل آپ سے ایک ایسی ترتیب ڈھونڈنے کو کہتا ہے جو پوری طرح روشن اور رساؤ سے پاک ہو۔

جو الٹ پھیر آپ کو پہیلی تھماتی ہے، وہ ہر ٹائل کے لیے صفر سے تین تک چوتھائی چکروں کی ایک بے ترتیب تعداد چنتی ہے۔ ¹ چنانچہ جو بورڈ آپ کے سامنے آتا ہے وہ اُس بے پناہ وسیع فضا سے یکساں امکان کے ساتھ نکالا جاتا ہے، سوائے ایک محتاط استثنا کے جو کھیل اس لیے رکھتا ہے کہ آپ کو پہلے سے حل شدہ گرڈ نہ تھما دے۔ ¹ زورِ بازو سے ہر امکان آزمانا ممکن نہیں: کھیل کے اپنے ٹیسٹ نوٹ کرتے ہیں کہ ہر ٹائل کی چاروں گردشیں آزمانا قوت نمائی (exponential) رفتار سے بڑھتا ہے، اور وہ مکمل تلاش صرف نو یا اس سے کم خانوں والے کھلونا بورڈوں پر ہی چلاتے ہیں۔ ²

تشاکل خاموشی سے شمار کو گھٹا دیتا ہے

وہ سرخی والا عدد زیادہ گنتا ہے، کیونکہ کچھ ٹائلوں کو اس سے فرق نہیں پڑتا کہ آپ انہیں کیسے گھماتے ہیں۔ چاروں طرف کنیکٹروں والا کراس، یعنی چوراہے کی شکل، چاروں سمتوں میں ایک جیسا نظر آتا ہے؛ اسے گھمانے سے کچھ نہیں بدلتا۔ سیدھی لکیر کے صرف دو الگ روپ ہیں، افقی اور عمودی، کیونکہ آدھا چکر اسے خود اسی پر منطبق کر دیتا ہے۔ صرف غیر متشاکل شکلوں، یعنی کہنی نما موڑ، T کی شکل والے ٹی، اور ایک کنیکٹر والے سرے، کی واقعی چاروں سمتیں الگ الگ ہوتی ہیں۔ ³

شکلوں کے نام کھیل کے ڈیزائن نوٹس میں درج ہیں؛ الگ سمتوں کی گنتی اس بات سے نکلتی ہے کہ چار بِٹ کا کنیکٹر ماسک بتائی گئی گردشوں کے تحت غیر تبدیل شدہ رہتا ہے۔ ³ مؤثر تلاش کی فضا 4⁴⁹ سے بالکل انہی فی ٹائل تشاکلوں کے حاصلِ ضرب جتنی چھوٹی ہے، مگر کہنی موڑوں اور ٹی شکلوں کے معقول آمیزے والے کسی بھی بورڈ پر پھر بھی فلکیاتی حد تک بڑی ہے۔

حل شدہ وائرنگیں آخر کتنی موجود ہیں؟

سوال کو الٹ دیجیے۔ جو سمتیں آپ آزما سکتے ہیں انہیں بھول جائیے؛ یہ پوچھیے کہ سرے سے کتنے حل شدہ بورڈ ممکن ہیں۔ Conduit کا ایک مکمل گرڈ پائپوں کا ایسا مجموعہ ہے جو جڑا ہوا ہے، جس میں بجلی ہر ٹائل تک پہنچتی ہے، اور جس میں کوئی فالتو لوپ نہیں، کیونکہ جنریٹر جو چیز بناتا ہے وہ ایک اسپیننگ ٹری (spanning tree) ہے: جڑا ہوا، بغیر چکر کے، منبع سے ہر نوڈ تک ایک ہی راستہ۔ ³ ایسی ہر وائرنگ، بالکل ٹھیک معنوں میں، گرڈ گراف کا ایک اسپیننگ ٹری ہے، جس میں راس خانے ہیں اور کنارے وہ مشترکہ سرحدیں ہیں جنہیں کوئی پائپ پاٹ سکتا ہے۔

اور اسپیننگ ٹریوں کو بالکل ٹھیک ٹھیک گنا جا سکتا ہے۔ کرچوف کا میٹرکس ٹری مسئلہ، جو 1847 کا ایک نتیجہ ہے، کہتا ہے کہ کسی بھی گراف کے اسپیننگ ٹریوں کی تعداد اس کے لاپلاسی میٹرکس کے کسی بھی کوفیکٹر کے برابر ہوتی ہے، یعنی ایک ایسا ڈیٹرمیننٹ جسے آپ کثیر رکنی وقت میں نکال سکتے ہیں۔ ⁴ گرڈوں کے لیے یہ شمار سائز کے ساتھ پھٹ پڑتا ہے: ایک معمولی سی 4×4 جالی کے ہی 100,352 اسپیننگ ٹری ہوتے ہیں، اور وہاں سے آگے یہ عدد بے تحاشا چڑھتا جاتا ہے۔ ان میں سے ہر ایک Conduit کا ایک جائز، پوری طرح روشن حل ہے۔ پہیلی اس لیے مشکل نہیں کہ جواب کم ہیں، بلکہ اس لیے کہ وہ قریب قریب جوابوں کے کہیں بڑے ہجوم میں چھپے ہوئے ہیں۔

مقامی اصول، ہمہ گیر نتائج

آپ امید کر سکتے ہیں کہ پہیلی ٹکڑوں میں بٹ جائے گی: اوپر بائیں والا ٹائل ٹھیک کیجیے، پھر اس کے ساتھ والا، اور سلیقے سے دور والے کونے تک بڑھتے جائیے۔ کبھی کبھی بورڈ کا کوئی حصہ واقعی اس طریقے کے آگے جھک جاتا ہے۔ کونے میں رکھے ٹائل کے صرف دو کنارے پڑوسیوں سے چھوتے ہیں، اس لیے اس کے کنیکٹر سخت پابند ہوتے ہیں؛ سرحد پر پڑا ایک سرے والا ٹائل صرف اندر کی طرف اشارہ کر سکتا ہے۔ یہ مجبوری کی چالیں قدم جمانے کی جگہ دیتی ہیں۔

لیکن جیتنے کی دونوں شرطیں اتنی فرماں برداری سے زنجیر نہیں بنتیں۔ رساؤ سے پاک ہونا ایک مقامی خاصیت ہے، آپ اسے کنارہ بہ کنارہ جانچ سکتے ہیں۔ بجلی سے جڑا ہونا ایسا نہیں: کوئی ٹائل روشن ہے یا نہیں، اس کا انحصار جوڑوں کی ایک ایسی اَن ٹوٹی زنجیر پر ہے جو پیچھے منبع تک، ممکنہ طور پر پورے بورڈ کے آر پار، جاتی ہے۔ ³ ایک کونے میں آپ کی کی ہوئی تبدیلی اس واحد راستے کو توڑ کر، جو کسی دور دراز علاقے کو بجلی پہنچا رہا تھا، اسے اندھیرے میں ڈبو سکتی ہے۔ یہی باہمی بندھن، کہ ہر ٹائل کی قسمت ممکنہ طور پر پورے گرڈ سے گزرتے کسی راستے سے بندھی ہے، گردش والی پہیلی کو آسان حساب کتاب میں ڈھلنے سے روکتا ہے، اور اسی وجہ سے وسیع تر Net/Pipes خاندان (پائپ جوڑنے والی پہیلیوں) کے حل کنندہ پروگرام سادہ بائیں سے دائیں جھاڑو کے بجائے قیود کی ترسیل (constraint propagation) اور تلاش پر ٹیک لگاتے ہیں۔ ⁵

حالتیں نہیں، گردشیں

حالتوں کی فضا کی ساری وسعت کے باوجود، جس مقدار پر Conduit آپ کو نمبر دیتا ہے وہ ننھی اور انسانی ہے: آپ نے کتنی بار ٹیپ کیا۔ اسکور ہے 1000 − 4 × چالیں − 2 × سیکنڈ، جس کی نچلی حد صفر ہے۔ ³ کسی بھی دیے گئے بورڈ کے لیے گردشوں کی ایک نظری کم از کم تعداد ہوتی ہے، یعنی تمام ٹائلوں پر، حل شدہ سمت تک پہنچنے کے لیے درکار کم سے کم چوتھائی چکروں کا مجموعہ، اور اس سے آگے ہر ضائع کیا ہوا چکر آپ کو چار پوائنٹ کا پڑتا ہے، اور ہر بے کار گزرا سیکنڈ دو پوائنٹ کا۔

چنانچہ اصل کھیل دو بے پناہ حقیقتوں اور ایک چھوٹی سی حقیقت کے بیچ بیٹھا ہے۔ گھاس کا ڈھیر 4⁴⁹ سمتوں جتنا چوڑا ہے؛ سوئیاں گرڈ کے بے شمار اسپیننگ ٹری ہیں؛ اور آپ کا کام ایک سے دوسرے تک، واحد جائز چال کی جتنی کم تکرار میں ہو سکے، سفر کرنا ہے۔ امتزاجیات ضمانت دیتی ہے کہ جواب اس میں موجود ہے۔ اسکورنگ خاموشی سے آپ کو للکارتی ہے کہ اسے بھٹکے بغیر ڈھونڈ نکالیں۔ ⁴