הבלוג של גרי רשף

09/03/2010

כיצד פותרים בעיות סודוקו?

Filed under: Uncategorized — תגיות: , — גרי רשף @ 21:36

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

Sudoku

בתור התחלה ברור שאם בשורה העליונה מופיעים כבר המספרים 8,9,2,7,4,1 – הם לא יופיעו בתאים אחרים באותה שורה, וכלל זה תקף גם לגבי עמודות וריבועים.
כלל מספר 1: אם יש מספר שמופיע במשבצת מסויימת, הוא לא יופיע במשבצות אחרות באותו שורה/עמודה/ריבוע.

הלאה- אפשר לראות שבמשבצת השלישית בשורה השלישית (הפינה הימנית התחתונה של הריבוע השמאלי העליון) יופיע המספר 1:
בשורה הראשונה כבר יש 1, בשורה השניה כבר יש 1, בשורה השלישית הוא יכול להופיע רק במשבצת שציינתי כי בעמודה השמאלית ובשני הריבועים הימניים העליונים כבר יש 1.
לכאורה גם המספר 7 יכול להופיע שם, אבל מכיוון שהמשבצת היחידית בעמודה השלישית בה ניתן לכתוב 1 זו משבצת זו- יכתב בה המספר 1.
כלל מספר 2: אם יש מספר שיכול להופיע רק במשבצת מסויימת בשורה/עמודה/ריבוע מסויים – הוא ירשם באותה משבצת (גם אם היו עוד מספרים מועמדים למשבצת..) ואת שאר האפשרויות ניתן למחוק.

בדיקה זו בעזרת כללי היסוד 1-2 נמשכת באופן איטרטיבי עד שלא ניתן למצוא עוד מספרים כאלו, כאשר כל מספר שכן נמצא- מחייב לבצע בדיקות חוזרות מכיוון שכעת יתכן ונגלה עוד מספרים כאלו.
בדרך כלל השיטה הזו טובה רק בבעיות סודוקו פשוטות, ובבעיות קשות יותר נצטרך לחפש בהמשך פתרונות יותר מתוחכמים.
בשלב זה אפשר כבר לכתוב בכל אחת מהמשבצות הפנויות אילו ערכים יכולים להופיע בה, ואז לחפש זוגות של משבצות באותו שורה/עמודה/ריבוע שבשתיהן יש שני ערכים אפשריים זהים.
למשל אם בשורה מסויימת יש שני משבצות בהן יכולים להופיע המספרים 4 ו-7, ברור שהם לא יוכלו להופיע במשבצות אחרות באותה שורה, וניתן יהיה למחוק את האופציה הזו מהן.
באופן דומה- אם בשלושה תאים באותו שורה/עמודה/ריבוע יכולים להופיע כך או אחרת שלושה ערכים- ניתן יהיה למחוק אותם משאר התאים בשורה/עמודה/ריבוע; וכך גם לגבי מספרים גדולים יותר. למשל- אם בתא 1 יכולים להופיע המספרים 6 ו-7, בתא 2 המספרים 7 ו-8 ובתא 3 המספרים 6 7 ו-8 (נניח ששלושתם באותה שורה); נובע מכך שהמספרים 6-7-8 יופיעו בשלושתם ולא בתאים האחרים בשורה.
כלל מספר 3: אם מספר המספרים השונים שיכולים להופיע ב-X תאים (באותו שורה/עמודה/ריבוע) הוא גם כן X – ברור שהם לא יוכלו להופיע בשאר התאים (באותו שורה/עמודה/ריבוע).

לבסוף- באופן דומה לסעיף הקודם, אפשר לחפש צירופי מספרים שמופיעים רק בתאים מסויימים. למשל- אם במשבצת 1 יכולים להופיע המספרים 1,2,3,4,5 ובמשבצת 2 המספרים 3,4,5,6, ואנחנו רואים שהמספרים 4,5 לא מופיעים בתאים אחרים באותה שורה; נובע מכאן שבשתי המשבצות הנ"ל יכולים להופיע רק הערכים 4,5 ואת שאר האפשרויות אפשר למחוק.
כלל מספר 4: אם X מספרים יכולים להיות רק ב-X משבצות ולא באחרות (באותו שורה/עמודה/ריבוע) – באותן משבצות לא יופיעו ערכים אחרים ולכן ניתן למחוק אותם.

