Սուդոկուի լուծում Python3-ով և հետքայլով

Ողջույն բոլորին, այսօր մենք պատրաստվում ենք ստեղծել Sudoku լուծիչ՝ օգտագործելով python 3: Այս բլոգի գրառման մեջ ես կանցնեմ խաղի տեսության և անհրաժեշտ ալգորիթմների միջով, որպեսզի կարողանաք հեշտությամբ հաղթել ցանկացած սուդոկու տախտակ:

Սուդոկուն հանելուկ խաղ է, որը խաղում է 9x9 տախտակի վրա, որտեղ նպատակն է լրացնել յուրաքանչյուր քառակուսի 1-ից 9 թվերով: Խաղի կանոնները պարզ են, որևէ սյունակում, տողում կամ ենթացանցում չեն կարող լինել կրկնօրինակ թվեր: . Ենթացանցերը ներքին 3x3 ցանց են 9x9 տախտակի ներսում: Ստորև ներկայացված է սուդոկու տախտակի պատկերը, որի առաջին ենթացանցը կանաչ է:

Կանոնները նվազագույն են, բայց այս հանելուկները կարող են դժվար լինել, քանի որ գոյություն ունի միայն մեկ լուծում Sudoku-ի վավեր տախտակների համար:

Սուդոկու հանելուկների կառուցում

Նախ, մենք կկառուցենք խաղ հանելուկներ ստեղծելու համար, որպեսզի փորձարկենք մեր լուծիչը:

Խաղը կառուցելու համար մենք պատրաստվում ենք երկքայլ մոտեցում ցուցաբերել: Մեր առաջին քայլը կլինի ամբողջական տախտակը լրացնել լուծումով՝ ապահովելու այն լուծելի: Այնուհետև, երբ իմանանք, որ հանելուկը լուծելի է, մենք դիմակ կկիրառենք:

Ապահովելու համար, որ մենք ստեղծում ենք եզակի նոր տախտակներ, մենք կօգտագործենք պատահական մոդուլը, որը տրամադրվում է python ստանդարտ գրադարանում: Օգտագործելով այս գրադարանը՝ մենք յուրաքանչյուր քառակուսի համար հնարավոր արժեքների ցանկից կընտրենք պատահական ընտրություն՝ ապահովելով, որ հետևում ենք կանոններին:

Մենք կկրկնենք խաղատախտակի միջով շարք առ տող՝ դիմակ ստեղծելու համար՝ ընտրելով պահելու համար ինդեքսների պատահական շարք: Ինչպես նկարագրված է 2012 թ. Չկա 16 թելադրանքով սուդոկու. Սուդոկուի նվազագույն քանակի թելադրանքների խնդիրը թղթում, մենք գիտենք, որ 17-ը եզակի լուծումներ ստեղծելու համար անհրաժեշտ հուշումների նվազագույն քանակն է:

Եզակի լուծումներ ստեղծելը կարևոր է, քանի որ ոչ եզակի լուծում ունենալը կհանգեցնի գլուխկոտրուկի անվավեր լինելուն: Քանի որ մենք ներկայումս չունենք լուծիչ, մենք չենք կարող հաստատել, որ մեր դիմակավորման գործառույթը ստեղծել է եզակի լուծում: Դրա պատճառով մենք օգտվում ենք 17 հուշումների նվազագույն կանոնից և ապահովում ենք, որ տալիս ենք ավելի քան 17 հուշում: Դրանով մենք մեծացնում ենք եզակի լուծում ստեղծելու հավանականությունը:

Հանուն այս բլոգի, մենք օգտագործում ենք 45 հուշումներ, քանի որ փորձարկումից հետո (ես օգտագործեցի մեր ստեղծած լուծիչը՝ ստուգելու համար), ես գտա, որ այն եզակի լուծում է տալիս մոտավորապես 82% դեպքերում:

Պարզ լուծում

Այժմ, երբ մենք կարող ենք ստեղծել հանելուկներ, մենք պետք է լուծենք դրանք: Այս հանելուկները լուծելու պարզ լուծումը մաքուր բիրտ ուժի մոտեցումն է: Դա անելու համար մենք կօգտագործենք ռեկուրսիա և կփորձենք արժեքների բոլոր հնարավոր համակցությունները: Քանի որ կան 6,670,903,752,021,072,936,960 եզակի հնարավոր լուծումներ Sudoku-ի տախտակի համար, անհրաժեշտ կլինի կրճատել որոնման տարածքը՝ օգտագործելով խաղի կանոնները:

