לטקס במטה הכללי הגיעו 36 קצינים משש אוגדות – שישה קצינים מכל אוגדה.יתר על כן, כל אוגדה שלחה לטקס סגן משנה אחד, סגן אחד, וכן סרן, רב-סרן, סגן-אלוף ואלוף-משנה. מנהל הטקס ביקש לסדר את הקצינים ב-6 שורות של ששה קצינים – כך שבכל שורה ובכל עמודה יעמוד קצין אחד מכל אוגדה וקצין אחד מכל דרגה. איך יסדר את הקצינים?
בבעיה הזאת התחבט ליאונרד אוילר, מתמטיקאי שוויצרי, בשנת 1779. אוילר אמנם התעניין בבעיה כדי לשעשע את עצמו, אך משלא הצליח לפתור אותה החליט לתקוף אותה ביתר רצינות. ארבע שנים לפני מותו הובילה אותו בעיית הקצינים למחקר של יצור מתמטי חדש – הריבוע הלטיני.
מהו ריבוע לטיני? כל מי שיודע מהו סודוקו יודע גם מהו ריבוע לטיני: זהו ריבוע המחולק למשבצות: n שורות ו-n עמודות, כאשר בכל משבצת מופיע אחד המספרים בין 1 ל-n (או אחת מ-n האותיות הראשונות באלפבית הלטיני – ומכאן השם “ריבוע לטיני”). על האותיות להיות מסודרות כך שבכל שורה ובכל עמודה תופיע כל אות בדיוק פעם אחת. כדרכם של מתמטיקאים נבר אוילר בריבועים הלטיניים שהמציא, שיער השערות, גילה תכונות מעניינות, מיין את הריבועים הלטיניים למשפחות שונות, כיד הדמיון הטובה עליו. הוא חש כי בעיית הקצינים אינה ניתנת לפתרון, ואף ניסח השערה כללית לגבי התנאים בהם הבעיה פתירה. הבעיה הכללית נפתרה רק ב-1960, כאשר הוכח כי השערתו של אוילר הייתה מוטעית. הבעיה המקורית אמנם אינה פתירה, אך עבור מספרים אחרים של אוגדות ודרגות, קיימים פתרונות.
השאלה היחידה שבאמת לא עניינה את אוילר היא השאלה היישומית. איזה תועלת עשויה לצמוח מחקר הריבועים הלטיניים? עבור אוילר הדבר לא העלה ולא הוריד. אולם, כפי שקרה לא פעם, יתברר כי לריבועים הלטיניים יש יישומים מעשיים רבים, ושעשועון הסודוקו הוא רק אחד מהם. ריבועים לטיניים שימשו לפיתוח אלגוריתמים לפתרון בעיות של חלוקת משאבים והקצאתם, שצצות כמעט בכל תחום של ייצור, מחשוב, ואפילו בחלוקת עוגה בין ילדים. שימוש נוסף לריבועים לטיניים הוא בתחום ההצפנה. אולם השימוש העיקרי לריבועים לטיניים הוא בסטטיסטיקה.
ויליאם גוסט (Gosset), מחלוצי הסטטיסטיקה, היה כימאי שעבר לפרנסתו במבשלות הבירה של גינס. אחד מתפקידיו היה למצוא דרכים לשיפור כמות ואיכות השעורה שגודלה עבור מפעלי הבירה. גוסט התבקש לבחון חמישה סוגי דשן שהוצעו לשימוש בגידול השעורה. פתרון פשטני לבעיה הוא לבחור חמישה שדות, ובכל שדה לנסות סוג אחר של דשן. ניסוי כזה הוא בעייתי. אם יהיו הבדלים ביבולים השונים, לא יהיה אפשר להסיק בודאות כי ההבדלים נגרמו על ידי הדשנים. בשדות שונים יש תנאי גידול שונים: אדמה, אקלים מזיקים, כל אלה יכולים להשפיע על גידול השעורה. הניסוי חייב להיות מבוקר: כל תנאי הגידול, פרט לסוג הדשן, חייבים להיות זהים במידת האפשר. הפתרון של גוסט היה לבחור שדה ריבועי, ולחלק אותו ל-25 ריבועים קטנים. בכל אחד מחלקי הריבוע נעשה שימוש בדשן אחר, כך שבכל שורה ובכל עמודה נעשה שימוש בכל סוגי הדשן. אם נסמן את סוגי הדשן ב-A, B, C, D, ו-E, השדה של גוסט נראה בערך כך:
כלומר, התכנון של גוסט התבסס על הריבוע הלטיני של אוילר. הפיזור של הדשנים על כל השדה מנעו גם את האפקט האפשרי של המיקום בשדה (במרכז או סמוך לקצה) על גידול השעורה. כל שנותר לעשות הוא להמתין לקציר ולהשוות את היבול שהתקבל מכל אחד מהדשנים. הניסוי של גוסט הוביל מאוחר יותר לפיתוח ענף שלם בסטטיסטיקה – תכנון ניסויים.
פורסם לראשונה באתר “רשימות” בתאריך 17 ביוני 2005 שם התקבלה שם התקבלה שם התקבלו9 תגובות
סודוקון בתאריך 6/18/2005 12:00:01 AM
שאלה ליוסי
האם יש אלגוריתם כללי לפתרון בעיות סודוקו (כלומר, האם הבעיה כריעה)?
אם כן, האם ידוע אלגוריתם יעיל? (פולינומיאלי בזמן ריצה)
אבנר בתאריך 6/18/2005 8:36:20 AM
התנאי היותר מורכב של ריבוע לטיני
פרט לכך שכל עמודה וכל שורה תכלול כל אחד מהפריטים, ישנם מצבים שבהם נדרש שגם סדר הפריטים ישתנה, כך שאם א הופיע בשורה אחת לפני ובצמוד ל-ב באף אחת מהשורות הבאות לא נחזור על כך (אותו תנאי תקף גם לטורים). בסודוקו של תשע נדמה לי שזה בלתי אפשרי, זה בודאות אפרשרי בריבוע לטיני של שלושה טורים על שלוש שורות. איפשהו בדרך בין 3X3 ל-9X9 הבעייה הופכת לבלתי פתירה.
יוסי [אתר] בתאריך 6/18/2005 1:22:21 PM
תשובה לסודוקון
קיים אלגוריתם כללי כמובן.
כיוון שמספר הסידורים של 81 סימנים ב-81 משבצות הוא סופי, הרי שניתן “פשוט” לעבור על כולם, עד שיימצא הפתרון הנכון.
לעומת זאת, מי שניסה לפתור סודוקו “קשה” נוכח בודאי כי לפעמים יש צורך בבדיקת מספר אפשרויות עבור משבצת מסויימת, ולכן המסקנה היא כי בעיית פתרון הסודוקו נמצאת ב-NP, ומכאן שלא ידוע אם קיים אלגוריתם יעיל (פולינומיאלי( לפתרון הבעיה.
יוסי [אתר] בתאריך 6/18/2005 1:25:03 PM
תשובה לאבנר
התנאי שציינת יכול להתקיים בכל ריבוע לטיני מסדר זוגי, ואינו יכול להתקיים בריבוע לטיני מסדר אי זוגי.
בתאריך 6/19/2005 12:00:23 AM
ישנה הוכחה מסודרת יותר
ישנה הוכחה מסודרת יותר להיות הבעיה של הסודוקו NP-שלמה (כל הבעיות בP הן בNP זה לא עוזר לי כלום לדעת שהיא בNP השאלה היא אם היא NP שלמה או בP)
אפשר למצוא במאמר מסויים של סינים.
יוסי לוי [אתר] בתאריך 6/19/2005 7:40:44 AM
תשובה למגיב הקודם
תודה על ההערה הנכונה
הראל בתאריך 7/5/2005 12:14:56 PM
לאונדר פולר, ידיהוט אחרונוט
בספרון שהוצאת ידיעות אחרונות הוציאה ונקרא משהו כמו “נפלאות הסודוקו”, כתוב בהקדמה שהסודוקו הומצא תחת השם “משבצות לטיניות” על ידי מתמטיקאי שוויצרי משועמם בשם לאונרד פולר.
ידיעות אחרונות כבר קראתם??
הראל בתאריך 7/5/2005 12:16:11 PM
NP-C
בערך האנגלי על סודוקו בויקיפדיה תמצאו קישור למאמר שמוכיח כי הבעייה היא NP שלמה.
ג. יפית בתאריך 8/31/2005 11:47:37 AM
גם חבר שלך כותב פה על סודוקו
http://www.notes.co.il/ben-hateva/12445.asp
אבל עם כל הצרה נשגבה ממני הדרך שהוא הרכיב שם את המשחק. די מבולבל מה שהוא עשה שמה.