67 lines
2.2 KiB
Python
67 lines
2.2 KiB
Python
"""
|
|
Implementiere einen Hill-Climbing-Algorithmus, der die Zahlen in
|
|
einem SUDOKU-Feld durch vertauschen innerhalb einer Zeile so
|
|
umsortiert, dass sie die SUDOKU-Bedingung auch für die Spalten
|
|
erfüllen.
|
|
"""
|
|
|
|
import numpy as np
|
|
import random
|
|
import math
|
|
|
|
def calculate_fitness(board):
|
|
# Previous fitness
|
|
column_violations = np.sum([len(set(board[:, i])) != 9 for i in range(9)])
|
|
|
|
# plus checking 3x3 sub-grids
|
|
grid_violations = 0
|
|
for block_row in range(0, 9, 3):
|
|
for block_col in range(0, 9, 3):
|
|
# Extract the 3x3 block
|
|
block = board[block_row:block_row + 3, block_col:block_col + 3].flatten()
|
|
if len(set(block)) != 9:
|
|
grid_violations += 1
|
|
|
|
return -(column_violations + grid_violations) # Negative because we want to maximize
|
|
|
|
board = np.array([
|
|
[1, 2, 3, 4, 5, 6, 7, 8, 9],
|
|
[1, 2, 3, 4, 5, 6, 7, 8, 9],
|
|
[1, 2, 3, 4, 5, 6, 7, 8, 9],
|
|
[1, 2, 3, 4, 5, 6, 7, 8, 9],
|
|
[1, 2, 3, 4, 5, 6, 7, 8, 9],
|
|
[1, 2, 3, 4, 5, 6, 7, 8, 9],
|
|
[1, 2, 3, 4, 5, 6, 7, 8, 9],
|
|
[1, 2, 3, 4, 5, 6, 7, 8, 9],
|
|
[1, 2, 3, 4, 5, 6, 7, 8, 9]
|
|
])
|
|
|
|
board_size = len(board) # Board is always quadratic
|
|
last_fitness = calculate_fitness(board)
|
|
T = 100
|
|
|
|
print("Working...")
|
|
while calculate_fitness(board) < 0:
|
|
# swap col in row with random other col
|
|
rand_row = random.randrange(board_size)
|
|
rand_col = random.randrange(board_size)
|
|
swap_col = (rand_col + random.randrange(1, board_size)) % board_size
|
|
|
|
board[rand_row, rand_col], board[rand_row, swap_col] = board[rand_row, swap_col], board[rand_row, rand_col]
|
|
current_fitness = calculate_fitness(board)
|
|
|
|
if current_fitness >= last_fitness:
|
|
last_fitness = current_fitness
|
|
else:
|
|
p = math.e ** (-(last_fitness - current_fitness) / T) # adjusted formula
|
|
print(p) # debugging
|
|
if p > random.random(): # if probability occurs
|
|
last_fitness = current_fitness
|
|
else:
|
|
board[rand_row, swap_col], board[rand_row, rand_col] = board[rand_row, rand_col], board[rand_row, swap_col]
|
|
T = max(T - 0.01, 0.1) # Decrease T more slowly and don't let it reach 0
|
|
|
|
# print(last_fitness) # debugging
|
|
|
|
print(board)
|