Sudoku 17 ledtrådar Svår
Senaste poänglistan för #0x471
Senaste poänglistan för Sudoku 17 ledtrådar
Så spelar du Sudoku 17 ledtrådar
Det har bevisats att ett standardsudoku-pussel måste ha minst 17 ledtrådar för att få en unik lösning.
Sudoku-regler:
-
Fyll i siffrorna 1-9 i varje rad, kolumn och 3x3 underrutnät i ett 9x9 rutnät.
-
Varje nummer kan bara visas en gång i varje rad, kolumn och 3x3 underrutnät.
-
Fyll i de tomma utrymmena med siffrorna 1-9 så att varje rad, kolumn och 3x3 underrutnät har alla siffror 1-9.
Sudoku är ett logikbaserat nummerplaceringspussel. Målet är att fylla ett 9x9-rutnät med siffrorna 1-9, så att varje rad, kolumn och 3x3-underrutnät innehåller alla nio siffrorna exakt en gång.
2009 bevisade Gary McGuire och hans team att alla Sudoku-pussel med 16 ledtrådar måste ha minst två lösningar. De gjorde detta genom att använda en teknik som kallas "döda mönster."
Ett dött mönster är en Sudoku-konfiguration som har två eller flera möjliga lösningar. McGuire och hans team fann att alla Sudoku-pussel med 16 ledtrådar måste innehålla minst ett dött mönster. Därför måste dessa pussel ha minst två lösningar.
Detta resultat har flera konsekvenser. För det första betyder det att det inte finns något sådant som ett Sudoku-pussel med 16 ledtrådar med en unik lösning. För det andra betyder det att alla Sudoku-pussel med 16 ledtrådar kan lösas på flera sätt. För det tredje betyder det att det finns ett oändligt antal Sudoku-pussel med 16 ledtrådar.
Här är en mer teknisk förklaring av beviset på att Sudoku-pussel måste ha minst 17 ledtrådar för att ha en unik lösning:
Beviset börjar med att överväga ett Sudoku-pussel med 16 ledtrådar. Vi kan se detta pussel som en uppsättning begränsningar för siffrorna som kan placeras i de tomma rutorna.
Vi kan sedan använda en teknik som kallas "backtracking" för att försöka hitta en lösning på pusslet. Backtracking är en rekursiv algoritm som försöker alla möjliga kombinationer av tal i de tomma rutorna tills den hittar en lösning.
Om det finns en unik lösning på pusslet, kommer backtracking så småningom att hitta den. Men om det finns flera lösningar, kanske backtracking aldrig hittar en lösning.
McGuire och hans team använde backtracking för att visa att om det finns ett Sudoku-pussel med 16 ledtrådar med en unik lösning så måste det finnas ett sätt att starta backtracking-algoritmen på ett sådant sätt att den alltid hittar lösningen.
De visade då att detta inte är möjligt. De gjorde detta genom att konstruera en uppsättning av 16 ledtrådar som leder till ett dött mönster. Det här döda mönstret innebär att det finns två möjliga lösningar på pusslet, och inget sätt att starta backtracking-algoritmen på ett sådant sätt att den alltid hittar samma lösning.
Detta resultat visar att alla 16 ledtrådar Sudoku-pussel måste ha minst två lösningar.
