Grid data-structure and placement algorithm for my Battleships implementation?

Question

I am trying to make my own version of the game Battleships (in German: Schiffe versenken).

I have made the game board as a 10x10 dataframe. The coordinates of the ships are created randomly. I have 4 different kinds of ships with lengths between 5 an 2. Each of these ships is a list. The elements of the list are made of the randomly created starting coordinates (ship_row, ship_col) and depending if the ship is horizontal or vertical the other elements are either ship_row + n or ship_col + n.

Problem: it can happen that the length of a ship exceeds the bounds of the dataframe. How can I set boundaries for those ship lists and how can I make a loop to create a new ship list if the first made one exceeds the boundaries?

Here my Code for the example ship Schlachtschiff:

board = []

for n in range (10):
    board.append(['O'] * 10)

board = pd.DataFrame(board)

g = rd.randint(1, 2)
random_row(board)
random_col(board)
ship_row = random_row(board)
ship_col = random_col(board)

for Schlachtschiff in board:
    if g == 1:
        Schlachtschiff = [(ship_row, ship_col),
                          (ship_row, ship_col + 1),
                          (ship_row, ship_col + 2),
                          (ship_row, ship_col + 3),
                          (ship_row, ship_col + 4)]
    else:
        Schlachtschiff = [(ship_row, ship_col),
                          (ship_row + 1, ship_col),
                          (ship_row + 2, ship_col),
                          (ship_row + 3, ship_col),
                          (ship_row + 4, ship_col)]

I tried to solve it with a while loop by looking at the last element of the created list, but that would not stop:

while Schlachtschiff[-1] not in board:
    if g == 1:
        Schlachtschiff = [(ship_row, ship_col),
                          (ship_row, ship_col + 1),
                          (ship_row, ship_col + 2),
                          (ship_row, ship_col + 3),
                          (ship_row, ship_col + 4)]
    else:
        Schlachtschiff = [(ship_row, ship_col),
                          (ship_row + 1, ship_col),
                          (ship_row + 2, ship_col),
                          (ship_row + 3, ship_col),
                          (ship_row + 4, ship_col)]

    if Schlachtschiff[-1] in board:
        break

