Last active
January 30, 2025 00:30
-
-
Save wycks/998a5146cdddc76a0a8546ff1f9e3ffe to your computer and use it in GitHub Desktop.
Revisions
-
wycks revised this gist
Jan 30, 2025 . 1 changed file with 49 additions and 20 deletions.There are no files selected for viewing
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters. Learn more about bidirectional Unicode charactersOriginal file line number Diff line number Diff line change @@ -15,13 +15,46 @@ def gcd_of_list(lst): return 1 return result def is_valid_number(grid, row, col, num): """Check if 'num' can be placed at grid[row, col] without breaking uniqueness.""" # Check row and column uniqueness if num in grid[row, :] or num in grid[:, col]: return False # Check 3×3 square uniqueness start_x, start_y = (row // 3) * 3, (col // 3) * 3 if num in grid[start_x:start_x+3, start_y:start_y+3]: return False return True def fill_grid(grid, predefined): """Fills the grid while keeping predefined numbers unchanged.""" empty_cells = [(r, c) for r in range(9) for c in range(9) if (r, c) not in predefined] random.shuffle(empty_cells) # Shuffle for randomness def backtrack(index): """Recursive backtracking function to fill the grid.""" if index == len(empty_cells): return True # All cells are filled row, col = empty_cells[index] for num in range(1, 10): # Try numbers 1-9 if is_valid_number(grid, row, col, num): grid[row, col] = num if backtrack(index + 1): return True grid[row, col] = 0 # Reset on failure return False # No valid number found return backtrack(0) # Start backtracking def generate_grid(): """Generates a 9x9 grid while keeping predefined values fixed.""" grid = np.zeros((9, 9), dtype=int) # Step 1: Predefined numbers (1-based indexing given, convert to 0-based) predefined = { (0, 7): 2, # Row 1, Column 8 (1, 8): 5, # Row 2, Column 9 @@ -38,18 +71,11 @@ def generate_grid(): for (r, c), val in predefined.items(): grid[r, c] = val # Step 2: Fill remaining numbers with a valid Sudoku-like solution if not fill_grid(grid, predefined): raise Exception("Failed to generate a valid grid.") # Step 3: Ensure row GCD is greater than 3x3 square GCD for row in range(9): square_x, square_y = (row // 3) * 3, (row % 3) * 3 square_numbers = [grid[i, j] for i in range(square_x, square_x+3) for j in range(square_y, square_y+3)] @@ -59,10 +85,13 @@ def generate_grid(): row_gcd = gcd_of_list(row_numbers) if row_gcd <= square_gcd: # Adjust row by swapping values (excluding predefined ones) for i in range(9): if (row, i) not in predefined: new_val = random.randint(1, 9) while new_val in grid[row, :] or new_val in grid[:, i]: # Ensure uniqueness new_val = random.randint(1, 9) grid[row, i] = new_val return grid @@ -72,4 +101,4 @@ def generate_grid(): end_time = time.time() print(grid) print(f"Execution Time: {end_time - start_time:.4f} seconds") -
Jan 30, 2025 . 1 changed file with 0 additions and 0 deletions.There are no files selected for viewing
File renamed without changes. -
Jan 30, 2025 .There are no files selected for viewing
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters. Learn more about bidirectional Unicode charactersOriginal file line number Diff line number Diff line change @@ -0,0 +1,75 @@ import numpy as np import math import random import time def gcd_of_list(lst): """Returns GCD of a list of numbers, ignoring zeros.""" filtered_lst = [num for num in lst if num != 0] # Ignore zeros if not filtered_lst: return 0 # If all are zeros, return 0 result = filtered_lst[0] for num in filtered_lst[1:]: result = math.gcd(result, num) if result == 1: # No need to continue if GCD is already 1 return 1 return result def generate_grid(): """Generates a 9x9 grid while keeping predefined values fixed.""" # Step 1: Initialize the grid with 0s grid = np.zeros((9, 9), dtype=int) # Step 2: Predefined numbers (1-based indexing given, convert to 0-based) predefined = { (0, 7): 2, # Row 1, Column 8 (1, 8): 5, # Row 2, Column 9 (2, 1): 2, # Row 3, Column 2 (3, 2): 0, # Row 4, Column 3 # Row 5 is empty (5, 3): 2, # Row 6, Column 4 (6, 4): 0, # Row 7, Column 5 (7, 5): 2, # Row 8, Column 6 (8, 6): 5 # Row 9, Column 7 } # Place predefined values for (r, c), val in predefined.items(): grid[r, c] = val # Step 3: Fill 3x3 squares with unique numbers while avoiding predefined spots for i in range(3): for j in range(3): numbers = list(range(1, 10)) # Numbers 1-9 random.shuffle(numbers) for x in range(3): for y in range(3): row, col = i * 3 + x, j * 3 + y if (row, col) not in predefined: # Skip predefined cells grid[row, col] = numbers.pop() # Step 4: Ensure row GCD is greater than 3x3 square GCD for row in range(9): square_x, square_y = (row // 3) * 3, (row % 3) * 3 square_numbers = [grid[i, j] for i in range(square_x, square_x+3) for j in range(square_y, square_y+3)] square_gcd = gcd_of_list(square_numbers) row_numbers = list(grid[row, :]) row_gcd = gcd_of_list(row_numbers) if row_gcd <= square_gcd: # Adjust row to have a higher GCD for i in range(9): if (row, i) not in predefined: # Modify only if not predefined grid[row, i] = random.randint(1, 9) # Replace with a new random number return grid # Measure Execution Time start_time = time.time() grid = generate_grid() end_time = time.time() print(grid) print(f"Execution Time: {end_time - start_time:.4f} seconds")