איך מחשבים פותרים סודוקו

עודכן ב־2026-10-05

חיפוש בנסיגה

הפותר מנסה להציב בתא ריק ספרה המותרת לפי הכללים וממשיך הלאה. אם אף ספרה אינה מובילה לפתרון, הוא מבטל בחירה קודמת ומנסה אחרת. בחירה תחילה בתא שמספר הספרות האפשריות בו הוא הקטן ביותר מקצרת לעיתים קרובות את החיפוש במידה רבה.

מקורות: Wikipedia: Sudoku solving algorithms, Peter Norvig: Solving Every Sudoku Puzzle

כיסוי מדויק ו-Dancing Links

אפשר לנסח מחדש סודוקו כבעיית כיסוי מדויק: בוחרים הצבות כך שכל תא, וכל ספרה בכל שורה, עמודה וריבוע, יכוסו בדיוק פעם אחת. במאמר מנובמבר 2000 תיאר דונלד קנות' את Dancing Links, דרך יעילה להריץ את אלגוריתם X שלו לחיפוש בנסיגה; כשהוא מיושם על מודל הכיסוי המדויק של סודוקו, הוא מוצא במהירות את כל הפתרונות של חידה.

מקורות: Wikipedia: Sudoku solving algorithms, Knuth, Dancing links (arXiv cs/0011047, 2000)

חיפוש אקראי

תוכנות מסוימות ממלאות את הלוח באקראי ואז משנות את סידור המספרים כדי לצמצם את מספר הסתירות, באמצעות שיטות כגון חישול מדומה או אלגוריתמים גנטיים. שיטות אלה נחקרו כגישות חלופיות; מידת הצלחתן תלויה בתוכנה ובחידה.

מקורות: Wikipedia: Sudoku solving algorithms

פותרים שחושבים כמו בני אדם

למנוע רמזים יש תפקיד אחר: לא רק למצוא את התשובה, אלא להציג את הצעד הבא שאדם יכול לעקוב אחריו. המנוע של האפליקציה שלנו מנסה טכניקות אנושיות בסדר קבוע, מהקלות ביותר, כגון יחיד נסתר, ועד הקשות ביותר, כגון שרשראות וקבוצות כמעט נעולות, ומשתמש בטכניקה הראשונה שמובילה להצבת ספרה; הטכניקות הקשות יותר פועלות תחילה באמצעות פסילת מועמדים. הטכניקה הקשה ביותר שבה הוא משתמש בחידה קובעת את רמת החידה באפליקציה.

מקורות: מה כל רמת קושי בסודוקו דורשת מכם

ראו גם

מקורות

כל המאמרים →