ads

Thursday, March 21, 2013

Online nonogram solver

This is clear javascript version of nonogram solver: http://a.teall.info/nonogram/.
Another my "just for fun" small program. It was made as simple as possible (in reasonable borders of course) and works completely on client-side browser. Algorithm uses finite-state machine to calculate possible cells to paint and eats, as I suppose, O(n2) machine time (and what do you want from NP-complete problem?). In addition there is brute-force search function in order if puzzle has no obvious solve steps but herewith has single solution. On huge grids solver runs deadly slow.


Eventually I'm a big fan of nonograms. My Android phone has CrossMe installed, and I play it often, especially if I have to wait for my wife while shoping =)
By the way, first attempt to create such solver was in 2000. We were first-year students and compete each other whose algo will solve puzzle from newspaper faster. But we even did not know about finite-state machines at that moment. I left my Intel 80486 computer to calculate grid for whole night, and after eight hours it was still unsolved =) Well, I will show my current algorithm to students after all =))

UPDATE. There is completely awesome survey about nonogram solvers and large collection of online and offline solvers and puzzles by Jan Wolter: http://webpbn.com/survey. I think everyone who interesting in nonograms will satisfied totally there. In additional, Jan presents list of puzzle exporters: http://webpbn.com/export.cgi.

UPDATE2. Great, google says this is the most popular solver we have for now: https://www.google.ru/#newwindow=1&q=online+nonogram+solver
For children getting upset with the solver: remember, a computer is not a human, it can't understand what the thing it's solving. If you have meet bad luck first time, try to use your intuition and help the solver checking/unchecking squares, and then let the solver has another try.

