Extreme Enthusiasm

Summary: last meeting of the Milano XP UG was about TTDing a program to solve Sudoku games. Pretty good fun.

Non ho mai avuto la pazienza per risolvere i sudoku. Essendo pigro, scriverò un programma per risolverli…

L’ultimo meeting del Milano XP User Group ha avuto come tema “risolviamo il Sudoku con TDD”. Il problema è: dato un sudoku, scrivi un programma che per ogni cella mi dice quali sono i numeri che posso legalmente scriverci dentro.

Numeri proibiti

In coppia con l’ottimo Roberto Valenti abbiamo affrontato il problema in Ruby. Abbiamo cominciato decidendo arbitrariamente di rappresentare il tabellone con un singolo array di interi. E’ la rappresentazione più semplice, e fino a quando non risulterà inadeguata non c’è bisogno di usarne una più complicata. YAGNI!

TEST_BOARD = [
  0,   1,  2,  3,  4,  5,  6,  7,  8, 
  9,  10, 11, 12, 13, 14, 15, 16, 17, 
  18, 19, 20, 21, 22, 23, 24, 25, 26, 
  27, 28, 29, 30, 31, 32, 33, 34, 35, 
  36, 37, 38, 39, 40, 41, 42, 43, 44, 
  45, 46, 47, 48, 49, 50, 51, 52, 53, 
  54, 55, 56, 57, 58, 59, 60, 61, 62, 
  63, 64, 65, 66, 67, 68, 69, 70, 71, 
  72, 73, 74, 75, 76, 77, 78, 79, 80, 
]

(Questa tabella di test è stata generata con un semplice programma.)

Da qualche parte bisogna iniziare. Abbiamo deciso di iniziare sviluppando metodi per estrarre righe, colonne e quadranti dalla tabella.

def test_row_col
  assert_equal [18, 19, 20, 21, 22, 23, 24, 25, 26], row(TEST_BOARD, 2)
  assert_equal [1, 10, 19, 28, 37, 46, 55, 64, 73],  col(TEST_BOARD, 1)
  assert_equal [27, 28, 29, 36, 37, 38, 45, 46, 47], quad(TEST_BOARD, 4, 1)
end

Da notare solo che quad(board, r, c) restituisce il quadrante dentro cui cade r, c. Quindi quad(board, 0, 0) sarà uguale a quad(board, 2, 2) perché entrambi restituiscono il primo quadrante.

A questo punto il problema è già quasi risolto. È più facile ottenere prima i numeri proibiti. Prima di tutto, se il tabellone è tutto vuoto, non ci sono vincoli.

# rappresentiamo le caselle vuote con 0
EMPTY_BOARD = Array.new(81, 0)
def test_forbidden_numbers_on_empty_board
  assert_equal [], forbidden_numbers(EMPTY_BOARD, 4, 4)
end

e la soluzione è facile:

def forbidden_numbers(board, r, c)
  []
end

Poi testiamo che vengano considerati proibiti i numeri che appaiono nel quadrante. Inputiamo un sudoku diagonale giusto per testare questo:

DIAG_BOARD = [
  1,0,0,0,0,0,0,0,0,
  0,2,0,0,0,0,0,0,0,
  0,0,3,0,0,0,0,0,0,
  0,0,0,4,0,0,0,0,0,
  0,0,0,0,5,0,0,0,0,
  0,0,0,0,0,6,0,0,0,
  0,0,0,0,0,0,7,0,0,
  0,0,0,0,0,0,0,8,0,
  0,0,0,0,0,0,0,0,9,
]
def test_forbidden_numbers_on_quadrant
  assert_equal [1,2,3], forbidden_numbers(DIAG_BOARD, 0, 1)
  assert_equal [7,8,9], forbidden_numbers(DIAG_BOARD, 8, 7)
end

e modifichiamo di conseguenza la funzione

def forbidden_numbers(board, r, c)
  quad(board, r, c).reject {|x| 0 == x}
end

Ora vogliamo tenere conto anche dei numeri che stanno sulle colonne

def test_forbidden_numbers_on_columns
  assert_equal [1], forbidden_numbers(DIAG_BOARD, 8, 0)
  assert_equal [6], forbidden_numbers(DIAG_BOARD, 0, 5)
end 

E fin qui è facile

