| Popis: |
Mestrado Bolonha em Métodos Quantitativos para a Decisão Económica e Empresaria O Sudoku é um puzzle popularmente conhecido, com aplicações em diversas áreas que se estendem desde a Criptografia à Medicina. Por ser um problema NP-completo, a maior parte dos esforços para o resolver focam-se em heurísticas e não em métodos exatos. Exemplo destes últimos são as estratégias humanas. A proposta deste Trabalho Final de Mestrado (TFM) consiste no desenvolvimento de um Sudoku Solver, em VBA. O solver desenvolvido é um algoritmo de duas fases que incorpora estratégias humanas (Fase 1) e backtracking (Fase 2). A Fase 2 só é executada se, terminada a Fase 1, não for encontrada uma solução admissível. Foi conduzida uma experiência computacional para testar a performance do solver para puzzles 9×9 de três níveis de dificuldade: fácil, moderado e difícil. Das 230 instâncias testadas, aproximadamente 55% foram resolvidas. O tempo máximo de resolução foi de 6,813 segundos, o tempo mínimo foi de 0,309 e a média do tempo total foi de 2,525 segundos. Sudoku is a popular puzzle, with applications in several areas ranging from Cryptography to Medicine. Because it is an NP-complete problem, most efforts to solve it focus on heuristics and not on exact methods. Examples of the latter are human strategies. The proposal of this Master’s Final Work (MFW) is the development of a Sudoku Solver, in VBA. The developed solver is a two-phase algorithm that incorporates human strategies (Phase 1) and a backtracking procedure (Phase 2). Phase 2 is only executed if a feasible solution has not been found after Phase 1 ends. It was conducted a computational experience to test the solver performance for 9×9 puzzles with three difficulty levels: easy, moderate, and hard. Among the 230 instances tested, approximately 55% were solved. The maximum running time was 6.813 seconds, the minimum time was 0.309, and the average total time was 2.525 seconds. info:eu-repo/semantics/publishedVersion |
