مدتهاست که هیچ معمای سودوکویی با تنها 16 راهنمایی ارائه نمی شود. ریاضی‌دانی به کمک 700 میلیون ساعت محاسبات ابررایانه‌ای ثابت کرده است که حداقل تعداد راهنمایی‌های لازم برای حل یک سودوکو 17خانه است.

مجید جویا: یک ریاضی‌دان ایرلندی از الگوریتمی پیچیده و میلیون‌ها ساعت از زمان ابررایانه‌ها استفاده کرد تا بتواند پاسخ معمایی مهم وحل نشده در ریاضیات سودوکو را بیابد. بازی سودوکو که اولین بار در ژاپن همه‌ پسند شد، از یک مربع 9 در 9 تشکیل شده که هر سطر و ستون آن باید با اعداد 1 تا 9 پر شود یه‌طوری که هر عدد در هر ستون، سطر یا 9 مربع 3در3 فقط بار ظاهر شود.
به گزارش نیچر، گری مک‌گوایر از کالج دانشگاهی دوبلین در اثباتی که در اول ژانویه روی اینترنت قرار گرفت، نشان داد که کمترین تعداد راهنمایی‌ها (یا ارقام ابتدای بازی) که برای تکمیل یک بازی لازم است، 17 خانه است و جدول‌هایی با 16 راهنمایی یا کمتر، پاسخ یکتایی ندارند. بیشتر سودوکوهای روزنامه‌ای چیزی در حدود 25 راهنمایی دارند، و هرچه که تعداد راهنمایی‌ها بیشتر شود، سختی معما هم کمتر می‌شود.
ریاضیدانان شرکت کننده در کنفرانسی که در هفتم ژانویه در بوستون ماساچوست برگزار شد، به اتفاق آرا بر این باور بودند که اثبات مک‌گوایر احتمالا معتبر است و پیشرفت بزرگی در حوزه رو به گسترش ریاضیات سودوکو محسوب می‌شود.
جیسون روزنهاوس، ریاضیدان دانشگاه جیمز مدیسون در هریسونبرگ ویرجینیا و نویسنده کتاب تازه منتشر شده ریاضیات سودوکو می‌گوید: «این رویکرد منطقی و قابل قبول است. می‌توانم بگویم که برخوردها در قبال آن، حاکی از یک خوشبینی محتاطانه بود».
کسانی که می‌خواهند یک معما را با استفاده از قوانین سودوکو حل کنند باید یک جدول 9 در 9 را به گونه‌ای پر کنند که هیچ رقمی در یک سطر یا ستون یا یکی از 9 مربع 3 در 3 داخل جدول، تکرار نشود. راهنمایی‌ها، خانه‌هایی هستند که در ابتدای بازی پر شده‌اند. مدت‌ها است که علاقه‌مندان این بازی‌ها دریافته‌اندکه به رغم اینکه معماهایی با 17 راهنمایی قابل حل هستند، ولی هیچ معمایی که با 16 راهنمایی قابل حل باشد دیده نشده است. این امر به این گمان منجر شد که شاید معمایی وجود نداشته باشد که با 16 راهنمایی به پاسخی یکتا برسد.