33 comments:

  1. i need your help. i finished typing the number in the rows and columns but when i pushed solve button it stops working and other window came out with two buttons : stop script and continue. but it is still Solving... wrote there.
    it took me 2 hour to write the numbers. Here is like 100 rows and 70 colums.
    when i push button save i got some of the code , where should i use it to not write down all the numbers again?

    ReplyDelete
    Replies
    1. You can use "Load" button to load previously saved grid code. Click "Load" button and paste code to opened dialig window. If your browser doesn't respond, you have to reload it.
      Sorry for this trouble and disappointing. It seems, that my program is unable to solve your grid in finite time because of its hugeness. As I have wrote in post below: if it will take 2 hours while solving of 90% of grid, but there will be no single solution, it will take additional 2*grid_size hours. Computer can't guess image like human can do, this is the main ussie of huge grids.

      Delete
  2. Hi, i am the same crazy anonymous who asked help before.:)) i found out how to do this but i think my computer is too weak to solve that nonogram or may be its too hard to solve for this programm . Can you please do this to me? (100 x 70) and here is the code.
    {"ver":[[12,35,19],[1,18,17],[1,20,20,13],[4,22,22],[1,5,23,23,9],[2,24,24],[4,25,25],[2,4,25,25],[3,26,26],[2,2,26,26],[4,2,26,26],[5,1,2,26,26],[1,1,2,1,26,26],[1,1,1,5,11,14,11,5],[1,1,2,2,6,5,2,5,6,3,2],[1,1,1,6,2,7,9],[1,2,26],[2,24,1],[4,6,2,11,3,6],[8,2,2,2,9,2,5],[10,3,3,2,2,6,4],[4,7,13,5,6,2,5,2,2,5],[2,2,4,2,1,6,1,2,6,4,6,5],[7,8,4,1,1,3,1,4,1,2,6,2,2,2,5],[6,2,2,4,5,1,4,1,2,7,1,1,1,5],[2,2,6,2,4,1,1,3,2,1,6,1,2,7,1,1,1,6],[5,2,2,3,2,3,3,4,5,5,2,4,2,2,2,3],[1,1,1,4,2,4,6,3,3,2,4,2,2,1,4],[3,2,1,1,4,1,14,2,2,2,3,2,2,1,1,4],[2,3,4,1,4,5,2,6,2,3,1,1,4],[1,5,9,5,5,2,2,3,4,4],[1,6,1,4,2,4,1,3,1,4,2,3,1,1,3],[1,4,2,3,2,1,1,1,3,2,1,2,4,13,4],[2,4,1,1,1,1,1,4,2,7,3,3,2,2],[3,6,1,1,4,3,2,3,2,2,2,1,12,2],[2,2,2,2,1,11,2,2,2,2,2,10,1,3,3],[2,2,2,2,2,2,10,2,2,5,1,2,8,1,1,1,1,1],[2,9,1,1,2,1,1,5,2,6,1,6,2,1,1,1,1],[1,10,2,2,2,1,2,2,2,2,1,1,2,2,1],[1,10,1,2,3,2,1,1,2,2,1,1,1,1],[2,9,1,2,1,1,2,1,7,3,3,2,1,1,2],[4,12,1,1,2,1,1,1,3,5,1,3,4],[2,8,1,10,1,1,1,8,2,1,1,1,3],[2,8,2,7,2,2,6,3,6,1,1,2,1],[3,8,8,1,1,7,9,4,2],[3,10,1,2,2,2,8,7,3,1,1,1],[4,18,3,14,13,7,2,2,2,2],[7,12,1,1,2,2,2,3,7,6,2,7,2],[20,6,4,13,2,8,8,2,1,2,1],[20,1,1,2,1,1,2,23,2,2,1],[4,2,3,7,5,11,2,21,2,2,2],[1,1,1,1,1,1,2,1,2,21,3,1,2],[1,1,1,1,1,1,1,1,2,19,3,1,2],[6,1,14,6,11,2,19,6,2],[6,1,14,6,10,3,3,19,2,3],[6,1,15,6,9,1,1,1,1,19,1,2],[6,2,15,6,9,1,1,1,1,19,1,1,3],[6,1,15,6,9,1,2,2,1,19,1,1,2],[6,1,15,6,8,1,3,1,19,2,1,2],[5,1,15,7,8,3,2,19,1,1,2],[1,1,1,1,1,1,2,1,10,19,1,1,2],[1,1,1,2,1,1,2,1,2,1,19,2,1,1],[1,1,1,1,2,1,2,1,1,2,19,2,1,1],[1,1,1,1,2,3,2,1,4,21,2,1,1],[1,1,2,1,2,9,30,3,1,2],[1,1,4,3,3,8,2,33,2],[1,2,3,10,14,30,3,3],[2,12,11,6,30,2,4],[2,13,11,6,30,2,5],[22,21,30,8]],"hor":[[6,1,2,1,4,7],[1,1,2,1,2,2,3,7],[1,1,2,1,5,2,1,5,7],[1,1,2,1,2,3,1,7,7],[6,6,2,1,10,16],[1,3,1,5,1,17,3],[2,2,2,4,3,3,1],[5,2,2,5,4,3,1],[1,3,1,2,4,9,2,1],[3,1,1,2,6,9,5,11,1],[3,2,1,1,2,1,7,5,3,2,1],[7,2,1,1,1,1,2,1,17,1,1],[1,1,1,2,1,1,1,1,1,1,14,3],[1,1,2,3,1,1,1,18,10,3],[1,2,1,2,2,3,1,15,7,2,3],[1,1,1,2,1,8,21,1,3],[1,1,1,2,2,10,10,7,1,3],[1,1,3,2,6,2,1,8,7,5],[1,1,4,2,4,3,1,6,7,4],[1,5,2,1,4,4,7,4],[1,5,3,4,7,3],[1,5,3,1,1,7,3],[1,6,2,2,1,1,1,7,2],[7,1,2,1,1,1,7,2],[7,3,2,1,4,1,1,1,7,2],[8,8,2,3,2,1,1,1,7,1],[8,12,2,2,3,1,1,7,1],[9,12,1,1,4,15],[9,5,5,7,3,6],[10,4,1,2,9,3,3],[11,4,1,1,2,3,3,10,3],[11,4,1,2,1,2,3,1,18,2,3],[12,3,3,2,5,1,1,7,2,3],[12,12,3,3,2,3,1,7,6],[12,24,4,7,5],[14,2,8,3,2,11,5],[14,1,1,7,3,2,5,4],[15,1,2,2,4,2,3,1,4],[15,1,2,4,1,4,10,2,3],[15,1,2,1,6,9,1,3],[16,6,2,2,1,1,1,7,2,2,2],[13,1,2,2,3,2,1,1,1,7,5,2],[12,1,3,3,1,2,1,1,1,7,4,1],[11,1,5,5,1,1,1,1,1,7,3,1],[10,1,1,6,1,1,1,1,1,1,7,4,1],[9,2,1,4,1,1,1,1,1,1,15,1],[8,1,1,5,1,3,1,1,1,5,6],[7,1,1,6,1,1,1,1,2,5],[6,1,5,5,1,1,4,4],[5,2,3,3,7,1,3,4],[4,1,2,2,4,6,1,2],[3,1,6,3,3,2,1,2],[2,1,2,2,1,1],[1,1,1,1,2,1,1],[1,1,1,1,7,2],[1,25,1,9,2,2],[1,25,1,1,12,1,2],[1,1,1,2,1,1,2,2,1,3],[1,1,2,1,1,1,1,1,10],[2,1,1,7,2,1,1,1,2,2,1,7],[3,1,3,9,4,1,4,4,1,6],[4,1,3,11,9,1,2,6],[5,2,12,3,6,6,6],[6,12,2,8,7],[7,15,6,27],[8,15,4,27],[9,9,32],[10,6,2,2,2,24],[11,5,2,3,2,23],[12,4,1,4,1,22],[13,3,2,1,1,3,2,21],[15,2,2,1,4,1,21],[14,2,3,1,4,1,21],[14,2,1,1,1,4,1,21],[14,2,6,1,1,4,1,21],[14,3,2,5,1,4,1,21],[13,3,2,1,4,1,21],[12,5,2,1,1,3,2,22],[12,3,1,1,4,1,22],[12,3,2,3,2,24],[11,4,2,31],[1,11,4,33],[1,10,8,4,5,27],[1,9,13,4,9,7],[1,9,12,1,7,3,6],[1,8,2,15,4,4,5],[1,8,1,1,12,2,9],[1,1,7,2,10,6,1,6,8],[1,1,7,4,1,13,2],[1,1,6,4,1,3,2],[1,1,5,4,2,2,16],[1,1,1,5,4,1,2,3],[1,1,1,5,4,1,2,1,1,2],[1,1,1,4,4,5,2,1,1],[1,1,1,3,1,4,1,4,1],[1,1,1,2,7,2,1,2],[1,1,1,2,1,5,4,3],[1,1,1,1,4,1,7,4],[1,1,1,1,2,3,5,6],[1,1,1,1,7,11]]}

    ReplyDelete
  3. I'm sorry that you have troubles with solver. You know, this is browser-powered program, and it is quite slow on huge grids. Especialy if it has no single solution. You can imagine: if it will take 2 hours while solving of 90% of grid, but there will be no single solution, it will take additional 2*grid_size hours! Human can easily solve some grids because he/she can guess encoded image. Computer can't. This is why we still rocks =)
    Once again, sorry for disappointing.

    ReplyDelete
  4. Thank you so much for aswering, do you know some of the progrem which could solve this huuuge nonogram? :))

    ReplyDelete
    Replies
    1. You can try to search "nonogram solver online" with Google. There are some of online solvers available. Unfortunately, they have its own nonogram code system, so you have to enter your nonogram once again there.
      And I'm surprised that my small simple program for students is at first place in google list, lol.
      Hope, you will get success with your nonogram =)

      Delete
    2. beacuase of great job

      Delete
  5. crappy program

    ReplyDelete
    Replies
    1. Thank you for your generous comment =) You spent your time to make world better.

      Delete
  6. Hi. I just ran across this page. I've made a bit of a hobby of testing out nonogram solvers. My survey is available at http://webpbn.com/survey/ .

    I upgraded my puzzle export page (http://webpbn.com/export.cgi) so that it can now export any of the 18,000 puzzles on webpbn.com in a format that can be loaded into your solver. Because everyone needs test data.

    I tried the first few puzzles from the sample set I use for initial tests of different solvers. It solved puzzles 1 and 6 easily and well. It found incomplete solutions to puzzles 21 and 27, and was completely unable to do anything with puzzle 23.

    It seems like you are just doing line solving, since on 27 and 23 you got just the line-solvable parts. Which is fine - most published puzzles are line-solvable. But you probably should have been able to solve puzzle 21, which is line solvable. I expect there is a bug somewhere that could easily be fixed to solve that puzzle. Aside from that, this is really pretty good for a simple solver.

    I've built a Javascript nonogram solver that is embedded in the webpbn.com site. It basically does what you do, but supports multicolor puzzles. My one cool trick was using regular expressions for line solving. I'd encode the current state of the puzzle into strings like "xx01xxx1xxx" where 0 is white, 1 is black and x is unknown. Then I'd compile a clue like "3 5" into a regular expression like /^([x0]*)[x1]{3}([x0]+)[x1]{5}([x0]*)$/. That would give me the left-most match of the blocks to the board. I could get the right-most match using a reversed clue and line state. Intersecting the two gives me cells I can mark. This worked great until browsers started competing to see whose regular expressions were faster, at which point several of them broke their regular expressions for the sake of running benchmarks faster, and I had to re-implement the whole thing as a finite state machine. Phooey.

    ReplyDelete
    Replies
    1. Hi! You have done just awesome great work! I will update this post and add links to your converter and survey article. I pleasantly surprised by this.
      Your idea to use regex is very interesting and funnily, I think it is simplest one.
      As for the bug you have found, I will try to manage to fix it, but unfortunately there is no time for this. But thank you for testing and for your attention.

      Delete
  7. Oh, and by the way, the 70x100 puzzle that some anonymous user wanted to solve in a previous comment shows a smiling man in the foreground holding an umbrella and making a V with the fingers of his other hand, while in the background there are two young women, one wearing a bikini and holding a volleyball. My C-language pbnsolve program solved it in 0.03 seconds. The puzzle is not a particularly difficult one except for being large. I am in awe of the person who transcribed all those numbers without an error. I'd find that harder to do than solving the puzzle manually.

    ReplyDelete
  8. Thanks for the solver! I use it when I'm stuck with the CrossMe app, and even when it says "solution impossible" I can usually guess how to finish it. However, this one has been giving me trouble, and there isn't a posted solution online. Maybe you can help me solve it? Here's the string, it's a 30x30:

    {"ver":[[7,13],[7,13],[8,12],[1,4,1,1,10],[4,1,1,2,1,1,9],[5,1,1,1,9],[6,8],[4,5,6,7],[7,4,6,1,6],[5,6,7,7],[4,4,2,3,4,6],[5,1,5,2,3,2,5],[5,2,2,3,1],[3,1,1,1,2],[2,2,6,4],[2,2,2,3,1],[1,2,1,1,5,1],[2,2,1,1,3,1],[1,3,4,2,1],[2,1,1,1,4],[3,8,2],[2,4,1,3],[2,1,5,1,2],[3,2,2,3],[2,1,2,2,2],[2,2,2,2],[3,5,3],[14,4],[4,8,5],[10,6]],"hor":[[3,3,1],[2,11,1],[2,14,1],[13,3,1],[7,9,2,1],[7,2,5,1,1],[4,2,2,6,2],[3,1,2,1,3,3],[6,1,3,2,4],[1,5,8],[3,1,1,3],[1,7,1,2,2],[5,1,1,1,1,1,2],[1,2,1,1,2,2],[1,5,2,1,1,2,2],[1,5,1,1,1,3,1,2],[2,4,2,1,4,2],[6,3,1,2,3],[3,5,1,4],[6,5,5],[4,1,2,4,2],[6,1,2,1,2],[7,1,1,2,2],[8,1,2,2],[11,2,2,1],[13,3,9],[22,6],[15,4,4],[11,3,1,3],[9,2,2]]}

    Thanks in advance!

    ReplyDelete
    Replies
    1. You know, solver as a mindless machine has produced this: https://157070d6-a-62cb3a1a-s-sites.googlegroups.com/site/tealyatina/share/nonogram_solver_example.png
      I guess that it would be a male face, but machine won't guess, she can only use brute-force until the Universe end =) Try to solve it out again by yourself, that's all I can suggest =)

      Delete
  9. is open source? if yes, can you give us the source?

    ReplyDelete
    Replies
    1. You can simple download it via your web-browser (File->Save page) but if you get troubles with this, here is direct link: https://sites.google.com/site/tealyatina/share/nonogram.zip
      Have fun!

      Delete
  10. Not sure if you still respond to comments here, I've been using CrossMe for a while and find that some of the puzzles are simply unsolvable. That led me to searching for online solutions and I found your solver. I entered the numbers for a puzzle I've been having trouble solving and your solver wasn't able to find a solution. The issue is, it didn't account for everything in the puzzle. I'm using iPhone and the puzzle is #4.115. When entering the numbers in your solver it doesn't account for clear solutions to the bottom few rows. I have entered my own results from CrossMe and attempted to Solve again but it comes up with little to no progress. I was just wondering if the design of the solver works from top to bottom, left to right or if it approaches all sides equally?

    Here is the serial of the puzzle:
    {"ver":[[7],[1,1,2],[3,2,2],[11],[1,4],[2,2,3,1],[2,3,1],[5,1],[1,5],[2,2,3],[4,2,4],[2,1,5,2],[3,1,1,1,2],[6,1,1,6],[2,2,1,1,1,1],[2,1,2,7,1],[2,1,2,5],[6,1,1,1,2],[1,2,2,1,2],[1,2,7],[5,2,3],[3,2,2,1],[2,2,4,2],[1,4,1,3],[2,4,1,2],[1,6,2,1,1],[2,6,6],[1,4,5],[2,4],[1,1,1,4,1,1,5]],"hor":[[3,7,2,1],[2,2,6,2,3],[4,2,3,1,5,1],[1,2,1,1,4,1,6],[1,1,1,1,1,1,4,1],[4,2,2,5,2],[1,2,11,5,1],[1,4,8],[6,8],[4,5,1],[14,2],[4,4,1],[1,1,1,1,4],[1,1,1,1,5,1],[8,1,1,3],[2,1,5,1,3,1],[2,4,4,4],[4,1,3,1,5],[3,5,3,4],[6,9]]}

    ReplyDelete
    Replies
    1. Hello Joosh!
      Thanks for the puzzle, it is a "compile time" right now on my work, and it was a pleasure to solve this while having a short break. Well, puzzle is very complicated, but I wonder why the solver wasn't able to solve it at once. Looks like something wrong with algo deciding a puzzle is not good for solving. I will check it later. What's about your puzzle, I solve it with the solver in three iterations, helping it by paint up some cells at the bottom. The solution is here: https://sites.google.com/site/tealyatina/share/nonogr150821.jpg
      Thanks again, when I get free time for the solver, I will fix it.

      Delete
    2. http://imgur.com/a/ZBdbU

      I ran the solver with just the numbers first. Then I filled in the bottom couple of rows and hit Solve again. It added a few most spots but not much. I continued to fill in the bottom right section and Solve again, each time it only added a few more cells. What confuses/concerns me is that when an amount of spaces are filled and the numerical requirement is met, it doesn't automatically "X" the adjacent spaces. It also isn't working from the bottom up in this scenario as the bottom right block of 5x5 can easily be filled in given the bottom row is an exact amount and the numbers in the bottom right are greater than 1. I'm not sure how you managed to get the solution (have you previously solved it?) but I appreciate the help.

      I will also note that I had a few puzzles that were unsolvable but then the app updated and they were functioning properly. I'm wondering if this is an outdated version of the app (iPhone 4, won't update to current iOS).

      Delete
  11. Thank you for this solver! However, I think it doesn't correctly solve some cases where there's some filled spaces at the edge of the screen so that they exactly fill the number of spaces given by the last digit of the line. In this case, the space to the left or top of the filled spaces should be crossed out, but this doesn't happen, and the solver stops with "bad luck". If I add these crosses manually, the solver happily continues. For instance, this happens if the solver fills the last 4 spaces to the right of a line, so that the edge is on the right of the last of the 4 spaces, and the last number given in that line is a "4".

    ReplyDelete
  12. This happens with the puzzle below; Fill an X in column 9 when it hangs, and it continues.

    {"ver":[[3,1],[5,1],[5,1,2],[5,1,2],[4,1,2],[7,1,2,1],[14,2,3],[18,1],[8,2,2],[8,1,2],[6,1,2],[6,1,2],[6,1],[6,1]],"hor":[[2],[4],[5],[13],[14],[14],[14],[3,9],[3,4],[3],[4],[1,2,1],[1,2,1],[1,2,1],[2,2,2],[1,1,1],[2,2,2],[8],[2,2],[1],[3],[1]]}

    ReplyDelete
  13. I try to solve this on the machine but it wont solve it's 20 x 15

    {"ver":[[1,2,1,2],[4,1,2],[3,2,1],[2,2,1],[3,1,2,1],[2,2,1,1,1,1,1],[1,1,2,1],[1,1,1,1,1,1],[1,1,2,2,1,2],[2,1,2,2,1,1],[2,1,3,2,1],[4,2,2,2],[4,4,1],[11],[2,3,4]],"hor":[[5],[2,2],[1,2],[1,3,1],[2,3],[3,2,2],[2,3,2],[1,1,1,3],[2,2,2],[2,2,1],[1,1,2],[2,2,3],[1,1,1,3,3],[3,2],[1,2,3],[3,2,1],[5,2],[1,1],[2,4,1],[8,2,1]]}

    ReplyDelete
  14. This doesn't solve all the puzzles for Pokemon Picross.

    ReplyDelete
    Replies
    1. It won't solve them AUTOMATICALLY.

      Sometimes, when you get those "bad luck" solutions, you have to help the solver out by entering known X's (bad tiles) or known filled squares (good tiles) and then click "Solve" again. All of the puzzles are solvable - Serebii got through them, obviously.

      Being lazy, though, and expecting to get the answer outright, however, will not help you in the least.

      Try using the edge method introduced in the game to actually figure out which ones are bad/good to be filled in.

      Delete
  15. This doesn't solve all the puzzles for Pokemon Picross.

    ReplyDelete
  16. can you tell me how to solve a color nonoram ? i have been looking all day for a solution online and cant find one

    ReplyDelete
  17. Sometimes you need add empty line around the pic to make solver work...
    It can't calculate the length when dots start at bottom or top

    THE ORIGIN PICROSS
    {"ver":[[6],[4,4],[5,5],[6,6],[6,6],[6,6],[5,5],[3,3],[1,8,1],[1,1,1,1],[1,1,1,1,1,1],[2,1,1,1,1,2],[3,3],[1,2,1],[1,1],[10],[2,2,2,2],[1,3,3,1],[1,3,3,1],[1,4,4,1]],"hor":[[0],[0],[8],[5,2,2],[6,1,2],[6,5,2,1],[6,1,2,3],[6,1,5],[4,1,2,5],[1,1,1,1],[1,1,1,1],[4,1,2,5],[6,1,5],[6,1,2,3],[6,5,2,1],[6,1,2],[5,2,2],[8],[0],[0]]}

    ADD THE EMPTY LINE
    {"ver":[[0],[6],[4,4],[5,5],[6,6],[6,6],[6,6],[5,5],[3,3],[1,8,1],[1,1,1,1],[1,1,1,1,1,1],[2,1,1,1,1,2],[3,3],[1,2,1],[1,1],[10],[2,2,2,2],[1,3,3,1],[1,3,3,1],[1,4,4,1],[0]],"hor":[[0],[0],[8],[5,2,2],[6,1,2],[6,5,2,1],[6,1,2,3],[6,1,5],[4,1,2,5],[1,1,1,1],[1,1,1,1],[4,1,2,5],[6,1,5],[6,1,2,3],[6,5,2,1],[6,1,2],[5,2,2],[8],[0],[0]]}

    ReplyDelete
  18. Well, actually I don't understand it at all. I need to solve a puzzle to get coordinates to find a geocache. Is there anybody who can help me please?

    ReplyDelete
  19. Can you post a picture of the puzzle or type out the grid size and the numbers?

    ReplyDelete
  20. Does anyone know of a good site that generates nonograms based on specific pixel input, as opposed to generating it based on an image (.jpg .png and the like)

    ReplyDelete
    Replies
    1. ...that, and/or one that generates up to a 61×61 puzzle?

      Delete