0
재귀를 배우고 있지만 알고리즘을 만드는 방법에 대한 참조가 필요합니다. 보드 전체를 최대한으로 채워서 모든 부분을 사용하도록 블록을 구성해야합니다. 모두에게 감사드립니다.요소 (테트리스 조각) 재귀 적으로 구성하는 방법
A
답변
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>
1
재귀 첫 번째는, 두 가지 아이디어를 가지고 각 당신은 작아해야하는 문제를 해결하는 (그래서이 경우에는 보드) 문제를 단계에서. 두 번째 중요한 아이디어는 각 단계가 동일하다는 것입니다.
그래서이 경우 조각을 놓은 다음 배치 된 조각을 제거한 상태에서 보드에서 다시 함수를 호출해야합니다. 조금 더 잠수 할 수 있습니다.
- 조각을 배치하고 기능을 호출 할 때마다 조각을 배치 할 수있는 위치의 수가 줄어 듭니다.
- 다시 함수를 호출 할 때마다 여전히 타일을 배치하려고합니다. 따라서 문제 공간이 작아도 문제는 일관되게 유지됩니다.
희망이 있습니다.
@fragilewindows, 내가 때문에 심지어 개선이 질문에 제안 된 수정을 거부하는 투표를하고있어, 그것은 스택 오버플로의 기준을 충족하지 않을 것입니다. 이 질문은 사이트 자원을 요구하고 있으므로 닫아야합니다. – HPierce