یک راه ممکن برای اثبات این گمان این بود که در تمام جدول‌های پر شده ممکن با استفاده از قوانین سودوکو، به دنبال همه معماهای ممکن با 16 راهنمایی بگردند، ولی این کار نیاز به زمان بسیار زیادی برای محاسبه داشت. در نتیجه مک‌گوایر مسئله را با طراحی یک «الگوریتم برخورد مجموعه‌ها» ساده کرد. با این الگوریتم او باید به دنبال چیزی می‌گشت که خود، آن را مجموعه‌های اجتنابناپذیر یا راه‌حل‌ها می‌نامید. برای اجتناب از این که یک مجموعه اجتناب‌ناپذیر منتج به راه‌حل‌های تکراری شود، راهنمایی‌ها باید همدیگر را بپوشانند یا به مجموعه‌های غیر قابل اجتناب برخورد کنند. وقتی که مجموعه‌های غیر قابل اجتناب پیدا شدند، کار محاسباتی خیلی کمتری لازم خواهد بود (هرچند هنوز هم مقدار قابل ملاحظه‌ای است) تا نشان داده شود که هیچ معمای 16 راهنمایی نمی‌تواند با همه آنها برخورد کند.
مک‌گوایر و گروهش که دو سال را به آزمودن این الگوریتم گذرانده بودند، از تقریبا 700 میلیون ساعت CPU در مرکز محاسبات پیشرفته ایرلند در دوبلین استفاده کردند تا با استفاده از الگوریتم برخورد مجموعه‌ها به دنبال جدول‌های ممکن بگردند. گوردون رویل، ریاضیدان دانشگاه استرالیای غربی در پرت که با استفاده از الگوریتم متفاوتی مشغول شمردن تعداد جدول‌های ممکن با 17 راهنمایی است، می‌گوید: «تنها راه واقع‌گرایانه ممکن برای انجام این کار، روی آوردن به استفاده ناشیانه از کامپیوتر بود. این مسئله چالش‌برانگیزی است که مردم را ترغیب می‌کند تا حد ممکن از شیوه‌های ریاضی و محاسباتی استفاده کنند. این مانند بالا رفتن از بلندترین کوه است».
به گفته لائورا تالمان، ریاضیدان  در دانشگاه جیمز مدیسون که در نوشتن کتاب «سودوکو را جدی بگیرید: ریاضیات پشت محبوب‌ترین معمای کاغذی» با روزنهاوس همکاری کرده، یکی از پیامدهای این رویکرد این است که وقتی را از دیگران می‌گیرد تا بتوانند برای بررسی این اثبات، زمان محاسباتی لازم را صرف کنند. تالمان اشاره می‌کند که این کتاب که هفته قبل منتشر شد، دیگر منسوخ شده است، چراکه در این کتاب آمده که مسئله باز می‌ماند و هر کسی که آن را حل کند، به ستاره‌ای در دنیای ریاضیات تبدیل خواهد شد.
مک‌گوایر می‌گوید که رویکرد او شاید به راه‌های دیگری غیر از مسیر ریاضیات هم برود. ایده برخورد مجموعه‌ها که او برای اثبات خود ایجاد کرده، در مقاله‌هایی در مورد تعیین توالی ژنی و شبکه‌های سلولی هم استفاده شده و او به دنبال این است که ببیند که آیا دیگر پژوهشگران نیز می‌توانند از الگوریتم او استفاده مفید کنند یا نه. وی می‌گوید: «امیدوارم که این کار، توجه بیشتری را به خود جلب کند».
ولی او به طنز ماجرا هم اشاره می‌کند که هر چه زمان بیشتری را به ریاضیات این معما اختصاص می‌دهد، زمان کمتری را به لذت بردن از آن می‌گذراند: «من هنوز این بازی را یک راه خوب برای استراحت می دانم، ولی صادقانه می‌گویم که حل کردن جدول کلمات متقاطع را ترجیح می‌دهم».

تصحیح:  نیچر تصحیح کردکه زمان محاسبه 7 میلیون ساعت سی.پی.یو و نه 700 میلیون ساعت سی.پی.یو بود
53271

برای دسترسی سریع به تازه‌ترین اخبار و تحلیل‌ رویدادهای ایران و جهان اپلیکیشن خبرآنلاین را نصب کنید.
کد خبر 193272

برچسب‌ها

نظر شما

شما در حال پاسخ به نظر «» هستید.
4 + 12 =

