۱۷ نشانه، بهترین راه حل جدول سودوکو

۱۷ نشانه، بهترین راه حل جدول سودوکوبرای حل جدول سودوکو معمولا باید از راه آزمایش و خطا پیش رفت تا در آخر بتوان این جدول پیچیده اعداد را به آخر رساند. برای ساده‌تر شدن حل آن معمولا باید تعداد نشانه‌هایی وجود داشته باشد که تاکنون تعداد ۱۷ نشانه و نه کمتر برای حل سودوکو بهترین راه محسوب می‌شده و اکنون ریاضیدانان دانشگاه کالج دوبلین موفق به اثبات این عدد شده‌اند.

جدول سودوکو برای سطح پایه از یک مربع ۹ × ۹ از ردیفها و ستونهایی از خانه‌هایی ساخته شده که باید با اعداد یک تا ۹ پر شوند.

این جدول به ۹ بخش سه در سه تقسیم می‌شود و برای حل آن باید اعدادی در این مربعها قرار گیرند که در ستونها یا مربعها تکراری نباشند. در زمان ایجاد این جدول برخی از خانه‌های آن از پیش پر می‌شوند و آن را به صورت یک معما درمی‌آورند تا فرد با تلاش بتواند سایر خانه‌های جدول را پر کند.

در این جدول هر چه تعداد خانه‌های از پیش پر شده بیشتر باشد، نشانه‌های بیشتری برای حل کامل آن در اختیار فرد قرار گرفته و ساده‌تر خواهد شد.

گری مک‌گووایر و همکاران وی در دانشگاه کالج دوبلین برای اثبات عدد ۱۷ از رویکرد brute force استفاده کردند که در آن تمام پاسخ‌های ممکن برای خانه‌های خالی مورد استفاده قرار می‌گیرد. متاسفانه این رویکرد بسیار زمانبر بوده، از این رو این محققان از روش دیگر استفاده کردند.

در شیوه جدید آنها گزینه‌های معادل را کنار گذاشتند که باعث کاهش گزینه‌های مورد آزمایش می‌شود. این محققان همچنین یک برنامه روزمره نوشتند که به آزمایش احتمال معادل بودن زیرمجموعه‌های خاص جدول با گزینه‌های دیگر می‌پردازد که ضرورت آزمایش تمام گزینه‌ها را از بین می‌برد و کاهش قابل توجهی در زمان بوجود می‌آورد.

اگرچه اجرای این برنامه یک سال کامل بطول انجامید اما دانشمندان توانستند در انتها تعداد ۱۷ نشانه را برای حل جدول اثبات کنند.

برچسب‌ها, , , , , ,

تمامی حقوق محفوظ است
Copyright 2005-2014 © sudoku.ir All rights reserved. site by: yadaboo.ir