Questo codice CoffeeScript definisce due classi principali per la generazione e la gestione di puzzle Sudoku: Allow e SudokuLogic.
La classe Allow serve a tenere traccia dei valori ancora possibili per una determinata cella del Sudoku.
Quando viene creato un oggetto Allow, viene inizializzato un array di dimensione N×N (dove N è la dimensione della sottomatrice, ad esempio 3 per un Sudoku 9×9) e tutti gli elementi vengono impostati a true, indicando che inizialmente tutti i valori sono ammessi.
Il metodo length conta quanti valori sono ancora ammessi, mentre il metodo minus rimuove un valore dall’insieme di quelli possibili, impostandolo a false.
La classe SudokuLogic si occupa di generare una griglia Sudoku completa e di creare un puzzle giocabile con soluzione unica.
Nel costruttore, viene prima generata una soluzione completa e valida usando una formula matematica che riempie la griglia rispettando le regole del Sudoku.
Per rendere la soluzione casuale, vengono effettuate una serie di permutazioni: scambi di coppie di numeri, scambi di colonne all’interno delle sottomatrici e scambi di righe all’interno delle sottomatrici. Questo garantisce che il puzzle generato sia sempre diverso.
Dopo aver generato la griglia completa, il codice cerca di rimuovere dei numeri per creare il puzzle da giocare, regolando la quantità di celle date in base al livello di difficoltà (lev) e alla dimensione della griglia.
Per ogni cella da rimuovere, si verifica che la cella possa assumere un solo valore possibile dato lo stato attuale del puzzle, così da garantire che la soluzione rimanga unica.
Se la rimozione di un numero permetterebbe più soluzioni, il valore originale viene ripristinato (backtracking).
Infine, la classe offre due metodi: getComplete, che restituisce la soluzione completa, e getUncomplete, che restituisce il puzzle con alcuni numeri rimossi (la versione giocabile).
Questo approccio assicura che ogni puzzle generato sia casuale, risolvibile e con una sola soluzione, con la difficoltà regolata dal numero di celle date.
# Allow: oggetto che maniene i valori ammissibili di ogni cella
# N: dimensione di una sottomatrice
class @Allow
constructor: (@N) ->
@array = new Array(@N * @N)
i = @N * @N
while (i--)
@array[i] = true
return this
# length: numero di valori ammissibili
length: () ->
i = @N * @N
counter = 0
while (i--)
counter++ if @array[i] is false
return counter
# minus: se viene aggiunto un numero lo tolgo dagli ammissibili
minus: (num) ->
num--;
if(num > -1 && num < @N * @N && @array[num] is true)
@array[num] = false
return yes
else
return no
# SudokuLogic: oggetto che memorizza e crea la griglia di gioco
# N: dimensione di una sottomatrice
# lev: livello (facile 1, medio 2, difficile 3, molto difficile 4)
class @SudokuLogic
constructor: (@N, @lev) ->
@grid = new Array(@N * @N * @N * @N) #(NxN)^2 caselle del sudoku
NPERM = @N * 14 # numero di permutazioni
# Da "http://en.wikipedia.org/wiki/Sudoku_solving_algorithms"
#
# Le griglie vuote possono essere risolte molto rapidamente.
#
# final int n = 3;
# final int[][] field = new int[n*n][n*n];
# for (int i = 0; i < n*n; i++)
# for (int j = 0; j < n*n; j++)
# field[i][j] = (i*n + i/n + j) % (n*n) + 1;
#
# Producendo il seguente Sudoku 9x9:
# +-----------------------+
# | 1 2 3 | 4 5 6 | 7 8 9 |
# | 4 5 6 | 7 8 9 | 1 2 3 |
# | 7 8 9 | 1 2 3 | 4 5 6 |
# |-------+-------+-------|
# | 2 3 4 | 5 6 7 | 8 9 1 |
# | 5 6 7 | 8 9 1 | 2 3 4 |
# | 8 9 1 | 2 3 4 | 5 6 7 |
# |-------+-------+-------|
# | 3 4 5 | 6 7 8 | 9 1 2 |
# | 6 7 8 | 9 1 2 | 3 4 5 |
# | 9 1 2 | 3 4 5 | 6 7 8 |
# +-----------------------+
for row in [0 ... @N * @N]
for col in [0 ... @N * @N]
@grid[row * @N * @N + col] = (row * @N + Math.floor(row / @N) + col) % (@N * @N) + 1
# Per generare un sudoku casuale effettuo NPERM permutazioni
# scambio tra loro coppie di numeri ( p1 e p2 )
for i in [0 ... NPERM]
p1 = Math.ceil(Math.random() * @N * @N)
while yes
p2 = Math.ceil(Math.random() * @N * @N)
break unless p1 is p2
for row in [0 ... @N * @N]
for col in [0 ... @N * @N]
if @grid[row * @N * @N + col] is p1
@grid[row * @N * @N + col] = p2
else if @grid[row * @N * @N + col] is p2
@grid[row * @N * @N + col] = p1
# scambio tra loro coppie di colonne con uguale indice in sottomatrici NxN
# nb: non posso effettuare permutazioni casuali tra righe con uguale
# indice in sottomatrici NxN poiche' avendo gia' permutato le colonne
# dovrei valutare ad ogni scambio i vincoli posti dalle regole
# su ciascuna sottomatrice... Non mi pare il caso
for i in [0 ... NPERM]
p1 = Math.floor(Math.random() * @N)
p2 = Math.floor(Math.random() * @N)
for row in [0 ... @N * @N]
# scambio la (i % @N)-esima colonna tra p1 e p2
tmp = @grid[row * @N * @N + (p1 * @N + i % @N)]
@grid[row * @N * @N + (p1 * @N + i % @N)] = @grid[row * @N * @N + (p2 * @N + i % @N)]
@grid[row * @N * @N + (p2 * @N + i % @N)] = tmp
# scambio coppie di colonne all'interno di ciascuna sottomatrice NxN
for i in [0 ... NPERM]
# scelgo le due colonne p1 e p2 (N col. per sottomatrice)
p1 = Math.floor(Math.random() * @N)
p2 = Math.floor(Math.random() * @N)
for row in [0 ... @N * @N]
tmp = @grid[row * @N * @N + (i % @N * @N + p1)]
@grid[row * @N * @N + (i % @N * @N + p1)] = @grid[row * @N * @N + (i % @N * @N + p2)]
@grid[row * @N * @N + (i % @N * @N + p2)] = tmp
# scambio coppie di righe all'interno di ciascuna sottomatrice NxN
for i in [0 ... NPERM]
# scelgo le due righe p1 e p2 (N righe per sottomatrice)
p1 = Math.floor(Math.random() * @N)
p2 = Math.floor(Math.random() * @N)
for col in [0 ... @N * @N]
tmp = @grid[(i % @N * @N + p1) * @N * @N + col]
@grid[(i % @N * @N + p1) * @N * @N + col] = @grid[(i % @N * @N + p2) * @N * @N + col]
@grid[(i % @N * @N + p2) * @N * @N + col] = tmp
@lgrid = @grid.slice 0 # griglia con n° givens (in base al livello e alla dimensione)
# All'aumentare della dimensione della griglia la generazione del livello
# va in un loop infinito e non riesce a rimuovere numeri.
# Il numero di givens percentuali necessari alla risoluzione deve crescere
# all'aumentare della dimensione.
givens = @N * @N * @N * @N
givens -= Math.floor(@N * @N * @lev)
# Garantisco l'unicita' della soluzione del Sudoku
# garantendo che per ogni passo, la cella che vado ad
# eliminare ammetta un unico valore in base a quelle date
while givens < @N * @N * @N * @N
# scelgo una cella che non sia gia' stata eliminata
while yes
cell = Math.floor(Math.random() * @N * @N * @N * @N)
break if Number.isFinite(@lgrid[cell])
# sostituisco il valore numerico con l'oggetto Allow
@lgrid[cell] = new Allow @N
# calcolo le coordinate su una ipotetica griglia bidimensionale
row = Math.floor(cell / (@N * @N))
col = cell % (@N * @N)
# Elimino dai valori possibili quelli determinati nella
for k in [0 ... @N * @N]
# 1: verticale
@lgrid[cell].minus @lgrid[row * @N * @N + k] if Number.isFinite(@lgrid[row * @N * @N + k])
# 2: orizzontale
@lgrid[cell].minus @lgrid[k * @N * @N + col] if Number.isFinite(@lgrid[k * @N * @N + col])
# 3: sottomatrice
sr = Math.floor(row / @N) + Math.floor(k / @N)
sc = Math.floor(col / @N) + (k % @N)
@lgrid[cell].minus @lgrid[sr * @N * @N + sc] if Number.isFinite(@lgrid[sr * @N * @N + sc])
# ripristino il valore se ho piu' di una soluzione
@lgrid[cell] = @grid[cell] if @lgrid[cell].length() <= 1
givens++
return this
getComplete: (i) ->
return @grid[i]
getUncomplete: (i) ->
return ' ' unless Number.isFinite(@lgrid[i])
return @lgrid[i]
window.generate = () ->
difficulty = parseInt(document.getElementById('difficulty').value, 10)
dimension = parseInt(document.getElementById('dimension').value, 10)
document.getElementById('sudoku').innerHTML = ''
document.getElementById('backtrack').innerHTML = ''
window.sudoku = new SudokuLogic dimension, difficulty
for row in [0 ... dimension * dimension]
x = document.createElement 'div'
x.className = 'columns'
for col in [0 ... dimension * dimension]
y = document.createElement 'div'
y.className = 'column'
p = document.createElement 'p'
p.innerHTML = window.sudoku.getComplete(row * dimension * dimension + col)
y.appendChild p
x.appendChild y
document.getElementById('sudoku').appendChild x
for row in [0 ... dimension * dimension]
x = document.createElement 'div'
x.className = 'columns'
for col in [0 ... dimension * dimension]
y = document.createElement 'div'
y.className = 'column'
p = document.createElement 'p'
p.innerHTML = window.sudoku.getUncomplete(row * dimension * dimension + col)
y.appendChild p
x.appendChild y
document.getElementById('backtrack').appendChild x
return