So here's the solution that worked from me - based off the maze solving algorithm linked to by @Floris.
There may be a bug or two, and it's certainly not optimized, but it works for now.
Should be pretty easy to follow, thanks for everyone's help:
-(BoardState)solutionPathExistsForColor {
//create a board copy where the last column equals the first
for (int i = 0; i < BOARD_ROWS+1; i++) {
for (int j = 0; j < BOARD_COLUMNS+1; j++) {
if (j == BOARD_COLUMNS) {
loopedBoard[i][j] = landed[i][0];
} else {
loopedBoard[i][j] = landed[i][j];
}
}
}
for (BoardState state = 1; state < kBoardStateCount; state++) {
//first check if it is possible there is a path
//for each row
for (int row = 0; row < BOARD_ROWS; row++) {
//set solution path to zero
for (int i = 0; i < BOARD_ROWS; i++) {
for (int j = 0; j < BOARD_COLUMNS; j++) {
solutionPath[i][j] = 0;
}
}
BOOL aTest = [self findPathToGoalRow:row //iterate
andGoalColumn:BOARD_COLUMNS //always the same
fromRow:row //iterate
andColumn:0 // always the same
ofState:state]; //iterate
if (aTest) {
CCLOG(@"Success! State %i", (int)state);
//now that you know a path exists, modify the path to contain all correct adjacent cells
[self fixSolutionPathOfColor:state];
return state;
} else {
CCLOG(@"Failure!");
}
}
}
return kBoardStateVOID;
}
-(BOOL)findPathToGoalRow:(int)goalRow
andGoalColumn:(int)goalColumn
fromRow:(int)fromRow
andColumn:(int)fromColumn
ofState:(BoardState)state {
//check to see if we've already seen this row and column
if (solutionPath[fromRow][fromColumn] == 1) {
return NO;
}
// if (x,y outside maze) return false
if (fromRow > BOARD_ROWS -1 || fromColumn > BOARD_COLUMNS || fromRow < 0 || fromColumn < 0) {
return NO;
}
// if (x,y is goal) return true
if (fromRow == goalRow && fromColumn == goalColumn) {
return YES;
}
// if (x,y not open) return false
//if ([self boardStateAtRow:fromRow andColumn:fromColumn] != state) {
if (loopedBoard[fromRow][fromColumn]!=state) {
return NO;
}
// mark x,y as part of solution path
solutionPath[fromRow][fromColumn] = 1;
// if (FIND-PATH(North of x,y) == true) return true
if ([self findPathToGoalRow:goalRow
andGoalColumn:goalColumn
fromRow:fromRow+1
andColumn:fromColumn
ofState:state]) {
return YES;
}
// if (FIND-PATH(East of x,y) == true) return true
if ([self findPathToGoalRow:goalRow
andGoalColumn:goalColumn
fromRow:fromRow
andColumn:fromColumn+1
ofState:state]) {
return YES;
}
// if (FIND-PATH(South of x,y) == true) return true
if ([self findPathToGoalRow:goalRow
andGoalColumn:goalColumn
fromRow:fromRow-1
andColumn:fromColumn
ofState:state]) {
return YES;
}
// if (FIND-PATH(West of x,y) == true) return true
if ([self findPathToGoalRow:goalRow
andGoalColumn:goalColumn
fromRow:fromRow
andColumn:fromColumn-1
ofState:state]) {
return YES;
}
// unmark x,y as part of solution path
solutionPath[fromRow][fromColumn] = 0;
return NO;
}
-(void)fixSolutionPathOfColor:(BoardState)color {
for (int column = 0; column < BOARD_COLUMNS; column++) {
BOOL bottomColumnOfSolutionPathFound = NO;
int checkingRow = 0;
while (!bottomColumnOfSolutionPathFound) {
if ([self solutionCellAtRow:checkingRow andColumn:column] == 1) {
bottomColumnOfSolutionPathFound = YES;
} else {
checkingRow++;
}
}
//you'll start with this bottom row and look below
if (solutionPath[checkingRow][column] == 1) {
int nextRowToCheck = checkingRow-1;
BOOL keepChecking = YES;
while (nextRowToCheck >= 0 && keepChecking) {
if ([self boardStateAtRow:(nextRowToCheck) andColumn:column] == color) {
if ([self solutionCellAtRow:(nextRowToCheck) andColumn:column] != YES) {
solutionPath[nextRowToCheck][column] = 1;
}
nextRowToCheck--;
} else {
keepChecking = NO;
}
}
//now repeat for above
nextRowToCheck = checkingRow+1;
keepChecking = YES;
while (nextRowToCheck < BOARD_ROWS && keepChecking) {
if ([self boardStateAtRow:(nextRowToCheck) andColumn:column] == color) {
if ([self solutionCellAtRow:(nextRowToCheck) andColumn:column] != YES) {
solutionPath[nextRowToCheck][column] = 1;
}
nextRowToCheck++;
} else {
keepChecking = NO;
}
}
}
}
}
Thanks!