Connect Four winner decider
Let’s take a series of moves and determine a winner for the classic turn-based game Connect Four. This was one of my favorite games growing up! It is played by dropping colored disks into a vertical 7 x 6 board such that each disk played rests on the disks (or base) below. The winner is the first player to connect four disks of their color in a vertical, horizontal, or diagonal row.
For the list of moves, a series of moves by each player may be represented by a list of strings as follows:
moves_list = ["F_Yellow", "A_Red", "D_Yellow", "D_Red", ... ]
Here each player is denoted by the color of their piece, and each move is denoted by the letter ‘A’ or ‘D’ etc. of the row that they put their piece into.
To determine the winner of any given move list, the strategy is simple: add each move to a matrix representing the game board, and check whether any four pieces are connected at each turn. To start with, define a function that takes in the move list and returns the winner if there is one and write a docstring that tells us what the funciton will do:
def connect_four_winner(moves_list): '''A function that takes a list of connect four moves (each move in the format of X_color where X is the row of piece addition and color is the color of the piece moved) and returns the winning color, or 'Draw' if there is no winner. '''
The next step is to initialize a board by using a matrix. The game board is 7 slots wide by 6 slots high, but it turns out that using a bigger board makes finding connected pieces more simple to program. Here is a 10 x 9 slot list of lists representing a board. The reason behind making the board larger will become clear in a moment.
# initialize the board board = [[0,0,0,0,0,0,0,0,0,0], [0,0,0,0,0,0,0,0,0,0], [0,0,0,0,0,0,0,0,0,0], [0,0,0,0,0,0,0,0,0,0], [0,0,0,0,0,0,0,0,0,0], [0,0,0,0,0,0,0,0,0,0], [0,0,0,0,0,0,0,0,0,0], [0,0,0,0,0,0,0,0,0,0], [0,0,0,0,0,0,0,0,0,0]]
Now let’s add each move to the board, one by one. Abitrarily classifying
'Red' as player 1 and
'Yellow' as player 2, each move in the list of moves is positioned by determining who moved.
for move in moves_list: if move[2:] == 'Red': piece = 1 else: piece = 2
To determine where each player’s piece lands, the letter corresponding to the row played is counted and the piece is added to the first open slot (open slots are denoted
'0') in that row. Our board is upside down, being filled top to bottom! This does not matter for determining the winner, however. The code above is omitted using
'...' for clarity.
for move in moves_list: ... for i, letter in enumerate('ABCDEFG'): if move == letter: for k in range(6): if board[k][i] == 0: board[k][i] = piece break
Note that pieces are added to the 7x6 slots in the lower left hand corner of the entire 10x9 board. Now it is clear why this is: after adding each piece to the board as above, it is easy to check if there are four slots of a color occupied in a row, column, or diagonal by iterating accross every position of the 7x6 board as a starting point. 10x9 comes from adding 3 to both width and height of the board, such that there are not index errors as one traverses each position of the real board. The slots outside the real board remain empty (
'0'), and so do not influence whether or not a player wins.
for move in moves_list: ... ... for i in range(6): for j in range(7): # check for a horizontal four count = 0 for k in range(4): if board[i][j+k] == piece: count += 1 else: break if count == 4: return 'Red' if piece == 1 else 'Yellow' # check for a vertical four count = 0 for n in range(4): if board[i+n][j] == piece: count += 1 else: break if count == 4: return'Red' if piece == 1 else 'Yellow' # check for diagonal four right count = 0 for r in range(4): if board[i+r][j+r] == piece: count += 1 else: break if count == 4: return 'Red' if piece == 1 else 'Yellow' # check for diagonal four left count = 0 for s in range(4): if board[i-s+3][j+s] == piece: count += 1 else: break if count == 4: return 'Red' if piece == 1 else 'Yellow' return 'Draw'
The trickiest part here is finding backwards diagonals, ie pieces arranged in a \ pattern. If we start at [0,0], an index error will be thrown because there is no -1 index in this list of lists! Instead, we offset the starting horizontal value by 3 such that all 4 slots tested are within the matrix size. Looking at a physical board should make it clear why this is a valid way to test for diagonals, even if not all pieces of the ‘real’ board are being tested. If there is no winner after all moves are made,
'Draw' is returned.
for move in moves_list: ... ... ... # check for diagonal four left count = 0 for s in range(4): if board[i-s+3][j+s] == piece: count += 1 else: break if count == 4: return 'Red' if piece == 1 else 'Yellow' return 'Draw'
Let’s test it out! The following move list results in a win by Red
moves_list = [ "F_Yellow", "G_Red", "D_Yellow", "C_Red", "A_Yellow", "A_Red", "E_Yellow", "D_Red", "D_Yellow", "F_Red", "B_Yellow", "E_Red", "C_Yellow", "D_Red", "F_Yellow", "D_Red", "D_Yellow", "F_Red", "G_Yellow", "C_Red", "F_Yellow", "E_Red"]
and if we print the board after adding each piece as a matrix by inserting the following into the moves loop:
import pprint pprint.pprint (board)
we see that the final board indeed has a diagonal four for red, in fact it has two!
[[2, 2, 1, 2, 2, 2, 1, 0, 0, 0], [1, 0, 2, 1, 1, 1, 2, 0, 0, 0], [0, 0, 1, 2, 1, 2, 0, 0, 0, 0], [0, 0, 0, 1, 0, 1, 0, 0, 0, 0], [0, 0, 0, 1, 0, 2, 0, 0, 0, 0], [0, 0, 0, 2, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0, 0]]
The full code is available here
Let’s write a program to solve a sudoku puzzle! Sudoku puzzles involve placing numbers 1-9 in squares on a 9x9 grid with some numbers filled in (above) such that every row or column contains one of each digit, and every smaller 3x3 square in bold also contains only one digit (ie no two 9s or two 1s).
There are a number of advanced strategies that once can use for this puzzle, but if time is not a limiting factor then we can use a very simple method to solve any given puzzle. The method is guess and check: for each empty grid space, let’s add a number between 1 and 9 and see if the puzzle is OK. If so, we continue on to the next grid but if not we simply increment the number tried (if 1 did not work, we try 2 etc.). If none of the numbers work, we go backwards and increment the number in the previous grid, and if none of those work we go backwards until a number does work. This method is often called backtracking, and there are a number of useful animations online for observing how this works.
The reason this algorithm works is because it potentially tries every combination of digits in the empty boxes, so if there is a possible solution then the solution will eventually be found! The program we will write here usually runs in a matter of tens to hundreds of milliseconds on challenging puzzles, but can take up to half a minute or more on extremely difficult ones. The sample problem here is challenging, and takes approximately a second to solve.
Let’s represent the Sudoku board as a matrix, which we can specify as a list of lists (1-dimensional arrays, to be precise) without having to resort to a library like numpy to make fancy two-dimensional arrays. Here is the representation of the puzzle above:
puzzle = [ [0, 0, 4, 0, 0, 1, 7, 0, 0], [0, 8, 0, 0, 2, 0, 0, 0, 0], [2, 0, 0, 0, 7, 0, 0, 0, 0], [0, 0, 0, 5, 0, 3, 0, 7, 8], [0, 0, 5, 0, 0, 0, 4, 0, 0], [9, 6, 0, 1, 0, 4, 0, 0, 0], [0, 0, 0, 0, 5, 0, 0, 0, 9], [0, 0, 0, 0, 1, 0, 0, 6, 0], [0, 0, 1, 7, 0, 0, 2, 0, 0]]
Now is the time to define a function, remembering a doc string that specifies valid inputs and expected outputs:
def solve(puzzle): '''A function that takes a list of lists denoting sudoku puzzle clues and places to guess (0s) and returns the completed puzzle as a list of lists. Expects a solveable puzzle, and will return only solution if multiple exist. '''
It is helpful to know which positions on the puzzle we need to try numbers, and which positions are given. With a nested loop, we can make a list named
ls of all coordinates of positions of to-be-found values as follows:
# make list of all positions to be determined ls =  for x in range(9): for y in range(9): if puzzle[x][y] == 0: ls.append([x,y]) # call backtracking function (below) return backtrack(puzzle, ls)
Now let’s apply the backtracking algorithm to the puzzle, but only on the positions of values to be found, by indexing over the list
ls. One can define another function within the first to do so, which is not absolutely necessary but provides clarity.
def backtrack(puzzle, ls): '''Solves the sudoku puzzle by iterating through the positions in ls and entering possible values into the puzzle array. Backtracking occurs when no entry is possible for a given space. ''' i = 0 while i in range(len(ls)): a, b = ls[i]
so now (a, b) is set to the coordinates of the first unknown space. This is a good time to initialize a variable
count to be 0, which will change to 1 if a digit cannot be inserted at the unknown space. If there are no legal moves in the first unknown space, the puzzle is not solveable! The
count becomes important in subsequent spaces, and signals the need to backtrack: if no digit can be insterted at a space, then count stays 0 and we will add a clause to initiate backtracking if that is the case. Let’s also initiate the variable
c, which will store the next number to be tested as follows:
count = 0 if puzzle[a][b] == 0: c = 0 else: c = puzzle[a][b] c += 1
Now come the tests: first the row (which is equal to
puzzle[a]), then the column (
ls2), and finally the 3x3 box (
ls3) are tested to see if
c is different than every element of these three lists.
while c < 10: if c not in puzzle[a]: ls2 =  for q in range(9): ls2.append(puzzle[q][b]) if c not in ls2: ls3 =  x, y = a // 3, b // 3 for k in range(3*x, 3*x+3): for l in range(3*y, 3*y+3): ls3.append(puzzle[k][l]) if c not in ls3:
c is a unique element, it is a possible move! If so, we add it to the puzzle by assigment, increment our variable ‘count’, and increment the index of the list of coordinates to be solved (
i) and break out of the while loop. If any of these tests fail,
c cannot be a valid move for the position
ls[i], so we increment c and continue the loop to test the next larger digit.
puzzle[a][b] = c count += 1 i += 1 break else: c += 1 else: c += 1 else: c += 1
If no digit 1-9 is a legal move at the given position the ‘count’ variable stays 0 and we use this to test whether a backtrack needs to be made. If so, we return the current position to 0 and decrement the index of the list of coordinates to be solved (
i). If all elements of this list have been iterated, we must have filled in a number at all positions so we can return the solved puzzle. Finally we call the intertior function
backtrack() in the exterior function
solve() with the arguments of the puzzle and the list of places to fill in.
if count == 0: puzzle[a][b] = 0 i -= 1 return puzzle
Markdown is not good a tracking spaces between code entries, so make sure to line up each if/else and loop The full sudoku solver code is available here.
Now let’s test the solver! Pretty printing (each element of a list is given its own line) is helpful here to make the matrix readable, so let’s add the input and pprint it).
# example of an input puzzle = [ [0, 0, 4, 0, 0, 1, 7, 0, 0], [0, 8, 0, 0, 2, 0, 0, 0, 0], [2, 0, 0, 0, 7, 0, 0, 0, 0], [0, 0, 0, 5, 0, 3, 0, 7, 8], [0, 0, 5, 0, 0, 0, 4, 0, 0], [9, 6, 0, 1, 0, 4, 0, 0, 0], [0, 0, 0, 0, 5, 0, 0, 0, 9], [0, 0, 0, 0, 1, 0, 0, 6, 0], [0, 0, 1, 7, 0, 0, 2, 0, 0]] # example function call import pprint pprint.pprint (solve(puzzle)) ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ [[5, 9, 4, 8, 3, 1, 7, 2, 6], [7, 8, 3, 4, 2, 6, 9, 1, 5], [2, 1, 6, 9, 7, 5, 8, 3, 4], [1, 4, 2, 5, 9, 3, 6, 7, 8], [8, 3, 5, 2, 6, 7, 4, 9, 1], [9, 6, 7, 1, 8, 4, 3, 5, 2], [3, 7, 8, 6, 5, 2, 1, 4, 9], [4, 2, 9, 3, 1, 8, 5, 6, 7], [6, 5, 1, 7, 4, 9, 2, 8, 3]] [Finished in 0.9s]
The output looks good! No 0s remaining and no obvious errors in digit placement. Running this program on pypy for speed, the time is down to 183 ms.
(base) bbadger@bbadger:~/Desktop$ time pypy sudoku_solver.py ... (matrix shown here) ... real 0m0.183s user 0m0.144s sys 0m0.021s
Battleship placement validator
Say you are playing battleship the old fashioned way: with paper and a drawn 10x10 grid. You mark the positions of your ships with ‘1’s, but after doing so wonder if you made a mistake. Is your battleship field valid according to the rules that ships may be touching each other, and ships comprise of one carrier size 4 square, two battleships size 3, three destroyers size 2, and four subs of size 1?
We can represent the battleship grid with a list of lists corresponding to a matrix:
field = [[1, 0, 0, 0, 0, 0, 0, 0, 0, 0], [1, 1, 1, 0, 0, 0, 0, 0, 1, 0], [1, 1, 0, 0, 0, 0, 0, 0, 1, 0], [1, 1, 0, 0, 0, 0, 0, 0, 0, 0], [1, 1, 0, 0, 0, 0, 0, 0, 1, 0], [1, 1, 0, 0, 1, 1, 1, 0, 0, 0], [1, 0, 0, 0, 0, 0, 0, 0, 1, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0, 0]]
How do we go about determining if this is a valid field? A simple test that comes to mind is to count the number of positions and determine if this number exceeds or falls short of what it should be (20), which can be accomplished by nesting two loops and incrementing a counter for each position with a ship (denoted
# preliminary check for the correct number of spaces count = 0 for lst in field: for element in lst: if element == 1: count += 1 if count != 20: return False
But for all the combinations of placements where there are the correct number of positions marked, how do we tell which ones are valid and which are not?
Suppose there was only one ship, a carrier. Then the problem is easier, and it is a simple task to see if the field is valid: simply loop over each element of the field (left to right and top to bottom is the order for two nested loops) and for the first
1, see if there are three other
1s to the right or below. The trailing
1s will not be above or behind because then we would not be observing the first
1! If there are indeed three
1s behind or below the first but no more
1s anywhere else, we have a valid board and vice versa.
With two ships this becomes more difficult. To which ship does the first
1 belong to? If we ignore this question and assume that the
1 belongs to one particular type of ship, we may mistakenly classify an invalid board as valid (or the opposite) because ships can be touching. But it is impossible to know which
1 belongs to which ship, so how do we proceed?
Making the problem smaller certainly helped, and this is a sign that recursion is the way forward with this problem. Using recursion, we can start with a grid with many
1s and eliminate them as we guess which pieces belong to which ship. We work around the problem of not knowing which ship is associated with each
1 by simply trying every option possible, and if any are valid then we have a valid board setup!
Let’s define a function and attach a docstring. A list of ships will be useful, so we define a list
ships using the ship size as the names for each ship. As we will be checking each position to determine if it is a part of the ship, it is helpful to add
0s along the right and lower borders of our matrix such that we avoid index errors while checking all
1s. Here we include a layer of
0s along the upper and left borders of the matrix for visual clarity. Our preliminary check for the correct number of ship spots is added here too.
def validate_battlefield(field): '''A function that takes a 10x10 list of lists corresponding to a battleship board as an argument and returns True if the field is a legal arrangement of ships or False if not. Ships are standard (1 carrier size 4, 2 battleships size 3, 3 destroyers size 2, 4 subs size 1) and ships may be touching each other. Only the location of hits are known, not the identity of each hit. ''' ships = [4, 3, 3, 2, 2, 2, 1, 1, 1, 1] import pprint # make a wrapper for the field for ease of iteration for i in field: i.insert(0, 0) i.append(0) field.insert(0, [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]) field.append([0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]) # preliminary check for the correct number of spaces count = 0 for lst in field: for element in lst: if element == 1: count += 1 if count != 20: return False # call a validate function on the prepared field return validate(field, ships)
Now comes the recursion. To avoid re-wrapping the field with
0s and re-checking to see if the correct number of spots are filled, we can define another function in this larger one and simply call this one. The strategy will be iterate along the original field until we see a
1, and then test if it can be the largest ship in the vertical direction. If so, we remove all
1s corresponding to this ship on the field, remove the largest ship from the list
ships, and copy the ships list (to avoid errors during recursion).
We then test whether this copied list is valid by calling the
validate function on this list with the copied ships
ships2, which causes the function
validate to be called over and over until either the list
ships has been exhausted, or until there are no other options for piece placement. If the former is true, the board is valid and the function returns
False is returned up the stack.
False reaches the first
if validate() statement, it causes the program to skip to
else, where we add back the ship we earlier erased from the board. Otherwise many invalid boards will be classified as valid! The horizontal direction must also be considered at each stage, so the code above is repeated but for check along each list. At the end, a last check for any remaining ships is made, and this function is called inside
def validate(field, ships): '''Assesses the validity of a given field (field), with a list of ships that are yet to be accounted for (ships). The method is to remove ships, largest to smallest, using recursion. Returns a boolean corresponding to the possibility of the field being legal or not. ''' for i in range(12): for j in range(12): if field[i][j] == 1: k = 0 while field[i+k][j] == 1: k += 1 if k == ships: del ships for m in range(k): field[i+m][j] = 0 if len(ships) == 0: y = 1 return True ships2 = ships[:] if validate(field, ships2): return True else: for x in range(k): field[i+x][j] = 1 ships = [k] + ships w = 0 while field[i][j+w] == 1: w += 1 if w == ships: del ships for n in range(w): field[i][j+n] = 0 if len(ships)==0: y = 1 return True ships3 = ships[:] if validate(field, ships3): return True else: for n in range(w): field[i][j+n] = 1 ships = [w] + ships if len(ships)==0: return True else: return False
Let’s test this out! With the battlefield shown above, we get
# example function call print (validate_battlefield(field)) ~~~~~~~~~~~~~~~~~~~~~~~~ True [Finished in 0.0s]
Manually trying to put ships in place should convince you that the field is indeed valid!