חידת סודוקו

Belgarath1

New member
חידת סודוקו

נותנים לכם לוח סודוקו (בגודל כלשהו) ובו משובצים כבר 2 מספרים. מיצאו אלגוריתם שמוצא שיבוץ של עוד מספר על הלוח כך שעדיין יהיה פיתרון חוקי.
 

inbal76

New member
הבהרה

ב"משובצים 2 מספרים" אני הכוונה היא ששני מספרים (למשל 1 ו-2) משובצים כבר בכל המקומות שלהם בלוח, כן? (אחרת זה טריוויאלי)
 

Belgarath1

New member
הכוונה

היא שרק שתי משבצות מלאות. וכן, אולי זה טריוויאלי.
 

inbal76

New member
אבל אם כך אז לא צריך שום אלגוריתם

קח כל מספר שונה משני המספרים שכבר יש, ושים אותו באיזה משבצת ריקה שאתה רוצה. הלוח נשאר פתיר.
 

inbal76

New member
או to be on the safe side...

פשוט שים אותו במשבצת ריקה שמתנגשת עם שתי המשבצות האחרות. במצב כזה קל להוכיח שזה פתיר: נקרא למספר השלישי X ולמשבצת הריקה A. קח פתרון חוקי כלשהו של הלוח עם השיבוץ של שני הראשונים כפי שנתון. אם במשבצת A יש מספר שונה מ-X, נניח Y, אז תחליף בין כל המופעים של X ו-Y וברור שגם זה פתרון חוקי (הרי אין הבדל בין X ו-Y).
 

inbal76

New member
ובכל לוח פרט ל-4X4 יעבוד גם הפתרון

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

inbal76

New member
אני חושבת שכן.

נתחיל עם הקביעה הברורה שכבר ציינו: בכל פתרון חוקי אפשר להחליף בין שני מספרים ולהשאר עם פתרון חוקי (הכוונה היא להחלפה של כל המופעים של אותם שני מספרים). עכשיו טענה: לכל 3 משבצות A,B,C קיים פתרון חוקי של הלוח שבו הן מכילות 3 מספרים שונים זה מזה. הוכחה: קח פתרון חוקי כלשהו. אם שתיים מבין השלוש מכילות אותו מספר, החלף את אחד מהמספרים עם מספר רביעי. (ואם שלושתן הכילו אותו מספר, חזור על תהליך פעמיים.) מכאן ברור שכל 3 מספרים שונים שתשים ב-3 משבצות שונות ישאירו אותך עם לוח פתיר, כי קיים פתרון חוקי שבו 3 המשבצות הללו מכילות 3 מספרים שונים, ואם הם לא המספרים "שרצינו" אז ניתן להחליפם עם אלו שכן. מקווה שלא טעיתי
תקנו אותי אם כן.
 

inbal76

New member
תיקון!!

ההוכחה שהבאתי לטענת העזר אינה נכונה כמובן
אבל הטענה עצמה כן נכונה. אני אנסה להוכיחה שוב.
 

inbal76

New member
הוכחה חלופית לטענת העזר

שוב, הטענה היא שלכל 3 משבצות A,B,C קיים פתרון חוקי של הלוח שבו הן מכילות 3 מספרים שונים זה מזה. לצורך הוכחה אפשר להשתמש בהחלפת שורות (או עמודות) שאינן חורגות מגבולות הבלוק. כלומר למשל בלוח 9 על 9 אפשר להחליף בין כל 2 עמודות מבין 1-2-3 או מבין 4-5-6 או 7-8-9. החלפה כזאת לא משנה את המספרים באף שורה, ובאף עמודה (ברור) וגם באף בלוק. לכן היא שומרת על חוקיות הפתרון. ע"י החלפת שורות ו/או עמודות באופן כזה, ניתן להגיע למצב ש-3 המשבצות שונות. זה יהיה קצת מייגע לעבור על כל המקרים כדי להראות את זה, אבל נראה לי שאפשר להשתכנע. (המקרה הכי "קשה" הוא של 3 משבצות ב-3 עמודות "סמוכות" (למשל 1-2-3), כולן עם אותו מספר. במקרה זה החלפת שורות תפתור את הבעיה (לכל משבצת כזאת יש 2 אפשרויות החלפה)). מה אתה אומר?
 

Belgarath1

New member
נראה הגיוני

הבעיה היא אולי באמת לבדוק את כל המקרים, למרות שאני לא רואה מקרה שזה לא יעבוד בו.
 
למעלה