Կանոնները օգտագործելու համար մենք կարող ենք օգտագործել մտապահումը և պահպանել այն արժեքները, որոնք տեղադրված են ընթացիկ տողում, ընթացիկ սյունակում և ընթացիկ ենթացանցում: Այսպիսով, մենք կարիք չունենք փորձել 1-ից 9-ի բոլոր համակցությունները, փոխարենը կարող ենք որոնել այն թվերը, որոնք դեռ չեն օգտագործվում:

Ընթացիկ տողում, ընթացիկ սյունակում և ընթացիկ ենթացանցում եղածն անգիր անելու համար, մենք կարող ենք դրանց արժեքները պահել հավաքածուների բառարաններում (բառարանները և հավաքածուները O(1) են որոնումների համար, քանի որ նրանք օգտագործում են հեշեր)՝ օգտագործելով իրենց համապատասխան ինդեքսը՝ որպես արագ մուտքի բանալին: . Սյունակի և տողի ինդեքսը որոշելը հեշտ է, բայց ենթացանկի ինդեքսը գտնելն ավելի բարդ է: Ենթացանցի ինդեքսը որոշելու համար կարող ենք օգտագործել հետևյալ հավասարումը.

Գործերն էլ ավելի արագացնելու համար մենք կարող ենք օգտագործել վաղաժամկետ դադարեցումը և այն գտնելուց հետո վերադարձնել առաջին կենսունակ լուծումը: Վաղ դադարեցումը կօգնի արագացնել հաշվարկը, քանի որ մենք այլևս կարիք չունենք ավելի շատ համակցություններ փորձել:

Այս մոտեցումը գործն անում է խնդիրը հաջողությամբ լուծելու միջոցով: Այնուամենայնիվ, դա այնքան էլ հաշվողականորեն արդյունավետ չէ, և մենք կարող ենք ավելի լավ անել, քան սա:

Հետադարձ լուծում

Այս խնդրի ավելի էլեգանտ մոտեցումը կլինի հետընթաց ծառի որոնումը: Այստեղ մենք կարող ենք օգտագործել հետընթաց ծառի որոնումը, քանի որ հնարավոր համակցությունները կարող ենք դիտել որպես ծառ (գրաֆիկի տվյալների կառուցվածք):

Հետևյալ ծառի որոնումը ծառի որոնման օպտիմիզացված ձև է, որտեղ ձեր որոնումը ծառի ցողունից վերսկսելու փոխարեն դուք կտրում եք այդ սխալ հանգույցը և նորից գնում ծառի վրա և շարունակում հաջորդ տարբերակը: Այսպիսով, դուք խնայում եք հաշվարկները՝ պահպանելով ընտրանքները, որոնք դուք գիտեք, որ ճիշտ են: Հետընթացի հնարավոր ուղու օրինակը ներկայացված է ստորև բերված դիագրամում:

Մեր հետընթացի ալգորիթմով մենք դեռ օգտագործում ենք ռեկուրսիոն, անգիր և վաղ կանգառը, ինչպես մեր բիրտ ուժի մեթոդը, բացառությամբ, որ այժմ մենք ավելի մեծ ուշադրություն ենք դարձնում ծառի (գրաֆիկի) ճյուղերին (եզրերին) և ավելի արդյունավետ որոնում:

Շնորհակալություն

Եվ ահա դուք ունեք այն, մենք հաջողությամբ ստեղծել ենք մեր սուդոկու լուծիչը: Դուք կարող եք ստուգել կոդի ամբողջական տարբերակը իմ GitHub-ում այստեղ: Ինչպես կռահեցիք, մենք կարող էինք օգտագործել հետընթացի ալգորիթմը մեր Sudoku խաղը կառուցելիս՝ այն ավելի արդյունավետ դարձնելու համար, և ես դա արեցի իմ Github-ի կոդը:

Շնորհակալություն կարդալու համար: Եթե ​​ձեզ դուր եկավ սա, մտածեք բաժանորդագրվել իմ հաշվին, որպեսզի տեղեկացված լինեք իմ ամենավերջին գրառումների մասին:

Հղում