如何递归地组织元素（俄罗斯方块的碎片）

Question

我正在学习递归，但我需要有关如何开始制作算法的参考资料。我需要组织方块以使用所有棋子，并尽可能多地填充棋盘。感谢大家。

Answer 1

递归有两个主要思想，第一个是在每一步你正在解决的问题（在这种情况下是板）应该变小。第二个重要的想法是每一步都是相同的。

所以在这种情况下，您将放置一个棋子，然后在移除放置的棋子的情况下再次在棋盘上调用该函数。让我们更深入地研究它们。

每放置一个棋子并调用该函数，您可以放置棋子的位置数就会减少。
每次您再次调用该函数时，您仍然只是在尝试放置瓷砖。因此，尽管问题 space 变小了，但问题仍然存在。

希望对您有所帮助！

Answer 2

下面是该算法的一个相当简单的实现，可帮助您入门。

它正在寻找一个完美的解决方案（电路板完全填满），一旦找到就会退出。对于您的示例板，这将按预期工作，但它可能运行永远与其他没有简单完美解决方案或根本没有完美解决方案的板一起使用。

更好的算法是：

寻找适合任何电路板的最佳解决方案（不仅仅是完美的解决方案）
使用更多的启发式方法来加快搜索速度

此算法的唯一改进是使用哈希 table 以避免在两个不同的移动组合产生相同配置时两次访问同一棋盘。

棋盘的每一行都表示为一个字节，每一块都表示为 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>

如何递归地组织元素（俄罗斯方块的碎片）

How to organize elements (pieces of Tetris) recursively

algorithm

recursion

jquery

recursive-backtracking