את ארבעת הכללים ניתן לצמצם לאחד – כלל 3 כולל בתוכו את כל הארבעה:
קודם כל – כלל 1 הוא מקרה פרטי של כלל 3 (עבור X=1), וכלל 2 הוא מקרה פרטי של כלל 4 (שוב, עבור X=1).
ולבסוף- אם לגבי X תאים תקף כלל 3 – לגבי שאר התאים תקף כלל 4. למשל, אם נעיין בדוגמה שלפני כלל 3, ברור ששאר המספרים (1,2,3,4,5,9) יופיעו בתאים 4,5,6,7,8,9; וזה המצב אליו מתייחס כלל 4.

שיטת הפתרון תהיה כזו: בכל שורה/עמודה/ריבוע נבדוק את כל תתי הקבוצות, ובכל תת קבוצה נבדוק אם מספר הערכים השונים הוא כמספר איברי תת הקבוצה. אם כן- נמחק אותם הערכים משאר המשבצות (אלו שאינן בתת הקבוצה).
מספר תתי הקבוצות של קבוצה בגודל N הוא 2N ובמקרה שלנו 512 (ניתן להתעלם משני מקרי הקצה- הקבוצה הריקה והקבוצה המלאה), ולכל מספר בתחום 1-510 נתאים תת קבוצה באופן דומה למה שמופיע בפוסט יחס של רבים לרבים ללא טבלת עזר.
הפרוצדורה הראשית P_Pitron תבצע את התרגיל הזה – פעם על השורות, פעם על העמודות ופעם על הריבועים;
ואת כל זה נעטוף בלולאה שתבדוק אם משהו התבצע – ואם כן (ובתנאי שעדיין יש אפשרויות למחיקה) – זה שוב יחזור על עצמו עד שלא יהיה מה למחוק:

Create Procedure P_Pitron(@Beaya Int) As

Truncate Table T_Ezer;--ריקון ומילוי טבלת העזר

With Nm As --עבור כל משבצת - מוכנסים 9 הערכים האפשריים לטבלת העזר

(Select 1 N

Union All

Select    N+1

From    Nm

Where    N<81)

Insert Into T_Ezer

Select    M.N Mishbezet,

        L.Shura,

        L.Amuda,

        L.Ribua,

        L.MoneS,

        L.MoneA,

        L.MoneR,

        P.N Pitron

From    Nm M,

        Nm P,

        T_Luah L

Where    P.N<=9

        And M.N=L.Mishbezet;

Delete --הערכים המיותרים במשבצות הנתונות - נמחקים

From    T_Ezer

Where    Exists (Select    *

                From    T_PerutBeayot PB --לטבלת פירוט הבעיות מוכנסים נתוני הבעיות השונות ונשמרים שם

                Where    Beaya=@Beaya

                        And T_Ezer.Mishbezet=PB.Mishbezet

                        And T_Ezer.Pitron<>PB.Natun);

Declare    @RC Int;

Set        @RC=1;

