4

javascript でラテン方陣問題の解決策をアニメーション化しようとしています。

そのために、再帰的なバックトラッキング アルゴリズムを以下に記述しました。

問題の解決は呼び出しによって開始され、問題search(0,0)なく機能し、計算後に解決策が表示されます。しかし、1つの正方形の色を変更した後、キャンバス全体を再描画するという点で、進行状況をアニメーションで表示したいと考えています。

私は、stackoverflow やキャンバス ゲームループに関するチュートリアルで見つかった、同様の問題に対する解決策の多くを取り入れようとしました。どちらもうまくいかなかったので、疑似コードアルゴリズムにできるだけ近いJavaScriptコードを提示しています（setTimeout「」またはrequestAnimationFrame「」なし）

これは、すべてのコードを含む 動作中の jsfiddleです。

function search(i, j){
    if (latinSquare[i][j] != -1){
        //this square is predefined, skip it
        searchNext(i, j);
    } else {
        var colour = latinSquare[i][j];
        while(colour < n-1){
            colour = colour + 1;
            latinSquare[i][j] = colour;
            //redraw the whole canvas
            drawLatinSquare();
            //check if curent constellation is legal
            var legal = true;
            for (var k = 0; k < n; k++){
                if (k != i){
                    if (latinSquare[k][j] == colour){
                        legal = false;
                        break;
                    }
                }
                if (k != j){
                    if (latinSquare[i][k] == colour){
                        legal = false;
                        break;
                    }
                }
            }
            if (legal){
                searchNext(i, j);
                if (window.found) return;
            }
        }
        latinSquare[i][j] = -1;
    }   
}

function searchNext(i, j){
    if (i < n-1){
        //proceed horizontally
        search(i+1, j);
    } else {
        if (j < n-1){
            //proceed in the next row
            search(0, j+1);
        } else {
            //we're done
            window.found = true;
        }
    }
}
4

2 に答える 2

1

このソリューションでは、配列の各反復を保持するために配列が作成されlatinSquareます。タイムアウト間隔は、配列の長さの関数です。

この方法の利点は、すべての計算が完了するまでアニメーションが開始されないため、非常に高速に実行されることです (解が見つかった場合)。

var lsa= [];

function drawLatinSquare() {
  var l= [];
  for(var i = 0 ; i < latinSquare.length ; i++) {
    l.push(latinSquare[i].slice());
  }      
  lsa.push(l);
  setTimeout(function() {
    var ls= lsa.shift();
    ctx.clearRect ( 0 , 0 , canvas.width, canvas.height );
    ctx.lineWidth= 1;
    //draw the grid
    for (var i = 0; i < n + 1; i++){
      ctx.beginPath();
      ctx.moveTo(0,i*21 + 0.5);
      ctx.lineTo((n*(21)+1),i*21 + 0.5);
      ctx.stroke();
    }
    for (var j = 0; j < n + 1; j++){
      ctx.beginPath();
      ctx.moveTo(j*21 + 0.5,0);
      ctx.lineTo(j*21 + 0.5,(n*(21)+1));
      ctx.stroke();
    }
    //draw the squares
    for (var i = 0; i < n; i++){
      for (var j = 0; j < n; j++){
        colour = ls[i][j];
        if (colour == -1){
          colour = "#FFFFFF";
        } else {
          colour = colours[colour];
        }
        ctx.fillStyle = colour;
        ctx.fillRect((i*21)+1.5,(j*21)+1.5,20,20);
      }
    }
  },10*lsa.length);
} //drawLatinSquare

フィドル

于 2015-04-12T16:16:26.627 に答える