Rez@ee
11th January 2012, 07:54 PM
http://www.khabaronline.ir/Images/News/Smal_Pic/19-10-1390/IMAGE634616964534176155.jpg
دانش‌های بنیادی - مدتهاست که هیچ معمای سودوکویی با تنها 16 راهنمایی ارائه نمی شود. ریاضی‌دانی به کمک 700 میلیون ساعت محاسبات ابررایانه‌ای ثابت کرده است که حداقل تعداد راهنمایی‌های لازم برای حل یک سودوکو 17خانه است.
مجید جویا: یک ریاضیدان ایرلندی از الگوریتمی پیچیده و میلیون‌ها ساعت از زمان ابررایانه‌ها استفاده کرد تا بتواند پاسخ معمایی مهم وحل نشده در ریاضیات سودوکو را بیابد. بازی سودوکو که اولین بار در ژاپن همه پسند شد، از یک مربع 9 در 9 تشکیل شده که هر سطر و ستون آن باید با اعداد 1 تا 9 پر شود یه‌طوری که هر عدد در هر ستون، سطر یا 9 مربع 3در3 فقط بار ظاهر شود.
به گزارش نیچر (http://www.nature.com/news/mathematician-claims-breakthrough-in-sudoku-puzzle-1.9751)، گری مک‌گوایر از کالج دانشگاهی دوبلین در اثباتی که در اول ژانویه روی اینترنت قرار گرفت، نشان داد که کمترین تعداد راهنمایی‌ها (یا ارقام ابتدای بازی) که برای تکمیل یک بازی لازم است، 17 خانه است و جدول‌هایی با 16 راهنمایی یا کمتر، پاسخ یکتایی ندارند. بیشتر سودوکوهای روزنامه‌ای چیزی در حدود 25 راهنمایی دارند، و هرچه که تعداد راهنمایی‌ها بیشتر شود، سختی معما هم کمتر می‌شود.
ریاضیدانان شرکت کننده در کنفرانسی که در هفتم ژانویه در بوستون ماساچوست برگزار شد، به اتفاق آرا بر این باور بودند که اثبات مک‌گوایر احتمالا معتبر است و پیشرفت بزرگی در حوزه رو به گسترش ریاضیات سودوکو محسوب می‌شود.
جیسون روزنهاوس، ریاضیدان دانشگاه جیمز مدیسون در هریسونبرگ ویرجینیا و نویسنده کتاب تازه منتشر شده ریاضیات سودوکو می‌گوید: «این رویکرد منطقی و قابل قبول است. می‌توانم بگویم که برخوردها در قبال آن، حاکی از یک خوشبینی محتاطانه بود».
کسانی که می‌خواهند یک معما را با استفاده از قوانین سودوکو حل کنند باید یک جدول 9 در 9 را به گونه‌ای پر کنند که هیچ رقمی در یک سطر یا ستون یا یکی از 9 مربع 3 در 3 داخل جدول، تکرار نشود. راهنمایی‌ها، خانه‌هایی هستند که در ابتدای بازی پر شده‌اند. مدت‌ها است که علاقه‌مندان این بازی‌ها دریافته‌اندکه به رغم اینکه معماهایی با 17 راهنمایی قابل حل هستند، ولی هیچ معمایی که با 16 راهنمایی قابل حل باشد دیده نشده است. این امر به این گمان منجر شد که شاید معمایی وجود نداشته باشد که با 16 راهنمایی به پاسخی یکتا برسد.یک راه ممکن برای اثبات این گمان این بود که در تمام جدول‌های پر شده ممکن با استفاده از قوانین سودوکو، به دنبال همه معماهای ممکن با 16 راهنمایی بگردند، ولی این کار نیاز به زمان بسیار زیادی برای محاسبه داشت. در نتیجه مک‌گوایر مسئله را با طراحی یک «الگوریتم برخورد مجموعه‌ها» ساده کرد. با این الگوریتم او باید به دنبال چیزی می‌گشت که خود، آن را مجموعه‌های اجتنابناپذیر یا راه‌حل‌ها می‌نامید. برای اجتناب از این که یک مجموعه اجتنابناپذیر منتج به راه‌حل‌های تکراری شود، راهنمایی‌ها باید همدیگر را بپوشانند یا به مجموعه‌های غیر قابل اجتناب برخورد کنند. وقتی که مجموعه‌های غیر قابل اجتناب پیدا شدند، کار محاسباتی خیلی کمتری لازم خواهد بود (هرچند هنوز هم مقدار قابل ملاحظه‌ای است) تا نشان داده شود که هیچ معمای 16 راهنمایی نمی‌تواند با همه آنها برخورد کند.
مک‌گوایر و گروهش که دو سال را به آزمودن این الگوریتم گذرانده بودند، از تقریبا 700 میلیون ساعت CPU در مرکز محاسبات پیشرفته ایرلند در دوبلین استفاده کردند تا با استفاده از الگوریتم برخورد مجموعه‌ها به دنبال جدول‌های ممکن بگردند. گوردون رویل، ریاضیدان دانشگاه استرالیای غربی در پرت که با استفاده از الگوریتم متفاوتی مشغول شمردن تعداد جدول‌های ممکن با 17 راهنمایی است، می‌گوید: «تنها راه واقع‌گرایانه ممکن برای انجام این کار، روی آوردن به استفاده ناشیانه از کامپیوتر بود. این مسئله چالش‌برانگیزی است که مردم را ترغیب می‌کند تا حد ممکن از شیوه‌های ریاضی و محاسباتی استفاده کنند. این مانند بالا رفتن از بلندترین کوه است».
به گفته لائورا تالمان، ریاضیدان در دانشگاه جیمز مدیسون که در نوشتن کتاب «سودوکو را جدی بگیرید: ریاضیات پشت محبوب‌ترین معمای کاغذی» با روزنهاوس همکاری کرده، یکی از پیامدهای این رویکرد این است که وقتی را از دیگران می‌گیرد تا بتوانند برای بررسی این اثبات، زمان محاسباتی لازم را صرف کنند. تالمان اشاره می‌کند که این کتاب که هفته قبل منتشر شد، دیگر منسوخ شده است، چراکه در این کتاب آمده که مسئله باز می‌ماند و هر کسی که آن را حل کند، به ستاره‌ای در دنیای ریاضیات تبدیل خواهد شد.
مک‌گوایر می‌گوید که رویکرد او شاید به راه‌های دیگری غیر از مسیر ریاضیات هم برود. ایده برخورد مجموعه‌ها که او برای اثبات خود ایجاد کرده، در مقاله‌هایی در مورد تعیین توالی ژنی و شبکه‌های سلولی هم استفاده شده و او به دنبال این است که ببیند که آیا دیگر پژوهشگران نیز می‌توانند از الگوریتم او استفاده مفید کنند یا نه. وی می‌گوید: «امیدوارم که این کار، توجه بیشتری را به خود جلب کند».
ولی او به طنز ماجرا هم اشاره می‌کند که هر چه زمان بیشتری را به ریاضیات این معما اختصاص می‌دهد، زمان کمتری را به لذت بردن از آن می‌گذراند: «من هنوز این بازی را یک راه خوب برای استراحت می دانم، ولی صادقانه می‌گویم که حل کردن جدول کلمات متقاطع را ترجیح می‌دهم».
تصحیح: نیچر تصحیح کردکه زمان محاسبه 7 میلیون ساعت سی.پی.یو و نه 700 میلیون ساعت سی.پی.یو بود
خبرانلاین
دانش‌های بنیادی - مدتهاست که هیچ معمای سودوکویی با تنها 16 راهنمایی ارائه نمی شود. ریاضی‌دانی به کمک 700 میلیون ساعت محاسبات ابررایانه‌ای ثابت کرده است که حداقل تعداد راهنمایی‌های لازم برای حل یک سودوکو 17خانه است.
مجید جویا: یک ریاضیدان ایرلندی از الگوریتمی پیچیده و میلیون‌ها ساعت از زمان ابررایانه‌ها استفاده کرد تا بتواند پاسخ معمایی مهم وحل نشده در ریاضیات سودوکو را بیابد. بازی سودوکو که اولین بار در ژاپن همه پسند شد، از یک مربع 9 در 9 تشکیل شده که هر سطر و ستون آن باید با اعداد 1 تا 9 پر شود یه‌طوری که هر عدد در هر ستون، سطر یا 9 مربع 3در3 فقط بار ظاهر شود.
به گزارش نیچر (http://www.nature.com/news/mathematician-claims-breakthrough-in-sudoku-puzzle-1.9751)، گری مک‌گوایر از کالج دانشگاهی دوبلین در اثباتی که در اول ژانویه روی اینترنت قرار گرفت، نشان داد که کمترین تعداد راهنمایی‌ها (یا ارقام ابتدای بازی) که برای تکمیل یک بازی لازم است، 17 خانه است و جدول‌هایی با 16 راهنمایی یا کمتر، پاسخ یکتایی ندارند. بیشتر سودوکوهای روزنامه‌ای چیزی در حدود 25 راهنمایی دارند، و هرچه که تعداد راهنمایی‌ها بیشتر شود، سختی معما هم کمتر می‌شود.
ریاضیدانان شرکت کننده در کنفرانسی که در هفتم ژانویه در بوستون ماساچوست برگزار شد، به اتفاق آرا بر این باور بودند که اثبات مک‌گوایر احتمالا معتبر است و پیشرفت بزرگی در حوزه رو به گسترش ریاضیات سودوکو محسوب می‌شود.
جیسون روزنهاوس، ریاضیدان دانشگاه جیمز مدیسون در هریسونبرگ ویرجینیا و نویسنده کتاب تازه منتشر شده ریاضیات سودوکو می‌گوید: «این رویکرد منطقی و قابل قبول است. می‌توانم بگویم که برخوردها در قبال آن، حاکی از یک خوشبینی محتاطانه بود».
کسانی که می‌خواهند یک معما را با استفاده از قوانین سودوکو حل کنند باید یک جدول 9 در 9 را به گونه‌ای پر کنند که هیچ رقمی در یک سطر یا ستون یا یکی از 9 مربع 3 در 3 داخل جدول، تکرار نشود. راهنمایی‌ها، خانه‌هایی هستند که در ابتدای بازی پر شده‌اند. مدت‌ها است که علاقه‌مندان این بازی‌ها دریافته‌اندکه به رغم اینکه معماهایی با 17 راهنمایی قابل حل هستند، ولی هیچ معمایی که با 16 راهنمایی قابل حل باشد دیده نشده است. این امر به این گمان منجر شد که شاید معمایی وجود نداشته باشد که با 16 راهنمایی به پاسخی یکتا برسد.یک راه ممکن برای اثبات این گمان این بود که در تمام جدول‌های پر شده ممکن با استفاده از قوانین سودوکو، به دنبال همه معماهای ممکن با 16 راهنمایی بگردند، ولی این کار نیاز به زمان بسیار زیادی برای محاسبه داشت. در نتیجه مک‌گوایر مسئله را با طراحی یک «الگوریتم برخورد مجموعه‌ها» ساده کرد. با این الگوریتم او باید به دنبال چیزی می‌گشت که خود، آن را مجموعه‌های اجتنابناپذیر یا راه‌حل‌ها می‌نامید. برای اجتناب از این که یک مجموعه اجتنابناپذیر منتج به راه‌حل‌های تکراری شود، راهنمایی‌ها باید همدیگر را بپوشانند یا به مجموعه‌های غیر قابل اجتناب برخورد کنند. وقتی که مجموعه‌های غیر قابل اجتناب پیدا شدند، کار محاسباتی خیلی کمتری لازم خواهد بود (هرچند هنوز هم مقدار قابل ملاحظه‌ای است) تا نشان داده شود که هیچ معمای 16 راهنمایی نمی‌تواند با همه آنها برخورد کند.
مک‌گوایر و گروهش که دو سال را به آزمودن این الگوریتم گذرانده بودند، از تقریبا 700 میلیون ساعت CPU در مرکز محاسبات پیشرفته ایرلند در دوبلین استفاده کردند تا با استفاده از الگوریتم برخورد مجموعه‌ها به دنبال جدول‌های ممکن بگردند. گوردون رویل، ریاضیدان دانشگاه استرالیای غربی در پرت که با استفاده از الگوریتم متفاوتی مشغول شمردن تعداد جدول‌های ممکن با 17 راهنمایی است، می‌گوید: «تنها راه واقع‌گرایانه ممکن برای انجام این کار، روی آوردن به استفاده ناشیانه از کامپیوتر بود. این مسئله چالش‌برانگیزی است که مردم را ترغیب می‌کند تا حد ممکن از شیوه‌های ریاضی و محاسباتی استفاده کنند. این مانند بالا رفتن از بلندترین کوه است».
به گفته لائورا تالمان، ریاضیدان در دانشگاه جیمز مدیسون که در نوشتن کتاب «سودوکو را جدی بگیرید: ریاضیات پشت محبوب‌ترین معمای کاغذی» با روزنهاوس همکاری کرده، یکی از پیامدهای این رویکرد این است که وقتی را از دیگران می‌گیرد تا بتوانند برای بررسی این اثبات، زمان محاسباتی لازم را صرف کنند. تالمان اشاره می‌کند که این کتاب که هفته قبل منتشر شد، دیگر منسوخ شده است، چراکه در این کتاب آمده که مسئله باز می‌ماند و هر کسی که آن را حل کند، به ستاره‌ای در دنیای ریاضیات تبدیل خواهد شد.
مک‌گوایر می‌گوید که رویکرد او شاید به راه‌های دیگری غیر از مسیر ریاضیات هم برود. ایده برخورد مجموعه‌ها که او برای اثبات خود ایجاد کرده، در مقاله‌هایی در مورد تعیین توالی ژنی و شبکه‌های سلولی هم استفاده شده و او به دنبال این است که ببیند که آیا دیگر پژوهشگران نیز می‌توانند از الگوریتم او استفاده مفید کنند یا نه. وی می‌گوید: «امیدوارم که این کار، توجه بیشتری را به خود جلب کند».
ولی او به طنز ماجرا هم اشاره می‌کند که هر چه زمان بیشتری را به ریاضیات این معما اختصاص می‌دهد، زمان کمتری را به لذت بردن از آن می‌گذراند: «من هنوز این بازی را یک راه خوب برای استراحت می دانم، ولی صادقانه می‌گویم که حل کردن جدول کلمات متقاطع را ترجیح می‌دهم».
تصحیح: نیچر تصحیح کردکه زمان محاسبه 7 میلیون ساعت سی.پی.یو و نه 700 میلیون ساعت سی.پی.یو بود
خبرانلاین