While    @RC>0 --הלולאה שתרוץ כל עוד יש נתונים למחיקה

        Begin

        Set        @RC=0;

        If (Select Count(*) C From T_Ezer)>81 And (Select Count(Distinct Mishbezet) C From T_Ezer)=81 --וידוא שטרם נמצא פתרון ושהנתונים הגיוניים

                Begin --מחיקת ערכים מיותרים משורות

                With Nm As

                (Select 1 N

                Union All

                Select    N+1

                From    Nm

                Where    N<510), --511זה בדיקת כל המשבצות וזה מיותר

                T1 As

                (select    *

                From    Nm

                Inner Join T_Ezer E

                        On Nm.N%POWER(2,E.MoneS)>=Power(2,E.MoneS-1)),

                T2 As

                (Select    *,

                        Dense_Rank() Over(Partition By Shura,N Order By Pitron) MoneN, --זה הפתרון שמצאתי למניית מספר הפתרונות השונים בכל קבוצה

                        Dense_Rank() Over(Partition By Shura,N Order By Mishbezet) MoneM --כנ"ל לגבי משבצות

                From    T1),

                T3 As

                (Select    *,

                        Max(MoneN) Over(Partition By Shura,N) MaxN,

                        Max(MoneM) Over(Partition By Shura,N) MaxM

                From    T2),

                T4 As

                (Select    N,

                        Shura,

                        Max(Case When MoneN=1 Then Pitron End) P1,

                        Max(Case When MoneN=2 Then Pitron End) P2,

                        Max(Case When MoneN=3 Then Pitron End) P3,

                        Max(Case When MoneN=4 Then Pitron End) P4,

                        Max(Case When MoneN=5 Then Pitron End) P5,

                        Max(Case When MoneN=6 Then Pitron End) P6,

                        Max(Case When MoneN=7 Then Pitron End) P7,

                        Max(Case When MoneN=8 Then Pitron End) P8,

                        Max(Case When MoneN=9 Then Pitron End) P9

                From    T3

                Where    MaxN=MaxM

                Group By N,

                        Shura)

                Delete

                From    T_Ezer

                Where    Exists (Select *

                                From    T4

                                Where    T4.Shura=T_Ezer.Shura

                                        And T_Ezer.Pitron In (T4.P1,T4.P2,T4.P3,T4.P4,T4.P5,T4.P6,T4.P7,T4.P8,T4.P9)

                                        And N%POWER(2,T_Ezer.MoneS)<POWER(2,T_Ezer.MoneS-1))

                Option (MaxRecursion 0);

                Set        @RC=@RC+@@RowCount;

                End

        If (Select Count(*) C From T_Ezer)>81 And (Select Count(Distinct Mishbezet) C From T_Ezer)=81 --וידוא שטרם נמצא פתרון ושהנתונים הגיוניים

                Begin --מחיקת ערכים מיותרים מעמודות

                With Nm As

                (Select 1 N

                Union All

                Select    N+1

                From    Nm

                Where    N<510), --511זה בדיקת כל המשבצות וזה מיותר

                T1 As

                (select    *

                From    Nm

                Inner Join T_Ezer E

                        On Nm.N%POWER(2,E.MoneA)>=Power(2,E.MoneA-1)),

                T2 As

                (Select    *,

                        Dense_Rank() Over(Partition By Amuda,N Order By Pitron) MoneN, --זה הפתרון שמצאתי למניית מספר הפתרונות השונים בכל קבוצה

                        Dense_Rank() Over(Partition By Amuda,N Order By Mishbezet) MoneM --כנ"ל לגבי משבצות

                From    T1),

                T3 As

                (Select    *,

                        Max(MoneN) Over(Partition By Amuda,N) MaxN,

                        Max(MoneM) Over(Partition By Amuda,N) MaxM

                From    T2),

                T4 As

                (Select    N,

                        Amuda,

                        Max(Case When MoneN=1 Then Pitron End) P1,

                        Max(Case When MoneN=2 Then Pitron End) P2,

                        Max(Case When MoneN=3 Then Pitron End) P3,

                        Max(Case When MoneN=4 Then Pitron End) P4,

                        Max(Case When MoneN=5 Then Pitron End) P5,

                        Max(Case When MoneN=6 Then Pitron End) P6,

                        Max(Case When MoneN=7 Then Pitron End) P7,

                        Max(Case When MoneN=8 Then Pitron End) P8,

                        Max(Case When MoneN=9 Then Pitron End) P9

                From    T3

                Where    MaxN=MaxM

                Group By N,

                        Amuda)

                Delete

                From    T_Ezer

                Where    Exists (Select *

                                From    T4

                                Where    T4.Amuda=T_Ezer.Amuda

                                        And T_Ezer.Pitron In (T4.P1,T4.P2,T4.P3,T4.P4,T4.P5,T4.P6,T4.P7,T4.P8,T4.P9)

                                        And N%POWER(2,T_Ezer.MoneA)<POWER(2,T_Ezer.MoneA-1))

                Option (MaxRecursion 0);

                Set        @RC=@RC+@@RowCount;

                End

        If (Select Count(*) C From T_Ezer)>81 And (Select Count(Distinct Mishbezet) C From T_Ezer)=81 --וידוא שטרם נמצא פתרון ושהנתונים הגיוניים

                Begin --מחיקת ערכים מיותרים מריבועים

                With Nm As

                (Select 1 N

                Union All

                Select    N+1

                From    Nm

                Where    N<510), --511זה בדיקת כל המשבצות וזה מיותר

                T1 As

                (select    *

                From    Nm

                Inner Join T_Ezer E

                        On Nm.N%POWER(2,E.MoneR)>=Power(2,E.MoneR-1)),

                T2 As

                (Select    *,

                        Dense_Rank() Over(Partition By Ribua,N Order By Pitron) MoneN, --זה הפתרון שמצאתי למניית מספר הפתרונות השונים בכל קבוצה

                        Dense_Rank() Over(Partition By Ribua,N Order By Mishbezet) MoneM --כנ"ל לגבי משבצות

                From    T1),

                T3 As

                (Select    *,

                        Max(MoneN) Over(Partition By Ribua,N) MaxN,

                        Max(MoneM) Over(Partition By Ribua,N) MaxM

                From    T2),

                T4 As

                (Select    N,

                        Ribua,

                        Max(Case When MoneN=1 Then Pitron End) P1,

                        Max(Case When MoneN=2 Then Pitron End) P2,

                        Max(Case When MoneN=3 Then Pitron End) P3,

                        Max(Case When MoneN=4 Then Pitron End) P4,

                        Max(Case When MoneN=5 Then Pitron End) P5,

                        Max(Case When MoneN=6 Then Pitron End) P6,

                        Max(Case When MoneN=7 Then Pitron End) P7,

                        Max(Case When MoneN=8 Then Pitron End) P8,

                        Max(Case When MoneN=9 Then Pitron End) P9

                From    T3

                Where    MaxN=MaxM

                Group By N,

                        Ribua)

                Delete

                From    T_Ezer

                Where    Exists (Select *

                                From    T4

                                Where    T4.Ribua=T_Ezer.Ribua

                                        And T_Ezer.Pitron In (T4.P1,T4.P2,T4.P3,T4.P4,T4.P5,T4.P6,T4.P7,T4.P8,T4.P9)

                                        And N%POWER(2,T_Ezer.MoneR)<POWER(2,T_Ezer.MoneR-1))

                Option (MaxRecursion 0);

                Set        @RC=@RC+@@RowCount;

                End

        End

