סודוקו
מתוך ויקיפדיה, האנציקלופדיה החופשית
סוּדוֹקוּ (יפנית: 数独) הוא חידה שבה יש למקם ספרות על לוח משובץ שגודלו 9×9 , המורכב מלוחות של 3×3. מטרת המשחק - למקם את המספרים 1 עד 9 על גבי לוח המשחק כך שבאותו טור, באותה שורה ובאותו אזור לא יופיע אותו מספר יותר מפעם אחת.
בלוח סודוקו ממוקמים מספרים, אשר יש להתייחס אליהם בעת מיקום המספרים במהלך המשחק.
המשחק הפך פופולרי ביפן בשנת 1986 ובבריטניה, בקנדה ובישראל בשנת 2005 בעקבות קידום המשחק בעיתונות.
תוכן עניינים |
[עריכה] היסטוריה
המשחק הומצא לראשונה בסין בשלהי המאה ה-18 ומשם עבר לאוסטריה ומאוסטריה לארצות הברית. משחק זה הופיע לראשונה בעיתון ניו יורקי בשם "Math Puzzles and Logic Problems" ("תשבצים מתמטיים ובעיות היגיון") בשנות ה-70 של המאה ה-20.
לא ידוע מי ייצר את הסודוקו הראשון.
המשחק הופיע בראשונה ביפן בשנת 1984 ונקרא: "סואוז'י ווא דוקושין ני קאגירו" (数字は独身に限る) שמשמעו - "המספר מוגבל רק בבדידותו (=היותו בלתי נשוי)" בהמשך קוצר השם ל"סודוקו", שמשמעו ביפנית (נוסף על היותו ראשי תיבות של הביטוי לעיל) "מספר יחיד" (数独).
בשנת 1997, שופט בדימוס הונג קונגי בשם ויין גולד, המתגורר בניו זילנד כתב תוכנית מחשב המייצרת תשבצים אלה ומכר אותה לעיתון "הטיימס" הבריטי, אשר החל במדור יומי קבוע בעיתון.
כיום החידות מפורסמות ביפן ובבריטניה גם בעיתונים יומיים, וכן בעיתון ה-"New York Post" בניו יורק. גם העיתונים האוסטרליים "האוסטרליאן" וה"סידני מורנינג הרלד" החלו בפירסום מדורים קבועים.
בשנת 2005 גם עיתונים ישראלים החלו לפרסם סודוקו על בסיס קבוע. בישראל פורסם סודוקו בירחון התשבצים "ניקוי ראש ענק", עוד לפני שפשטה האופנה בעיתונים, תחת השם "תשע ברבוע". בירחון זה פורסמו גם שעשועוני קאקורו תחת השם "מספרים וסיכומים".
בחודש מרס 2006, בעיר "לוקה", באיטליה, התקיימה אליפות העולם הראשונה לפתרון סודוקו. המשתתפים היו בני כל הגילים מגיל 15 (המשתתף מגרמניה) ועד גיל 61 (המשתתף מאיטליה). באליפות השתתפו 85 איש מ-22 מדינות. כלכלנית ורואת חשבון צ'כית בת 31 בשם יאנה טיילובה מהעיר מוסט זכתה באליפות. יאנה הקדימה בדירוג את תומס סניידר, בוגר אוניברסיטת הרווארד בן 26 שסיים במקום השני ואת וויי-הא-הואן בן 30, מהנדס תוכנה בגוגל, קליפורניה שסיים במקום השלישי. את הגביע העניק למנצחת השופט ויין גולד. לא ידוע עדיין אם ומתי תתקיים האליפות הבאה.
[עריכה] הוראות המשחק
המשחק מתבצע על טבלה של 9×9 ריבועים המסודרים בתשעה אזורים של 3×3 ריבועים. בחלק מהריבועים נמצאים מספרים ויש להשלים ולמלא את יתרת הריבועים הריקים במספרים בין 1 ל- 9, כך שבאותו טור, באותה שורה ובאותו אזור לא יופיע אותו מספר יותר מפעם אחת.
[עריכה] שיטות פתרון
[עריכה] שלב ראשון
שיטת הפתרון המומלצת היא חיפוש של מספרים החסרים באזורים (אזור=3X3 ריבועים) והשלמתם לפי המיקום האפשרי באזור. כמו בדוגמה המוצגת - חיפוש היכן אפשר להציב את המספר 7 באזור השמאלי העליון. זוהי בעצם אלימינציה של המיקומים שבהם המספר לא יוכל להשתבץ.
טיפ 1 לשלב הראשון כדי לבחור איזה מספר כדאי לחפש כדאי לרשום בצד את כל המספרים (1 עד 9) ולידם כמה פעמים הם מופיעים כבר. המספר הכי נפוץ הוא המספר שהכי קל יהיה להשלים את שאר המיקומים החסרים שלו. כך, נתחיל מהמספר הכי נפוץ ונמשיך עם הנפוצים יותר עד שנסיים במספר הכי פחות נפוץ.
טיפ 2 לשלב ראשון עבור כל אזור שנבדוק, אם אין מיקום אחד ודאי שבו יכול להשתבץ המספר, נסמן כל ריבוע שבו המספר יכול להיות בסימון קטן עם עיפרון את המספר שבדקנו - למשל נסמן 7 קטן בפינה של הריבוע.
טיפ 3 לשלב ראשון לא לשכוח - כל פעם שנזהה בודאות מספר בריבוע מסוים, נרשום אותו ונמחוק (נשים איקס) את הסימונים של אותו מספר באזור, בשורה ובעמודה שלו - מאחר והוא כבר לא יופיע שוב בהם. אם נראה שמחיקת סימון משאירה מיקום אחד בלבד שמספר יכול להופיע באזור, עמודה או שורה - זהו המיקום הודאי שלו!
[עריכה] שלב שני
לאחר מעבר על כל המספרים, והשלמת המיקומים הודאיים שלהם, נישאר עם מיקומים נוספים שבהם סימנו איזה מספרים יכולים להיות בהם. עכשיו אפשר לעבור על אזורים, שורות או עמודות שבהם נשארו מעט (2 או 3) ריבועים ריקים, ונבדוק איזה מספרים נשארו בהם ובאיזה מיקומים. כך נוכל להצליב שוב מספרים ומיקומים ולפתור עוד ריבועים.
[עריכה] שלב שלישי
ככל שהתשבץ קשה יותר, יש יותר מיקומים שאין להם מספר ודאי שנזהה בשלבים שהצגנו. במקרה של תשבץ קשה נגיע לשלב שיש מיקומים עם מספר סימונים שאלימינציה לא פותרת וצריך להתחיל עם ניסוי וטעיה. יש לבחור צומת החלטה קריטי ולבחור בו אחת מהאפשרויות. צומת קריטי - מיקום בו יש מעט (עדיף 2) מספרים אפשריים, ובחירת מספר אחד יזהה בודאות מספרים במיקומים אחרים. כך נמשיך עד שנפסול את האפשרות שבחרנו (תוביל לכפילות באזור, שורה או עמודה), או שנראה שהיא פותרת את התשבץ. האתגר הוא בחירת צומת ההחלטה הנכון שיוביל לפתרון. צומת לא טוב לא יקדם אותנו הרבה.
[עריכה] נוסחים שונים
משחק של 9×9 הינו הנפוץ ביותר אולם אפשריות גם חידות של 4 אזורים של 2×2, וכן חידות של 4 אזורים של 5×5. נוסח קשה במיוחד הוא של 16×16 משבצות עם 16 אזורים, של 4×4. קיימות גם חידות פחות סימטריות של 6 אזורים של 2×3.
כמו כן קיימת גרסאות מתקדמות יותר של הסודוקו:
- סודוקו X, בו גם שני האלכסונים הראשיים מכילים את הספרות 1 עד 9.
- סאמוראי סודוקו, שהוא שילוב של מספר לוחות סודוקו, המחוברים ביניהם.
- קילר סודוקו, מעין שילוב של סודוקו וקאקורו. מכיל "כלובים" עם מספרים, כאשר כל מספר מציין את סכום הספרות הנמצאות באותו כלוב. נחשב על ידי רבים לגרסה המאתגרת ביותר של הסודוקו.
[עריכה] סודוקו ומתמטיקה
בעיית פתירת הסודוקו ללוח בגודל משתנה, ידועה כבעיה NP-שלמה [1].
מתמטיקאים הציעו לטפל בבעיית הסודוקו על ידי בניית מודל מתמטי שלו. המודל המוצע הוא גרף, והמטרה היא להתבסס על תוצאות תורת הגרפים. לפי מודל זה לוח הסודוקו הוא גרף ובעיית שיבוץ 9 המספרים שקולה לבעיית צביעה עם 9 צבעים. מטרת המשחק למצוא צביעה של הגרף כך שבכל שורה, טור ובלוק יופיעו כל תשעת הצבעים, בהנתן צביעה חלקית של הגרף.
את הלוח (גריד) ניתן לייצג כגרף דו-ממדי שבו כל קודקוד מתואר באמצעות זוג סדור
, כאשר x ו y הם מספרים שלמים שנעים בין 1 ל 9 (כולל). נאמר ששני קודקודים
ו
הם מתואמים אם מתקיים אחד מהבאים:
or , כלומר: הם באותו טור.
or, כלומר: הם באותה שורה.
and
, כלומר: הם באותו הבלוק.
נאמר שהסודוקו פתור אם נצליח לצבוע את הגרף ב 9 צבעים (שנסמן במספרים 1-9) כך שכל זוג קודקודים מתואמים יהיה בעל צבעים שונים.
פתרון סודוקו תקף הוא גם ריבוע לטיני. ישנם הרבה פחות פתרונות סודוקו מאשר ריבועים לטיניים, משום שפתרון סודוקו דורש אילוץ נוסף, אזורי (הבלוקים). למרות זאת, מתמטיקאים הצליחו לחשב את מספר הפתרונות לסודוקו של 9X9. בשנת 2005 מצא ברטרם פלגנהאור (Bertram Felgenhauer) שמספר הפתרונות לסודוקו 9X9 הוא 6,670,903,752,021,072,936,960. [2] מספר זה שווה ל
כאשר המספר האחרון הוא ראשוני. תוצאה זו חושבה בשיטות קומבינטוריות שנעזרו בחישוב "כוח גס" באמצעות מחשב. התוצאה התקבלה בניתוח שערך פרייזר יארוויס (Frazer Jarvis) ואושרה על-ידי אד ראסל (Ed Russell). מאמר שיפרט את השיטות שבהן הם השתמשו לחיישובים ניתן לראות כאן [3].
המספר המקסימלי של נתונים שניתן לספק מבלי שהפתרון יקבע ביחידות הוא גודל הלוח עצמו פחות 4. למשל: אם חסרים שני מספרים בתאים שהם פינות של מלבנים מאונכים, אזי קיימות שתי דרכים לשבצם. המספר המינימלי של נתונים שיש לספק על מנת שהפתרון יקבע ביחידות הוא עדיין בגדר בעיה בלתי פתורה, למרות שעבור ואריאציות מסוימות נמצאו פתרונות (עבור הואריאציה הסטנדרטית ללא אילוצי סימטריה, התשובה היא 17, עם אילוצי סימטריה סיבובית התשובה היא 18. תשובה זו נמצאה על ידי חובבי חידות יפניים [4]).
[עריכה] עגולוקו
עגולוקו הינו סוג של חידת סודוקו. העגולוקו מבוסס על אותו עיקרון של הסודוקו - שיבוץ של כל הספרות מ-1 עד 9.
הביטו בתמונה: העיגול מחולק לשמונה 'משולשי פיצה', ארבעה מעגלים ועיגול אמצעי המכיל ספרה אחת. כל 2 פיצות שכנות או כל מעגל, בשיתוף הספרה שבעיגול האמצע, צריכים להכיל את הספרות 1-9. שימו לב, ספרת האמצע תופיע פעם אחד בכל החידה, וכל מספר אחר יופיע 4 פעמים.
[עריכה] איך מכינים עגולוקו?
לעזר, כל טבעת צבועה בצבע אחר, על מנת למנוע בלבול בין הטבעות. העקרון פשוט: לשבץ (לפי רמת קושי) כמה מספרים מ-1 עד 9, בלי שיתנגשו אחד בשני לפי החוקים.
- ברמה הכי קשה צריך לשבץ לפחות 11 ספרות.
- השיבוץ יכול להיות בכל אחת מן המשבצות - כך שיש אפשרות לא לשבץ מלכתחילה את משבצת האמצע.
[עריכה] ראו גם
[עריכה] קישורים חיצוניים
| מיזמי קרן ויקימדיה | ||
|---|---|---|
- סודוקו ישראלי
- 数独 Sudoku Maniac 1
- כלי לפתרון סודוקו
- תוכנות פתרון
- עזרה בסודוקו
- יצירת סודוקו
- הכנסת סודוקו (הוראות באנגלית)
- אתר עם מליוני משחקי סודוקו בחינם
- משחק יומי
- סודוקו בחינם
- סודוקו
- סודוקו פלוס
- חוקים והיסטוריה של המשחק
- S סודוקו.קום
- סודוקו יומי
- פופולריות בבריטניה:
- הפופולריות של סודוקו (חדשות ה-BBC, 22 באפריל 2005)
- כתבה מעיתון האובזרוור על הסודוקו (15 במאי, 2005)


