我可以使用 Processing 逐步绘制我的回溯吗？

Question

我想用processing写一个backtracking -8 Queens-可视化代码

所以我尝试在 setup() 中使用 noLoop() 并调用 redraw() 然后在每个更新步骤中调用 delay(100) 但它没有用。

这是我的功能。

int cellH = 38, cellW = 38, n = 8;
PImage img;
boolean [][] grid;
boolean [] visC, visMD, visSD;
boolean firstTime = true;

void drawQueen(int r, int c){
  image(img, c*cellW, r*cellH, cellW, cellH);
}

void drawGrid(){
  background(255);
  for(int r = 0 ; r < n ; ++r){
    for(int c = 0 ; c < n ; ++c){
     if((r&1) != (c&1)) fill(0);
     else  fill(255);
     rect(c*cellW, r*cellH, (c+1)*cellW, (r+1)*cellH);
   }
  }
}

void updateQueens(){
  for(int r = 0 ; r < n ; ++r)
    for(int c = 0 ; c < n ; ++c)
      if(grid[r][c] == true)
        drawQueen(r, c);
}
boolean backTrack(int r){
 if(r == n)  return true;
 else{
   for(int c = 0 ; c < n ; ++c){
     if(!visC[c] && !visMD[n+r-c] && !visSD[r+c]){
       //Do
       grid[r][c] = visC[c] = visMD[n+r-c] = visSD[r+c] = true;
       redraw();
       delay(100);
       //Recurse
       if(backTrack(r+1))  return true;
       //Undo
       grid[r][c] = visC[c] = visMD[n+r-c] = visSD[r+c] = false;
     }
   }
 }
 return false;
}

void setup(){
  size(280, 280);
  cellH = 280/n;
  cellW = 280/n;

  grid = new boolean[n][n];
  visC = new boolean[n];
  visMD = new boolean[2*n];
  visSD = new boolean[2*n];

  noLoop();
  img = loadImage("queen.png");
  backTrack(0);
}

void draw(){
  drawGrid();
  updateQueens();
}

当我运行草图时只出现最终状态。

还有其他想法吗？

Answer 1

根据 documentation:

In structuring a program, it only makes sense to call redraw() within events such as mousePressed(). This is because redraw() does not run draw() immediately (it only sets a flag that indicates an update is needed).

重绘不会导致绘制屏幕。它设置了一个需要调用 draw() 的标志，这发生在循环结束时。一个解决方案是将 draw() 重命名为 drawScreen() 并调用它而不是 redraw().

Answer 2

处理的方式是通过将 draw 函数转换为该循环的主体来模拟循环，并在 setup 函数中进行所有初始化。

为了模拟递归，你可以把它变成一个循环然后做上面的事情，通常这可以使用一个堆栈来实现，你基本上用你的替换系统的堆栈；我读了一些书（查看 this question 了解一些想法），我发现如果递归调用在函数体的末尾，则很容易将递归转换为带有堆栈的循环。

现在的问题是，你有一些代码在应该在调用 returns 之后执行的递归调用之后，但是查看它，它只是撤消对全局变量所做的更改，如果我们将这些变量视为状态的一部分，我们就可以克服这个问题（不是很有效，也不会很好地扩展，但在你的情况下它会) 所以 undo 部分将不是必需的，递归调用将是函数主体中的最后一件事（让我们暂时离开内部 for 循环）。

为此，我定义了一个名为 State 的 class，如下所示 ..

    class State {
      private final int SIZE = 8;
      private boolean grid[][], visC[], visR[], visMD[], visSD[];

      int r, c;

      State() {
        visC = new boolean[SIZE];
        visR = new boolean[SIZE];
        visMD = new boolean[2*SIZE];
        visSD = new boolean[2*SIZE];
        grid = new boolean[SIZE][SIZE];
      }

      State(State other) {
        this();
        cpyArr(other.visMD, this.visMD);
        cpyArr(other.visSD, this.visSD);
        cpyArr(other.visC, this.visC);
        cpyArr(other.visR, this.visR);

        for (int i = 0 ; i < other.grid.length ; ++i)
          for (int j = 0 ; j < other.grid[i].length ; ++j)
            this.grid[i][j] = other.grid[i][j];

        this.r = other.r;
        this.c = other.c;
      }

      void cpyArr(boolean from[], boolean to[]) {
        for (int i = 0 ; i < from.length ; ++i) to[i] = from[i];
      }

      boolean isValid(int r, int c) {
        return (r < SIZE && c < SIZE && !visR[r] && !visC[c] && !visMD[SIZE + r - c] && !visSD[r + c]);
      }

      // actually update this sate with r and c
      void affect() {
        grid[r][c] = visC[c] = visMD[SIZE + r - c] = visSD[r + c] = true;
      }

      PVector[] getPositions() {
        ArrayList<PVector> ret = new ArrayList<PVector>();
        for (int i = 0; i < SIZE; ++i)
          for (int j = 0; j < SIZE; ++j)
            if (grid[i][j]) ret.add(new PVector(j, i));
        return ret.toArray(new PVector[0]);
      }
    }

