Générateur et Solveur de Sudoku en Python
Transféré par
Céline LuttiGénérateur et Solveur de Sudoku en Python
Transféré par
Céline Lutti## Générateur Solveur Sudoku ##
## Générer une grille complète
import random
def is_valid(board, row, col, num):
for i in range(9):
if board[row][i] == num or board[i][col] == num:
return False
startRow, startCol = 3 * (row // 3), 3 * (col // 3)
for i in range(startRow, startRow + 3):
for j in range(startCol, startCol + 3):
if board[i][j] == num:
return False
return True
def fill_board(board):
for i in range(9):
for j in range(9):
if board[i][j] == 0:
nums = list(range(1, 10))
[Link](nums)
for num in nums:
if is_valid(board, i, j, num):
board[i][j] = num
if fill_board(board):
return True
board[i][j] = 0
return False
return True
def generate_complete_board():
board = [[0] * 9 for _ in range(9)]
fill_board(board)
return board
## Retirer des chiffres pour créer un puzzle
def copy_board(board):
return [row[:] for row in board]
def is_solvable(board):
def solve(board):
for i in range(9):
for j in range(9):
if board[i][j] == 0:
for num in range(1, 10):
if is_valid(board, i, j, num):
board[i][j] = num
if solve(board):
return True
board[i][j] = 0
return False
return True
return solve(copy_board(board))
def generate_puzzle(board, clues=30):
while sum([Link](0) for row in board) < 81 - clues:
row, col = [Link](0, 8), [Link](0, 8)
while board[row][col] == 0:
row, col = [Link](0, 8), [Link](0, 8)
removed_num = board[row][col]
board[row][col] = 0
if not is_solvable(board):
board[row][col] = removed_num
return board
def generate_sudoku(clues=30):
board = generate_complete_board()
puzzle = generate_puzzle(board, clues)
return puzzle
## Solveur du sudoku
def print_board(board):
for row in board:
print(" ".join(str(num) if num != 0 else '.' for num in row))
def solve_sudoku(board):
def solve(board):
for i in range(9):
for j in range(9):
if board[i][j] == 0:
for num in range(1, 10):
if is_valid(board, i, j, num):
board[i][j] = num
if solve(board):
return True
board[i][j] = 0
return False
return True
solve(board)
return board
## Exemple utilisation
if __name__ == "__main__":
puzzle = generate_sudoku(clues=30)
print("Generated Sudoku Puzzle:")
print_board(puzzle)
print("\nSolved Sudoku:")
solve_sudoku(puzzle)
print_board(puzzle)
## Générateur de sudoku ##
import random
def is_valid(board, row, col, num):
for i in range(9):
if board[row][i] == num or board[i][col] == num:
return False
startRow, startCol = 3 * (row // 3), 3 * (col // 3)
for i in range(startRow, startRow + 3):
for j in range(startCol, startCol + 3):
if board[i][j] == num:
return False
return True
def fill_board(board):
for i in range(9):
for j in range(9):
if board[i][j] == 0:
nums = list(range(1, 10))
[Link](nums)
for num in nums:
if is_valid(board, i, j, num):
board[i][j] = num
if fill_board(board):
return True
board[i][j] = 0
return False
return True
def generate_complete_board():
board = [[0] * 9 for _ in range(9)]
fill_board(board)
return board
def copy_board(board):
return [row[:] for row in board]
def is_solvable(board):
def solve(board):
for i in range(9):
for j in range(9):
if board[i][j] == 0:
for num in range(1, 10):
if is_valid(board, i, j, num):
board[i][j] = num
if solve(board):
return True
board[i][j] = 0
return False
return True
return solve(copy_board(board))
def generate_puzzle(board, clues=30):
while sum([Link](0) for row in board) < 81 - clues:
row, col = [Link](0, 8), [Link](0, 8)
while board[row][col] == 0:
row, col = [Link](0, 8), [Link](0, 8)
removed_num = board[row][col]
board[row][col] = 0
if not is_solvable(board):
board[row][col] = removed_num
return board
def generate_sudoku(clues=30):
board = generate_complete_board()
puzzle = generate_puzzle(board, clues)
return puzzle
## Soleur de sudoku ##
def print_board(board):
for row in board:
print(" ".join(str(num) if num != 0 else '.' for num in row))
def solve_sudoku(board):
def solve(board):
for i in range(9):
for j in range(9):
if board[i][j] == 0:
for num in range(1, 10):
if is_valid(board, i, j, num):
board[i][j] = num
if solve(board):
return True
board[i][j] = 0
return False
return True
solve(board)
return board
## Interface utilisateur pour jouer ##
def get_user_input():
while True:
user_input = input("Enter your move (row col num) or 'q' to quit: ").strip()
if user_input.lower() == 'q':
return None, None, None
try:
row, col, num = map(int, user_input.split())
if 1 <= row <= 9 and 1 <= col <= 9 and 1 <= num <= 9:
return row - 1, col - 1, num
else:
print("Invalid input. Row, column, and number must be between 1 and
9.")
except ValueError:
print("Invalid input format. Please enter row, column, and number
separated by spaces.")
def play_sudoku():
puzzle = generate_sudoku(clues=30)
solution = copy_board(puzzle)
solve_sudoku(solution)
while True:
print_board(puzzle)
row, col, num = get_user_input()
if row is None:
print("Thanks for playing!")
break
if puzzle[row][col] != 0:
print("This cell is already filled. Please choose another cell.")
elif not is_valid(puzzle, row, col, num):
print("Invalid move. This number cannot be placed here.")
else:
puzzle[row][col] = num
if puzzle == solution:
print("Congratulations! You have solved the Sudoku puzzle!")
break
if __name__ == "__main__":
play_sudoku()
pip install colorama tabulate
import random
from colorama import Fore, Style, init
from tabulate import tabulate
init(autoreset=True)
def is_valid(board, row, col, num):
for i in range(9):
if board[row][i] == num or board[i][col] == num:
return False
startRow, startCol = 3 * (row // 3), 3 * (col // 3)
for i in range(startRow, startRow + 3):
for j in range(startCol, startCol + 3):
if board[i][j] == num:
return False
return True
def fill_board(board):
for i in range(9):
for j in range(9):
if board[i][j] == 0:
nums = list(range(1, 10))
[Link](nums)
for num in nums:
if is_valid(board, i, j, num):
board[i][j] = num
if fill_board(board):
return True
board[i][j] = 0
return False
return True
def generate_complete_board():
board = [[0] * 9 for _ in range(9)]
fill_board(board)
return board
def copy_board(board):
return [row[:] for row in board]
def is_solvable(board):
def solve(board):
for i in range(9):
for j in range(9):
if board[i][j] == 0:
for num in range(1, 10):
if is_valid(board, i, j, num):
board[i][j] = num
if solve(board):
return True
board[i][j] = 0
return False
return True
return solve(copy_board(board))
def generate_puzzle(board, clues=30):
while sum([Link](0) for row in board) < 81 - clues:
row, col = [Link](0, 8), [Link](0, 8)
while board[row][col] == 0:
row, col = [Link](0, 8), [Link](0, 8)
removed_num = board[row][col]
board[row][col] = 0
if not is_solvable(board):
board[row][col] = removed_num
return board
def generate_sudoku(clues=30):
board = generate_complete_board()
puzzle = generate_puzzle(board, clues)
return puzzle
def print_board(board, original_board):
table = []
for i in range(9):
row = []
for j in range(9):
if original_board[i][j] == 0 and board[i][j] != 0:
[Link]([Link] + str(board[i][j]) + Style.RESET_ALL)
elif board[i][j] == 0:
[Link]('.')
else:
[Link]([Link] + str(board[i][j]) + Style.RESET_ALL)
[Link](row)
print(tabulate(table, tablefmt="grid"))
def solve_sudoku(board):
def solve(board):
for i in range(9):
for j in range(9):
if board[i][j] == 0:
for num in range(1, 10):
if is_valid(board, i, j, num):
board[i][j] = num
if solve(board):
return True
board[i][j] = 0
return False
return True
solve(board)
return board
def get_user_input():
while True:
user_input = input("Enter your move (row col num) or 'q' to quit: ").strip()
if user_input.lower() == 'q':
return None, None, None
try:
row, col, num = map(int, user_input.split())
if 1 <= row <= 9 and 1 <= col <= 9 and 1 <= num <= 9:
return row - 1, col - 1, num
else:
print("Invalid input. Row, column, and number must be between 1 and
9.")
except ValueError:
print("Invalid input format. Please enter row, column, and number
separated by spaces.")
def play_sudoku():
puzzle = generate_sudoku(clues=30)
original_puzzle = copy_board(puzzle)
solution = copy_board(puzzle)
solve_sudoku(solution)
while True:
print_board(puzzle, original_puzzle)
row, col, num = get_user_input()
if row is None:
print("Thanks for playing!")
break
if original_puzzle[row][col] != 0:
print("This cell is already filled. Please choose another cell.")
elif not is_valid(puzzle, row, col, num):
print("Invalid move. This number cannot be placed here.")
else:
puzzle[row][col] = num
if puzzle == solution:
print("Congratulations! You have solved the Sudoku puzzle!")
break
if __name__ == "__main__":
play_sudoku()
# Bibliothèques:
# colorama pour la coloration des chiffres.
# tabulate pour afficher la grille sous forme de tableau.
# Fonctions:
# print_board: Affiche la grille avec les chiffres d'origine en rouge,
# les chiffres remplis par l'utilisateur en vert et les cases vides en blanc.
# play_sudoku:
# Gère l'interaction utilisateur, affiche la grille, et permet à l'utilisateur d'entrer
des mouvements
# avec les chiffres colorés pour mieux visualiser l'état du puzzle.
# Affichage:
# La grille est affichée sous forme de tableau avec une bordure pour une
meilleure lisibilité.
# Les chiffres d'origine sont en rouge ([Link]), et les chiffres entrés par
l'utilisateur sont en vert ([Link]).
# Ce programme devrait être exécuté dans un terminal qui supporte les séquences
ANSI pour les couleurs,
# comme celui intégré dans PyCharm.
# Vous pouvez lancer le programme et interagir avec la grille directement dans le
terminal de PyCharm.
Common questions
Alimenté par l’IATo ensure solvability, the Sudoku generator employs a process of removing clues while maintaining the puzzle's solvability. This is done by attempting to remove a number from the board, creating an empty cell, and then checking if the altered board remains solvable by using the 'is_solvable' function. If the board isn't solvable after removal, the number is placed back, ensuring each puzzle remains solvable with the specified number of clues .
The manual input function incorporates checks for input validity and number range to ensure the game rules are followed and to prevent invalid or erroneous entries from disrupting gameplay. By limiting inputs to values between 1 to 9 for both row, column, and number, the function ensures entries align with Sudoku's structural requirements and prevents accidental game logic violations. This validation preserves game integrity and provides a user-friendly experience by catching errors before they impact the game .
The program's user interface enhances interaction by allowing the player to enter moves in the format 'row col num', providing immediate feedback on move validity and whether the selected number can be legally placed. The program uses color coding with colorama to highlight numbers originally present in the puzzle in red and user-added numbers in green, helping the player visually distinguish between initial puzzle values and their inputs for easier problem-solving .
The solvability check algorithm relies on a recursive backtracking method, which can be inefficient due to its exhaustive search nature. It may explore many redundant paths when the puzzle difficulty increases or when many possibilities exist. To mitigate these inefficiencies, improvements such as constraint propagation or more sophisticated methods like the dancing links algorithm could be integrated to reduce unnecessary computations. Additionally, heuristics to choose the most constrained cell first (minimum remaining values) can lessen the search space and improve solving efficiency .
Creating a copy of the Sudoku board when checking for solvability is necessary to preserve the original puzzle state. When trying to solve the board for checking solvability, the algorithm temporarily fills empty cells. Without a copy, these changes would alter the initial puzzle, making it different from what was intended for the player. Thus, maintaining a separate copy ensures the original puzzle remains unchanged while testing the game's solvability .
The Sudoku solver algorithm uses a backtracking approach. It systematically attempts to fill empty cells with numbers from 1 to 9. For each number, it checks if placing it would result in a valid board state using the 'is_valid' function. If a valid placement is found, the algorithm proceeds recursively. If an invalid board state is encountered, it backtracks by removing the last placed number and trying the next possibility. This exhaustive search continues until a solution or all possibilities are exhausted .
The program prevents overwriting of initial numbers by maintaining an original copy of the puzzle and checking this before allowing a user's move. During gameplay, if a user attempts to place a number in a cell already filled in the original puzzle (i.e., not a 0), the program identifies this action and prompts the user to select another cell. This approach ensures that initial conditions of the puzzle are intact and not altered inadvertently .
The method's advantage lies in its ability to generate diverse and unique Sudoku puzzles each time by randomizing the order in which numbers are tried when filling the grid, leading to different puzzle configurations even with the same logic. However, its disadvantage is that it may lead to longer computation times due to potential recursive backtracking when an attempted number fails in multiple scenarios. Random guessing might not always be efficient and could lead to many recursive calls, affecting performance .
Color coding enhances the visual experience by making it easier for players to differentiate between numbers originally present in the puzzle and those they have entered. Original numbers are displayed in red, while user-inputted numbers appear in green. This distinction helps players focus on solving the puzzle and avoid overwriting given numbers, thus aiding in visual management and decision-making during gameplay .
The 'is_valid' function checks the legality of placing a number in a Sudoku cell by verifying three conditions: the number must not appear in the same row, the same column, or the same 3x3 subgrid containing the cell in question. The function iterates through the row and column indices to check for duplicates and computes the starting indices of the 3x3 subgrid to perform a similar check within that region .