Flying memes

Eravamo rimasti al seguente quesito: “Come implementiamo l’insieme di costrizioni che abbiamo evinto in modo da risolvere il problema delle 8 regine con i Dancing Links ?”

Guardiamo insieme il codice di ‘dancing_links_queens.rb‘:

def initialize()
    labels = (1..42).to_a
    @dla = DancingLinksArena.new(labels,[false]*16 + [true]*26)
    given_list = []
    row_data = []

    8.times do |x|
      8.times do |y|
        row_data[0] = x+1
        row_data[1] = y+1 + 8
        row_data <<  ((y+1) - (x+1)) + 7  + 16  unless [-7,7].include?(y - x)
        row_data <<  (x + y + 2) - 2 + 13 + 16  unless [0,14].include?(x + y)
        new_row = @dla.add_initial_row(row_data)
        row_data = []
      end
    end
  end

Nella prima riga creo un array di 42 elementi ( 8 righe + 8 colonne + 13 diagonali da sx a dx + 13 diagonali da dx a sx ), da notare che considero solo 13 diagonali per direzione ( e non 15 ) perchè 2 contengono un solo elemento. Ognuno di questi 42 elementi diverrà una colonna nella matrice DLX.

Nella seconda riga creo un oggetto ‘Dancing Links’ al quale passo l’array di etichette e un array di 16 ‘true’ e 26 ‘false’, questo perchè le prime 16 colonne sono primarie (cioè dovranno contenere esattamente un 1) mentre le ultime 26 sono secondarie (cioè possono contenere o 0 o 1 elemento). Questa scelta è stata dettata dal fatto che mentre per ogni riga e ogni colonna della scacchiera dovrà necessariamente essere presente una regina, lo stesso non è valido per ogni diagonale ( abbiamo solo 8 regine e 26 diagonali… ).

Ora mi resta solo da impostare per ognuna delle 64 caselle della scacchiera le relative costrizioni ed aggiungerle alla DLA, nel dettaglio per ogni casella devo specificare il ‘nome’ (da 1 a 42) dei label corrispondenti alla costrazione che definisce tale casella; facciamo un esempio, per la casella 1-1 questi sono i label interessati:

• il label 1 che corrisponde alla riga 1
• il label 9 che corrisponde alla colonna 1
• il label 36 che identifica la diagonale che interessa la casella 1-1

Potete visionare e testare l’esempio completo sul mio account di github

Tags: 8 regine, Dancing Links, Ruby, ruby-dlx