Pagina 1 di 1

Compressione di sudoku

Inviato: sab set 15, 2018 10:14 am
da giobimbo
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).