4

I'm trying to animate a solution to the latin-square-problem in javascript.

To do so, I wrote the recursive backtracking algorithm below.

Solving the problem is initiated by calling search(0,0) and it works just fine, displaying a solution after calculating. But I want it to show an animation on it's progress, in terms of redrawing the whole canvas, after changing the colour of one square.

I tried to incoorporate many of the solutions to similar problems, found on stackoverflow or in tutorials about canvas gameloops. Neither of them worked for me, so I'm presenting the javascript code as close as possible to my pseudo-code algorithm (without any setTimeout's or requestAnimationFrame's)

Here's a working jsfiddle containing all the code. 

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 回答
0

您可以包装对主计算函数的调用以使其显示，然后延迟对实际计算函数的调用：

function search(i,j) {
    drawLatinSquare();
    setTimeout(function() { _search(i,j)} , 15);
}

function _search(i, j){
  //... your real search function

问题是有太多的组合无法看到它们全部用于“大”n：你应该选择你想要展示的东西我害怕。

另外，如果我是您，我会进行第一次检查以查看迭代次数，以便您可以显示进度条或类似内容。

https://jsfiddle.net/ezstfj9f/4/

于 2015-04-12T15:32:33.100 回答