D'une manière ou d'une autre, je l'ai trouvé.
Si vous voulez résoudre des mathématiques sans puissance humaine, il est bien connu que vous pouvez le résoudre en utilisant la programmation linéaire ou le réseau de Hopfield. Cependant, je pensais qu'il serait possible de le résoudre en poussant le nombre d'essais sans connaître les règles de Sugoku, alors j'ai en fait essayé.
C'est une sorte de jeu de puzzle. Voir wikipedia pour plus de détails. Allemagne
optuna Une bibliothèque python pour l'optimisation des hyperparamètres développée par Preferred Networks. L'algorithme de recherche par hyperparamètres utilise TPE, qui est identique à HyperOpt.
En un mot, en omettant des explications détaillées, même si la cible d'optimisation est une boîte noire, cela optimisera la fonction objectif de manière agréable.
Comme mentionné ci-dessus, nous utiliserons optuna. Par conséquent, la fonction objectif est définie de manière à ce que la valeur diminue à mesure que la réponse s'approche de la bonne réponse.
La fonction objectif décide de compter le nombre de violations de règle. Ici, moins de violations sont synonymes de se rapprocher de la bonne réponse. Je ne connais pas explicitement la bonne réponse, mais comme je minimise la valeur de la fonction objectif, j'atteins finalement 0 violation et la bonne réponse.
def evaluate(answer):
#Il viole la boucle de l'allemand et renvoie le nombre. Si la réponse est correcte, l'évaluation sera 0
#La réponse est un tableau bidimensionnel 9x9 avec des nombres de 1 à 9 dans chaque élément
tmp = np.reshape(answer, [3, 3, 3, 3])
loss = np.sum((
#Nombre de violations dans chaque colonne
np.sum([np.count_nonzero(np.logical_not(np.any(answer == i, axis=0))) for i in range(9)]),
#Nombre de violations dans chaque ligne
np.sum([np.count_nonzero(np.logical_not(np.any(answer == i, axis=1))) for i in range(9)]),
#Nombre de violations par zone 3x3
np.sum([np.count_nonzero(np.logical_not(np.any(tmp == i, axis=(1, 3)))) for i in range(9)]),
))
return loss
Le nombre de violations ne compte pas le nombre de numéros en double, mais le nombre de numéros qui n'apparaissent pas.
Si les règles sont respectées, 1-9 apparaîtra une fois pour chaque condition. S'il y a des doublons en raison d'une violation de règle, le nombre d'apparitions de l'un des autres numéros a diminué à 0, alors comptez-le.
Dans le cas de la duplication, il existe différents schémas de 2 à 9 fois, mais si le nombre d'apparitions diminue, il n'y en a que 0, donc je pense qu'il sera plus simple de compter cela.
Le problème que je voulais résoudre était codé en dur dans le code source. C'est fondamentalement le même que le code de la documentation optuna.
from itertools import product
import numpy as np
import optuna
import click
"""
Le problème est https://ja.wikipedia.org/wiki/%E6%95%B0%E7%8B%À partir de l'image d'exemple AC
-----------------
|5|3| | |7| | | | |
|-+-+-+-+-+-+-+-+-|
|6| | |1|9|5| | | |
|-+-+-+-+-+-+-+-+-|
| |9|8| | | | |6| |
|-+-+-+-+-+-+-+-+-|
|8| | | |6| | | |3|
|-+-+-+-+-+-+-+-+-|
|4| | |8| |3| | |1|
|-+-+-+-+-+-+-+-+-|
|7| | | |2| | | |6|
|-+-+-+-+-+-+-+-+-|
| |6| | | | |2|8| |
|-+-+-+-+-+-+-+-+-|
| | | |4|1|9| | |5|
|-+-+-+-+-+-+-+-+-|
| | | | |8| | |7|9|
-----------------
"""
#La partie avec la valeur à l'avance
preset = {'p00': 5, 'p01': 3, 'p04': 7,
'p10': 6, 'p13': 1, 'p14': 9, 'p15': 5,
'p21': 9, 'p22': 8, 'p27': 6,
'p30': 8, 'p34': 6, 'p38': 3,
'p40': 4, 'p43': 8, 'p45': 3, 'p48': 1,
'p50': 7, 'p54': 2, 'p58': 6,
'p61': 6, 'p66': 2, 'p67': 8,
'p73': 4, 'p74': 1, 'p75': 9, 'p78': 5,
'p84': 8, 'p87': 7, 'p88': 9}
def evaluate(answer):
#Comme ci-dessus
def objective(trial):
candidate = (1, 2, 3, 4, 5, 6, 7, 8, 9)
answer = np.empty([9, 9], dtype=np.uint8)
for i, j in product(range(9), repeat=2):
key = 'p{}{}'.format(i, j)
if key in preset:
answer[i, j] = preset[key]
else:
answer[i, j] = trial.suggest_categorical(key, candidate)
return evaluate(answer)
def run(n_trials):
study_name = 'sudoku'
study = optuna.create_study(study_name=study_name, storage='sqlite:///sudoku.db', load_if_exists=True)
study.optimize(objective, n_trials=n_trials)
show_result(study.best_params, study.best_value)
df = study.trials_dataframe()
df.to_csv('tpe_result.csv')
def show_result(best_params, best_value):
for i in range(9):
for j in range(9):
key = 'p{}{}'.format(i, j)
if key in preset:
print('*{:1d}'.format(preset[key]), end='')
else:
print('{:2d}'.format(best_params[key]), end='')
print('')
print('loss: {}'.format(best_value))
@click.command()
@click.option('--n-trials', type=int, default=1000)
def cmd(n_trials):
run(n_trials)
def main():
cmd()
if __name__ == '__main__':
main()
Je suis désolé pour ceux qui ont lu jusqu'ici en prévision.
Je n'ai pas pu le résoudre du tout.
Le temps requis pour chaque évaluation est beaucoup plus long que prévu et le nombre d'essais n'est pas suffisant. Le nombre d'essais est de 0 pendant environ 7 secondes et de 200 pendant environ 25 secondes.
Même si nous continuons ainsi, il faudra des centaines de milliers à des millions d’essais pour parvenir à la bonne réponse, je pense donc qu’il est impossible d’y parvenir en réalité.
Enfin, pour le moment, la sortie au bout de 200 fois est affichée.
*5*3 5 5*7 2 6 1 2
*6 7 8*1*9*5 7 3 5
4*9*8 6 3 7 8*6 4
*8 1 4 7*6 9 7 6*3
*4 3 9*8 5*3 2 7*1
*7 8 9 3*2 1 5 4*6
3*6 1 6 7 9*2*8 7
5 7 3*4*1*9 8 1*5
4 7 6 2*8 4 3*7*9
loss: 73.0
Les nombres avec * sur le côté gauche sont les nombres du début comme indices de réponse.
Dougoku ne peut pas être résolu avec optuna (algorithme TPE). J'avais l'intention de pousser par le nombre d'essais, mais le temps de calcul était beaucoup plus long que prévu et je ne pouvais pas pousser.
optuna (algorithme TPE) prend plus de temps à échantillonner à mesure que le nombre d'essais augmente.
La cause de cet échec était le long temps de calcul de l'algorithme TPE, donc je pense que ce problème peut être résolu en utilisant un autre algorithme. Puisque l'algorithme TPE ne considère pas la distribution conditionnelle en premier lieu, c'est un algorithme plutôt inadapté pour résoudre les mathématiques.
La prochaine fois, j'aimerais essayer un algorithme qui échantillonne à partir d'une distribution conditionnelle. Par conséquent, il est nécessaire de comprendre les règles de Sugoku avant de résoudre. Cela aurait été une tentative imprudente pour parvenir à la bonne réponse sans connaître les règles de l'Allemagne comme cette fois.
Le calendrier est complètement indécis. Je pense que l'algorithme sera un système de recuit simulé, mais l'heure d'affichage est indécise car je vais l'étudier à partir de maintenant.
Recommended Posts