matrix.py

def solve_puzzle(matrix):
    """
    Solves the n×n puzzle where allowed moves are:
      (1) rotate a row,
      (2) rotate a column,
      (3) add 1 to all entries in a row,
      (4) add 1 to all entries in a column.

    Returns a list of moves (as tuples) that transforms the matrix into a constant matrix,
    or an empty list if no solution is possible.
    """
    n = len(matrix)
    total = sum(sum(row) for row in matrix)
    if total % n != 0:
        print("No solution possible: total sum is not 0 modulo n.")
        return []
    moves = []
    # --- Step 1: Row rotations ---
    # We fix row 0 as our base. Compute its difference pattern.
    base = matrix[0]
    base_diffs = [base[j] - base[0] for j in range(n)]
    row_rotations = [0] * n  # record rotation for each row (0 means no rotation)
    rotated_rows = [None] * n
    rotated_rows[0] = base[:]  # no rotation for row 0
    # For each other row, find a rotation so that its differences match base_diffs.
    for i in range(1, n):
        found = False
        for r in range(n):
            rotated = matrix[i][r:] + matrix[i][:r]
            # Compute differences relative to the first element in the rotated row.
            diffs = [rotated[j] - rotated[0] for j in range(n)]
            if diffs == base_diffs:
                row_rotations[i] = r
                rotated_rows[i] = rotated
                found = True
                break
        if not found:
            print(f"No valid rotation found for row {i}. No solution possible.")
            return []
    # Record the row rotation moves.
    for i in range(n):
        if row_rotations[i] != 0:
            # A positive shift r means "rotate row i to the left by r"
            moves.append(("rotate_row", i, row_rotations[i]))
    # --- Step 2: Compute row and column additions ---
    # After rotations, each row i becomes: B[i] where B[i][j] = B[i][0] + (base[j] - base[0]).
    # Let r_i = B[i][0]. To equalize rows, we can add (max(r_i) - r_i) to row i.
    r_vals = [row[0] for row in rotated_rows]
    R_max = max(r_vals)
    row_adds = [R_max - r for r in r_vals]
    # For the columns: note that in the base row the j-th entry is base[j] = base[0] + delta_j.
    # To cancel out these differences, add (max(delta) - delta) to column j,
    # where delta[j] = base[j] - base[0] and max(delta) is the maximum value among these.
    delta = [base[j] - base[0] for j in range(n)]
    D_max = max(delta)
    col_adds = [D_max - d for d in delta]
    # Define the final target: after row additions and column additions, every cell becomes:
    #   (B[i][0] + (base[j]-base[0])) + (R_max - B[i][0]) + (D_max - (base[j]-base[0])) = R_max + D_max.
    target = R_max + D_max
    # Record row addition moves.
    for i in range(n):
        for _ in range(row_adds[i]):
            moves.append(("add_row", i))

    # Record column addition moves.
    for j in range(n):
        for _ in range(col_adds[j]):
            moves.append(("add_col", j))

    return moves

def rotate_row(matrix, i, r):
    """Rotate row i to the left by r positions."""
    n = len(matrix)
    matrix[i] = matrix[i][r:] + matrix[i][:r]
    return matrix

def rotate_column(matrix, j, r):
    """Rotate column j upward by r positions."""
    n = len(matrix)
    column = [matrix[i][j] for i in range(n)]
    rotated_column = column[r:] + column[:r]
    for i in range(n):
        matrix[i][j] = rotated_column[i]
    return matrix

def add_to_row(matrix, i):
    """Add 1 to all entries in row i."""
    n = len(matrix)
    for j in range(n):
        matrix[i][j] += 1
    return matrix

def add_to_column(matrix, j):
    """Add 1 to all entries in column j."""
    n = len(matrix)
    for i in range(n):
        matrix[i][j] += 1
    return matrix

def print_matrix(matrix):
    """Print the matrix in a formatted way."""
    for row in matrix:
        print(" ".join(f"{x:2d}" for x in row))
    print()

def apply_moves(matrix, moves):
    """Apply the list of moves to the matrix and show the result after each move."""
    current_matrix = [row[:] for row in matrix]  # Deep copy of the matrix

    print("Initial matrix:")
    print_matrix(current_matrix)

    for idx, move in enumerate(moves, 1):
        if move[0] == "rotate_row":
            _, i, r = move
            current_matrix = rotate_row(current_matrix, i, r)
            print(f"Move {idx}: Rotate row {i} to the left by {r} positions:")
        elif move[0] == "rotate_col":
            _, j, r = move
            current_matrix = rotate_column(current_matrix, j, r)
            print(f"Move {idx}: Rotate column {j} upward by {r} positions:")
        elif move[0] == "add_row":
            _, i = move
            current_matrix = add_to_row(current_matrix, i)
            print(f"Move {idx}: Add 1 to all entries in row {i}:")
        elif move[0] == "add_col":
            _, j = move
            current_matrix = add_to_column(current_matrix, j)
            print(f"Move {idx}: Add 1 to all entries in column {j}:")

        print_matrix(current_matrix)

    # Check if the resulting matrix is constant
    first_value = current_matrix[0][0]
    is_constant = all(current_matrix[i][j] == first_value for i in range(len(current_matrix)) for j in range(len(current_matrix)))

    if is_constant:
        print(f"The matrix has been successfully transformed into a constant matrix with value {first_value}.")
    else:
        print("The matrix is not constant after applying all moves.")

    return current_matrix

# --- Example Usage ---
if __name__ == "__main__":
    # Example 3x3 matrix.
    matrix = [
        [3, 1, 2],
        [2, 3, 1],
        [1, 2, 3]
    ]
    solution = solve_puzzle(matrix)
    if solution:
        print("Solution moves:")
        for move in solution:
            print(move)
        print("\nExecuting moves:")
        final_matrix = apply_moves(matrix, solution)
    else:
        print("No solution exists for the given matrix.")