KUBOK 16 PUZZLE SOLVER

A Kubok 16 board is composed of a 4 by 4 grid. Numbers from 1 to 16 must be placed

into the grid to solve the puzzle. No number may repeat. Each column must

add up to the numbers along the top of the grid. Each row must add up to

the numbers along the left side of the grid. Some cells already have a

number (non-zero values) defined for that cell and cannot be changed.

//You can familarize yourself with Kubok 16 on the internet.

Program

Write a program “kubokSolver” that takes an array of arrays of integers grid, an array of intergers rowSum, and an array of integers colSum single. The grid will contain the initial state of the puzzle.

Inputs

colSum has 4 numbers, one for each column, and each between 10 and 58.

rosSum has 4 numbers , one for each row, and each between 10 and 58.

grid is an array containing four arrays of integers. Each of the four arrays of integers represent a row of the grid. 0 is used to represent an empty cell in the grid.

The numbers must be between 0 and 16. Numbers from 1 to 16 cannot be

repeated.

Sample file

column sums: 19,35,30,52

row sums: 36,41,35,24

grid:

0,0,4,0

0,14,0,11

2,0,12,0

0,8,0,0

Expected Output

Once the program has solved the puzzle, output the solution in the following

“`

9 7 4 16

3 14 13 11

2 6 12 15

5 8 1 10

The Correct Answer and Explanation is :

Here’s a Python program to solve the Kubok 16 puzzle using backtracking. The program ensures that:

Each number from 1 to 16 is used only once.
Each row sums up to the specified rowSum.
Each column sums up to the specified colSum.
The numbers already given in the grid remain unchanged.

Kubok 16 Solver Code

from itertools import permutations

def is_valid(grid, rowSum, colSum):
    """Check if the current grid satisfies row and column sums."""
    for r in range(4):
        if sum(grid[r]) != rowSum[r]:
            return False
    
    for c in range(4):
        if sum(grid[r][c] for r in range(4)) != colSum[c]:
            return False
    
    return True

def solve_kubok(grid, rowSum, colSum):
    """Solve the Kubok 16 puzzle using backtracking."""
    all_numbers = set(range(1, 17))
    
    # Collect all pre-filled numbers
    used_numbers = {num for row in grid for num in row if num > 0}
    unused_numbers = list(all_numbers - used_numbers)

    # Generate all permutations of the unused numbers
    for perm in permutations(unused_numbers):
        temp_grid = [row[:] for row in grid]  # Copy grid
        idx = 0  # Index for filling missing values
        
        # Fill empty cells with permuted numbers
        for r in range(4):
            for c in range(4):
                if temp_grid[r][c] == 0:
                    temp_grid[r][c] = perm[idx]
                    idx += 1
        
        # Check if this configuration is valid
        if is_valid(temp_grid, rowSum, colSum):
            return temp_grid  # Return the solved grid
    
    return None  # No solution found

# Example Input
colSum = [19, 35, 30, 52]
rowSum = [36, 41, 35, 24]
grid = [
    [0, 0, 4, 0],
    [0, 14, 0, 11],
    [2, 0, 12, 0],
    [0, 8, 0, 0]
]

# Solve the puzzle
solution = solve_kubok(grid, rowSum, colSum)

# Display the result
if solution:
    for row in solution:
        print(" ".join(map(str, row)))
else:
    print("No solution found.")

Explanation

1. Problem Breakdown

The puzzle consists of a 4×4 grid.
Each row must sum to a predefined value.
Each column must sum to a predefined value.
Given numbers (not 0) cannot be changed.
We need to place numbers 1-16 exactly once.

2. Approach

Step 1: Identify the missing numbers
- Extract the numbers already present.
- Determine the missing numbers.
Step 2: Generate possible arrangements
- Use itertools.permutations to try all possible ways to distribute the missing numbers.
Step 3: Check validity
- Ensure that each row sums to rowSum.
- Ensure that each column sums to colSum.
- If a valid arrangement is found, return it as the solution.

3. Complexity Considerations

The program explores permutations of the missing numbers.
The solution works efficiently since there are only 16 numbers, making permutations feasible.

4. Expected Output

For the given input:

column sums: 19,35,30,52
row sums: 36,41,35,24
grid:
0,0,4,0
0,14,0,11
2,0,12,0
0,8,0,0

The program outputs:

which satisfies all row and column constraints.

Why This Works

Backtracking + Permutations ensures all possible combinations are tested.
Efficiency: Since it’s a small grid, brute-force checking is feasible.
Correctness: The constraints ensure a unique valid solution.

Would you like additional features, like a step-by-step solution display? 🚀