它包含表示该递归状态所需的所有内容，现在代码看起来像..

stack.push(initialState);
while(stack.size() != 0) {
    State currentState = stack.pop();
    // do stuff ...
    stack.push(nextState);
}

我们可以将 draw 函数的主体视为 while 循环的主体，并使用 noLoop() 在堆栈为空时停止它，因此最终代码将类似于 ..

import java.util.Stack;

final int GRID_SIZE = 8;
float cellH, cellW;
PImage img;

Stack<State> stack;

void setup() {
  size(500, 500);
  frameRate(5);

  cellH = (float) height / GRID_SIZE;
  cellW = (float) width / GRID_SIZE;

  img = loadImage("queen.png");

  stack = new Stack<State>();
  State state = new State();
  state.r = -1;
  state.c = -1;
  stack.push(state);

  noLoop();

}

void draw() {
  // stop if the stack is empty
  if (stack.size() == 0) {
    noLoop();
    return;
  }

  State current = stack.pop();
  drawGrid(current);

  // stop when a solution is found
  if (current.r == GRID_SIZE - 1) {
    noLoop();
    return;
  }

  for (int c = GRID_SIZE - 1; c >= 0; --c) {
    State next = new State(current);

    if (!next.isValid(current.r+1, c)) continue;
    next.c = c;
    next.r = current.r + 1;
    next.affect();

    stack.push(next);
  }

}

void drawGrid(State state) {
  float cellH = height / GRID_SIZE;
  float cellW = width / GRID_SIZE;

  background(255);
  for (int r = 0; r < GRID_SIZE; ++r) {
    for (int c = 0; c < GRID_SIZE; ++c) {
      if ((r&1) != (c&1)) fill(0);
      else  fill(255);
      rect(c*cellW, r*cellH, (c+1)*cellW, (r+1)*cellH);
    }
  }

  PVector pos[] = state.getPositions();
  for (PVector vec : pos) {
    image(img, vec.x * cellW + cellW * 0.1, vec.y * cellH + cellH * 0.1, cellW * 0.8, cellH * 0.8);
  }
}

// to resume the search after a solution is found
void keyPressed() {
  if (key == ' ') loop();
}

注意 inner for-loop 我们留到后面的部分，它被颠倒了所以第一个要执行的状态与回溯探索的第一个状态相同.

现在在数据文件中为 queen.png 资源放一些漂亮的图片，结果非常好...

Answer 3

我尝试使用 Thread 解决它，它给了我一个很好的输出，所以这是我的代码：

int cellH = 38, cellW = 38, n = 8;
PImage img;
boolean [][] grid;
boolean [] visC, visMD, visSD;
boolean firstTime = true;

Thread thread;

void setup(){
  size(560, 560);
  cellH = 560/n;
  cellW = 560/n;

  grid = new boolean[n][n];
  visC = new boolean[n];
  visMD = new boolean[2*n];
  visSD = new boolean[2*n];
  img = loadImage("queen.png");
  thread = new Thread(new MyThread());

  thread.start();
}

void draw(){
  if(thread.isAlive())
    drawGrid();
  else{
    noLoop();
    endRecord();
    return;
  }
}

void drawGrid(){
  background(255);
  for(int r = 0 ; r < n ; ++r){
   for(int c = 0 ; c < n ; ++c){
     if((r&1) != (c&1)) fill(0);
     else  fill(255);
     rect(c*cellW, r*cellH, (c+1)*cellW, (r+1)*cellH);
     if(grid[r][c] == true)
       image(img, c*cellW, r*cellH, cellW, cellH);
   }
  }
}

boolean backTrack(int r){
  if(r == n)  return true;
  else{
    for(int c = 0 ; c < n ; ++c){
      if(!visC[c] && !visMD[n+r-c] && !visSD[r+c]){
        //Do
        grid[r][c] = visC[c] = visMD[n+r-c] = visSD[r+c] = true;

        try{
          Thread.sleep(200);
        }catch(InterruptedException e){System.out.println(e);}  

        //Recurse
        if(backTrack(r+1))  return true;
        //Undo
        grid[r][c] = visC[c] = visMD[n+r-c] = visSD[r+c] = false;

        try{
          Thread.sleep(200);
        }catch(InterruptedException e){System.out.println(e);}
      }
    }
  }
  return false;
}

class MyThread implements Runnable{    
  public void run(){    
    backTrack(0);    
  }
}

这是输出：

我可以使用 Processing 逐步绘制我的回溯吗？

Can I draw a step by step my backtracking using Processing?

processing

backtracking