def forbidden_numbers(board, r, c)
  result = quad(board, r, c) + col(board, c)
  result.reject {|x| 0 == x}
end

E così via per le righe

def forbidden_numbers(board, r, c)
  result = quad(board, r, c) + col(board, c) + row(board, r)
  result.reject {|x| 0 == x}
end

Ora, è facile prevedere problemi nel caso in cui il tabellone non è una diagonale: rischiamo di avere numeri duplicati, e comunque non nell’ordine crescente che i nostri test si aspettano. Scriviamo un test che espone un problema, e lo risolviamo in stile Unix, con sort e uniq

def forbidden_numbers(board, r, c)
  result = quad(board, r, c) + col(board, c) + row(board, r)
  result = result.reject {|x| 0 == x}
  result.sort
  result.uniq
end

I numeri permessi, a questo punto, sono semplicemente il complemento di quelli proibiti.

def possible_numbers(board, r, c)
  complement(forbidden_numbers(board, r, c))
end

def complement(ar)
  universe = [1,2,3,4,5,6,7,8,9]
  universe.reject {|x| ar.member?(x) }
end  

Espiazione

Avrai notato che fino ad ora abbiamo lavorato in maniera molto poco object-oriented. Poco male! Il punto è risolvere il problema nella maniera più semplice possibile. Però a questo punto il nostro codice comincia ad avere parecchie “funzioni” che se ne stanno appese nel vuoto. E non mi piace il fatto che in parecchi punti dobbiamo convertire le coordinate “lineari” della nostra lista in coordinate quadrate (r,c).

Decidiamo di rifattorizzare il codice per nascondere l’implementazione della tabella. Creiamo una classe Board inizializzata da un array

class Board
  def initialize(list)
    @list = list.dup
  end
end

e passiamo 10 minuti a convertire tutti i nostri test, spostando dentro alla classe i metodi che prima fluttuavano nel vuoto. Sempre però un test alla volta, spostando solo i metodi necessari, e sempre rieseguendo i test. Alla fine abbiamo questi test

class TestNameOfTestCases < Test::Unit::TestCase  
  def test_board_at
    b = Board.new(SOLVED_BOARD)
    assert_equal b.at(0, 0), 8
    assert_equal b.at(2, 3), 1
  end

  def test_set
    b = Board.new(SOLVED_BOARD)
    b.set(2,3,255)
    assert_equal 255, b.at(2, 3)
  end
  
  def test_board_find_hole
    b = Board.new(SOLVED_BOARD)
    assert_equal nil, b.find_hole
    b.set(1, 2, 0)
    assert_equal [1, 2], b.find_hole
  end

  def test_row_col
    b = Board.new(TEST_BOARD)
    assert_equal [18, 19, 20, 21, 22, 23, 24, 25, 26], b.row(2)
    assert_equal [1, 10, 19, 28, 37, 46, 55, 64, 73],  b.col(1)
    assert_equal [0, 1, 2, 9, 10, 11, 18, 19, 20], b.quad(0, 0)
    assert_equal [0, 1, 2, 9, 10, 11, 18, 19, 20], b.quad(1, 1)
    assert_equal [0, 1, 2, 9, 10, 11, 18, 19, 20], b.quad(2, 2)
    assert_equal [27, 28, 29, 36, 37, 38, 45, 46, 47], b.quad(4, 1)
    assert_equal [30, 31, 32, 39, 40, 41, 48, 49, 50], b.quad(5, 5)
  end
  
  def test_forbidden_numbers_on_quadrant
    assert_equal [], Board.new(EMPTY_BOARD).forbidden_numbers(4, 4)
    assert_equal [1,2,3], Board.new(DIAG_BOARD).forbidden_numbers(0, 1)
  end
  
  def test_forbidden_numbers_on_quad_and_row
    b = Board.new(DIAG_BOARD)
    b.set(0, 4, 4)
    assert_equal [1,2,3,4], b.forbidden_numbers(0, 1)
  end

  def test_forbidden_numbers_on_quad_and_col
    b = Board.new(DIAG_BOARD)
    b.set(4, 0, 5)
    assert_equal [1,2,3,5], b.forbidden_numbers(1, 0)
  end
  
  def test_possible_numbers_on_problem
    b = Board.new(PROBLEM)
    assert_equal [3], b.possible_numbers(0, 1)
  end

  def test_complement
    assert_equal [], Board.complement([1,2,3,4,5,6,7,8,9])
    assert_equal [9], Board.complement([1,2,3,4,5,6,7,8])
    assert_equal [1,4,9], Board.complement([2,3,5,6,7,8])
  end

