Utilize este identificador para referenciar este registo: http://hdl.handle.net/10400.2/1283
Título: A scale to measure the difficulty of sudoku puzzles
Autor: Coelho, José
Palavras-chave: Sudoku
Instance hardness
Transformation to SAT
Nível de dificuldade dos exemplos
Transformação em SAT
REA
Data: 2007
Editora: Universidade Aberta
Citação: Coelho, José Silva - A scale to measure the difficulty of sudoku puzzles. "Revista de Ciências da Computação" [Em linha]. ISSN 1646-6330. A. 2, vol. 2, nº 2 (2007), p. 39-55
Resumo: In the last few years, Sudoku has become a popular game, deserving the attention of many researchers. Most Sudoku puzzles are classified as easy, average and hard according to their degree of difficulty. However when asked about the criteria used to classify them, there is no clear answer. This paper presents a PnP (paper-and-pencil) method to solve and measure the degree of difficulty of Sudoku puzzles. Contrary to other methods, this method can classify the puzzles automatically without human intervention. The scale used here was inspired on the type of scale used in the snow trails: green, blue, red and black. The Sudoku puzzle is transformed to SAT, and its level is set depending on the SAT problem being easy or hard to solve in SAT, which is equivalent to the puzzle being solved using an easy or hard PnP method. A classifier and a set of classified Sudoku problems are made available on the web.
Resumo: Nos últimos anos, o Sudoku tornou-se um jogo muito popular, merecendo a atenção de muitos investigadores. A maior parte dos puzzles de Sudoku é classificada como simples, média ou difícil, consoante o seu grau de dificuldade. Contudo, quando questionados acerca do critério de classificação, não existe uma resposta clara. Este artigo apresenta um método manual para medir o grau de dificuldade dos puzzles de Sudoku. Ao contrário de outros métodos, este método classifica os puzzles automaticamente, sem intervenção humana. A escala utilizada é inspirada na escala utilizada nas pistas de neve: verde, azul, vermelho e negro. O puzzle de Sudoku é transformado num problema de SAT e o nível de dificuldade é dado pela resolução do problema de SAT, o qual é equivalente ao da resolução manual. O classificador de dificuldade e um conjunto de puzzles de Sudoku classificados estão disponíveis na Web.
URI: http://hdl.handle.net/10400.2/1283
ISSN: 1646-6330
Aparece nas colecções:REA - Revista de Ciências da Computação
Revista de Ciências da Computação

Ficheiros deste registo:
Ficheiro Descrição TamanhoFormato 
p_39_55. pdf.pdf198,89 kBAdobe PDFVer/Abrir


FacebookTwitterDeliciousLinkedInDiggGoogle BookmarksMySpace
Formato BibTex MendeleyEndnote Degois 

Todos os registos no repositório estão protegidos por leis de copyright, com todos os direitos reservados.