C# Programiranje-Backtracking - Sudoku - Rešavanje sudoku-a (Sudoku solver)

C# Programiranje-Backtracking - Sudoku - Rešavanje sudoku-a (Sudoku solver)
00:00 Uvod
00:15 Šta je sudoku
01:02 Backtracking
02:30 Rešavanje sudoku-a
09:30 Program
Rekurzija
Bektreking
Sudoku je logička igra koja se sastoji od rešavanja kvadratne matrice dimenzija 9x9, podeljene na manje kvadrate dimenzija 3x3. Cilj igre je popuniti svako polje u matrici sa brojevima od 1 do 9, tako da svaka kolona, svaki red i svaki manji kvadrat 3x3 sadrže sve brojeve od 1 do 9, bez ponavljanja.
Jedan od najčešćih pristupa za rešavanje Sudoku-a je metoda backtracking-a, koja sistematski isprobava moguće vrednosti za svako prazno polje u tabli, vraćajući se unazad kada dođe do konflikta ili nevalidnog rasporeda.
Backtracking je opšti algoritamski pristup koji se koristi za rešavanje problema pretraživanja, posebno kada je potrebno generisati sve (ili neke) moguće kombinacije rešenja. Ovaj pristup je posebno koristan kada se susrećemo sa problemima koji imaju moguće rešenje koje se sastoji od niza koraka ili odluka, a svaka odluka može dovesti do potencijalno ispravnog ili pogrešnog rešenja.

Backtracking radi rekurzivno, "probajući" svaku mogućnost, a zatim se vraća unazad (backtracking) kada se naiđe na neispravnu odluku. Ovaj proces se nastavlja sve dok se ne pronađe ispravno rešenje ili se isprobaju sve moguće kombinacije.
U kontekstu problema kao što je Sudoku, backtracking se koristi za sistematsko isprobavanje svake moguće vrednosti za svako prazno polje u tabli, i to rekurzivno.

Kada se naiđe na prazno polje, algoritam pokušava da postavi broj od 1 do 9 na to polje, a zatim proverava da li je to rešenje ispravno. Ako jeste, nastavlja se rekurzivno dalje.

Ako dođe do tačke gde se ne može postaviti ispravan broj (npr. jer je već postavljen u istom redu, koloni ili 3x3 kvadratu), algoritam se vraća unazad (back) i proba sa drugim brojem.

Backtracking tutorijal na srpskom

C# Programming-Backtracking - Sudoku - Solving sudoku (Sudoku solver)
Recursion
Backtracking
Sudoku is a logic game that consists of solving a square matrix of dimensions 9x9, divided into smaller squares of dimensions 3x3. The object of the game is to fill each square in the matrix with the numbers 1 to 9, so that each column, each row and each smaller 3x3 square contains all the numbers 1 to 9, without repetition.
One of the most common approaches to solving Sudoku is the backtracking method, which systematically tries possible values ​​for each empty space in the board, going back when a conflict or invalid layout occurs.
Backtracking is a general algorithmic approach used to solve search problems, especially when it is necessary to generate all (or some) possible combinations of solutions. This approach is particularly useful when faced with problems that have a possible solution consisting of a series of steps or decisions, each decision leading to a potentially right or wrong solution.

Backtracking works recursively, "trying" every possibility, then backtracking when an incorrect decision is encountered. This process continues until the correct solution is found or all possible combinations are tried.
In the context of a problem like Sudoku, backtracking is used to systematically try every possible value for every empty field in the board, recursively.

When an empty field is encountered, the algorithm tries to place a number from 1 to 9 in that field and then checks to see if that solution is correct. If so, it continues recursively.

If it reaches a point where a correct number cannot be placed (eg because it is already placed in the same row, column or 3x3 square), the algorithm goes back and tries another number.

Backtracking tutorial in Serbian
Backtracking, recursion