e questo codice

class Board
  def initialize(list=nil)
    @list = list.dup
  end
  
  def at(r, c)
    @list[r*9 + c] 
  end
  
  def set(r, c, val)
    @list[r*9 + c] = val
  end

  def forbidden_numbers(r, c)
    result = quad(r, c)
    result += row(r)
    result += col(c)
    result = result.reject { |n| n == 0 }
    result.sort
    result.uniq
  end

  def possible_numbers(r, c)
    Board.complement(forbidden_numbers(r, c))
  end

  def self.complement(ar)
    universe = [1,2,3,4,5,6,7,8,9]
    universe.reject {|x| ar.member?(x) }
  end

  def quad(r, c)
    result = []
    for rr in ((r/3)*3...(r/3)*3+3)
      for cc in ((c/3)*3...(c/3)*3+3)
        result << at(rr, cc)
      end
    end
    result
  end
  
  def row(n)
    @list[n*9...(n+1)*9]
  end

  def col(c)
    (0...9).map {|r| at(r, c)}
  end
  
  def list
    @list
  end
  
private
  def linear_to_r_c(index)
    [index / 9, index % 9]
  end
end

Facciamo un test di accettazione: prendiamo un sudoku risolto, e a turno cancelliamo un elemento. La funzione possible_numbers deve restituire il numero appena tolto.

  def test_solved_board
    b = Board.new(SOLVED_BOARD)
    for r in (0...9)
      for c in (0...9)
        element = b.at(r, c)
        b.set(r, c, 0)
        assert_equal [element], b.possible_numbers(r, c)
        b.set(r, c, element)
      end
    end
  end  

Funziona! E' vero che potremmo fare dei test più accurati, ma sono abbastanza confidente che la nostra soluzione sia corretta. Comunque, se non fossimo al pub alle 8 di sera probabilmente mi metterei il berretto da tester e farei qualche test in più.

Una volta si chiamava A.I.

Avevamo ancora un filo di energia, così abbiamo deciso di continuare scrivendo un metodo solve(board) che restituisca un sudoku completato.

In generale, questo tipo di problemi si risolvono per mezzo di ricerca. Ovvero, non c'è un algoritmo che mi possa dire in un colpo solo qual'è il numero da mettere. Quasi tutti i puzzle ricadono in questo schema: il problema delle N regine, il problema del 15, il cubo di Rubik...

Abbiamo uno stato iniziale; per ogni stato abbiamo un certo numero di mosse a disposizione. Risulta un albero di stati. Le foglie di questo albero sono stati in cui il gioco è risolto (yuppi!), oppure stati in cui il gioco non è risolto e non ci sono altre mosse possibili (buuu).

Il problema allora è esplorare l'albero degli stati in maniera da trovare il prima possibile un nodo-soluzione. Ci sono due strategie di base, che si applicano a tutti i puzzle. La strategia breadth-first: partendo dalla radice, considero tutti i nodi raggiungibili. Ho trovato la soluzione? Se no, per ogni nodo trovato, considero tutti i suoi nodi raggiungibili. Cioè, esamino tutti i nodi di livello 2. Vado avanti così, esaminando tutti i nodi di livello n fino a che non trovo una soluzione.

Il vantaggio del breadth-first è che trova di sicuro la soluzione più breve. Lo svantaggio è che rischio di metterci moltissimo tempo a trovarla.

L'altra strategia agnostica è depth-first: dalla radice scelgo la prima mossa, poi la prima mossa, e sempre la prima mossa fino a quando non raggiungo una foglia. Se è un fallimento, torno indietro di *un* passo e esamino la seconda mossa. Se esaurisco tutte le mosse possibili a quel livello, torno indietro di un altro passo e considero la seconda mossa da lì.

Lo svantaggio del depth-first è che non è garantito che possa mai trovare una soluzione. Nel caso del sudoku, però, questo non è un problema perché la profondità dell'albero è sempre limitata dal numero di caselle vuote da riempire.

