Sudoku - genetický algoritmus
V posledních dnech všichni čekají na novou mutaci koronáče, britského, jihoafrického, či z jiného koutu světa. Rozhodl jsem se, že už čekat nebudu, a zamutuji si sám. Navíc jsem si u toho i něco pokřížil …
V rámci dřívějšího řešení Sudoku pomocí hrubé síly mne napadlo, zda by nešly použít pro řešení také genetické algoritmy.
Ty se používají pro hledání optimálních řešení u složitých úloh. Nejsou mně schopny zajistit to nejlepší řešení, ale mohly by najít alespoň nějaké.
Zkoušel jsem hledat na internetu a našel jsem několik pokusů o použití GA pro řešení Sudoku. Lidé je používali pro řešení konkrétních zadání, nebo pro generování nových.
Jako inspiraci jsem si vzal tohle: Solving, Rating and Generating Sudoku Puzzles with GA
Reprezentace jednoho řešení
Jedno řešení Sudoku jsem se rozhodl reprezentovat pomocí dvourozměrné matice o stranách 9×9. Vzhledek k tomu, že budu hledat řešení pro konkrétní zadání, musím zajistit, aby zadaná pole zůstala vždy na svém místě. Proto je součástí reprezentace jednoho řešení také maska o stejném rozměru, která obsahuje boolean hodnotu, zda je pozice fixní.
Podstatná otázka pro implementaci GA je, jakým způsobem budu provádět křížení dvou řešení a jak mutaci. Vyšel jsem z metody doporučené ve výše uvedeném textu, a sice takto:
- Každý podčtverec Sudoku musí vždý obsahovat všechna čísla 1..9. Na úrovni podčtverců budu tedy realizovat mutace
- Křížit dvě řešení budu tak, že budu vyměňovat jejich podčtverce jako celek
Těmito pravidly bude zajišťeno, že na úrovni podčtverců budu mít vždy správný počet čísel. Optimalizace se bude hledat na úrovni řádků a sloupců.
Pro implementaci dvourozměrného pole jsem použil numpy.
Postup řešení
Nejdříve nějaké základní definice, abych měl z čeho vycházet:
import numpy as np
import random
random.seed(0)
WIDTH = 9
GRID = WIDTH // 3
POPULATION_SIZE = 6
MAX_ITERATION = 10000
MUTATE_PROBABILITY = 0.5
SAMPLE = '003870509060032180049651230016200053050006072072305010200768000000020700730510000'
def grid(a, i):
j, k = (i // GRID) * GRID, (i % GRID) * GRID
return a[j:j+GRID, k:k+GRID]
Vzorek pro řešení je zadán jako řetězec SAMPLE (jedná se o zřetězené řádky, kdy neznámé pozice jsou reprezentovány 0).
Funkce grid je pomocná. Vybere mně jeden podčtverec s rozměrem 3×3 z celkové matice.
Třída Solution
Reprezentuje jedno řešení Sudoku. Zahrnuje matici s konkrétním řešením a matici masky fixních pozic.
class Solution:
def __init__(self, data, mask):
self._data = data
self._mask = mask
def __lt__(self, other):
return id(self) < id(other)
def data(self):
return self._data
def clone(self):
return Solution(np.copy(self._data), self._mask)
def fitness(self):
return sum([WIDTH - len(set(self._data[i, :])) for i in range(WIDTH)]) + sum([WIDTH - len(set(self._data[:, i])) for i in range(WIDTH)])
def mutate(self, probability):
def mutate_grid(i):
g = grid(self._data, i)
t = np.where(grid(self._mask, i))
if len(t[0]) >= 2 and random.random() < probability:
u, v = random.randrange(len(t[0])), random.randrange(len(t[0]))
x1, y1 = t[0][u], t[1][u]
x2, y2 = t[0][v], t[1][v]
g[x1, y1], g[x2, y2] = g[x2, y2], g[x1, y1]
for g in range(WIDTH):
mutate_grid(g)
return self
metoda fitness
Tahle metoda mně spočítá, jak „dobré“ je dané řešení. Jedná se o součet všech konfliktů na řádcích a ve sloupcích. Čím větší hodnota vyjde, tím horší řešení to je.
V případě, že vyjde fitness == 0, pak jsem našel správné řešení zadaného Sudoku.
metoda mutate
Jejím účelem je trochu zmutovat stávající řešení.
Projdu tedy postupně všechny podčtverce a zmutuji každý zvláště.
V rámci jednoho podčtverce hledám ty pozice, které mohu přesouvat (podle masky), a ty pak vzájemně vyměním. Vše je ještě omezeno pravděpodobností, takže mutace vznikají jen někdy.
Třída SolutionGenerator
Jedná se o pomocnou třídů pro inicializaci populace GA.
Ze zadaného vzorku Sudoku vytvoří jedno řešení, které následně mutuje, a tím dodává další řešení pro naplnění populace.
class SolutionGenerator:
def __init__(self, sample):
a = np.array([int(i) for i in sample]).reshape(WIDTH, WIDTH)
m = np.logical_not(np.array(a, dtype=bool))
all_nums = set(range(1, WIDTH+1))
for gi in range(WIDTH):
g = grid(a, gi)
missing = all_nums - set(g.flatten())
places = np.where(g == 0)
for i, v in enumerate(missing):
g[places[0][i], places[1][i]] = v
self._init = Solution(a, m)
def __iter__(self):
return self
def __next__(self):
self._init = self._init.clone().mutate(0.5)
return self._init
Třída GA
No a tady se již dostávám k jádru řešení, tedy k implementaci vlastního genetického algoritmu.
Nejdříve zdrojová třída, a pak nějaké komentáře k řešení:
class GA:
PARENTS = 2
def __init__(self, population_size, solution_generator):
self.population_size = population_size
self.population = []
while len(self.population) < population_size:
solution = next(solution_generator)
self.population.append((solution.fitness(), solution))
def termination_criteria(self):
return [s for f, s in self.population if f == 0]
def select_parents(self):
res = []
coefficient = sum([1/f for f, s in self.population])
while len(res) < self.PARENTS:
threshold = random.random()
fitness = 0.0
for f, s in self.population:
fitness += 1 / f / coefficient
if fitness >= threshold and s not in res:
res.append(s)
break
return res
@staticmethod
def crossover(parents):
def swap_grid(g1, g2):
for r in range(g1.shape[0]):
for c in range(g1.shape[1]):
g1[r, c], g2[r, c] = g2[r, c], g1[r, c]
child_1 = parents[0].clone()
child_2 = parents[1].clone()
for i in range(0, WIDTH, 2):
swap_grid(grid(child_1.data(), i), grid(child_2.data(), i))
return [child_1, child_2]
def reduce_population(self):
while len(self.population) > self.population_size:
max_fitness = max([f for f, s in self.population])
remove_index = [i for i, p in enumerate(self.population) if p[0] == max_fitness][0]
self.population.pop(remove_index)
def run(self, max_iterations):
for iteration in range(max_iterations):
solutions = self.termination_criteria()
if solutions:
return solutions
for child in GA.crossover(self.select_parents()):
child.mutate(MUTATE_PROBABILITY)
self.population.append((child.fitness(), child))
self.reduce_population()
else:
best = sorted(self.population)[0]
print(f"BEST FITNESS: {best[0]}")
return []
Do konstruktoru předám požadovanou velikost populace a generátor, kterým je možné si populaci naplnit.
Vlastní populace je reprezentována jako pole dvojic: <fitness, solution>
metoda termination_criteria
Metoda vyhodnotí, jestli některé řešení z populace nevyhovuje konečnému řešení. Hledám tedy ta řešení, která mají fitness == 0. Pokud se nějaká taková najdou, pak se vráci jako seznam těchto řešení.
metoda select_parent
Ta mně má najít rodiče, které budu vzájemně křížit. V tomto řešení hledám 2 rodiče. Jako metodu jsem použil „Roulette Wheel Selection“ s pravděpodobností výběru řešení odpovídající jejímu fitness. Výsledkem volání je seznam vybraných rodičů.
metoda crossover
Toto je implementace křížení dvou rodičů.
Parametrem jsou vybraní rodiče. Vytvořím dva potomky, u nichž jsou křížově prohozeny jejich podčtverce. Výsledkem metody jsou dva noví potomci.
metoda reduce_population
Po křížení mně přibudou v populaci dvě nová řešení. Aby se mně populace nerozrůstala, provedu její redukci a vyhodím nejhorší řešení dle jejich fitness.
metoda run
Toto je výkonné tělo GA.
Jako parametr dostane maximální počet iterací, které jsem ochoten provést. Pokud se v rámci těchto iterací nepodaří najít řešení, běh GA končí s tím, že řešení nenašel.
Postup lze shrnout takto:
- Vlastní běh provádím v iteracích, jejich maximální možný počet byl zadán parametrem
- V rámci jedné itarace pak:
- zjistím, zda náhodou nějaké řešení nesplňuje kritéria pro ukončení; pokud ano, pak mám řešení a končím
- vyberu dva rodiče pro křížení
- provedu křížení
- pro každého nově vzniklého potomka provedu jeho mutaci a následně zařazení do populace
- zredukuji populaci
A to je vše. Takto to vypadá, pokud to celé spustím:
sols = GA(POPULATION_SIZE, SolutionGenerator(SAMPLE)).run(MAX_ITERATION)
if sols:
for s in sols:
print(s.data())
else:
print("NO SOLUTION FOUND")
Zkoušel jsem trochu experimentovat se složitostí Sudoku a parametry, které je potřeba pro jeho vyřešení.
Vytvořil jsem si sady po čtyřech zadáních se 40, 50 a 60 neznámými políčky.
Zkoušel jsem nastavit parametry:
- velikost populace
- maximální počet iterací
- pravděpodobnost mutace
Takhle to vypadalo. Jednotlivé skupiny testů je třeba odkomentovat.
random.seed(0)
# 60 holes
SAMPLES = [
'000800060567930004000001030916000000008000000002300016000700005000000000000000020',
'000000200000030900060000003180000000645000820003100000000000009090004030000903080',
'000000000003008000000000048438000012075000000009001005060007003080050000050800000',
'000000040043000100000001203004000890009840000000000000501900008400000007000010050',
]
POPULATION_SIZE = 20
MAX_ITERATION = 200000
MUTATE_PROBABILITY = 0.4
# 50 holes
# SAMPLES = [
# '023004569007000000000051230910047003058096000072000906001760045000000000700500000',
# '500000040020000950060020170180540007600307021900000005350008000700014000010050704',
# '006204307040000000002630108400006910005002800020001075004020000000453690001060000',
# '002050040900600000075400200150230006369800700200060500501000068400020900000300002',
# ]
# POPULATION_SIZE = 20
# MAX_ITERATION = 200000
# MUTATE_PROBABILITY = 0.4
# 40 holes
# SAMPLES = [
# '023004509560932084000051037900000853050196000402305006090000000005023701734509600',
# '031700000427800950000420003002506397045300801070180465000270610098014030200900004',
# '000090350500710260702635140408076010175042806600000000964020580000400091050060024',
# '800000600940680070000491083150207006309805000280109534501974300030506007090010050',
# ]
# POPULATION_SIZE = 6
# MAX_ITERATION = 50000
# MUTATE_PROBABILITY = 0.4
for s in SAMPLES:
sols = GA(POPULATION_SIZE, SolutionGenerator(s)).run(MAX_ITERATION)
if sols:
for s in sols:
print(s.data())
else:
print("NO SOLUTION FOUND")
print("-" * 22)
U všech jsem nakonec našel nějaké řešení s výjimkou jednoho vzorku s 50-ti děrami. Tam se řešení najít nepovedlo, ani když jsem nafoukl počet iterací.
A to je zatím vše.
-
Připojuji se k poděkování za článek o GA.
BTW: Když se mi před cca 15 roky dostalo pod ruku první sudoku, tak jsem si na to hned udělal v Pythonu malý prográmek a od té doby už jsem neměl potřebu sudoku počítat z hlavy.
Ten můj prográmek to řeší tak, jak by to řešil člověk.
Tedy hledá, číslo, které může určit se 100% jistotou, že do prázdného místa patří.
Pokud takové nenajde, tak hledá pozici, do které pasuje nejméně číslic, postupně je dosadí a pokračuje dál, jako by to byly dvě rozdílné zadání.
U těch těžších sudoku, kde už toho chybí hodně občas najde víc než jedno správné řešení.Hlavní kód obstarávají 2 funkce na cca 20 řádků.
-
Filip JirsákStříbrný podporovatelU těch těžších sudoku, kde už toho chybí hodně občas najde víc než jedno správné řešení.
Byl by příklad takového zadání? Podle mne správně zadané Sudoku je takové, které vede na právě jedno řešení.
ČLÁNKY DO MAILU