Is there a simple way to make a backtracking algorithm in Python?

Question

I need help making a python algorithm. I want to make a grid and place a "x" on cells based on certain rules. The grid is 15 rows and 100 columns. There should only be 1 "x" per column. There should be 4 "x" in each row. The "x" in each row should be spaced apart by 1, 2, and 3 spaces apart. The number of spaces between each "x" can be in any order such as 3, 2, 1 or 1, 3, 2. There can only be 4 "x" for every 12 columns. No "x" can be placed in columns 30-40.

I also tried to plot the results in Python and Excel. This is what I have so far:

import numpy as np
import matplotlib.pyplot as plt

class Board:
    def __init__(self, rows, cols, value='x', num_values=4, spacings=None):
        self.rows = rows
        self.cols = cols
        self.value = value
        self.num_values = num_values
        self.spacings = spacings if spacings else {}
        self.board = [['']*cols for _ in range(rows)]

    def is_valid(self, row, col):
        # Check if value is already in the same column
        for r in range(self.rows):
            if self.board[r][col] == self.value:
                return False

        # Check if there are no more than num_values of the same value in the same row
        if sum(1 for v in self.board[row] if v == self.value) >= self.num_values:
            return False

        # Check if values are spaced apart based on row
        if row in self.spacings:
            spacing = self.spacings[row]
            for c in range(col - spacing, col + spacing + 1):
                if 0 <= c < self.cols:
                    if self.board[row][c] == self.value:
                        return False

        # Check if no more than num_values of the same value in each group of 12 columns
        group_start = (col // 12) * 12
        group_end = group_start + 12
        group_values = [self.board[row][c] for c in range(group_start, group_end) if self.board[row][c] == self.value]
        if len(group_values) >= self.num_values:
            return False

        return True

    def solve(self, row=0, col=0):
        if row == self.rows:
            return True

        next_row = row + (col + 1) // self.cols
        next_col = (col + 1) % self.cols

        for value in [self.value]:
            if self.is_valid(row, col):
                self.board[row][col] = self.value
                if self.solve(next_row, next_col):
                    return True
                self.board[row][col] = ''

        return False

    def plot_board(self):
        plt.figure(figsize=(12, 8))
        plt.imshow(np.array([[0 if cell == '' else 1 for cell in row] for row in self.board]), cmap='binary', aspect='auto')
        plt.title('Board Visualization')
        plt.xlabel('Columns')
        plt.ylabel('Rows')
        plt.xticks(np.arange(0, self.cols, 12), np.arange(0, self.cols, 12))
        plt.yticks(np.arange(0, self.rows), np.arange(0, self.rows))
        plt.grid(True, color='gray')
        plt.show()


def main():
    rows = 15
    cols = 100
    value = 'x'
    num_values = 4
    spacings = {1, 2, 3}


    board = Board(rows, cols, value, num_values, spacings)
    if board.solve():
        print("Solution:")
        board.plot_board()
    else:
        print("No solution exists.")

if __name__ == "__main__":
    main()

Answer 1

The solve implementation looks a bit like backtracking, but doesn't really backtrack. Backtracking means that when no solution is found by the recursive search, you try to next possible candidate at that point in the recursion, until you either find a general solution or you run out of candidates. In the implementation here, if no solution is found with board[i][j] = 'x' (for any i and j) then you're not trying out any other candidate solutions, so you're not backtracking and never finding any solutions.