Backtracking con Killer Sudoku

Question

Backtracking con Killer Sudoku

#1 da (3 voti)
#2 da (1 voti)
#3 da (0 voti)

1

Sto sviluppando un risolutore Killer Sudoku per un progetto scolastico. Ho programmato 10 strategie umane che mostrano quello che stanno facendo per essere il più educativo possibile.

In questo momento è in grado di risolvere i Killer Sudokus, ma il mio insegnante mi ha proposto di utilizzare il backtracking per risolvere ogni possibile griglia.

Ho provato per una settimana a cercare risorse generali sul backtracking o sulle risorse basate su Sudoku ... Il fatto è che con Killer Sudoku, non puoi semplicemente dire che una cella ha una soluzione senza fare affidamento sulle zone e su ciò che le cellule scritte in precedenza implicano zone e possibilità ovunque.

Quello che mi piacerebbe fare è qualcosa che applica tutte le mie strategie ogni volta che suggerisce che un numero sia più efficiente e restituisca l'unica soluzione.

Ma per applicare le strategie, abbiamo bisogno di una copia della griglia giusto? Quindi posso clonare completamente i miei oggetti usando alcuni metodi e posso applicare le mie strategie usando un altro metodo.

Quale sarebbe la struttura per questa funzione?

PS: Ho provato più volte a scrivere del codice e ogni volta che la soluzione restituita era errata. (La griglia può essere facilmente verificata per la validità)

Era qualcosa del genere:

def bt(sudoku)
  if sudoku.valid? then
    true
  else
    sudoku2 = sudoku.clone
    sudoku2.first_cell_not_solved.possibilities.each do |p|
      sudoku2.first_cell_not_solved.solution = p
    end
    sudoku2.apply_all_strategies
    if sudoku.completed?
      return sudoku.valid?
    else
      bt(sudoku2)
    end
  end
end

puzzles ruby

posta Cydonia7 07.05.2012 - 17:37

fonte

3 risposte

1

In realtà è più facile scrivere un esauriente programma di backtracking piuttosto che risolvere uno specifico puzzle del Sudoku. L'algoritmo è piuttosto semplice. Non è necessario clonare la griglia.

value[i] = 0 for i in 0..totalCells-1;
int currentCell = 0;

while (currentCell != totalCells) {
  ++value[currentCell];
  if (value[currentCell] > 9) {
    value[currentCell] = 0; // erase
    --currentCell; // backtrack
    if (currentCell < 0) throw new UnsolvableSudokuException();
  } else if (!anyConstraintViolated) {
    ++currentCell; // advance to next cell
  }
}

Potresti pensare che questo funzionerebbe a lungo, ma anche con un linguaggio più lento come Perl questo algoritmo risolve il normale Sudoku in un paio di secondi.

risposta data 08.05.2012 - 04:30

fonte

0

Un'alternativa alla clonazione sarebbe utilizzare il ricordo modello.

def bt(sudoku)
  if !sudoku.valid?
    throw Exception()
  if sudoku.completed? then
    true
  else
    memento = sudoku.dump
    sudoku.first_cell_not_solved.possibilities.each do |p|
      sudoku.first_cell_not_solved.solution = p
      sudoku.apply_all_strategies
      if sudoku.valid? and bt(sudoku)
        return true
      sudoku.restore(memento)
    end
    false
  end
end

risposta data 08.05.2012 - 11:36

fonte

Leggi altre domande sui tag puzzles ruby

L'utente non può manipolare gli elementi HTML che sono disabilitati per l'utente non autorizzato uso del tag script in diverse posizioni della pagina [chiuso]

score 3 · Accepted Answer

Dove hai sudoku2.first_cell_not_solved.set_first_possibility_as_solution , devi effettivamente eseguire il ciclo di tutte le possibilità sulla prima cella non risolta, quindi scorrere tutte le possibilità sulla seconda cella non risolte, ecc. Ogni volta che vedi se la scelta di tale possibilità produce un soluzione applicando le tue strategie. In caso contrario, annulla (cioè backtrack) quella possibilità e scegli quella successiva. Scegliendo sempre la prima possibilità, il tuo codice di esempio non esegue alcun backtracking.

Questo tipo di algoritmo a forza bruta ha il potenziale per richiedere un molto, molto tempo. Il trucco sta nel scegliere la cella giusta per andare prima. Ad esempio, la scelta di una cella con solo due possibilità produrrà probabilmente un risultato più veloce rispetto alla scelta di una cella completamente aperta. Inoltre, è probabile che tu possa risolvere gli stessi sotto-puzzle molte volte, quindi una sorta di memoizzazione di solito è molto utile.

Modifica : qualcosa del genere (perdona gli errori ruby, non conosco la lingua):

def bt(sudoku)
  if sudoku.completed? then
    return sudoku.valid?
  else
    sudoku.first_cell_not_solved.possibilities.each do |p|
      sudoku2 = sudoku.clone
      sudoku2.first_cell_not_solved.solution = p     
      sudoku2.apply_all_strategies
      if bt(sudoku2)
        sudoku = sudoku2
        true
      end
    end
  end
  false
end