17 نشانه، بهترين راه حل جدول سودوكو

به گزارش سرويس علمي خبرگزاري دانشجويان ايران (ايسنا)، جدول سودوكو براي سطح پايه از يك مربع 9 در 9 از رديفها و ستونهايي از خانه‌هايي ساخته شده كه بايد با اعداد يك تا 9 پر شوند.

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

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

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

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

اگرچه اجراي اين برنامه يك سال كامل بطول انجاميد اما دانشمندان توانستند در انتها تعداد 17 نشانه را براي حل جدول اثبات كنند.