Scribd
Upload
2 views

task 4 code

The document contains Python functions for solving and validating Sudoku puzzles, including shifting rows and columns. It features a backtracking algorithm to solve Sudoku and a method to find all combinations of row and column shifts. Additionally, it includes a main function to handle multiple test cases of Sudoku grids.

Uploaded by

niidarko13
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as TXT, PDF, TXT or read online on Scribd
2 views

task 4 code

The document contains Python functions for solving and validating Sudoku puzzles, including shifting rows and columns. It features a backtracking algorithm to solve Sudoku and a method to find all combinations of row and column shifts. Additionally, it includes a main function to handle multiple test cases of Sudoku grids.

Uploaded by

niidarko13
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as TXT, PDF, TXT or read online on Scribd
You are on page 1/ 3

def shift_row(row, shift, N):

"""Shifts a row to the left."""


shifted_row = row[shift:] + row[:shift]
return shifted_row

def shift_col(grid, col_index, shift, N):


"""Shifts a column upwards."""
col = [grid[i][col_index] for i in range(N)]
shifted_col = col[shift:] + col[:shift]
for i in range(N):
grid_copy = [row[:] for row in grid]
for r in range(N):
grid_copy[r][col_index] = shifted_col[r]
return grid_copy

def is_valid_sudoku(grid, N):


"""Checks if the Sudoku grid is valid (no duplicates in rows, cols, blocks)."""

# Check rows
for r in range(N):
row_vals = [int(x) for x in grid[r] if x != 'X']
if len(row_vals) != len(set(row_vals)):
return False

# Check columns
for c in range(N):
col_vals = [int(grid[i][c]) for i in range(N) if grid[i][c] != 'X']
if len(col_vals) != len(set(col_vals)):
return False

# Check blocks (assuming N is a perfect square for simplicity)


block_size = int(N**0.5)
for i in range(0, N, block_size):
for j in range(0, N, block_size):
block_vals =
for r in range(i, i + block_size):
for c in range(j, j + block_size):
if grid[r][c] != 'X':
block_vals.append(int(grid[r][c]))
if len(block_vals) != len(set(block_vals)):
return False
return True

def solve_sudoku(grid, N):


"""Solves the Sudoku puzzle using backtracking."""

def find_empty(grid):
for i in range(N):
for j in range(N):
if grid[i][j] == 'X':
return (i, j)
return None

def is_valid(grid, num, pos, N):


# Check row
for i in range(N):
if grid[pos[0]][i] == num and pos[1] != i:
return False
# Check column
for i in range(N):
if grid[i][pos[1]] == num and pos[0] != i:
return False

# Check N x N box (can be optimized for Sudoku)


box_x = pos[1] // int(N**0.5)
box_y = pos[0] // int(N**0.5)
box_size = int(N**0.5)

for i in range(box_y * box_size, box_y * box_size + box_size):


for j in range(box_x * box_size, box_x * box_size + box_size):
if grid[i][j] == num and (i, j) != pos:
return False

return True

find = find_empty(grid)
if not find:
return True
else:
row, col = find

for num in range(1, N + 1):


num = str(num)
if is_valid(grid, num, (row, col), N):
grid[row][col] = num

if solve_sudoku(grid, N):
return True

grid[row][col] = 'X'

return False

def find_all_shifts(grid, N, S):


"""
Finds all combinations of row and column shifts.

Args:
grid: The shifted Sudoku grid.
N: The size of the Sudoku grid.
S: The number of shifts.

Returns:
A list of lists, where each inner list represents a combination of shifts.
Each shift is a tuple: ('R', row_index, shift_value) or ('C', col_index,
shift_value)
"""

def generate_shifts(current_grid, current_shifts, remaining_shifts, N,


all_shifts):
if remaining_shifts == 0:
temp_grid = [row[:] for row in grid]

# Apply shifts to a copy of the grid


for shift in current_shifts:
if shift[0] == 'R':
temp_grid[shift[1]] = shift_row(temp_grid[shift[1]], shift[2], N)
elif shift[0] == 'C':
temp_grid = shift_col(temp_grid, shift[1], shift[2], N)

#Only add valid solutions


if is_valid_sudoku(temp_grid, N):
all_shifts.append(current_shifts[:]) # Append a copy
return

# Try row shifts


for r in range(N):
for s in range(1, N):
new_shifts = current_shifts + [('R', r, s)]
generate_shifts(grid, new_shifts, remaining_shifts - 1, N,
all_shifts)

# Try column shifts


for c in range(N):
for s in range(1, N):
new_shifts = current_shifts + [('C', c, s)]
generate_shifts(grid, new_shifts, remaining_shifts - 1, N,
all_shifts)

all_possible_shifts =
generate_shifts(grid,, S, N, all_possible_shifts)
return all_possible_shifts

def apply_shifts(grid, shifts, N):


"""Applies the reverse shifts to the grid."""

#reverse the shifts before applying them


reversed_shifts =
for shift in reversed(shifts):
reversed_shifts.append(shift)

for shift in reversed_shifts:


if shift[0] == 'R':
grid[shift[1]] = shift_row(grid[shift[1]], N - shift[2], N)

for shift in reversed_shifts:


if shift[0] == 'C':
grid = shift_col(grid, shift[1], N - shift[2], N)
return grid

# Main function
def main():
num_cases = int(input())
for case_num in range(1, num_cases + 1):
N, S = map(int, input().split())
grid =
for _ in range(N):
row = input().split()
grid.append(row)

all_shifts = find_all_shifts(grid, N, S)

print(f"Case #{case_num

You might also like