Nakna delmängder
Nakna delmängder
Tillhörande tekniker
Vad är Naked Subsets i Sudoku?
En naked subset är en grupp på N celler inom ett och samma hus (rad, kolumn eller block) vars sammanlagda kandidater innehåller exakt N olika siffror. Eftersom dessa N siffror måste fylla dessa N celler, kan de inte förekomma i någon annan cell i det huset. Detta gör att du säkert kan eliminera dessa siffror från de återstående cellerna.
Ordet "naked" betyder att kandidaterna är fullt synliga och blottade. Du behöver inte leta efter siffror som är dolda bland andra kandidater. Subseten avslöjar sig tydligt genom blyertsmarkeringarna i dessa celler.
Det finns fyra naked subset-tekniker, en för varje möjlig gruppstorlek:
- Naked single (N=1) -- en cell med en kandidat
- Bara par (N=2) -- två celler vars sammanlagda kandidater är exakt två siffror
- Naked triple (N=3) -- tre celler vars sammanlagda kandidater är exakt tre siffror
- Naked quad (N=4) -- fyra celler vars sammanlagda kandidater är exakt fyra siffror
Dessa fyra tekniker bildar en familj. De delar samma underliggande logik och skiljer sig bara i antalet inblandade celler. När du förstår grundprincipen blir de större subseten naturliga förlängningar av de enklare.
Grundprincipen: Varför naked subsets fungerar
Logiken bakom naked subsets vilar på ett grundläggande räkneargument som ibland kallas duvslagsprincipen. Enkelt uttryckt: om du har N platser och exakt N föremål att fylla dem med, går varje föremål i exakt en plats, och inga andra föremål kan uppta dessa platser.
Tänk dig en rad med nio celler. Varje olöst cell har en uppsättning kandidatsiffror, de blyertsmarkeringar som fortfarande lagligt kan stå i den cell. Anta att du hittar två celler i den raden vars kandidater båda hämtas från samma tvåsiffriga pool, säg {4, 6}. En av dessa celler måste innehålla 4 och den andra måste innehålla 6. Det finns inte plats för någon annan arrangemang. Detta betyder att ingen annan cell i raden kan innehålla 4 eller 6, eftersom båda siffrorna är fullt utnyttjade av dessa två celler.
Samma resonemang skalar upp. Tre celler vars sammanlagda kandidater uppgår till exakt tre siffror låser dessa tre siffror i dessa tre celler. Fyra celler med fyra sammanlagda kandidater låser alla fyra siffror. I varje cell kan de låsta siffrorna elimineras från alla andra celler i det gemensamma huset.
Denna princip gäller på samma sätt oavsett om huset är en rad, en kolumn eller ett 3x3-block. Det enda kravet är att alla N celler tillhör samma hus.
Naked single: Grunden för Sudoku-lösning
En naked single är den enklaste möjliga nakna delmängden. Den uppstår när en cell bara har en enda kandidat kvar i sina blyertsmarkeringar. Eftersom det bara finns en siffra som lagligt kan stå i den cell, är den siffran lösningen för cell.
Varje Sudoku-lösare, människa eller algoritm, förlitar sig på nakna singlar. De är det sista steget i elimineringskedjan: efter att alla begränsningar från rad, kolumn och block har tagit bort omöjliga siffror, är den sista kvarvarande kandidaten svaret.
Att hitta en naked single kräver att du noggrant håller reda på blyertsmarkeringarna för varje cell. En cell börjar med upp till nio möjliga kandidater. När du placerar siffror någon annanstans på brädet elimineras kandidater:
- Om en siffra placeras någonstans i samma rad, ta bort den från cell:s kandidater.
- Om en siffra placeras någonstans i samma kolumn, ta bort den från cell:s kandidater.
- Om en siffra placeras någonstans i samma 3x3-block, ta bort den från cell:s kandidater.
När dessa elimineringar reducerar en cell till en enda kandidat har du hittat en naked single.
Betrakta cell R5C3 i ett delvis löst pussel. Rad-, kolumn- och blockbegränsningarna eliminerar följande siffror:
- Rad 5 innehåller redan: 1, 3, 5, 8
- Kolumn 3 innehåller redan: 2, 6, 9
- Block 4 (det mellersta vänstra blocket) innehåller redan: 7
Tillsammans är siffrorna 1, 2, 3, 5, 6, 7, 8 och 9 alla eliminerade. Den enda kvarvarande kandidaten är 4. Cell R5C3 måste vara 4. Detta är en naked single.
Nakna singlar bör vara din första kontroll efter varje drag. Varje gång du placerar en siffra kan den reducera närliggande celler till en enda kandidat. I enklare pussel kan kedjor av nakna singlar lösa stora delar av brädet utan någon annan teknik. Även i svårare pussel rensar nakna singlar upp brädet efter att mer avancerade tekniker har eliminerat kandidater.
Bara par: Två celler, två kandidater, kraftfulla elimineringar
En bara par uppstår när två celler i samma hus vardera innehåller exakt samma två kandidater och inga andra kandidater. Eftersom dessa två siffror måste placeras i dessa två celler kan du eliminera båda siffrorna från varje annan cell i det huset.
Nakna par är en av de vanligaste tillämpade medelavancerade Sudoku-strategierna. De förekommer ofta och låser upp betydande framsteg genom att ta bort kandidater som blockerar andra tekniker.
Anta att två celler i rad 1 båda innehåller kandidaterna {4, 6} och inga andra kandidater:
- R1C2 har kandidater: {4, 6}
- R1C7 har kandidater: {4, 6}
En av dessa celler kommer att vara 4 och den andra kommer att vara 6. Vi vet ännu inte vilken som är vilken, men vi vet med säkerhet att 4 och 6 är helt förbrukade av dessa två celler. Därför kan ingen annan cell i rad 1 innehålla 4 eller 6.
Om R1C4 hade kandidaterna {3, 4, 6, 9} kan den reduceras till {3, 9} genom att ta bort 4 och 6. Om R1C8 hade kandidaterna {2, 6} kan den reduceras till {2}. Den reduktionen till en enda kandidat är i sig en naked single, vilket löser cell omedelbart.
Granska varje hus efter celler med exakt två kandidater. När du hittar två celler i samma hus med identiska två-kandidatuppsättningar har du ett bara par. Eftersom celler med bara två blyertsmarkeringar sticker ut visuellt är nakna par bland de enklaste medelavancerade teknikerna att upptäcka.
En användbar vana: när du märker en cell med bara två kandidater, kontrollera omedelbart om någon annan cell i samma rad, kolumn eller block delar samma par.
Naked triple: Tre celler, tre kandidater, en subtil twist
En naked triple uppstår när tre celler i samma hus har kandidater som helt och hållet hämtas från samma pool av exakt tre siffror. Den sammanlagda mängden av alla kandidater i de tre cellerna innehåller exakt tre olika siffror.
Här är den viktiga insikten som överraskar många lösare: varje enskild cell behöver inte innehålla alla tre siffrorna. En giltig naked triple kan innehålla celler med bara två av de tre siffrorna. Det som spelar roll är att unionen av alla kandidater i de tre cellerna sammanlagt utgör exakt tre olika värden.
Många spelare lär sig nakna par först och antar sedan att nakna tripplar kräver tre celler som var och en innehåller samma tre kandidater, som {1, 3, 7} i alla tre cellerna. Även om det är en giltig form av en naked triple, är det inte den enda och inte ens den vanligaste.
Betrakta dessa tre celler i kolumn 5:
- R2C5: {1, 3}
- R4C5: {1, 7}
- R8C5: {3, 7}
De sammanlagda kandidaterna är {1, 3, 7}, vilket är exakt tre siffror i tre celler. Detta är en giltig naked triple, även om ingen enskild cell innehåller alla tre siffrorna.
Logiken är densamma som med nakna par. Dessa tre siffror måste fylla dessa tre celler i någon ordning. En cell får 1, en får 3, en får 7. Därför kan 1, 3 och 7 elimineras från varje annan cell i kolumn 5.
Börja med att identifiera celler med två eller tre kandidater. I ett givet hus, om du hittar tre celler vars sammanlagda kandidater bildar en mängd på exakt tre siffror, har du en naked triple.
En praktisk metod:
1. I varje hus, lista alla olösta celler med tre eller färre kandidater.
2. Välj valfri kombination av tre sådana celler.
3. Ta unionen av deras kandidater. Om unionen har exakt tre siffror är det en naked triple.
Eftersom det finns flera möjliga kombinationer kräver nakna tripplar mer noggrann genomsökning än nakna par. Det är en del av vad som gör dem till en teknik med högre svårighetsgrad.
Naked quad: Fyra celler, fyra kandidater, maximal komplexitet
En naked quad är den största vanligt förekommande nakna delmängden. Den uppstår när fyra celler i ett hus har kandidater som helt och hållet hämtas från samma pool av exakt fyra siffror. Precis som med tripplar behöver enskilda celler inte innehålla alla fyra siffrorna. Det avgörande villkoret är att unionen av kandidater över alla fyra cellerna är exakt fyra olika värden.
Logiken är identisk med mindre nakna delmängder. Fyra siffror måste fylla fyra celler. Dessa siffror får inte förekomma någon annanstans i huset.
Nakna kvadrupler hittas sällan genom slumpmässig granskning. Med fyra celler och fyra siffror finns det många fler möjliga kombinationer att kontrollera. I ett hus med sex olösta celler finns det 15 möjliga sätt att välja fyra av dem. Att kontrollera varje kombination mentalt är mödosamt.
De flesta lösare som hittar nakna kvadrupler gör det antingen genom systematisk kontroll eller genom att först upptäcka att de återstående cellerna bildar en komplementär dold delmängd.
Trots sin sällsynthet förekommer nakna kvadrupler i riktiga pussel, särskilt de som är klassade som medelsvåra till utmanande. Att ha tekniken i sin repertoar säkerställer att du inte fastnar när enklare tekniker har uttömts.
Så hittar du nakna delmängder: praktiska granskningstips
Att hitta nakna delmängder effektivt kräver ett strukturerat tillvägagångssätt snarare än slumpmässig granskning. Här är tekniker som erfarna lösare använder:
Börja med små kandidatantal: Celler med färre kandidater deltar oftare i nakna delmängder. En cell med två kandidater kan ingå i ett par, en trippel eller en kvadrupel. En cell med fem kandidater är mindre användbar eftersom den bidrar med för många siffror till unionen. Granska varje hus efter celler med två kandidater först. Leta efter matchande par. Titta sedan på celler med två eller tre kandidater tillsammans för att hitta tripplar.
Arbeta hus för hus: Välj en rad, kolumn eller ett block och undersök alla dess olösta celler tillsammans. Lista deras kandidater. Leta efter kluster av celler vars kandidater överlappar inom en liten siffropool.
Använd räkningskontrollen: För varje grupp av N celler som du misstänker kan bilda en naken delmängd, räkna de olika siffrorna i deras kombinerade kandidater. Om antalet är lika med N har du hittat en naken delmängd. Om antalet överstiger N är dessa celler inte en naken delmängd.
Kontrollera efter varje eliminering: När en annan teknik tar bort kandidater från en cell, kontrollera den cells hus igen. Elimineringen kan ha skapat en ny naken delmängd som inte var synlig tidigare. Många nakna par uppstår som en bieffekt av tidigare elimineringar.
Leta efter komplementet: Om ett hus har K olösta celler och du misstänker att en naken delmängd finns men inte kan hitta den direkt, försök titta på komplementet. Att hitta en dold delmängd av storlek M innebär automatiskt en naken delmängd av storlek K - M.
Förhållandet mellan nakna delmängder och dolda delmängder
Nakna delmängder och dolda delmängder är två sidor av samma mynt. Att förstå deras dualitet fördjupar din förståelse för Sudoku-logik och kan hjälpa dig hitta mönster du annars skulle missa.
En dold delmängd uppstår när N siffror i ett hus endast förekommer inom N specifika celler. Siffrorna är "dolda" eftersom dessa celler även kan innehålla andra kandidater. Elimineringen tar bort de extra kandidaterna från dessa N celler och lämnar bara de dolda siffrorna.
I varje hus med K olösta celler gäller att om det finns en naken delmängd av storlek N, finns det automatiskt en dold delmängd av storlek K - N. De två delmängderna är komplementära: de delar upp de olösta cellerna och de återstående siffrorna i två icke-överlappande grupper.
Tänk till exempel på en rad med 6 olösta celler. Om två av dessa celler bildar ett bara par, bildar de återstående fyra cellerna en dolt fyrkant (eller motsvarande, en naked quad finns bland dessa fyra cellers uteslutna siffror). Du kan hitta endera och tillämpa motsvarande elimineringar.
Denna dualitet innebär att du har två vägar till samma eliminering. Om ett hus har många olösta celler är en liten naken delmängd (par eller trippel) lättare att upptäcka än en stor dold delmängd. Omvänt, om ett hus har få olösta celler kan en dolt par vara lättare att hitta än att söka efter den komplementära naked quad.
Erfarna lösare växlar mellan nakna och dolda perspektiv beroende på vilket som är mest praktiskt i en given situation. Förmågan att se båda sidorna ger dig en betydande fördel.
Svårighetsprogression: Från nybörjare till avancerad
De fyra nakna delmängdsteknikerna spänner över flera svårighetsnivåer, vilket speglar hur mycket svårare de är att hitta när gruppstorleken ökar:
Naked single (N=1): Nivå 2, Lätt
Bara par (N=2): Nivå 3, Lätt
Naked triple (N=3): Nivå 4, Måttlig
Naked quad (N=4): Nivå 5, Utmanande
Svårighetsökningen handlar inte om logiken, som är identisk i varje cell, utan om sökkomplexiteten:
Naked single: Du behöver bara kontrollera en cell. Om den har en kandidat är du klar. Ingen kombinationssökning krävs.
Bara par: Du behöver hitta två celler med matchande kandidater. I ett hus med sex olösta celler finns 15 möjliga par att kontrollera. Men eftersom du letar efter celler med exakt två identiska kandidater är det visuella mönstret distinkt och lätt att känna igen.
Naked triple: Du behöver hitta tre celler vars kombinerade kandidater totalt utgör tre siffror. I ett hus med sex olösta celler finns 20 möjliga tripplar. Sökningen är svårare eftersom cellerna inte behöver ha identiska kandidatmängder.
Naked quad: Du behöver hitta fyra celler bland potentiellt många olösta celler. Antalet kombinationer växer, och fyrsiffriga unioner är svårare att beräkna mentalt. De flesta kvadrupler hittas indirekt, antingen genom systematisk kandidaträkning eller genom att upptäcka den komplementära dolt par.
Pusselsvårighetsgrader beror ofta på vilka tekniker som krävs för att lösa dem. Ett pussel som inte behöver något utöver nakna singlar och par klassas som lätt. Ett pussel som kräver nakna tripplar går in på måttlig nivå. Ett pussel som kräver en naked quad är åtminstone utmanande.
Vanliga misstag och hur man undviker dem
Misstag 1: Att förvänta sig att alla celler innehåller alla siffror
Det vanligaste felet med nakna tripplar och kvadrupler är att anta att varje cell i delmängden måste innehålla alla N siffror. Detta är fel. En naked triple med cellerna {1,3}, {1,7} och {3,7} är helt giltig även om ingen cell innehåller alla av 1, 3 och 7.
Hur man undviker det: Kontrollera alltid unionen av kandidater, inte enskilda celler. Räkna de distinkta siffrorna över alla celler i gruppen. Om antalet är lika med antalet celler är det en naken delmängd oavsett hur siffrorna är fördelade mellan de enskilda cellerna.
Misstag 2: Att förväxla nakna och dolda delmängder
En bara par har N celler med kandidater begränsade till N siffror. En dolt par har N siffror begränsade till N celler, men dessa celler kan ha ytterligare kandidater.
Med en bara par eliminerar du parets siffror från andra celler i huset. Med en dolt par eliminerar du icke-parets siffror från parets egna celler.
Hur man undviker det: Fråga dig själv: "Tittar jag på celler med begränsade kandidater (naken) eller siffror med begränsade platser (dold)?" Begränsningens riktning avgör vilken typ av delmängd du har hittat.
Misstag 3: Att eliminera från fel celler
När du hittar en bara par {4, 6} i cellerna R1C2 och R1C7 eliminerar du 4 och 6 från de andra cellerna i rad 1. Du eliminerar inte andra kandidater från R1C2 och R1C7 själva. bara par:s kandidater förblir intakta i delmängdens egna celler.
Hur man undviker det: Kom ihåg regeln: nakna delmängder eliminerar sina siffror från celler utanför delmängden. Dolda delmängder eliminerar icke-delmängdens siffror från celler inuti delmängden.
Misstag 4: Att glömma att kontrollera alla delade hus
Två celler kan dela mer än ett hus. Till exempel delar R1C1 och R1C3 både rad 1 och block 1. Om de bildar en bara par kan du eliminera parets siffror från andra celler i rad 1 och från andra celler i block 1. Begränsa inte dina elimineringar till bara ett hus.
Hur man undviker det: För varje naken delmängd du hittar, kontrollera vilka hus alla delmängdens celler delar. Tillämpa elimineringar i varje delat hus.
När du ska använda nakna delmängder i ditt lösningsarbetsflöde
Nakna delmängder bör kontrolleras i ordning från minsta till största:
1. Nakna singlar först. Efter varje placering, sök efter nya nakna singlar. De är gratis och omedelbara.
2. Nakna par sedan. När inga fler nakna singlar återstår, sök efter nakna par i varje rad, kolumn och block. De är den vanligaste mellanliggande tekniken och låser ofta upp fler nakna singlar.
3. Nakna tripplar därefter. När paren inte räcker, bredda sökningen till tripplar. Fokusera på hus där flera celler har två eller tre kandidater.
4. Nakna kvadrupler sist. Sök bara efter kvadrupler när mindre delmängder och andra tekniker har uttömts. Med tanke på deras svårighetsgrad, överväg att först leta efter dolda par eller tripplar, eftersom de kan vara lättare att hitta och avslöjar samma information genom dualitetsprincipen.
Genom att följa denna progression tillämpar du de enklaste och mest produktiva teknikerna först och sparar mental ansträngning till när den verkligen behövs.
Sammanfattning
Nakna delmängder är en familj av fyra Sudoku-tekniker som förenas av en enda elegant princip: N celler i ett hus med exakt N kombinerade kandidater låser dessa siffror på plats, vilket gör att du kan eliminera dem från alla andra celler i huset.
Från den anspråkslösa naked single som löser en cell direkt, via nakna par och tripplar som rensar bort kandidater, till den svårfångade naked quad som kräver noggrant systematiskt sökande, utgör dessa tekniker en ryggrad i logisk Sudoku-lösning. Att behärska dem ger dig pålitliga verktyg som fungerar på pussel i alla svårighetsgrader och bygger grunden för att ta sig an ännu mer avancerade strategier som dolda delmängder, fiskmönster och kedjor.
Tillhörande tekniker