I'm implementing a flood-fill algorithm for python minesweeper.
Before I show you the algorithm, let me define some things that are important:
BOARD, when pretty printed, looks like this:
X 1 1 1 3 X 2 1 2 X 2 2 3 X 2 X X 3 1 2 1 1
2 2 1 2 X 3 X 3 2 X 2 2 X X 2 3 4 X 4 X 3 X 1
X 2 1 X 2 3 3 X 2 1 1 1 3 3 2 1 X 2 4 X 4 1 1
X 2 2 3 3 2 X 4 3 1 1 X 1 1 2 3 4 X 3 1 1 1 1
2 3 2 X X 2 2 X X 1 2 3 3 2 2 X X 3 4 X 2 1 X
X 2 X 3 3 2 3 3 3 2 1 2 2 X X 4 X 3 2 3 X X 2 1 1
1 3 2 2 1 X 2 X 1 2 X 3 X 4 X X 4 3 1 2 X 3 1
1 2 X 2 2 2 2 1 1 3 X 4 2 3 3 3 X X 3 2 1 1 1 1 1
X 3 1 3 X 2 2 X 2 1 X 1 1 4 X X 1 1 X 2
X 3 1 3 X 2 1 2 2 2 2 2 2 3 X 3 1 2 3 X
2 3 X 2 1 1 1 1 1 1 X 2 2 X 4 X 3 1 1 X 2
X 2 1 1 1 1 2 X 1 1 2 3 X 2 2 X X 2 1 1 1
2 2 1 2 3 X 2 1 1 1 X 2 1 1 1 2 2 2 2 2 1
X 2 1 X X 3 2 1 1 3 3 2 1 1 1 1 1 2 X X 2
X 2 1 2 2 3 X 2 1 X X 2 2 X 1 2 X 3 3 X 2 1 1 1
1 2 1 1 2 X 2 2 3 4 X 2 2 2 4 X 3 1 1 1 1 X 1
1 X 1 2 2 3 2 X 3 2 1 1 X 3 X 2 2 2 2
1 1 1 1 X 2 X 3 X 1 1 1 2 1 1 1 X 1
Obviously the X's represent mines, and the numbers represent number of mines surrounding that place. Empty spaces obviously mean that there are no numbers there. Basically BOARD is how I'm storing my information.
CURRENT_BOARD, when pretty printed, looks like this:
[A][B][C][D][E][F][G][H][I][J][K][L][M][N][O][P][Q][R][S][T][U][V][W][X][Y]
[1] O O O O O O O O O O O O O O O O O O O O O O O O O
[2] O O O O O O O O O O O O O O O O O O O O O O O O O
[3] O O O O O O O O O O O O O O O O O O O O O O O O O
[4] O O O O O O O O O O O O O O O O O O O O O O O O O
[5] O O O O O O O O O O O O O O O O O O O O O O O O O
[6] O O O O O O O O O O O O O O O O O O O O O O O O O
[7] O O O O O O O O O O O O O O O O O O O O O O O O O
[8] O O O O O O O O O O O O O O O O O O O O O O O O O
[9] O O O O O O O O O O O O O O O O O O O O O O O O O
[10] O O O O O O O O O O O O O O O O O O O O O O O O O
[11] O O O O O O O O O O O O O O O O O O O O O O O O O
[12] O O O O O O O O O O O O O O O O O O O O O O O O O
[13] O O O O O O O O O O O O O O O O O O O O O O O O O
[14] O O O O O O O O O O O O O O O O O O O O O O O O O
[15] O O O O O O O O O O O O O O O O O O O O O O O O O
[16] O O O O O O O O O O O O O O O O O O O O O O O O O
[17] O O O O O O O O O O O O O O O O O O O O O O O O O
[18] O O O O O O O O O O O O O O O O O O O O O O O O O
the zeros are covered cells. BOARD and CURRENT_BOARD have the same number of rows and columns.
Finally,
POSSIBLE_MINE_NUMBERS = ['1','2','3','4','5','6','7','8']
So, when the user enters a row and column value, eg 1,A, it is coverted into python indexing, (0,0) and passed into this floodfill algorithm (note the print statements I used for crude debugging).
def floodfill(CURRENT_BOARD, row, col):
print row
print col
if BOARD[row][col] in POSSIBLE_MINE_NUMBERS:
CURRENT_BOARD[row][col] = BOARD[row][col] + ' '
else:
if CURRENT_BOARD[row][col] != ' ':
CURRENT_BOARD[row][col] = ' '
if row > 0:
print 'a'
floodfill(CURRENT_BOARD, row - 1, col)
if row < len(BOARD[row]) - 1:
print 'b'
floodfill(CURRENT_BOARD, row + 1, col)
if col > 0:
print 'c'
floodfill(CURRENT_BOARD, row, col - 1)
if col < len(BOARD) - 1:
print 'd'
floodfill(CURRENT_BOARD, row, col + 1)
Now, this algorithm works fine in any position other than the bottom row of the board (row 17). When I try to run it on the bottom row, for example 18, e (17, 4) I get the following output (due to my debugging) (LOOK AT THE last 3):
17
4
16
4
15
4
14
4
a
16
4
b
15
3
c
15
5
d
a
17
4
b
16
3
c
16
5
d
a
18
4
it says 'a', 18, and 4! So for some reason the floodfill algorithm is jumping from 16 to 18 on the first if branch. This makes absolutely no sense to me and I'm not sure why I'm getting this strange behavior. If you look at the rest of that output, you can also see it jumping two row indices at some points.
Can anybody see anything wrong with the algorithm?
You're saying if row < len(BOARD[row]) which is comparing the row index to the length of a row (i.e. number of columns) not to the number of rows. Similarly, you're comparing col, a column index, to len(BOARD), but len(BOARD) is surely the number of rows, not the number of columns.