Sudoku tilbakesporing
Det berømte Sudoku -spillet består av å fylle en kube med 9 x 9 celler arrangert i 9 undergrupper av 3 x 3 celler, med tall fra 1 til 9, med begrensningen om at det samme tallet ikke må gjentas i samme rad, kolonne eller undergruppe på 9.
En Sudoku har flere celler med en startverdi, så vi må begynne å løse problemet fra denne delløsningen uten å endre noen av de innledende cellene.
Oppløsningsstrategi ved hjelp av tilbakesporing
Sudoku - bordet som skal løses er gitt av en matrise "Sol [1..9,1..9] på 0..9" der Sol[i, j] representerer verdien som nevnte celle tar, med verdien 0 tilsvarer til en tom boks.
En hjelpematrise “initial[ 1..9 , 1..9] of Bool” vil bli brukt, der initial[i, j] representerer en celle med en startverdi som ikke kan endres og tilsvarer cellen “Sol[i] , j]”.
Ved forgrening av letetreet vil vi kun gjøre det hvis delløsningen vi ser på er k-lovende, det vil si at vi fra nevnte delløsning kan fortsette å bygge delløsninger. For å løse dette punktet vil vi bruke en hjelpefunksjon kalt "is_feasible".
Funksjonen "is_feasible" sjekker for en gitt celle at verdien ikke gjentas i samme rad, kolonne eller 3x3 undergruppe, og oppfyller dermed begrensningen som vi nevnte i den detaljerte beskrivelsen av problemet.
Siden en Sudoku kan ha flere løsninger, vil vi implementere algoritmen deretter.
Det genererte letingstreet vil ha følgende egenskaper:
Hvor m er antallet tomme celler i utgangspunktet.
- Antall barn for hver node = 9:
Ett barn for hver mulig verdi av celle i j.
Pseudokodeimplementering
Proc sudoku_VA (i, j: Nat; sol[1..9, 1..9] av 0..9; initial[1..9, 1..9] av Bool)
Hvis (initial [i, j] = False) Da
For (k := 1) Inntil 9 Do
sol[i, j] := k; //sett kryss
Hvis (er_gjennomførbart (i, j, sol)) Da
saker
i = 9 ^ j = 9 -> displayByScreen(sol);
i < 9 ^ j = 9 -> sudoku_VA (i+1, 1, sol, initial);
i <= 9 ^ j < 9 -> sudoku_VA( i , j+1, sol, initial);
Sluttsaker;
Slutt ja;
sol[i, j]: = 0; //Fjern merket
EndTo;
Else //initial[i, j] = Sant
saker
i = 9 ^ j = 9 -> displayByScreen(sol);
i < 9 ^ j = 9 -> sudoku_VA (i+1, 1, sol, initial);
i <= 9 ^ j < 9 -> sudoku_VA( i , j+1, sol, initial);
Sluttsaker;
Slutt ja;
FinProc;
Første samtale
Proc sudoku (g[1..9, 1..9] av 0..9)
Var
Bool initial[1..9, 1..9];
FinVar;
For (i := 1) Inntil 9 Do
For (j := 1) Inntil 9 Do
initial[i, j] := Sol[i, j] != 0;
EndTo;
EndTo;
sudoku_VA(1, 1, sol, initial);
FinProc;
Hjelpefunksjoner
Hjelpefunksjon som sjekker gjennomførbarheten av en delløsning.
Moro er_gjennomførbart (i, j : Nat; sol[1..9, 1..9] av 0..9) DEV Bool
Var
gyldig : Bool;
k,l: Nat;
FinVar;
gyldig := Sant;
k:= 1;
Mens (k <= 9 ^ gyldig) Gjør //Vi sjekker kolonnen
If ( sol[i, j] = sol[k, j] ^ k != i ){
Gyldig := Falsk;
Slutt ja;
k:= k + 1;
EndWhile;
l:= 1;
Mens (l <= 9 ^ gyldig) Gjør //Vi sjekker raden
If ( sol[i, j] = sol[i, l] ^ l != j ){
Gyldig := Falsk;
Slutt ja;
1:= 1 + 1;
EndWhile;
// Ovennevnte kan komprimeres slik, til en enkelt stund som sjekker rader og kolonner.
// Mens (k<=9 ^ gyldig) Gjør
// If ( (g[i, j] = g[k, j] ^ k != i) v (g[i, j] = g[i, k] ^ k != j))
// Gyldig := False;
// Slutt ja;
// EndWhile;
k := korrespondanse 3x3(i);
l := korrespondanse 3x3(j); //Vi sjekker undergruppen til 3x3
Mens ( k < correspondence3x3(i) + 3 ^ valid ) Gjør //av effektivitetshensyn du kan før dette stadiet, tilordne til en variabel
Mens ( l < samsvar3x3(j) + 3 ^ gyldig) Gjør // verdien av korrespondanse3x3(x) til x=io = j; så 2 samtaler unngås
Hvis ( sol[i, j] = sol[k, l] ^ i != k ^ j != l) Så // til nevnte funksjon som resulterer i bedre effektivitet.
gyldig := Falsk;
Slutt ja;
1:= 1 + 1;
EndWhile;
k:= k + 1;
l := korrespondanse 3x3(j);
EndWhile;
retur gyldig;
FinFun;
Hjelpefunksjon som brukes til å finne ut den første cellen som vi skal gjøre gjennomførbarhetskontrollen av en gitt celle i dens tilsvarende undergruppe av 3x3 celler.
Morsom korrespondanse 3x3 (i: Nat) DEV Nat
Var
k: Nat;
resultat: Nat;
FinVar;
Hvis (i MOD 3 = 0) Da
k := (i DIV 3);
I et annet tilfelle
k := (I DIV 3) + 1;
Slutt ja;
saker
k = 1 -> resultat := 1;
k = 2 -> resultat := 4;
k = 3 -> resultat := 7;
Sluttsaker;
returnere resultat;
FinFun;
Andre løsningsstrategier