E' facile implementare una ricerca depth-first, usando una funzione ricorsiva.

def solve(prob)
  return prob if prob.solved?
  for move in prob.possible_moves
    try = solve(prob.apply(move))
    # if solved, stop here
    return try if try
  end
  # no more moves
  return false
end

Lo stack implicito nella valutazione della funzione ricorsiva mi tiene traccia di a che punto sono nella mia esplorazione dell'albero.

Risolviamo un gioco completo

Con questo schema in mente, scriviamo il nostro primo test. Se il problema è risolto, deve restituire la tabella risolta

def test_solve
  assert_equal SOLVED_BOARD, solve(Board.new(SOLVED_BOARD))
end

E fin qui è facile. Poi proviamo a togliere una posizione dal gioco completato, e ci aspettiamo che ritrovi di nuovo la soluzione

def test_solve
  b = Board.new(SOLVED_BOARD)
  assert_equal SOLVED_BOARD, solve(b)

  b.set(0,0,0) # metto 0 alla posizione 0,0
  assert_equal SOLVED_BOARD, solve(b)
end  

Anche questo si risolve facilmente. Ci serve una funzione che trovi il primo "buco". Se il buco non c'è, assumiamo che il gioco sia risolto

class Board
  def find_hole
    @list.each_with_index { |e, index|
      return linear_to_r_c(index) if e == 0
    }
    nil
  end
end

def solve(board)
  if !board.find_hole 
    return board.list
  end
  r, c = board.find_hole
  possibles = board.possible_numbers(r, c)
  board.set(r, c, possibles.first)
end

Questo però assume che ci sia per forza un numero possibile. Cosa succede se siamo a un nodo di fallimento? Lo simuliamo passandogli un sudoku irrisolvibile

def test_failure_node
  b = Board.new(SOLVED_BOARD)
  b.set(0, 1, 8 )  # mossa non valida! ma non importa
  b.set(0, 0, 0)   # questo buco ora è irrisolvibile
  assert_equal false, solve(b)
end

def solve(board)
  if !board.find_hole 
    return board.list
  end
  r, c = board.find_hole
  possibles = board.possible_numbers(r, c)
  return false if !possibles
  board.set(r, c, possibles.first)
end

A questo punto facciamo emergere la nostra soluzione presentando problemi sempre più difficili. In realtà essendo un po' stufi abbiamo preso una scorciatoia: abbiamo preso un problema da risolvere completo, e abbiamo implementato direttamente la soluzione ricorsiva. Con qualche calcio l'abbiamo fatta funzionare:

PROBLEM = [
  1, 0, 2, 0, 0, 0, 7, 0, 0,
  0, 4, 7, 0, 2, 1, 3, 0, 0,
  0, 8, 0, 7, 0, 3, 0, 1, 0,
  4, 6, 0, 1, 0, 0, 0, 8, 0,
  0, 0, 0, 2, 6, 4, 0, 0, 0,
  0, 5, 0, 0, 0, 9, 0, 6, 4,
  0, 9, 0, 5, 0, 7, 0, 2, 0,
  0, 0, 1, 3, 4, 0, 9, 7, 0,
  0, 0, 6, 0, 0, 0, 8, 0, 3,
]
def test_solution
  sol = sove(PROBLEM)
  assert sol, "non ha risolto il problema :-("
  do_print sol
end  

def solve(board)
  if !board.find_hole 
    return board.list
  end
  r, c = board.find_hole
  possibles = board.possible_numbers(r, c)
  for p in possibles
    board.set(r, c, p)
    solved = solve(Board.new(board.list))
    return solved if solved
  end
  return false
end

Questo problema viene risolto in 0.2 secondi sul mio Mac G4. Un problema più difficile, a livello evil da www.websudoku.com, viene risolto in 10 secondi. Sono molto soddisfatto.

Penso che la performance si possa migliorare nettamente, per il caso difficile, modificando semplicemente il metodo find_hole. Se invece di restituire il primo buco restituisse il buco che è maggiormente vincolato, immagino che taglieremmo di molto il numero di tentativi falliti. E questo, caro lettore, resta come esercizio...

This entry was posted on 1 September 2006 at 13:15 and is filed under Agile. You can follow any responses to this entry through the RSS 2.0 feed. You can leave a response, or trackback from your own site.