Select    --הדפסת הפתרון - אם יש

        Max(Case When Amuda=1 Then Pitron End) A1,

        Max(Case When Amuda=2 Then Pitron End) A2,

        Max(Case When Amuda=3 Then Pitron End) A3,

        Max(Case When Amuda=4 Then Pitron End) A4,

        Max(Case When Amuda=5 Then Pitron End) A5,

        Max(Case When Amuda=6 Then Pitron End) A6,

        Max(Case When Amuda=7 Then Pitron End) A7,

        Max(Case When Amuda=8 Then Pitron End) A8,

        Max(Case When Amuda=9 Then Pitron End) A9

From    T_Ezer

Where    (Select COUNT(*) C From T_Ezer)=81

Group By Shura

Order By Shura;

את נתוני הבעיות יש לקלוט לטבלת בעיות שכוללת את תיאור הבעייה,

וטבלת פירוט הבעיות שכוללת את הנתונים השונים של כל בעייה:

Create Table T_Beayot(Beaya Int Identity(1,1) Primary Key,

                    Teur    Varchar(MAX));

Create Table T_PerutBeayot(Beaya Int Not Null,

                        Mishbezet TinyInt Not Null,

                        Natun TinyInt Not Null,

                        Constraint T_PerutBeayot_PK Primary Key (Beaya ,Mishbezet));

המשבצות ממוספרות 1..81 משמאל לימין ומלמעלה למטה,

וכדי להקל על הקליטה צירפתי פרוצדורה שעושה זאת בקלות (כולל דוגמה כיצד להפעילה):

Create Procedure P_Klita(@B Varchar(Max),

                        @PB Varchar(269)) As

Declare    @ID Int;

Set        @PB=Replace(REPLACE(Replace(REPLACE(@PB,'|',''),'-',''),Char(13),''),CHAR(10),'');--נוריד מעברי שורה ותווי עיצוב ונשאיר רק 81 תווי נתונים

Insert Into T_Beayot(Teur)

Select    @B;

Set        @ID=@@Identity;

With Nm As

(Select 1 N

Union All

Select    N+1

From    Nm

Where    N<81)

Insert Into T_PerutBeayot(Beaya, Mishbezet, Natun)

Select    @ID Beaya,

        Nm.N Mishbezet,

        SubString(@PB,Nm.N,1) Natun

From    Nm

Where    SubString(@PB,Nm.N,1)<>'0';

Select    @ID [The problem number is:];

P_Klita

'דוגמה מתוך http://www.sudoku.co.il/ רמה קלה',

'------------

|089|027|041|

|040|010|200|

|060|009|800|

-------------

|350|200|700|

|600|803|004|

|002|100|038|

-------------

|006|300|050|

|005|040|060|

|120|750|980|

-------------'

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

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

וטבלת הלוח בה יש 81 רשומות עבור 81 המשבצות, ולגבי כל משבצת מצויים מספר השורה, מספר העמודה, מספר הריבוע, ומספר המשבצת בכל אחד משלושת אלו (משמש לשליפת תתי הקבוצות):

