Michael Kohn-Eber was my father’s uncle. Born in 1885 in Galicia to Hanna Eber and Don Kohn, he was raised in Vienna in the home of Reuben Asher Braudes—Hanna’s second husband and a prominent Hebrew writer. Growing up in a household deeply engaged in the early Zionist movement, Michael was profoundly influenced by Braudes’ close ties with Theodor Herzl and other pioneering Zionist figures.
Michael became a leading figure in the Poale Zion Left, a Jewish socialist movement that fused Marxist principles with Zionist ideals. In Austria, he led the faction that opposed rejoining the World Zionist Organization, viewing it as too bourgeois. Under his leadership, Poale Zion Left became a force in Vienna’s labor movement, organizing strikes and engaging in significant political activism.
I learned a lot about Michael’s political work from my father, Dan Carmel, who often spoke of his uncle’s influence. Yet, for years, I found no trace of Michael’s legacy online and began to wonder if my father had perhaps overstated his importance. That changed when I discovered a scholarly study by Mario Kessler from Australia, which extensively studied the activities of Poale Zion Left in Austria—including Michael’s role.
To honor Michael and restore his place in history, I created a Wikipedia pagebased on my father’s memories and Kessler’s research. I also owe an apology to my late father for doubting his stories. He was an amateur historian with a deep commitment to truth, and I should have trusted his memory.
And Michael — your story is now preserved. You may rest in peace.
For my birthday, my wonderful sons, Adi, Omer, and Matan, surprised me with an extraordinary gift — a personal Wikipedia page. I’m so proud of them, and I can only imagine how much effort it took them to gather all the details. Among all my achievements, my greatest success will always be my sons.
Joining the Technological Innovation Institution (TII)
After 6.5 years with Amazon it’s time to move on. As always, leaving is involved with a mixture of feelings. I had the pleasure of working on many exciting project with amazing colleagues. But life is too short. Bye Bye Amazon, keep working hard and making fun. Now, I’m starting a new position at the Technology Innovation Institute (TII). TII is a UAE-based institute that focuses on many research areas including Generative AI. Falcon, one of the leading open-source Large Language Models, is one of its exciting projects. I’m joining a new research team that will work on the integration of generative AI and Information Retrieval. At the same time, we will contribute directly to the vision of scientific collaboration articulated in the Abraham Accords. To the many who ask, our new office is in Haifa.
חמישים שנה עברו מהמלחמה ההיא. הזמן עושה את שלו וזכרונם של אירועים ומקומות מיטשטש ונעלם. רסיסים של זכרונות עולים במוחי, עם שמות ופנים שאת חלקם כבר איני מצליח לקשר. וכבר לא ברור מה האמת ומה הן רק הזיות שהתקבעו בזכרוני. הכתובים הבאים מנסים להכניס סדר בזכרונותי איני מתיימר להיות צמוד לאמת המוחלטת. כל הנאמר כאן הוא על אחריותי בלבד ואין להתייחס אליו כאל מסמך היסטורי מחייב.
התגייסתי במאי 1973, לשריון כמובן, לפי מיטב המסורת הנהוגה בקיבוצי, בית השיטה. שלושה חודשי טירונות בבט״ר רפיח וחודשיים קורס מקצועות בבית הספר לשריון בג׳וליס, ליד אשקלון. הוצבתי לטנקי המג״ח, מגמת תותחנות. אחי המאומץ, דוד כליון ז״ל, שהתגייס שלושה חודשים לפני והוצב לטנקי השוט, ניגש לאימי ובאנדרסטייטמנט אופייני מזהיר אותה: ״האם שמעת על האסון הנורא, בנך הוצב למג״חים. אלו אינם טנקים אמיתיים, הם עשויים מפח ונדלקים מכל זיק, את חייבת לעשות משהו אם אינך רוצה לראות את הבן שלך נשרף כמו אבוקה של יום העצמאות.״ אמא נבהלת וניגשת לרן שריג, חבר הקיבוץ וקצין בכיר בשריון, כדי לשנות את רוע הגזרה. הוא מרגיע אותה ואני נשאר במג״חים.
יום חמישי 4.10.1973. סיום קורס המקצועות. אנו צועדים בסך במסדר הסיום בניצוחו של הסוס הלבן, הרס״ר המיתולוגי של בית הספר לשריון. אנו מוצבים לגדודי הסדיר של חטיבה 14 בסיני על מנת לעבור את אימון הצמ״פ הבסיסי שמשלים את אימון הטנקיסט, אני מוצב לגדוד 52. אבי גור, הסמ״פ של הפלוגה המאמנת מכנס אותנו במגרש המסדרים ומסביר לנו את המצופה מאיתנו. ״..מחכים לכם 3 חודשים קשים ביותר של אימונים במדבר, תנוחו היטב בזמן החופשה ותנצלו את הזמן כי אצלנו בסיני לא תלקקו דבש … ואבוי למי שלא יחזור בזמן.״ הוא משחרר אותנו לחופשת רגילה בת שבוע ומזכיר את הכוננות הגבוהה ואת האפשרות שנוזעק במקרה שתפרוץ מלחמה. לנו זה נשמע כמו מס שפתים המקובל לפני כל חופשה. וכך אנו יוצאים לשבוע חופש שלרוע המזל יתקצר ל 24 שעות.
יום שישי ה 5.10, ערב יום כיפור, 17:00. אני יושב בבית הורי נהנה מהשקט היורד על הקיבוץ. ולפתע, דפיקה בדלת – האזעקה השקטה הופעלה ורכב נשלח לאסוף אותי, ועוד כמה חברים נוספים מהעמק. אני מזמין את כולם לחדר האוכל, לארוחה מפסקת, ואנו בדרך לתל-אביב לנקודת הכינוס בבית החייל. טוד שהצטרף אלינו מקורס טיס מספר שהוא שמע במו אוזניו את זעירא (ראש אמ״ן) אומר שאין מה לדאוג וזו אזעקת שווא, ושמייד יחזירו אותנו הביתה. אשרי המאמין, אנו עולים לאוטובוסים ויורדים לסיני להצטרף לגדודים.
יום כיפור, שבת, 6.10, 10:00 בבוקר. אנו מגיעים לבסיס הגדוד במעבר המיתלה, כ 30 ק״מ מתעלת סואץ. המג״ד עמנואל סקל אוסף אותנו לתדרוך בחדר האוכל הגדודי: ״בעוד מספר שעות תפרוץ מלחמה״ הוא מודיע, ״המצרים מתכוננים לחצות את התעלה. אבל אל דאגה – אנחנו מוכנים היטב. מי שצם, שיחדל בפקודת הרב הגדודי״. הוא מראה לנו על המפה את הארמיה המצרית העומדת מולנו (כ 850 טנקים, כאלף קני ארטילריה) ואת פלוגות הגדוד הערוכות מולן. יחסי הכוחות נראים לי בלתי סבירים בעליל – 33 טנקים נגד ארמיה שלמה? מישהו שואל מדוע איננו תוקפים ראשונים ואינו נענה, שאלתו מרחפת באוויר עד היום. נו מילא, נדפוק אותם בדיוק כפי שעשינו בששת הימים.
אנו עדיין במדי א׳, כל אחד מקבל עוזי עם שתי מחסניות וקפל״ד, ואנו נשלחים לבונקר לעזור בפירוק משאיות תחמושת. לאנשי הפלוגה המאמנת שלנו אין זמן עבורנו, הם עסוקים בהתארגנות לקראת היציאה לקו ואנו מרגישים קצת אבודים במקום בלתי מוכר וללא שום גורם שינחה אותנו ויאמר לנו מה לעשות.
יום כיפור, שבת, 14:00. יעף מטוסי מיג החולף מעלינו מפר את השקט. צופר אזעקה חזק נשמע ופלוגות הטנקים מזנקות לעבר התעלה. שאגת הטנקים והאדמה הרועדת גורמים לי לתחושה שאני שותף לרגע היסטורי, אגרוף הפלדה נכנס לפעולה והגיע הזמן ולהראות לאויב שאיתנו לא מתעסקים. המיגים ממשיכים להסתובב באין מפריע בשמי המיתלה. אנו יורים כמו משוגעים עם העוזי, אש לא תכליתית בעליל, עד שנגמרות המחסניות. מטוסים שלנו שמגיעים למרחב מיורטים מיד על ידי טילי קרקע-אוויר ואנו רואים את חופות הטייסים כשהם נוטשים את המטוס הבוער. אין ספק, אנו במלחמה. המיגים חגים מעלינו באין מפריע ואנו שומעים פיצוצים מסביב לבסיס – פצצות השהייה שלמרבה המזל אינן גורמות נזק רב. ושמועות מתחילות לחלחל על הברוך בקו החזית, על זה שנפגע ועל ההוא שנהרג, ועל המעוזים המכותרים והתעוזים שננטשו. איננו מכירים את השמות אך כבר ברור לנו שהחגיגה של ששת הימים לא תחזור על עצמה. והנפגעים מתחילים להגיע מהחזית בזרם שאינו פוסק. אנו עוזרים בנשיאת אלונקות מהנגמ״שים אל ההליקופטרים. ולפתע אני פוגש את איציק, בן דודי מהקריות. נראה שהוא בטראומה, הוא שירת בבסיס טילים קדמי שנפגע קשה בהפצצות ברגע פרוץ המלחמה. הם ספגו אבדות כבדות ונסוגו למיתלה. הוא מספר כיצד הם ישבו בתחתונים בזמן שהמיגים ירדו עליהם. אני חושב לעצמי שאת כולנו תפסו עם התחתונים מופשלים.
המצב בחזית בכי רע, הגדוד נשחק וכמעט שלא נשארו צוותים מתפקדים. המסר הוא שחייבים להחזיק מעמד עד שיגיעו כוחות המילואים. אבל איפה הם? כמה זמן לוקח להם להגיע? בגדוד מתקבלת החלטה לנצל את הבשר הטרי (אותנו), למרות שעדיין איננו טנקיסטים מדופלמים, ולהשתמש בנו כדי להשלים צוותים חסרים. אני מתחנן שיבחרו בי אך לרוע המזל לא נמצא צוות עבורי. אני פוגש את אדמונד שבת, מט״ק מהקיבוץ שלי שהגיע לבסיס כדי לטפל בתקלה בטנק שלו. אני מתחנן לפניו שיעלה אותי כתותחן אצלו בצוות. אדמונד מסרב ולא נכנע לתחנוני. מספר שעות מאוחר יותר הטנק שלו נפגע, חלק מהצוות נהרג ואדמונד נפצע קשה בראשו. יתכן שאני בחיים היום כתוצאה מסירובו.
ובינתיים אנו מסתובבים ללא רועה בבסיס הקטן המתמלא באנשי מילואים. חלק קטן מאיתנו, למרבה הבושה, מנצלים את האנדרלמוסיה, מרימים רגליים ומסתלקים בחזרה לעורף. הנותרים מנסים לעזור במידת האפשר. אני מתנדב לשמור על מכלאת שבויים שהוקמה בחופזה, מעגל מגודר בגדר תלתלית ובמרכזו יושבים השבויים, כפותים ומעוררי רחמים. הם נראים מסוממים וריח עז נידף מהם – ריחו של הפחד. אנו מחלקים להם מים. לגבי אוכל, אנו מאד קצרים במזון אך משתדלים לספק להם מה שניתן.
לאחר מספר ימים, כשהמצב בחזית מתייצב, שולחים אותנו בחזרה לג׳וליס. הרעיון בגדול הוא להעביר אותנו אימון צמ״פ זריז, להכשיר אותנו כדי למלא את שורות הלוחמים המדולדלות. בזמן ארוחת הערב בחדר האוכל הענק, בשיחה מקרית ליד השולחן עם קצין מהחטיבה, כאשר הוא שומע שאני מבית השיטה הוא מביט בי במבט בוחן ושואל האם שמעתי על אלון שנהרג ביום הראשון, ועל מיכה, שותפי לחדר במגורי הנוער, ועל יוחי, המדריך האגדי שלנו. אני בשוק. אני מחליט להרים רגליים, ולנסוע לקיבוץ.
בית השיטה, סוכות, 22:00. הקיבוץ כולו מואפל והחברים מרוכזים בחדר האוכל לשמוע את אירועי היום. בקיבוץ כמעט ולא נשארו גברים. גם אבי, הפלמ״חניק הוותיק, מגויס. אחי הצעיר מיקי בן ה 16 לוקח על עצמו לנהל את הרפת, וגלי ואלון, בני כיתתי שעדיין לא גויסו מרכזים את ענף הכותנה בשיא עונת הקטיף. אני פוגש את אימי בחדר הורי ושומע על החברים שנפלו. בקיבוץ מנהלים טבלאות קשר עם הלוחמים, רשימת מנותקי הקשר ארוכה כאורך הגלות. אני שואל על כליון (למרות שהוא שוטניק, עדיין מענין לשמוע מה קרה לו). ידוע שהוא נלחם בגולן בחטיבה 7 אך אין כל ידיעה לגביו. בדיעבד התברר כי הוא שירת כתותחן של המג״ד אביגדור קהלני ובגופם הם עצרו את הדיוויזיות הסוריות בעמק הבכא. כליון הצטיין ונרשם בדפי ההיסטוריה כתותחן שחיסל את המספר הרב ביותר של טנקי אויב במהלך המלחמה. אבל הטמבל החליט שלא להתקשר בגלל אמונה טפלה וגרם לאביו ולהורי לחרדה נוראית. אני שואל על על רמון ועל רוני ועל יתר החברים מהכיתה אבל אין יותר מדי אינפורמציה. האווירה בלתי נסבלת – תחושה חזקה של חדלון וחוסר אונים. השמועות על מספר נוראי של הרוגים ונעדרים מרחפות באוויר, שמועות שלרוע המזל יתבררו כנכונות, אחד עשר לוחמים בני הקיבוץ נהרגו במלחמה. מועקה יורדת עלי ואני לא עומד בכך. כבר 2:00 בלילה. אני מחבק את אמא, מבטיח שאתקשר כשאוכל ומבקש מגלי להקפיץ אותי בחזרה לעפולה עם הג׳יפ של הכותנה. ומשם בטרמפים בחזרה לבסיס.
אנו יורדים לצמ״פ בן שבוע בצאלים. המפקד, קצין קטוע יד, מגיבורי מלחמת ששת הימים, לא מפסיק לצעוק עלינו. אני לא מקנא בו – לך תהפוך טירונים לטנקיסטים בשבוע. אנו לומדים מספר תרגולות בסיס, יורים מספר פגזים, וזהו, מוכנים לחזור לחזית. המצרים שומעים על כך ונכנסים לפאניקה.
עד שאנו מגיעים, הפסקת אש. שוב פספסתי את ההזדמנות להילחם. אנו מצטרפים לגדוד סיור המוצב מעבר לתעלה. הטנקים שלנו חדשים מהניילון, הישר מהימ״חים בגרמניה. על הסרבלים החדשים והיפים כתוב באנגלית שאנו שייכים לצבא ארה״ב ושיא השיאים, אנו מקבלים כנשק אישי מ-16, במקום העוזי המעפן. חוליות קומנדו עדיין מסתובבות בשטח ואנו מנסים לצוד אותן. וגם איסוף שלל הופך לחלק עיקרי מסדר היום. אנו מוצאים טנדר שטח מצרי שמוחרם לטובת הצוות ומשמש אותנו לטיולים באזור ולהובלת משאות. אני מוצא קלאץ׳ מדהים ביופיו עם קת עץ אדומה שהופך לנשק האישי שלי. אני גם זוכר בערגה פחיות שימורים של ריבת תאנים מצרית, הטובה שאכלתי בחיי. החיים הופכים לנוחים יחסית. זהו גדוד מילואים ולאף אחד אין סבלנות לעסוק בענייני משמעת. אנו הופכים לביטניקים, עם שיער עד הכתפיים, ועם זמן פנוי רב להסתובב ולחפש מציאות. האוכל בשפע כתוצאה מאספקה בלתי פוסקת מהאגודה למען החייל, והטנק שלנו הופך לרכב צועני, עם ספה מצועצעת על הסיפון האחורי (בשביל מנוחת הצהריים) ויריעה צבעונית להגנה מהשמש. ותא הזיווד מלא בשוקולדים וסיגריות. רק חבל שבתור ליציאה הביתה אנו אחרונים, עדיפות ראשונה ניתנת לבעלי המשפחות.
הצוות ואני (עם הסוודר השחור) על הטנק, גד׳ סיור 817, מתחם צ״ח, מעבר לתעלה
אך הפיקניק לא נמשך זמן רב, מעבירים אותנו לגדוד 46, חטיבה 401, לפלוגה של עירא עפרון. הפלוגה חונה בחצרה של וילה נטושה, קרוב לק״מ ה101. עירא, אדם גדול ממדים עם קול בס עמוק ומטיל מורא, שואג שיש לנו שעתיים להתגלח ולהסתפר ולהפוך חזרה לחיילי שריון מדוגמים. אנו נכנסים לשגרה של שמירות אינסופיות ומעט אימונים. הכוננות בשיאה, יש שמועות שלמרות הפסקת האש גדודי קומנדו מצרים ינסו להשתלט על ג’בל עתקה הנישא מעלינו כדי לפתוח מסדרון לשחרור הארמיה השלישית הנצורה.
סוף סוף הגיע תורי לצאת הביתה. אנו עוצרים בשק״ם ברפידים ובתור לאורנג׳דה אני פוגש את אבי המשרת שם כחובש בבית החולים הצבאי. לא התראינו כבר חודשיים. אבי, שאיבד את כל משפחתו בשואה ונחלץ בעור שיניו מהנאצים, ולחם בשלוש מלחמות, נרגש עד דמעות לראות אותי בריא ושלם. אנו מתחבקים ומתעדכנים על המצב בחזית ובבית.
אני נקרא לאוהל המפקד ומתבשר שנבחרתי להישלח לקורס מפקדי טנקים. השריון נותר ללא שדרת פיקוד וכל זב חוטם מופנה למסלול פיקוד. להרבה חניכים בקורס ניסיון קרבי רב ולכל אחד מהם תורת לחימה משלו. חלקם חזרו לשירות לאחר פציעה והם עדיין נושאים את צלקות הקרב. על חלק מהם ניתן לזהות בבירור את הטראומה שהם עברו. הקורס אינטנסיבי ביותר, סוף סוף אני זוכה להכשרה מסודרת והופך לטנקיסט מקצועי. תוך מספר שבועות אנו מוסמכים למפקדי טנקים ונשלחים חזרה לגדודים.
לאחר שירות קצר כמט״ק בגדוד 195, חטיבה 401, אני נקרא לקורס קציני שריון בביר-תמדה. זהו הקק״שׁ הראשון לאחר המלחמה המועבר במתכונת מלאה. אנו מוסמכים לקציני שריון למרות שלא עברנו את בה״ד 1, ויתרו לנו עקב הנסיבות. כשנה וקצת לאחר הגיוס אני כבר קצין שריון מנוסה וותיק (יחסית) העוסק בהדרכת צמ״פים בשרשרת, מכשיר את דור הלוחמים הבא.
כשאני מנסה לחשוב מה נשאר לי מהמלחמה ההיא, אין לי ספק שאילו החברים והמפקדים המופלאים שזכיתי לשרת עמם. לא זכיתי להשתתף בקרבות עצמם, הייתי בשולי המערכה, אך ראיתי כיצד קור רוח ונחישות מביאים את ההכרעה בקרב. ראיתי חיילים בגדולתם וגם, מה לעשות, בשפלותם. אני במיוחד רוצה לציין את עמנואל סקל, מג״ד גדוד 52, עם קולו השקט והשקול ברשת הקשר. ואת אברהם בן-ארצי, מ״פ פלוגה ל׳, גדוד 195, שקלט אותי כמט״ק לפלוגתו ולימד אותי את משמעותה של מנהיגות הבנויה על אמפטיה וסובלנות, גישה כה שונה מזו שהיתה מקובלת בשריון באותו הזמן. ויהודה גלר איש הסיור, מג״ד גדוד 419 בחטיבה 500 בה שירתתי כקצין. מקצוען ואיש שטח בחסד עליון שתרגל אותנו ללא סוף בלוחמת לילה. ויעקב קרני המ״פ שחזר מאמריקה כדי להשתתף במלחמה והתנדב לקבע לעזור בשיקום הצבא הסדיר, וספי שאומן הנאמן שנהרג במלחמת לבנון, וגדעון תרן, ועופר פעיל, ועמוס דותן, המדריכים מהקק״ש, ועוד רבים רבים, נפלאים ונהדרים. וחברי הלוחמים, אחי גיבורי התהילה, שהייתי מוכן לעשות הכל למענם כשם שאני בטוח שהם היו עושים למעני. ואין לי ספק שהמלחמה לא הייתה מסתיימת כפי שהסתיימה ללא גבורתם ונחישותם. וכשיגיע יום פקודה, כנראה בקרוב, האם נזכה למסירות והקרבה כזו גם היום? האמת, אינני יודע, הייתי רוצה להאמין שכן
תוצאות החיסונים כנגד הקורונה בבלימת המגפה אכן מדהימות, ועדיין רבים מפקפקים אם הם אכן נחוצים. עם מכחישי המגיפה אין לי ויכוח, חבל על הזמן, אין טיעון שישכנע אותם. אולם ברצוני להעלות .ולהתוכח עם טיעון אחד כנגד החיסונים שיש בו היגיון פנימי רב יש שיאמרו, מה החיסונים הללו לכם? האנושות יודעת להתמודד היטב עם מגיפות ללא התערבות מלאכותית חיצונית. קחו לדוגמה את מגיפת הדבר מימי הביניים, המוות השחור. נכון, כרבע מאוכלוסית אירופה נמחקה, אך למה לראות את רבע הכוס הריקה? שלוש רבעים שרדו והמשיכו לשגשג ולהוביל את המין האנושי. זו דרכו של הטבע – אין מקום לחלשים ורק החזקים והמסתגלים שורדים. מלתוס טען כבר מזמן שאפידמיה היא אחד הכלים של הטבע לווסת את גודל האוכלוסיה. ״אל נע יעקבונו פגרי הנחשלים״ אמר ביאליק, בהקשר אחר, ואולי הוא צודק? ויותר מכך, החיסונים אכן מעכבים את התפשטות המגיפה אך מצד שני הם גורמים לה לשהות בקרבנו יותר זמן מהנחוץ. השפעת הספרדית מלפני כ 100 שנה, עם עשרות מיליוני קורבנותיה, נמשכה כשנתיים בלבד ונעלמה כשם שבאה. הקורונה מהלכת בקרבנו כבר קרוב לשנתיים והקץ לא נראה באופק. האם לא סביר לחשוב שגם החולרע הזו כבר הייתה זכרון רחוק לולי היינו מתערבים? אני חייב להודות שיש טעם רב בטיעונים הנ״ל. אולם מצד שני התפיסה המקובלת, לפחות בחברות המערביות, היא שיש להלחם על כל נפש חיה, ושיש להשקיע ככל שניתן כדי לשמר אותה. ״לא תעמוד על דם רעיך״ אומרים ביהדות ואני מאמין שניתן למצוא ביטויים דומים באיסלם ובנצרות. מצווים אנו לעזור לחלש ולכל מי שזקוק לעזרה. הגישה שלא להשאיר אף אחד מאחור היא מהסיבות המרכזיות להתקדמות המין האנושי. מרגרט מיד אמרה שהסימן הראשון לציביליציה הוא עצמות אדם שהתאחו משבר, כלומר בני אדם שזכו לסעד מחבריהם. שיתוף הפעולה בין הפרטים והצורך לתמוך בחולים ובחלשים הובילה אותנו לאן שהובילה. כל הרפואה המודרנית התפתחה מתפישה זו. יש שיאמרו שחבל על המאמץ, מוטב היה לנו שלא היינו מתקדמים כל כך, המודרניזציה מביאה איתה הרבה סבל, אך אני מאמין שמטבענו אנו מתוכנתים לחקור בלא נודע ולנסות להתקדם ולהשתפר. איננו יכולים לסגת. חיסוני הקורונה הם דוגמה מצוינת לכך. הטבע האנושי מכתיב את המאמץ העצום בחיפוש אחר חיסון. אינני טוען מהי הגישה הנכונה אך כל אחד חייב לבחור צד. אם אתה מאמין בקדמה ובמדע כחלק אינטגרלי של עצם מהותנו, ובחרת בחיים (להתחסן ולחסן). אני, את שלי בחרתי
I’ve recently become interested in solving Sudoku puzzles, realizing that I’m really bad in it. I can handle the easy ones, however, puzzles marked as medium or difficult are two complicated for me. I guess my main weak-spots are the heavy book-keeping required, and that it almost impossible to recover from an error done during the solution process.
Sudoku, meaning “singular number” in Japanese, consists of an N X N grid, divided into BxB blocks (e.g. a 3×3 block corresponds to a 9×9 puzzle, as presented in Figure 1). Each puzzle has some cells that have already been filled in (called clues). We have to fill in the rest of the cells with numbers in the range [1.. N} such that in all rows, all columns and all blocks, every number appears exactly once. The puzzle at the right of Figure 1 is a solution to the puzzle on the left.
Figure 1: Left: A Sudoku puzzle. Right: its solution
As a lazy scientist who hates hard work but also can’t stand unsolved puzzles, I decided to write a Sudoku solver program based on searching over all legal assignments for a given puzzle. Unfortunately, Sudoku is an NP-complete problem [1], when generalized to N × N grids, in the sense that all known solvable algorithms do so inefficiently; in spite of the fact that if a candidate solution is given, it takes only polynomial time to check its correctness. Therefore, a naive search approach is unlikely to be efficient so we need some domain knowledge (called heuristics in AI terminology [5]) to direct our problem solver.
There are many approaches for solving Sudoku puzzles, including CSP-based solutions [6], genetic algorithms [7], and modeling Sudoku as an exact cover problem while using the dancing links techniques [8]. Peter Norvig [2], the famous AI pioneer, provided a Python code for a Sudoku solver based on integrating CSP with search. In this study I follow Norvig by integrating common Sudoku strategies, popular among Sudoku fans, into the search process.
Heuristic search is one of my favorite AI techniques. Realizing the difficulty in searching over huge spaces, it is inspired from the ways humans tend to solve the problem and whether human strategies can be applied to improve our solver performance. This is especially useful for (the few) tasks for which humans are still superior to machines. In the following I will describe the HS-solver that is based on backtracking search, integrated with the human strategies. I’ll begin with the search algorithm, and then describe the heuristics. I’ll also report the results of some experiments I conducted on a popular benchmark of 95 9×9 puzzles which had already been used in Norvig study [2].
2. Backtracking
We represent a Sudoku puzzle by an NxN matrix holding all values that have already been set on the grid. At the beginning, only clue cells are set with their values, while all other cells are set to zero. In addition, we manage an auxiliary NxN matrix of BitSet objects. BitSet is a Java class that can be used to efficiently maintain a set of values, including adding, removing, and querying the containment of a specific value. Any constraint entry (i,j) represents all candidates that can be legally assigned to cell (i,j). In addition we keep for each row/column/block (a unit for short) a BitSet that maintains all values that have already been set in this unit. finally, we also holds a list of non-assigned cells in the puzzle.
The following Java code includes some important methods of the Sudoku class. The full Java code of the SudokuSolver is publicly available on https://github.com/davidcarmel/SudokuSolver.
Data structure and some important methods of the Sudoku class
Our first trial for solving the puzzle is by a naive backtracking algorithm. Backtracking is a classical depth-first search. It first examines if the puzzle already been solved. If not, it collects all non assigned cells and sort them based on their cardinality (preferring cells with fewer candidates). It then traverses over the sorted cells, setting trying to set the cell’s candidates. If the value is legal in this cell, it applies itself recursively on the modified puzzle. If all settings fail we back up to a higher level seeking for an alternative track. As already been mentioned, while this algorithm is guaranteed to find a solution, if exists, this process is inefficient and may take forever to run. Here is the code for the backtracking algorithm.
We ran this function over the 95 puzzles, when limiting the search to 100M calls. 93 out of the 95 puzzles can be solved, with an average of 1.7M calls per puzzle, in 18.2 seconds per puzzle on my laptop. Well, this takes too much time and certainly is not satisfying.
Table 1: Search results of Backtracking algorithm when limited to 100M calls. Only 93 out of 95 puzzles can be solved.
3. Heuristics
Can we do better? hopefully — this is what we would like to explore. Having some domain knowledge of the problem space can help our solver to navigate the vast domain and save us a lot of precious time. We will apply some common Sudoku strategies [3] in order to improve our backtracking algorithm. It turns out that all strategies are closely related to CSP, focusing on reducing the number of legal candidates (the constraints) for non-assigned cells. The difference is that while in CSP, constraints are given and we look for a solution that obey them, in our case we apply the strategies to reduce their number by eliminating inconsistent constraints. The less constraints we have on legal assignments, the smaller the search domain to explore.
Strategy I: Candidate Reduction If a value is being set to a cell, then it can’t be set to any other cells of its units. Therefore, we can safely remove any cell candidate if it is already being set in one of its units. Whenever a cell is set, it may reduce the number of candidates of other non-assigned cells of its units. Furthermore, when only one candidate is left for a cell, it can be safely set thus entailing additional candidate reduction.
Calling this strategy by the HS-solver, prior to running the search process, enables solving all puzzles, including P$, and P41, the two puzzles in which backtracking failed. The results reveals significant reduction in the search efforts. On average, search is reduced to 23.8K calls per puzzle (98.6% improvement with respect to naive search) while the maximum calls over all puzzles is reduced from 22.M to 377K. In particular, the problematic puzzles P5 and P41 are now being solved in a reasonable number of calls (and run-time) by invoking this strategy.
Strategy II: Uniqueness in Unit: The 2nd strategy also applies a very simple rule: If a candidate is legal in only one of the unit cells, then it can be safely nailed to this cell. Of course, any new cell setting entails further reduction in candidate number.
We apply this strategy, together with candidate reduction, as part of the backtracking search. The average number of calls per puzzle is reduced to 100 (98% improvement) and the maximum calls over all puzzles to 1403, in 25ms per puzzle. Solving P5 and P41 becomes a piece of cake. It seems that we have cracked this benchmark.
Strategy III: Hidden pairs A pair of candidates is called hidden if it occurs in exactly two unit cells, and none of its members is candidate in all other unit cells. Then, the two unit’s cells holding this pair must be assigned with one of the pair members, therefore all other candidates for these two cells can be dropped. Note that we do not know which pair member should be set in which cell, however any candidate reduction is blessed.
Well, the average number of calls is reduced to 40.8, and the maximum number of calls over all puzzles is only 331. The number of calls continues to drop for the P5 and P4 tricky puzzles.
Strategy IV: Naked pairs: A pair is called naked if it is lonely in a cell. If a pair is naked in two unit cells, then it can be dropped from all the other unit cells. following the same logic of hidden pairs.
Table 2: Algorithm performance with the heuristic strategies.
Table 2 presents the results of backtracking, and after adding each of the strategies. The average number of calls is reduced to 26.2 and the maximum calls over all puzzles to 252. The problematic tricky puzzles are also solved smoothly. The average run-time per puzzle is 29ms. The two right columns relate to difficult puzzles described in the following. We can conclude that our code is robust to handle quite complicated 9×9 puzzles.
4. Man vs Machine
What about really hard puzzles? Norvig [2], mentioned a Finnish mathematician, Arto Inkala, who proposed the (Inkala-2006 puzzle) as “the most difficult Sudoku-puzzle known so far” and the Inkala-2010 puzzle as “the most difficult puzzle I’ve ever created.” Looking at the right columns in Table 2, we can see that these two puzzles can be solved with a few calls, in a few milliseconds . Norvig also provided a benchmark of 11 “difficult” puzzles (eleven puzzles). None of them really challenges the HS-solver (10.4 calls on average, 25ms). This is not surprising, problems seem difficult to humans are not necessarily difficult to machines and vice versa. Norvig also generated artificial puzzles by shuffling existing ones, looking for a “killer puzzle” that will challenge his own solver. The puzzle shown in Figure 2 is such a killer. This is not an “official” Sudoku puzzle (you will not find it in Newspapers) because it has multiple solutions (Norvig found 13 different solutions but maybe there are more.) Interestingly, it only takes 19 calls, in 195ms, for the HS-solver to converge to the solution shown on the right.
Figure 2: A killer puzzle generated by Norvig [2], on the left, and a solution found by the HS-solver on the right.
5. Conclusions
It turns out that Sudoku, considered by many as a great challenge for human intellect, (and in particular, a great challenge for myself), does not provide a real challenge to naive search program plus some basic strategies. Are there puzzles out there that our HS-solver will not be able to solve in a reasonable time? It is very likely that the answer is yes; it would be great if we can find such examples. One direction is to move to larger puzzles of 16×16 or even 25×25, unfortunately, I could not find any reliable benchmark for such puzzles. If you are familiar with, please let me know. There are many more complicated Sudoku strategies in the arsenal such as X-wing, Y-wing, Sword-fish and more [3]. At present, I was unable to find any evidence that they are really needed, but hopefully they will be helpful for really difficult puzzles to be found in the future.
Amazon scientists and conference general chairs Liane Lewin-Eytan and David Carmel on the transformations wrought when data goes online.
“.. Two of the three general chairs at this year’s ACM Conference on Web Search and Data Mining (WSDM) are scientists from Alexa Shopping’s offices in Haifa, Israel: Liane Lewin-Eytan, senior manager of applied research, and David Carmel, a principal applied scientist.
When they volunteered for the role, Lewin-Eytan and Carmel were hoping to bring the conference to Jerusalem. “It was the beginning of March [2020],” Lewin-Eytan says. “We had a beautiful bid, with many, many attractions in Jerusalem, because the steering committee of the conference takes also into consideration what the country can offer to participants. We were very excited to bring it here — it was a big honor to the local community — but because of COVID-19, we ended up online. We still hope to host the conference here one day. …”
לאחרונה קראתי את ספרו המצוין של רוברט האריס, קצין ומרגל, על פרשת דרייפוס וספיחיה. סרטו של רומן פולנסקי על סמך הספר, מאד נאמן למקור ומאד מומלץ.
ובכן האם יש דמיון כלשהו? הפוך גוטה, הפוך.
לעובדות היבשות: דרייפוס, קצין בצבא הצרפתי, הואשם בריגול ונשפט בבית דין צבאי. המסמך המרשיע, שהתברר כזיוף, הוצג לשופטים בלבד ולנאשם לא ניתנה זכות התגובה. העונש היה אכזרי במיוחד, סילוק מהצבא בבושת פנים וגלות עד סוף ימיו בבידוד מוחלט באי השדים. מספר שנים מאוחר יותר, קצין מודיעין בשם קולונל פיקאר, מגלה את המרגל האמתי, אך כשהוא מודיע לממונים עליו ודורש לשחרר את דרייפוס ממאסרו, הוא נתקל בחומה של התנגדות (מה חשובה האמת? מדוע אכפת לך מקצין יהודון?) וכשפיקאר אינו מוותר הממסד כולו, הצבאי והפוליטי, נחלצים להציגו כבוגד ומביאים להגלייתו למחוזות הנידחים של האימפריה הצרפתית. למזלו של דרייפוס, פיקאר מצליח בדרך לא דרך לגייס מספר עיתונאים, אנשי רוח, ופוליטיקאים מהאופוזיציה (הדרייפוסרים) הדורשים משפט חוזר ומצליחים לחשוף את ההונאה הגדולה של המשפט. הפרשה קורעת את דעת הקהל הצרפתית ומובילה להתפרצויות אנטישמיות ולחוסר יציבות פוליטית. היא מסתיימת בחנינה לדרייפוס ובהחזרתו לצבא. אסטרהאזי, המרגל האמתי, מעולם לא עמד למשפט.
אם משהו מהפרשה העגומה הזו מזכיר את משפט נתניהו הוא ה”טיפול” שזוכה לו אביחי מנדלבליט, בדומה ל”טיפול” שזכה לו פיקאר, עקב התעקשותו על שמירת החוק והדין. גם שם הטיפול כולל הסתת ההמון, שתילת חצאי אמיתות בעיתונות, וכל יתר הטכניקות המוכרות. להבדיל מדרייפוס שמצא את עצמו לבד לגמרי כנגד הרשויות, הממסד והמערכות הפוליטיות החזקות ביותר במדינה, כולל חלקים נרחבים בתקשורת, נחלצות להגנת נתניהו ואינן בוחלות בשום צעד. אני חושב על דרייפוס המסכן שכל עולמו חרב עליו כשהבין שכל מאמציו להשתלב בחברה הצרפתית דרך שירותו בצבא לא עמדו לזכותו. הדבר האחרון שעולה בדמיוני הוא את מר נתניהו, אדון הממשלה, התקשורת, ודעת הקהל, המרשה לעצמו להשתלח בשופטיו ובמערכת המשפט ללא כל מורא מאימת הדין.
David Carmel Blog 