要素（テトリスの一部）を再帰的に編成する方法

Question

私は再帰を学習していますが、アルゴリズムの作成を開始する方法についての参考文献が必要です。私はボードの可能な最大の充填で、すべての部分を使用するブロックを整理する必要があります。ありがとうございます。

Answer 1

ここでは、始めに役立つこのアルゴリズムのかなり単純な実装です。

完璧なソリューション（ボードが完全に埋め込まれている場所）を探していて、見つかるとすぐに終了します。これはあなたのサンプルボードに期待どおりに動作しますが、単純な完璧な解決策を持たない他のボードや完全な解決策がまったくなくても、永久に動くことがあります。

優れたアルゴリズムになります。すべてのボードに最適なソリューションのための

• ルック検索

だけ洗練をスピードアップするために（だけでなく、完璧なもの）

使用よりヒューリスティックこのアルゴリズムでは、ハッシュテーブルを使用して、2つの異なる移動の組み合わせが同じ構成を生成するときに、同じボードを2回訪問することを回避します。

ボードの各行はバイトとして表され、各部分は2x2ビットとして表されます。

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

再帰は、次の2つの主要なアイデアを持って、最初はそれぞれの問題をステップということである（ので、この場合はボード）あなたが問題を解決している小さな取得する必要があります。 2番目の重要なアイデアは、各ステップが同じであるということです。

この場合、ピースを配置し、配置されたピースを取り外した状態で再びボード上で関数を呼び出すことがあります。もう少し詳しく教えてください。

1. ピースを配置して機能を呼び出すたびに、ピースを配置できる位置の数を減らします。
2. この関数をもう一度呼び出すたびに、タイルを配置しようとしています。したがって、問題のスペースは小さくても問題は一貫しています。

希望します。