To stop the ships from overlapping I wrote this code (Note "Kreuzer is the second kind of ship, being created the same way as above):

for i in Schlachtschiff:
    for j in Kreuzer:
        if i == j:
            random_row(board)
            random_col(board)
            ship_row_1 = random_row(board)
            ship_col_1 = random_col(board)
            g = rd.randint(1, 2)

            if g == 1:
                Kreuzer = [(ship_row, ship_col),
                           (ship_row, ship_col + 1),
                           (ship_row, ship_col + 2)]
            else:
                Kreuzer = [(ship_row, ship_col),
                           (ship_row + 1, ship_col),
                           (ship_row + 2, ship_col)]

Now I dont have that problem anymore thanks to help of @smci. My code looks as follows now:

board = []
board = pd.DataFrame(data='□', index=range(1, 10 + 1),

columns=list('ABCDEFGHIJ')) print(board)

def random_row(board):
    return rd.randint(0, len(board) - 1)

def random_col(board):
     return rd.randint(0, len(board) - 1)

def Schiff_erstellen(Schiff, Start, Stop):
    g = rd.randint(1, 2)
    random_row(board)
    random_col(board)
    ship_row = random_row(board)
    ship_col = random_col(board)
    Schiff = [(ship_row, ship_col)]
    while Schiff[-1] > (ship_row_probe, ship_col_probe):
        g = rd.randint(1, 2)
        random_row(board)
        random_col(board)
        ship_row = random_row(board)
        ship_col = random_col(board)
        Schiff=[(ship_row, ship_col)]
        if g == 1:
            for i in range(Start, Stop):
                Schiff.append((ship_row, ship_col + i))
        else:
            for i in range(Start, Stop):
                Schiff.append((ship_row + i, ship_col))
        if Schiff[-1] <= (ship_row_probe, ship_col_probe):
            break

    return Schiff

Answer 1

First let's take a look at placing a single ship. A ship is a line segment, so you need three random numbers to characterize it: a boolean direction (horizontal or vertical), and the coordinates of the upper left-hand corner. I'm assuming that for any given ship, the length is fixed. Now if you know the length is L and the board is MxN, you can restrict the positions like this:

def generate_ship(L, M, N):
    """ Returns the slices to fill in on an MxN board to get a random L-sized ship """
    # True = vertical
    direction = random.randrange(2)
    rsize = direction * (L - 1)
    csize = (not direction) * (L - 1)
    row = random.randrange(M - rsize)
    col = random.randrange(N - csize)
    return slice(row, row + 1 + rsize), slice(col, col + 1 + csize)

Multiplying by direction and not direction saves you the trouble of having to use if statements to handle the different cases. You can use the result of this function directly with df.iloc, since it's a tuple of slices:

import numpy as np
import pandas as pd
import random
from string import ascii_uppercase

M = N = 10
df = pd.DataFrame(np.tile([[' ']], [M, N]), index=np.arange(M), columns=list(ascii_uppercase[:N]))
df.iloc[generate_ship(3, M, N)] = 'O'

So far so good, but now you want to generate multiple non-overlapping ships. The simplest method is brute-force: start with the largest ship and keep generating a new ship until you get one that doesn't overlap:

M = N = 10
df = pd.DataFrame(np.tile([[' ']], [M, N]), index=np.arange(M), columns=list(ascii_uppercase[:N]))
for L in (5, 4, 4, 3, 3, 2, 2, 2):
    while True:
        ship = generate_ship(L, M, N)
        if (df.iloc[ship] == ' ').all():
            df.iloc[ship] = 'O'
            break

A much more deterministic approach would be to maintain a grid of available coordinates and prune it every time you generate a ship. You could, for example, maintain an 2xMxN array recording the largest ship that can be placed at a given location. Every time you place a ship you would update this array. To generate, you would simply select from locations available via something like np.argwhere(options[direction] >= L):

class ShipGenerator:
    def __init__(self, M, N):
        horiz = np.arange(N, 0, -1)[None, :].repeat(M, axis=0)
        vert = np.arange(M, 0, -1)[:, None].repeat(N, axis=1)
        self.options = np.stack((horiz, vert), axis=0)

    def generate_ship(self, L):
        options = np.argwhere(self.options >= L)
        n = len(options)
        if n == 0:
            raise ValueError(f'Unable to generate ship of size {L}. '
                             f'Max remaining space is {self.options.max(None)}')

        direction, row, col = options[random.randrange(len(options))]
        row_end = row + 1 + direction * (L - 1)
        col_end = col + 1 + (not direction) * (L - 1)

        self.clear_region(row, row_end, col, col_end)
        return (slice(row, row_end), slice(col, col_end))

    def clear_region(self, r_start, r_end, c_start, c_end, margin=0):
        """ Once a ship has been generated, update the map to restrict squared around it """
        r_start = max(r_start - margin, 0)
        c_start = max(c_start - margin, 0)
        r_end = min(r_end + margin, self.options.shape[1])
        c_end = min(c_end + margin, self.options.shape[2])

        # Update ship + margin
        self.options[:, r_start:r_end, c_start:c_end] = 0

        # Update horizontal restrictions
        self.options[0, r_start:r_end, :c_start] = \
            np.minimum(self.options[0, r_start:r_end, :c_start],
                       np.arange(c_start, 0, -1))

        # Update vertical restrictions
        self.options[1, :r_start, c_start:c_end] = \
            np.minimum(self.options[1, :r_start, c_start:c_end],
                       np.arange(r_start, 0, -1)[:, None])

Generating a board now becomes that much simpler:

df = pd.DataFrame(np.tile([[' ']], [M, N]), index=np.arange(M), columns=list(ascii_uppercase[:N]))
generator = ShipGenerator(M, N)
for L in (5, 4, 4, 3, 3, 2, 2, 2):
    df.iloc[generator.generate_ship(L)] = 'O'

You would want to maintain a board to record enemy hits, but also metadata for the individual ships. Storing metadata on the board would be wasteful. Instead, you can create a Ship object that contains the metadata, including the slices made by generate_ship. The board then becomes a set of labels that are indices into a list of Ships.