The way it is with processing, is that you simulate loops by turning the draw function to the body of that loop and do all the initialization in setup function.
To simulate a recursion, you can turn it into a loop then do the above, usually this can be made using a stack and you basically replace the system's stack with yours; I have done some reading (check this question for some thoughts) and I found it would be very easy to turn the recursion into loop with a stack if the recursive call is at the end of the function's body.
Now the problem here, is that you have some code after the recursive call that should be executed after the call returns, but looking into it, it's just undoing changes made to global variables, we can overcome that if we consider those variables as a part of the state (not very efficient and won't scale well, but in your case it will do) so the undo part won't be necessary and the recursive call will be the last thing in the function's body (let's leave the inner for-loop for now).
So to do that I defined a class called State and it is as follows ..
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]);
}
}
it contains all that would be needed to represent the state of that recursion, now the code would look something like ..
stack.push(initialState);
while(stack.size() != 0) {
State currentState = stack.pop();
// do stuff ...
stack.push(nextState);
}
We can consider the body of draw function as the body of that while loop and use noLoop() to stop it when the stack is empty, so the final code would be something like ..
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();
}
Notice that inner for-loop part that we left for later, it's reversed so the first state to be executed is the same as the first state that the backtracking would have explored.
Now putting some nice image for the queen.png resource in data file, the result is very nice ...
