XCSP 2.1 Benchmark Database

ukHeraldExtConvert

Lecoutre's category

Lecoutre's tooltips

Given a grid and a dictionary, the problem is to fulfill the grid with the words contained in the dictionary. Here, three series of grids (Herald, puzzle, Vg) and four dictionaries (lex, ogd, uk, words) have been used. Herald refers to crossword puzzles taken from the Herald Tribune (Spring, 1999), Puzzle refers to crossword puzzles mentioned in [Ginsberg, Dynamic Backtracking, JAIR, 93] and [Ginsberg et al., Search Lessons Learned from Crossword Puzzles, AAAI-90] and Vg refers to blank grids. Lex is a dictionary used in [Samaras-Stergiou, Binary encodings of non binary satisfaction problems: algorithms and experimental results, JAIR, 2005], Uk corresponds to the UK cryptic solvers dictionary, words corresponds to the dictionary found in /usr/dict/words under Linux and Ogd corresponds to a french dictionary. Lex and words are small dictionaries whereas Uk and Ogd are large ones. The model used to represent the instances is the one identified by m1 in [Beacham-Chen-Silito-vanBeek, Constraint Programming lessons learned from crossword puzzles, 2001]. However, for the Vg grids, all instances only involve constraints in extension as for these grids, putting two times the same word has been authorized. Thank you to Hadrien Cambazard, Kostas Stergiou and Julian Ullmann for their help.

Source

Comments

Number of instances: 3 (0 processed, 0 partially processed, 3 failed)

Processing completed

Partially processed

Processing failed
crossword-m1-uk-05-01_ext
crossword-m1-uk-05-02
crossword-m1-uk-05-02_ext

XCSP 2.1 Benchmarks

ukHeraldExtConvert