B. Sudoku
Un tabel de dimensiuni 6X6 se numește grilă Sudoku dacă îndeplinește simultan următoarele 3 condiții:
(1) În fiecare rând orizontal apar toate numerele 1,2,3,4,5,6
(2) În fiecare rând vertical apar toate numerele 1,2,3,4,5,6
(3) În fiecare dintre zonele A,B,C,D,E,F apar toate numerele 1,2,3,4,5,6
Zonele A,B,C,D,E,F sunt definite în figura următoare:
A A A B B B
A A A B B B
C C C D D D
C C C D D D
E E E F F F
E E E F F F
Dacă se cunosc doar o parte dintre valorile grilei, dar suficient de multe, se pot determina și celelalte valori necunoscute ale grilei prin observații și gândire logică. O astfel de grilă incompletă se mai numește joc Sudoku. Un joc Sudoku corect trebuie să poată fi completat unic, obținându-se astfel o grilă Sudoku completă.
Gigel îi propune lui Ionel să rezolve următorul joc Sudoku, în care se cunosc valorile de la 26 dintre pozitii:
0 0 3 4 5 0
4 5 6 1 0 3
2 1 0 3 6 5
3 0 5 0 1 4
5 0 1 6 4 2
6 4 2 0 3 0
După ce Ionel completează zerourile din grilă cu valori din mulțimea 1,2,3,4,5,6, astfel încât să fie respectate cele trei reguli (1),(2),(3), Gigel îl felicită și îi propune lui Ionel să construiască un alt joc Sudoku care să aibă ca soluție aceeași grilă ca și jocul anterior, dar care să aibă completate un număr minim de poziții. Ionel găsește pe Internet multe aplicații care rezolvă jocuri Sudoku, dar totuși nu reușește să rezolve problema și vă cere ajutorul dumneavoastră!
Este posibil ca să existe mai multe soluții. Oricare soluție care respectă condițiile cerute va fi considerată corectă.
Sursa: problemă originală (Ionel-Vasile Pit-Rada)
B. Sudoku
A 6X6 size table is called a Sudoku grid if it simultaneously meets the following 3 conditions:
(1) All numbers 1,2,3,4,5,6 appear in each horizontal row
(2) All numbers 1,2,3,4,5,6 appear in each vertical row
(3) In each of the zones A, B, C, D, E, F all the numbers 1,2,3,4,5,6 appear
The zones A,B,C,D,E,F are defined in the next figure:
A A A B B B
A A A B B B
C C C D D D
C C C D D D
E E E F F F
E E E F F F
If only a part, but enought, of the values of the grid are known, the other unknown values of the grid can be determined by observations and logical thinking. Such an incomplete grid is also called a Sudoku game. A correct Sudoku game must be able to be completed uniquely, thus obtaining a complete Sudoku grid.
Gigel proposes to Ionel to solve the following Sudoku game, in which the values from 26 of the positions are known:
0 0 3 4 5 0
4 5 6 1 0 3
2 1 0 3 6 5
3 0 5 0 1 4
5 0 1 6 4 2
6 4 2 0 3 0
After Ionel completes the zeros in the grid with values from the set 1,2,3,4,5,6, so that the three rules (1), (2), (3) are satisfied, Gigel congratulates him and proposes to Ionel to build another Sudoku game that has as solution the same grid as the previous game, but that has completed a minimum number of positions. Ionel finds many applications on the Internet that solve Sudoku games, but still fails to solve the problem and asks for your help!
There might be several solutions. Any solution that meets the required conditions will be considered correct.
Source: original problem (Ionel-Vasile Pit-Rada)
Logic
Determinarea numărului minim de poziții ocupate în grilă SUDOKU 6x6 astfel încât să existe o soluție unică de completare a acesteia , este o cerință a problemei ?
Da, gasirea unei astfel de grile (cu un nr.min de elemente completate) este de fapt cerinta problemei.
1) Cănd se afirmă că sunt posibile mai multe soluții, se face referire la valoarea numărului minim de elemente precompletate sau la variantele de precompletare a grilei cu numărul minim de elemente ?
Expresia "mai multe solutii posibile" se refera la solutii care au tot numarul minim de pozitii completate, dar multimile pozitiilor completate diferite.
Se cere pentru aceeași grilă completată un alt joc cu număr minim de numere. De aici deduc că sudoku-minim cerut de problemă poate avea numere 0 pe poziții în care sudoku-inițial avea număr nenul și număr nenul pe poziții unde în sudoku-inițial avea 0. Cerința prolemei este să plasăm un număr minim de numere, care generează soluție unică, iar această soluție este identică cu soluția sudoku-lui prezentat în problemă care nu are un număr minim de numere nenule). Cele două jocuri nu au nimic în comun în afară de soluția unică identică.