{"action":"created","issue":{"url":"https://api.github.com/repos/heyLu/mukanren-presentation/issues/4","labels_url":"https://api.github.com/repos/heyLu/mukanren-presentation/issues/4/labels{/name}","comments_url":"https://api.github.com/repos/heyLu/mukanren-presentation/issues/4/comments","events_url":"https://api.github.com/repos/heyLu/mukanren-presentation/issues/4/events","html_url":"https://github.com/heyLu/mukanren-presentation/issues/4","id":53380883,"number":4,"title":"Incorrect or incomplete solutions","user":{"login":"heyLu","id":527119,"avatar_url":"https://avatars.githubusercontent.com/u/527119?v=3","gravatar_id":"","url":"https://api.github.com/users/heyLu","html_url":"https://github.com/heyLu","followers_url":"https://api.github.com/users/heyLu/followers","following_url":"https://api.github.com/users/heyLu/following{/other_user}","gists_url":"https://api.github.com/users/heyLu/gists{/gist_id}","starred_url":"https://api.github.com/users/heyLu/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/heyLu/subscriptions","organizations_url":"https://api.github.com/users/heyLu/orgs","repos_url":"https://api.github.com/users/heyLu/repos","events_url":"https://api.github.com/users/heyLu/events{/privacy}","received_events_url":"https://api.github.com/users/heyLu/received_events","type":"User","site_admin":false},"labels":[],"state":"open","locked":false,"assignee":null,"milestone":null,"comments":1,"created_at":"2015-01-05T10:06:47Z","updated_at":"2015-01-09T13:13:27Z","closed_at":null,"body":"We're still not solving certain nonograms, let's collect them here.\r\n\r\n* the [famous one](http://jowang.name/dotpix/#/play/18): most likely requires guessing\r\n\r\n    ```prolog\r\n    nonogramGenForceLimes(\r\n        [[6],[1,1],[1,1,1,1],[1,1,1,1],[1,1,1,1],[1,1,1,1],[1,1,1,1], [1,1,1,1],[1,1],[6]],\r\n        [[6],[1,1],[1,1,1,1],[1,4,1],[1,1],[1,1],[1,4,1],[1,1,1,1],[1,1],[6]],\r\n        F, _),\r\n        printNonogram(F).\r\n    ```\r\n* a [bigger one](http://www.janko.at/Raetsel/Nonogramme/338.a.htm), where many values are missing\r\n\r\n    ```prolog\r\n    nonogramGenForceLimes(\r\n        [[9],[7,2],[2,5,2],[2,2,2,2],[1,3,3,1],[1,1],[1,2,2,1],[1,2,2,1],[1,1],[1,1,1],[1,2,1],[2,1,2,2],[2,5,2],[2,2],[9]],\r\n        [[9],[2,2],[2,2],[2,2],[5,2,1,1],[5,2,1,1],[3,1,1,1,1],[3,1,1],[5,2,1,1],[1,2,2,3,1],[1,1,2,1],[2,2],[2,2],[2,2],[9]],\r\n        F, _),\r\n        printNonogram(F).\r\n    ```"},"comment":{"url":"https://api.github.com/repos/heyLu/mukanren-presentation/issues/comments/69332372","html_url":"https://github.com/heyLu/mukanren-presentation/issues/4#issuecomment-69332372","issue_url":"https://api.github.com/repos/heyLu/mukanren-presentation/issues/4","id":69332372,"user":{"login":"heyLu","id":527119,"avatar_url":"https://avatars.githubusercontent.com/u/527119?v=3","gravatar_id":"","url":"https://api.github.com/users/heyLu","html_url":"https://github.com/heyLu","followers_url":"https://api.github.com/users/heyLu/followers","following_url":"https://api.github.com/users/heyLu/following{/other_user}","gists_url":"https://api.github.com/users/heyLu/gists{/gist_id}","starred_url":"https://api.github.com/users/heyLu/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/heyLu/subscriptions","organizations_url":"https://api.github.com/users/heyLu/orgs","repos_url":"https://api.github.com/users/heyLu/repos","events_url":"https://api.github.com/users/heyLu/events{/privacy}","received_events_url":"https://api.github.com/users/heyLu/received_events","type":"User","site_admin":false},"created_at":"2015-01-09T13:13:26Z","updated_at":"2015-01-09T13:13:26Z","body":"We can now solve the above two, putting the rows and columns in one list and sorting it by the number of possibilities per line once at the start.\r\n\r\nHowever, we can't solve bigger problems like the following two:\r\n\r\n* [scoccer player](https://commons.wikimedia.org/wiki/File:Paint_by_numbers_Animation.gif)\r\n\r\n    ```prolog\r\n    nonogramGenForceLimes(\r\n        [[3],[5],[3,1],[2,1],[3,3,4],[2,2,7],[6,1,1],[4,2,2],[1,1],[3,1],[6],[2,7],[6,3,1],[1,2,2,1,1],[4,1,1,3],[4,2,2],[3,3,1],[3,3],[3],[2,1]],\r\n        [[2],[1,2],[2,3],[2,3],[3,1,1],[2,1,1],[1,1,1,2,2],[1,1,3,1,3],[2,6,4],[3,3,9,1],[5,3,2],[3,1,2,2],[2,1,7],[3,3,2],[2,4],[2,1,2],[2,2,1],[2,2],[1],[1]],\r\n        F, _),\r\n    printNonogram(F).\r\n    ```\r\n\r\n    forcing doesn't help us much here, only giving us about 10 fields.\r\n* \"genie\", an example that's distributed with this [nonogram solver](http://jsimlo.sk/griddlers/)\r\n\r\n    ```\r\n    nonogramSolveSorted([[20, 5], [15, 3, 3], [11, 3, 5], [8, 5, 2, 2], [6, 2, 2, 5], [5, 10, 3], [4, 4, 5, 2], [3, 7, 1, 6], [2, 19, 3], [2, 21, 2, 1], [1, 6, 1, 14, 1], [1, 6, 13, 1], [1, 5, 11, 1], [4, 12], [3, 11], [7, 3, 10], [1, 3, 2, 1, 3, 9], [2, 1, 2, 1, 2, 1, 4, 3], [2, 5, 1, 3, 2, 2, 4], [3, 3, 1, 3, 1, 2, 5], [4, 3, 1, 3, 1, 1, 5], [2, 2, 3, 3, 2, 1, 1, 4], [1, 1, 3, 2, 4], [2, 2, 2, 2, 2, 1, 4], [5, 10, 3, 5], [2, 7, 9], [2, 3, 5, 11], [6, 22], [2, 3, 1, 10, 1], [3, 2, 3, 1, 5, 5, 2], [5, 2, 2, 1, 8, 6], [5, 2, 1, 1, 11, 6], [3, 2, 1, 3, 3, 9, 3], [3, 1, 1, 5, 10, 2], [3, 2, 2, 1, 16], [3, 2, 4, 3, 12, 6], [3, 2, 19, 1, 4], [5, 8, 7, 3, 2, 1], [7, 2, 3, 3, 3, 2, 1], [7, 12, 2, 1], [10, 4, 10, 2, 1], [12, 1, 2, 1, 2, 1], [1, 1, 4, 1, 13, 1], [3, 3, 4, 1, 1, 1, 2], [7, 4, 2, 1, 2, 2], [1, 2, 2, 7, 2, 1, 2], [4, 5, 3, 1, 2, 6], [11, 2, 3, 1, 8], [2, 12], [13, 9, 8, 9]], [[13, 3, 3, 1], [10, 2, 2, 1], [8, 4, 2, 2, 1], [7, 2, 5, 5, 1], [6, 13, 3, 1, 1], [5, 14, 1, 1, 1], [4, 13, 3, 1, 1], [4, 2, 5, 5, 1], [3, 4, 2, 2, 1], [3, 2, 2, 1], [3, 3, 2, 2, 3, 1], [2, 2, 8, 6, 1], [2, 1, 1, 3, 2, 2, 4, 2], [2, 1, 2, 2, 2, 2, 5, 2, 9], [2, 2, 3, 1, 1, 2, 2, 2, 1, 5], [1, 6, 6, 2, 1, 1, 1, 1, 2, 1], [1, 13, 2, 2, 1, 1, 2, 2, 2, 1], [1, 8, 1, 2, 2, 1, 2, 4, 1], [1, 6, 5, 4, 3, 1], [1, 6, 7, 1, 1, 2, 3, 1], [6, 1, 4, 2, 2, 7, 1], [5, 1, 1, 2, 1, 2, 2, 1], [5, 4, 4, 2, 1, 1], [6, 2, 4, 1, 1, 1, 1], [2, 3, 3, 4, 2, 1, 3], [8, 2, 4, 1, 2, 3], [2, 2, 4, 4, 2, 2, 7, 2], [2, 7, 4, 2, 1, 2, 3, 3, 1, 2, 2], [6, 4, 6, 1, 1, 11, 1, 4], [1, 10, 1, 4, 2, 14, 1, 2], [2, 1, 7, 1, 1, 1, 9, 2, 1, 2], [1, 9, 4, 1, 9, 2, 1, 2], [1, 9, 1, 12, 2, 1, 2], [1, 3, 9, 12, 2, 1, 1], [6, 11, 4, 8, 2, 1, 1], [2, 2, 14, 6, 6, 2, 1, 2], [5, 11, 7, 6, 2, 1, 1, 1], [3, 8, 1, 6, 2, 3, 1, 2, 1], [8, 3, 7, 2, 2, 2, 4, 1], [2, 5, 2, 8, 4, 2, 2, 2, 1], [1, 23, 2, 2, 1], [21, 10, 3, 1], [13, 4, 5, 4, 1], [7, 4, 2, 2, 1], [8, 1]], F)\r\n    ```\r\n\r\n    even `nonogramGenForce` runs out of stack space. the `cols` call in `commons` takes too long, e.g. `length(L, 45), time((possibilities([1,1,1,1], L, PS), commons(PS, C))).` already about 10 seconds.\r\n\r\n    we could fix this by writing a combination of `possibilities` and `commons`, that aggregates the possibilities while generating them."}}