1

我正在学习递归，但我需要有关如何开始制作算法的参考。我需要组织积木来使用所有的棋子，尽可能地填满棋盘。谢谢大家。

在此处输入图像描述

4

2 回答 2

1

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

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

  1. 每次您放置一块并调用该函数时，您可以放置​​一块的位置数量都会减少。
  2. 每次再次调用该函数时，您仍然只是在尝试放置图块。因此，尽管问题空间较小，但问题仍保持一致。

希望这可以帮助！

于 2016-08-06T01:01:26.273 回答
1

这是该算法的一个相当幼稚的实现，可帮助您入门。

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

更好的算法将：

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

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

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

于 2016-08-15T16:33:11.173 回答