{"entities":{"Q5958200":{"pageid":8135002,"ns":120,"title":"Item:Q5958200","lastrevid":47754526,"modified":"2026-01-02T14:51:48Z","type":"item","id":"Q5958200","labels":{"en":{"language":"en","value":"A probabilistic approach to solving crossword puzzles"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 1715195"}},"aliases":{},"claims":{"P31":[{"mainsnak":{"snaktype":"value","property":"P31","hash":"fd5912e4dab4b881a8eb0eb27e7893fef55176ad","datavalue":{"value":{"entity-type":"item","numeric-id":56887,"id":"Q56887"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5958200$080AAA65-7109-464B-A89E-E427AAC1A0DF","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"d7d8e7e8672680be9d82c5d9b5c65360476246c1","datavalue":{"value":{"text":"A probabilistic approach to solving crossword puzzles","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q5958200$DA8CD9E9-768E-4EBC-82AC-C136314AB02F","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"b71263a80e758373b55ec122b21c23061def2d36","datavalue":{"value":"0982.68119","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5958200$A7FB77C5-765E-480A-8A49-4EED92C3B809","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"006009379f0ecace2b9256248cd0bba6d7af3025","datavalue":{"value":"10.1016/S0004-3702(01)00114-X","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5958200$480FE232-A007-4AD6-8920-E9A1C5667254","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"92953e4586e720c3bdd013770f6ffbe01a60f284","datavalue":{"value":{"entity-type":"item","numeric-id":230823,"id":"Q230823"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5958200$D68CAE35-10D4-46D6-A7A5-D9E9911A37C5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"b20ce8dc4913cbd3064ac817ed8eda11dc98371c","datavalue":{"value":{"entity-type":"item","numeric-id":235378,"id":"Q235378"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5958200$611276AF-3544-4708-AD8C-9A9C6B5BA315","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"e6b5131d95e587a950650eb15adccf3400585bd7","datavalue":{"value":{"entity-type":"item","numeric-id":235379,"id":"Q235379"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5958200$38A74508-9BED-4D8E-9CF6-0BEDFDD9D313","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"984e6510ec40a363d20e607cce2cc2f8b07918ae","datavalue":{"value":{"entity-type":"item","numeric-id":72340,"id":"Q72340"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5958200$19FE6689-7EF8-4C73-9EB6-118F473CD4AA","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"de0bbc1f0efc0eda52d8a37720ec217ae66c93cd","datavalue":{"value":{"time":"+2002-03-03T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q5958200$7408B0B0-FA0F-41CA-BAAD-C18F845E9E8F","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"1e7f9ab65f133543555837d796ba45001399b25f","datavalue":{"value":"We attacked the problem of solving crossword puzzles by computer: given a set of clues and a crossword grid, try to maximize the number of words correctly filled in. After an analysis of a large collection of puzzles, we decided to use an open architecture in which independent programs specialize in solving specific types of clues, drawing on ideas from information retrieval, database search, and machine learning. Each expert module generates a (possibly empty) candidate list for each clue, and the lists are merged together and placed into the grid by a centralized solver. We used a probabilistic representation as a common interchange language between subsystems and to drive the search for an optimal solution. Proverb, the complete system, averages 95.3\\% words correct and 98.1\\% letters correct in under 15 minutes per puzzle on a sample of 370 puzzles taken from the New York Times and several other puzzle sources. This corresponds to missing roughly 3 words or 4 letters on a daily \\(15\\times 15\\) puzzle, making Proverb a better-than-average cruciverbalist (crossword solver).","type":"string"},"datatype":"string"},"type":"statement","id":"Q5958200$317941D2-61BF-40C1-9BD2-E6BE6B1128F2","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"a0dc380a7a6964f00e6560e4112710836960e832","datavalue":{"value":"68T20","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5958200$A3A6E024-6812-423F-9C67-87EF01F15EE7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"1f66a3c6f6c4263d812ea49e5394cac6ea83ef9b","datavalue":{"value":"68T37","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5958200$EDC500DF-673C-4936-B662-9EE3B69CDA33","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"0c482855bdda0ebdf362751695e0b56892c75a86","datavalue":{"value":"1715195","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5958200$48723C30-E2C0-4073-9518-32C811013ACB","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"041569f08cb94b22569e12cd5ef535a419db2f14","datavalue":{"value":"crossword puzzles","type":"string"},"datatype":"string"},"type":"statement","id":"Q5958200$618FD070-CA23-41E5-91E2-B1FD5CC079B5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"8584c6e1f30022e38b3142ba97a768d1f1ecb116","datavalue":{"value":"probabilistic reasoning","type":"string"},"datatype":"string"},"type":"statement","id":"Q5958200$92ABFFE8-4AF1-4977-86FA-E016F90EBDFF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"d3604872cd1c96e6c8dde657fdf1aa052bd30f77","datavalue":{"value":"information retrieval","type":"string"},"datatype":"string"},"type":"statement","id":"Q5958200$B42CCA72-D317-4145-992C-2B0520E21777","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a2ec4fc41188e08e749e18c790e1493758946d55","datavalue":{"value":"loopy belief propagation","type":"string"},"datatype":"string"},"type":"statement","id":"Q5958200$F88FBB6F-3B90-4A20-AFAD-A835629D66B4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"96c19d7440b9f10381fac3614544fa4753f6b867","datavalue":{"value":"probabilistic constraint satisfaction","type":"string"},"datatype":"string"},"type":"statement","id":"Q5958200$7FF7C582-AD92-44E0-9876-1D5E018B2BF6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"6321702cb82fb5a0603c9b0c508aa4ef15348e29","datavalue":{"value":"posterior probability","type":"string"},"datatype":"string"},"type":"statement","id":"Q5958200$39576F2E-0146-454B-B188-9C86F1A93B72","rank":"normal"}],"P1463":[{"mainsnak":{"snaktype":"value","property":"P1463","hash":"505d008ba9ec699c3e03e14abcae2354bf366638","datavalue":{"value":{"entity-type":"item","numeric-id":14425,"id":"Q14425"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5958200$AF637BA8-DF45-4B90-A52A-2F2CB4A6414B","rank":"normal"}],"P1460":[{"mainsnak":{"snaktype":"value","property":"P1460","hash":"57f7fea50d2ce1b39b695c4a1313582eed405e38","datavalue":{"value":{"entity-type":"item","numeric-id":5976449,"id":"Q5976449"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5958200$10A5472B-A7B7-4755-AA59-9D4EF1E15D8C","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"836ad2a04f82225da478ca9f694f5cd99360b315","datavalue":{"value":{"entity-type":"item","numeric-id":4198056,"id":"Q4198056"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5958200$B29B5FD6-E28D-4054-83B4-37FF21D91D74","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"675045958e8c6349b2048c0aea4ffb76c75876e5","datavalue":{"value":{"entity-type":"item","numeric-id":4536707,"id":"Q4536707"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5958200$56FFD899-9BCD-4B92-BD15-5EE5FE3C1E02","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1bc7b0f82e42c56ee306811b6c3df8af19432e03","datavalue":{"value":{"entity-type":"item","numeric-id":1231783,"id":"Q1231783"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5958200$D14514AF-7DC4-4F73-B4AC-5AE9EF37691E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"320be0100130068b2dc0b1290f4357d23b143166","datavalue":{"value":{"entity-type":"item","numeric-id":4064159,"id":"Q4064159"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5958200$499CD94B-E5ED-45FD-82F3-B6B5B9F16C8F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"52aa670414d4f6fec55d4a91be050421f173db46","datavalue":{"value":{"entity-type":"item","numeric-id":2674206,"id":"Q2674206"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5958200$E9A82373-1EF1-4E36-A11C-87AFFFAFF225","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7a2d7f66eae34bce09c14e9d162a2ab247e4ed16","datavalue":{"value":{"entity-type":"item","numeric-id":3674091,"id":"Q3674091"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5958200$B59D005E-0388-4B76-A81C-B3FCDAF1C554","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"9ed6bd3ac6df9032c4319ed09d2dde231f2a2f5f","datavalue":{"value":{"entity-type":"item","numeric-id":4546684,"id":"Q4546684"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a6c2e57f16a78eb691fb012d845aa9a343a9b0d9","datavalue":{"value":{"amount":"+0.9954174757003784","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q5958200$C5DD58C4-4D4F-485B-9DAF-9B5AB4E32F1C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"7244003d0512f8191683aa7904cfaf52548f76b0","datavalue":{"value":{"entity-type":"item","numeric-id":3112651,"id":"Q3112651"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"bb39cf814525eb910225e7b7927832c4ed4535ac","datavalue":{"value":{"amount":"+0.8025521636009216","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q5958200$7F6FF271-4E17-4D25-8C44-46BF6A609A1D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"1a69e1b1650d98b6186b2115a868f6848382cd21","datavalue":{"value":{"entity-type":"item","numeric-id":4530856,"id":"Q4530856"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c0f4b967f088a9051ebdbeaea67eb30b9925488f","datavalue":{"value":{"amount":"+0.7131969928741455","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q5958200$B6315687-5967-4234-90EB-AEAF7A1ECDF5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"bf29e4ff369977301dc67e3068b300764aa7934d","datavalue":{"value":{"entity-type":"item","numeric-id":5243989,"id":"Q5243989"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"713414152b8fccbe58f36bb1814e68825b7b7f85","datavalue":{"value":{"amount":"+0.6990596055984497","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q5958200$A5B945EF-EE2A-4DBF-89A6-829402E54BA1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ba779b1862b4de38212363deb64c71360d18ef96","datavalue":{"value":{"entity-type":"item","numeric-id":4690066,"id":"Q4690066"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"2bd3444349da830cc00d69590efb9569e5faa905","datavalue":{"value":{"amount":"+0.6970444321632385","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q5958200$CAA462C6-774D-4A42-BED7-C179E210EE04","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:5958200","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:5958200"}}}}}