Wie Elemente (Stücke von Tetris) rekursiv zu organisieren

Question

Ich lerne Rekursion, aber ich brauche eine Referenz, wie man den Algorithmus zu starten. Ich muss Blöcke organisieren, um alle Teile zu verwenden, mit der maximalen möglichen Füllung des Brettes. Dank an alle.

Answer 1

Hier ist eine ziemlich naive Implementierung dieses Algorithmus, um Ihnen den Einstieg zu erleichtern.

Es ist auf der Suche nach einer perfekten Lösung (wo die Platte vollständig gefüllt ist) und wird beendet, sobald es einen findet. Dies funktioniert wie erwartet für Ihr Beispiel-Board, aber es kann für immer mit anderen Boards laufen, die keine einfache perfekte Lösung oder keine perfekte Lösung haben.

Ein besserer Algorithmus würde:

• Suchen Sie die beste Lösung für jede Board (nicht nur die perfekte one)
• Verwenden mehr Heuristik die Suche

Die einzige Verfeinerung zu beschleunigen Bei diesem Algorithmus wird eine Hash-Tabelle verwendet, um zu vermeiden, dass die gleiche Karte zweimal besucht wird, wenn zwei verschiedene Zugkombinationen die gleiche Konfiguration erzeugen.

Jede Zeile der Platine wird als Byte dargestellt und jedes Stück wird als 2x2 Bit dargestellt.

var b = [ 
 
     // initial board 
 
     0b00000000, 
 
     0b00000000, 
 
     0b00000100, 
 
     0b00000000, 
 
     0b00000000, 
 
     0b00000000, 
 
     0b00000000, 
 
     0b00000000 
 
    ], 
 
    piece = [ 
 
     // bitmasks of pieces as [ top_bitmask, bottom_bitmask ] 
 
     [ 0b11, 0b01 ], [ 0b11, 0b10 ], [ 0b01, 0b11 ], [ 0b10, 0b11 ] 
 
    ], 
 
    // hash table of visited boards 
 
    hash = {}, 
 
    // statistics 
 
    node = 0, hit = 0; 
 

 
function solve(sol) { 
 
    var x, y, p, s; 
 
    
 
    // compute hexadecimal key representing the current board 
 
    var key = 
 
     ((b[0] | (b[1] << 8) | (b[2] << 16) | (b[3] << 24)) >>> 0).toString(16) + '-' + 
 
     ((b[4] | (b[5] << 8) | (b[6] << 16) | (b[7] << 24)) >>> 0).toString(16); 
 

 
    node++; 
 
    
 
    if(hash[key]) { 
 
    // abort immediately if this board was already visited 
 
    hit++; 
 
    return false; 
 
    } 
 
    if(key == 'ffffffff-ffffffff') { 
 
    // return the current solution if the board is entirely filled 
 
    return sol; 
 
    } 
 
    
 
    // save board in hash table 
 
    hash[key] = true; 
 

 
    // for each position and each type of piece ... 
 
    for(y = 0; y < 7; y++) { 
 
    for(x = 0; x < 7; x++) { 
 
     for(p = 0; p < 4; p++) { 
 
     // ... see if we can insert this piece at this position 
 
     if(!(b[y] & (piece[p][0] << x)) && !(b[y + 1] & (piece[p][1] << x))) { 
 
      // make this move 
 
      b[y]  ^= piece[p][0] << x; 
 
      b[y + 1] ^= piece[p][1] << x; 
 

 
      // add this move to the solution and process recursive call 
 
      s = solve(sol.concat(x, y, p)); 
 
      
 
      // unmake this move 
 
      b[y]  ^= piece[p][0] << x; 
 
      b[y + 1] ^= piece[p][1] << x; 
 

 
      // if we have a solution, return it 
 
      if(s) { 
 
      return s; 
 
      } 
 
     } 
 
     } 
 
    } 
 
    } 
 
    return false; 
 
} 
 

 
function display(sol) { 
 
    var n, x, y, html = ''; 
 

 
    for(n = 0; n < 64; n++) { 
 
    html += '<div class="cell"></div>'; 
 
    } 
 
    $('#container').html(html); 
 
    
 
    for(n = 0; n < sol.length; n += 3) { 
 
    for(y = 0; y < 2; y++) { 
 
     for(x = 0; x < 2; x++) { 
 
     if(piece[sol[n + 2]][y] & (1 << x)) { 
 
      $('.cell').eq(7 - sol[n] - x + (sol[n + 1] + y) * 8) 
 
      .addClass('c' + sol[n + 2]); 
 
     } 
 
     } 
 
    } 
 
    } 
 
} 
 

 
setTimeout(function() { 
 
    display(solve([])); 
 
    console.log(node + ' nodes visited'); 
 
    console.log(hit + ' hash table hits'); 
 
}, 500);

#container { width:160px; height:160px } 
 
.cell { width:19px; height:19px; margin:1px 1px 0 0; background-color:#777; float:left } 
 
.c0 { background-color:#fb4 } 
 
.c1 { background-color:#f8f } 
 
.c2 { background-color:#4bf } 
 
.c3 { background-color:#4d8 }

<script src="https://ajax.googleapis.com/ajax/libs/jquery/2.1.1/jquery.min.js"></script> 
 
<div id="container">Searching...</div>

Answer 2

Rekursion hat zwei Hauptideen, die erste ist, dass bei jedem Schritt das Problem (in diesem Fall also das Brett) Sie sind die Lösung des Problems sollte kleiner. Die zweite wichtige Idee ist, dass jeder Schritt derselbe ist.

In diesem Fall wäre es also, dass Sie ein Stück platzieren und dann die Funktion erneut auf dem Board aufrufen, wobei das platzierte Stück entfernt wird. Lass uns ein bisschen mehr tauchen.

1. Jedes Mal, wenn Sie ein Stück platzieren und die Funktion aufrufen, wird die Anzahl der Positionen reduziert, an denen Sie ein Stück platzieren können.
2. Jedes Mal, wenn Sie die Funktion erneut aufrufen, versuchen Sie immer noch, Kacheln zu platzieren. Das Problem bleibt also konstant, obwohl der Problembereich kleiner ist.

Hoffe, das hilft!