نظرات

  • نظرات منتشر شده: 19
  • نظرات در صف انتشار: 0
  • نظرات غیرقابل انتشار: 0
  • بدون نام IR ۱۱:۵۸ - ۱۳۹۰/۱۰/۱۹
    6 11
    منظور از 700000000 ساعت را نفهمیدم؟چه کامپیوتر باشه چه انسان 700 میلیون ساعت یعنی 700 میلیون ساعت. یعنی 79908 سال!نکنه منظورتون 700 میلیون محاسبه باشه؟
    • دبیر سرویس دانش IR ۱۲:۳۱ - ۱۳۹۰/۱۰/۱۹
      30 1
      با تشکر از دقت شما کاربر عزیز، اگر به ترجمه خبر دقت کنید، متوجه می‌شوید که 700 میلیون ساعت زمان سی.پی.یو برای انجام این محاسبات استفاده شده است. اگر این محاسبات فقط با استفاده از یک سی.پی.یو انجام می‌شد (مانند ریزپردازنده مرکزی یک دستگاه رایانه شخصی معمولی که در نمونه‌های 1.5 گیگاهرتز بیش از 1.5 میلیارد محاسبه در ثانیه است) آنگاه این محاسبات 700 میلیون ساعت طول می‌کشید؛ اما از آن‌جا که ابررایانه‌ها از هزاران سی.پی.یو استفاده می‌کنند و سرعت پردازش آن‌ها نیز بیشتر از پردازنده‌های معمولی است، این محاسبات زمان به‌مراتب کم‌تری طول کشیده است. این مزیت مهم ابررایانه‌ها به افزایش استفاده از آنها در تحقیقات علمی منجر شده است.
    • بدون نام IR ۱۲:۴۵ - ۱۳۹۰/۱۰/۱۹
      3 17
      به هر حال باز هم گفتار شما نمی‌تواند منطقی باشد. منظور شما دقیقاً از ساعت چیست؟ Clock در پردازنده است؟
    • سالار IR ۱۳:۰۳ - ۱۳۹۰/۱۰/۱۹
      12 3
      خیلی کار خوبی کردین جوابش را دادین. ولی بچه ها خوبه نسبت به چیزی اطلاع ندارند مجادله نکنند. با یک سرچ ساده متوجه درستی پاسخ دبیر سرویس می شوید. گوگل کنید. مطلب فارسی هم زیاد است.
    • دبیر سرویس دانش IR ۱۳:۰۸ - ۱۳۹۰/۱۰/۱۹
      14 0
      کامپیوتری را در نظر بگیرید که سی.پی.یو آن تک هسته‌ای با سرعت 1.6 گیگا هرتز است. این ریزپردازنده در هر ثانیه 1.6 میلیارد محاسبه انجام می‌دهد. اگر از این ریزپردازنده به مدت یک ساعت استفاده کنید، آن‌گاه یک ساعت سی.پی.یو برای محاسبات خود صرف کرده‌اید که با احتساب سرعت پردازنده، شما حدود 5800 میلیارد محاسبه انجام داده‌اید. اگر ریزپردازنده شما دوهسته‌ای باشد، به ازای همان 1 ساعت فعالیت، شما 2 ساعت سی.پی.یو برای محاسبه خود صرف کرده‌اید و می‌توانید دو برابر محاسبات را انجام دهید.
    • دبیر سرویس دانش IR ۱۳:۰۹ - ۱۳۹۰/۱۰/۱۹
      11 1
      برای استفاده از یک ابررایانه که از تعداد زیادی ریزپردازنده مرکزی تشکیل شده، از واحد زمان سی.پی.یو استفاده می‌کنند، این مقدار از تقسیم تعداد تخمینی محاسبات بر سرعت محاسبه هر پردازنده بدست می‌آید. هشتصد میلیون ساعت سی.پی.یو بدان معنی است که برای انجام این محاسبات 800 میلیون ساعت-سی.پی.یو هزینه شده است. یعنی شما می‌توانید با استفاده از 800 میلیون سی.پی.یو این محاسبات را در یک ساعت انجام دهید که برای انجام آن با استفاده از یک سی.پی.یو، 800 میلیون ساعت باید وقت بگذارید. اگر فرض کنیم این ابررایانه 10هزار ریزپردازنده شش هسته‌ای داشته باشد، آن‌گاه در هر ساعت از 60 هزار هسته محاسباتی بهره می‌برد و طی یک و نیم سال به 800 میلیون ساعت سی.پی.یو خواهد رسید.
  • بدون نام IR ۱۱:۵۹ - ۱۳۹۰/۱۰/۱۹
    7 13
    دوست عزيز مترجم! تيتر و ترجمه خبر شما از لحاظ علمي اشتباه است.اگر به منبع اصلي خبر در نشريه نيچر مراجعه كنيد نوشته شده: McGuire and his team used about 7 million CPU hours اين عبارت به اين معنا نيست كه 700 ميليون ساعت محاسبه به طول انجاميده. 700 ميليون ساعت چيزي در حدود 1000 سال است.بلكه اين بدين معناست كه ابررايانه مورد استفاده در ساعت 700 ميليون محاسبه قادر به انجام دادن بوده است. لطفا در ترجمه خبرهادقت بيشتري بفرماييد.
    • دبیر سرویس دانش IR ۱۲:۳۴ - ۱۳۹۰/۱۰/۱۹
      21 1
      متاسفانه برداشت شما کاربر عزیز از متن اصلی اشتباه است. ریزپردازنده‌ای که در هر ساعت 700 میلیون محاسبه انجام دهد، در هر ثانیه 195هزار محاسبه انجام خواهد داد، یعنی سرعت آن چیزی حدود 200 کیلوهرتز خواهد بود و این فناوری مربوط به اواخر دهه 1990 میلادی است! ریزپردازنده‌هایی که امروزه در گوشی‌های همراه هوشمند و تبلت‌ها استفاده می‌شوند سرعتی بیش از 1 گیگاهرتز (یعنی بیش از 1 میلیارد محاسبه در ثانیه )دارند.
    • بدون نام IR ۱۲:۵۷ - ۱۳۹۰/۱۰/۱۹
      20 1
      آقا صلوات بفرستید
  • بدون نام IR ۱۲:۲۳ - ۱۳۹۰/۱۰/۱۹
    2 33
    توجه: هفتصد میلیون ساعت = 800 قرن! چشم بسته هر مطلبی را منتشر نکنید.
    • بدون نام IR ۱۵:۵۱ - ۱۳۹۰/۱۰/۱۹
      11 2
      لطف کنید و چشمتان را باز کنید و به توضیحاتی که برای کامنتها دیگر گذاشته شده توجه کنید تا مفهوم ساعت CPU را با ساعت عادی اشتباه نگیرید.
  • مهندس الکترونیک IR ۱۲:۵۸ - ۱۳۹۰/۱۰/۱۹
    24 1
    من از این دوستان که نظر مخالف گذاشتن میخام بپرسم که وقتی میگویند فلان کار مثلا 25 میلیون نفر ساعت طول کشیده معنی اینه که اگر یک نفر این کار رو میکرد 25 میلیون ساعت طول میکشه، ولی وقتی نفرات بیشتر و ماشین آلات( که توانایی چندین نفر رو دارن) هم استفاده میشن مثلا این پروژه تو 2 سال تموم میشه. پس از دوستان خواهش میکنم که به مبنای محاسبات و تبدیل آنها توجه بیشتری بکنن، چون این عدد و ترجمه اون کاملا از نظر علمی درسته.
    • بدون نام IR ۲۰:۳۶ - ۱۳۹۰/۱۰/۲۰
      0 4
      اولاً نظر مخالف نیست. یک بحث فنی است. بحث بر سر این است که ترجمه و تیتر این خبر مناسب نیست.
  • حامد IR ۱۵:۱۴ - ۱۳۹۰/۱۰/۱۹
    19 2
    اصلا هیچکس به خود خبر که درباره سودوکو بود اهمیتی نداده
    • بدون نام IR ۱۳:۰۲ - ۱۳۹۰/۱۰/۲۰
      6 1
      شدیدا دمت گرم
  • مسعود IR ۱۹:۰۵ - ۱۳۹۰/۱۰/۱۹
    8 1
    دوست عزیز که مخالفی بهتره بری از اول راهنمایی ریاضی بخونی
  • بدون نام US ۰۲:۴۸ - ۱۳۹۰/۱۰/۲۳
    2 1
    دعوا نکنید سایت نیچر درست کرد. 7 میلیون ساعت
  • بدون نام IR ۱۳:۵۸ - ۱۳۹۰/۱۰/۳۰
    3 1
    يعني دوستان هنوز واژه هايي مثل "نفر-ساعت" "كيلومتر - مسافر" و امثال اينو نشنيدن كه از شنيدن "سي پي يو- ساعت" تعجب كردن؟
  • مهندس کامپیوتر IR ۰۱:۲۱ - ۱۳۹۱/۰۱/۲۱
    2 0
    سلام دوستان ، بحث جالبی بود ، و با اینکه به قول دوستمون با هم مجادله کردین ،اما خوبه که ما هم یه چیزایی یاد گرفتیم ولی این هم بدونیم که معمولا سرعت ابر رایانه ها با تعداد پردازش در ثانیه اعلام میشن مثلا ( 1 کوادریلیون در ثانیه ) = 1000000000000000 پردازش در ثانیه . موفق باشید