반응형
# sudoku using python
def is_valid_move(board, row, col, num):
"""
Check if placing 'num' at position (row, col) is a valid move.
"""
# Check the row
if num in board[row]:
return False
# Check the column
if num in [board[i][col] for i in range(9)]:
return False
# Check the 3x3 subgrid
start_row, start_col = 3 * (row // 3), 3 * (col // 3)
for i in range(start_row, start_row + 3):
for j in range(start_col, start_col + 3):
if board[i][j] == num:
return False
return True
def solve_sudoku(board):
"""
Solve the Sudoku puzzle using backtracking.
"""
empty_cell = find_empty_cell(board)
if not empty_cell:
# Puzzle is solved
return True
row, col = empty_cell
for num in range(1, 10):
if is_valid_move(board, row, col, num):
board[row][col] = num
if solve_sudoku(board):
return True
# If the current placement doesn't lead to a solution, backtrack
board[row][col] = 0
# No valid move found, need to backtrack
return False
def find_empty_cell(board):
"""
Find an empty cell in the Sudoku grid.
"""
for i in range(9):
for j in range(9):
if board[i][j] == 0:
return (i, j)
return None
def print_board(board):
"""
Print the Sudoku grid.
"""
for i in range(9):
if i % 3 == 0 and i != 0:
print("- - - - - - - - - - - -")
for j in range(9):
if j % 3 == 0 and j != 0:
print("|", end=" ")
print(board[i][j], end=" ")
print()
# Example Sudoku puzzle (0 represents empty cells)
sudoku_board = [
[5, 3, 0, 0, 7, 0, 0, 0, 0],
[6, 0, 0, 1, 9, 5, 0, 0, 0],
[0, 9, 8, 0, 0, 0, 0, 6, 0],
[8, 0, 0, 0, 6, 0, 0, 0, 3],
[4, 0, 0, 8, 0, 3, 0, 0, 1],
[7, 0, 0, 0, 2, 0, 0, 0, 6],
[0, 6, 0, 0, 0, 0, 2, 8, 0],
[0, 0, 0, 4, 1, 9, 0, 0, 5],
[0, 0, 0, 0, 8, 0, 0, 7, 9]
]
print("Sudoku Puzzle:")
print_board(sudoku_board)
print("\nSolving...\n")
if solve_sudoku(sudoku_board):
print("Sudoku Solution:")
print_board(sudoku_board)
else:
print("No solution exists.")반응형
'프로그래밍 > Python' 카테고리의 다른 글
| [python] 알고리즘 - 정렬 (0) | 2023.09.27 |
|---|---|
| [python] sudoku 만들기 - 랜덤 문제 (0) | 2023.09.27 |
| [python] How to send text messages with Python for Free (0) | 2023.09.26 |
| [python] algorithm, 알고리즘 (0) | 2023.09.20 |
| [python] GUI 비밀번호 자동 생성기 (0) | 2023.09.18 |
