دگرگون

مدتهاست که هیچ معمای سودوکویی با تنها ۱۶ راهنمایی ارائه نمی شود. ریاضی‌دانی به کمک ۷۰۰ میلیون ساعت محاسبات ابررایانه‌ای ثابت کرده است که حداقل تعداد راهنمایی‌های لازم برای حل یک سودوکو ۱۷خانه است.

 
خبر آنلاین:یک ریاضی دان ایرلندی از الگوریتمی پیچیده و میلیون ها ساعت از زمان ابررایانه ها استفاده کرد تا بتواند پاسخ معمایی مهم وحل نشده در ریاضیات سودوکو را بیابد. بازی سودوکو که اولین بار در ژاپن همه پسند شد، از یک مربع ۹ در ۹ تشکیل شده که هر سطر و ستون آن باید با اعداد ۱ تا ۹ پر شود یه طوری که هر عدد در هر ستون، سطر یا ۹ مربع ۳در۳ فقط بار ظاهر شود.
گری مک گوایر از کالج دانشگاهی دوبلین در اثباتی که در اول ژانویه روی اینترنت قرار گرفت، نشان داد که کمترین تعداد راهنمایی ها (یا ارقام ابتدای بازی) که برای تکمیل یک بازی لازم است، ۱۷ خانه است و جدول هایی با ۱۶ راهنمایی یا کمتر، پاسخ یکتایی ندارند. بیشتر سودوکوهای روزنامه ای چیزی در حدود ۲۵ راهنمایی دارند، و هرچه که تعداد راهنمایی ها بیشتر شود، سختی معما هم کمتر می شود.
ریاضیدانان شرکت کننده در کنفرانسی که در هفتم ژانویه در بوستون ماساچوست برگزار شد، به اتفاق آرا بر این باور بودند که اثبات مک گوایر احتمالا معتبر است و پیشرفت بزرگی در حوزه رو به گسترش ریاضیات سودوکو محسوب می شود.
جیسون روزنهاوس، ریاضیدان دانشگاه جیمز مدیسون در هریسونبرگ ویرجینیا و نویسنده کتاب تازه منتشر شده ریاضیات سودوکو می گوید: «این رویکرد منطقی و قابل قبول است. می توانم بگویم که برخوردها در قبال آن، حاکی از یک خوشبینی محتاطانه بود».کسانی که می خواهند یک معما را با استفاده از قوانین سودوکو حل کنند باید یک جدول ۹ در ۹ را به گونه ای پر کنند که هیچ رقمی در یک سطر یا ستون یا یکی از ۹ مربع ۳ در ۳ داخل جدول، تکرار نشود. راهنمایی ها، خانه هایی هستند که در ابتدای بازی پر شده اند. مدت ها است که علاقه مندان این بازی ها دریافته اندکه به رغم اینکه معماهایی با ۱۷ راهنمایی قابل حل هستند، ولی هیچ معمایی که با ۱۶ راهنمایی قابل حل باشد دیده نشده است. این امر به این گمان منجر شد که شاید معمایی وجود نداشته باشد که با ۱۶ راهنمایی به پاسخی یکتا برسد.
یک راه ممکن برای اثبات این گمان این بود که در تمام جدول های پر شده ممکن با استفاده از قوانین سودوکو، به دنبال همه معماهای ممکن با ۱۶ راهنمایی بگردند، ولی این کار نیاز به زمان بسیار زیادی برای محاسبه داشت. در نتیجه مک گوایر مسئله را با طراحی یک «الگوریتم برخورد مجموعه ها» ساده کرد. با این الگوریتم او باید به دنبال چیزی می گشت که خود، آن را مجموعه های اجتناب ناپذیر یا راه حل ها می نامید. برای اجتناب از این که یک مجموعه اجتناب ناپذیر منتج به راه حل های تکراری شود، راهنمایی ها باید همدیگر را بپوشانند یا به مجموعه های غیر قابل اجتناب برخورد کنند. وقتی که مجموعه های غیر قابل اجتناب پیدا شدند، کار محاسباتی خیلی کمتری لازم خواهد بود (هرچند هنوز هم مقدار قابل ملاحظه ای است) تا نشان داده شود که هیچ معمای ۱۶ راهنمایی نمی تواند با همه آنها برخورد کند.
مک گوایر و گروهش که دو سال را به آزمودن این الگوریتم گذرانده بودند، از تقریبا ۷۰۰ میلیون ساعت CPU در مرکز محاسبات پیشرفته ایرلند در دوبلین استفاده کردند تا با استفاده از الگوریتم برخورد مجموعه ها به دنبال جدول های ممکن بگردند. گوردون رویل، ریاضیدان دانشگاه استرالیای غربی در پرت که با استفاده از الگوریتم متفاوتی مشغول شمردن تعداد جدول های ممکن با ۱۷ راهنمایی است، می گوید: «تنها راه واقع گرایانه ممکن برای انجام این کار، روی آوردن به استفاده ناشیانه از کامپیوتر بود. این مسئله چالش برانگیزی است که مردم را ترغیب می کند تا حد ممکن از شیوه های ریاضی و محاسباتی استفاده کنند. این مانند بالا رفتن از بلندترین کوه است».
به گفته لائورا تالمان، ریاضیدان در دانشگاه جیمز مدیسون که در نوشتن کتاب «سودوکو را جدی بگیرید: ریاضیات پشت محبوب ترین معمای کاغذی» با روزنهاوس همکاری کرده، یکی از پیامدهای این رویکرد این است که وقتی را از دیگران می گیرد تا بتوانند برای بررسی این اثبات، زمان محاسباتی لازم را صرف کنند. تالمان اشاره می کند که این کتاب که هفته قبل منتشر شد، دیگر منسوخ شده است، چراکه در این کتاب آمده که مسئله باز می ماند و هر کسی که آن را حل کند، به ستاره ای در دنیای ریاضیات تبدیل خواهد شد.
مک گوایر می گوید که رویکرد او شاید به راه های دیگری غیر از مسیر ریاضیات هم برود. ایده برخورد مجموعه ها که او برای اثبات خود ایجاد کرده، در مقاله هایی در مورد تعیین توالی ژنی و شبکه های سلولی هم استفاده شده و او به دنبال این است که ببیند که آیا دیگر پژوهشگران نیز می توانند از الگوریتم او استفاده مفید کنند یا نه. وی می گوید: «امیدوارم که این کار، توجه بیشتری را به خود جلب کند».
ولی او به طنز ماجرا هم اشاره می کند که هر چه زمان بیشتری را به ریاضیات این معما اختصاص می دهد، زمان کمتری را به لذت بردن از آن می گذراند: «من هنوز این بازی را یک راه خوب برای استراحت می دانم، ولی صادقانه می گویم که حل کردن جدول کلمات متقاطع را ترجیح می دهم».
تصحیح: نیچر تصحیح کردکه زمان محاسبه ۷ میلیون ساعت سی.پی.یو و نه ۷۰۰ میلیون ساعت سی.پی.یو بود.