Create Table T_Luah(Mishbezet TinyInt Primary Key,

                    Shura TinyInt,

                    Amuda TinyInt,

                    Ribua TinyInt,

                    MoneS TinyInt,

                    MoneA TinyInt,

                    MoneR TinyInt);

With Nm As

(Select 1 N

Union All

Select    N+1

From    Nm

Where    N<81),

T1 As

(Select    N Mishbezet,

        (N-1)/9+1 Shura,

        (N-1)%9+1 Amuda

From    Nm),

T2 As

(Select    *,

        3*((Shura-1)/3)+(Amuda-1)/3+1 Ribua

From    T1)

Insert Into T_Luah

Select    *,

        Row_Number() Over(Partition By Shura Order By Mishbezet) MoneS,

        Row_Number() Over(Partition By Amuda Order By Mishbezet) MoneA,

        Row_Number() Over(Partition By Ribua Order By Mishbezet) MoneR

From    T2;

Create Table T_Ezer(Mishbezet TinyInt Not Null,

                    Shura TinyInt Not Null,

                    Amuda TinyInt Not Null,

                    Ribua TinyInt Not Null,

                    MoneS TinyInt Not Null,

                    MoneA TinyInt Not Null,

                    MoneR TinyInt Not Null,

                    Pitron TinyInt Not Null);

Create Unique Clustered Index T_Ezer_Idx On T_Ezer(Mishbezet, Pitron);

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

הרצתי את הפרוצדורה כנגד מדגם של בעיות מרמת הקושי הגבוהה ביותר במספר אתרים, וכולן נפתרו תוך כ-15 שניות.

לדעתי ניתן לקצר את זמן הפתרון אם פותרים בהתחלה עבור תתי קבוצות בגודל 1 ו-2: ניתן לעשות זאת על ידי שליפות הרבה יותר פשוטות ומהירות, ואם זה לא יפתור את הבעייה – זה יפתור 90% ממנה..

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

22/04/2010 עדכון הפוסט: יש פתרון מהיר ומלא משלי http://michaeljswart.com/?p=4.
הקוד מסיים תוך שניה פחות או יותר, ומתברר שיש בעיות בלתי פתירות שמצריכות "שימוש בכח", למשל הבעיה הבאה:

P_Klita
'http://www.sudoku.name/index-hb.php #5394',
'——————–
|003|800|400|
|700|000|000|
|500|006|100|
——————–
|005|020|003|
|060|000|050|
|100|400|200|
——————–
|007|500|008|
|000|000|006|
|008|004|500|
——————–';

שמצטמצמת בסוף למצב הבא:

29,1,3,8,5,7,4,6,29

7,29,6,1,4,29,8,3,5

5,8,4,23,39,6,1,7,29

4,7,5,9,2,8,6,1,3

8,6,2,7,13,13,9,5,4

1,3,9,4,6,5,2,8,7

6,4,7,5,19,129,3,29,8

29,5,1,23,8,239,7,4,6

3,29,8,6,7,4,5,29,1

והוא פותר אותה על ידי ניסוי וטעיה: בהתחלה מבטל את ה-9 שבפינה השמאלית העליונה ואם זה לא הולך אז את ה-2.
זה מתבצע בדרך של בחירת הערך המקסימלי הראשון ממשבצת בעלת שתי אפשרויות – כל זה בתוך טרנזקציה,
ואם זה לא הולך – ביצוע Roll Back לטרנזקציה ובחירת הערך המינימלי הראשון..
בפועל זה כנראה פותר את כל הבעיות הסרבניות.

מודעות פרסומת

להגיב »

עדיין אין תגובות.

RSS feed for comments on this post. TrackBack URI

להשאיר תגובה

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

הלוגו של WordPress.com

אתה מגיב באמצעות חשבון WordPress.com שלך. לצאת מהמערכת / לשנות )

תמונת Twitter

אתה מגיב באמצעות חשבון Twitter שלך. לצאת מהמערכת / לשנות )

תמונת Facebook

אתה מגיב באמצעות חשבון Facebook שלך. לצאת מהמערכת / לשנות )

תמונת גוגל פלוס

אתה מגיב באמצעות חשבון Google+ שלך. לצאת מהמערכת / לשנות )

מתחבר ל-%s

יצירה של אתר חינמי או בלוג ב־WordPress.com.

%d בלוגרים אהבו את זה: