Immagino tutti sappiano cos’è un sudoku, una griglia 9x9 formata da nove mini-griglie 3x3, chiamate “blocchi”, riempiti con i numeri da 1 a 9 in modo che ogni riga e ogni colonna del sudoku contenga numeri diversi.
Scegliamo tre numeri e cancelliamo gli altri sei, in tutto il sudoku, rimanendo con tre numeri in ogni blocco, totale 27 in tutto.
Prendiamo due file orizzontali di blocchi e sovrapponiamole a quella rimanente; si presentano due casi:
1) qualche blocco ha 2 o 3 numeri in una casella
2) tutti i blocchi hanno un solo numero per casella.
Chiamiamo questa fila di blocchi sovrapposti “componente orizzontale”.
Adesso prendiamo due file verticali di blocchi e sovrapponiamole a quella rimanente; si presentano due casi:
1) qualche blocco ha 2 o 3 numeri in una casella
2) tutti i blocchi hanno un solo numero per casella.
Chiamiamo questa fila di blocchi sovrapposti “componente verticale”.
Usando queste due componenti possiamo costruire una o più famiglie di sudoku, una delle quali conterrà il sudoku di partenza. Ovviamente ci sono tante gradazioni di compressione ma ci limitiamo a 3 livelli:
Alto - ambedue le componenti del sudoku compresso hanno tutti i blocchi con un solo numero per casella e ogni blocco ha righe e colonne contenenti sempre numeri diversi. Con le componenti orizzontale e verticale si ottiene una sola famiglia di sudoku;
Medio - almeno una componente ha tutti i blocchi con un solo numero per casella. Con le componenti orizzontale e verticale si ottengono m famiglie di sudoku;
Basso - nessuna componente ha tutti i blocchi con un solo numero per casella. Con le componenti orizzontale e verticale si ottengono n famiglie di sudoku, con n>m.
Prendiamo per esempio il sudoku qui sotto:
4…1…2 3…6…9 7…5…8
9…6…3 5…7…8 4…1…2
5…7…8 4…1…2 3…6…9
3…5…9 1…4…6 2…8…7
1…8…4 7…2…5 9…3…6
6…2…7 8…9…3 5…4…1
7…9…5 6…3…1 8…2…4
2…3…1 9…8…4 6…7…5
8…4…6 2…5…7 1…9…3
Scegliendo i numeri 1, 2, 3 e cancellando tutti gli altri rimaniamo con:
0…1…2 3…0…0 0…0…0
0…0…3 0…0…0 0…1…2
0…0…0 0…1…2 3…0…0
3…0…0 1…0…0 2…0…0
1…0…0 0…2…0 0…3…0
0…2…0 0…0…3 0…0…1
0…0…0 0…3…1 0…2…0
2…3…1 0…0…0 0…0…0
0…0…0 2…0…0 1…0…3
per cui sovrapponendo la prima e la seconda fila orizzontale di blocchi alla terza otteniamo:
030…100…200 310…003…001 020…002…000
012…003…301 000…020…000 000…130…200
000…020…000 002…100…230 301…000…013
questa è la componente orizzontale.
Invece sovrapponendo le prime due file verticali alla terza otteniamo:
030…100…200
000…001…302
003…010…020
312…000…000
100…023…000
000…200…031
000…032…010
200…300…100
021…000…003
questa è la componente verticale. Ambedue le componenti hanno blocchi con più di un elemento per casella, quindi scegliendo 1, 2 e 3 abbiamo una compressione di basso livello.
Problema 1. Trovare i tre numeri che danno il massimo livello di compressione per il sudoku qui sotto:
4…1…2 3…6…9 7…5…8
9…6…3 5…7…8 4…1…2
5…7…8 4…1…2 3…6…9
3…5…9 1…4…6 2…8…7
1…8…4 7…2…5 9…3…6
6…2…7 8…9…3 5…4…1
7…9…5 6…3…1 8…2…4
2…3…1 9…8…4 6…7…5
8…4…6 2…5…7 1…9…3
Problema 2. Costruire un sudoku che possieda una compressione di alto livello (e scrivere i tre numeri scelti per ottenerla).
Compressione di sudoku
Moderatori: Gianfranco, Bruno
Questo forum è una sezione del PORTALE DI BASE CINQUE