code for a simple nanogram function

1 view (last 30 days)
Mark Aingorine on 11 Oct 2021
Edited: John D'Errico on 20 Nov 2021
Hello, I really need some help
been stuck on a simple nanogram for ages now
i need to create a function that preduces a nanogram mat nxn after i input the row vectors and coulmn vectors
for example if i input
Rownum = [ 1 4 4 1 2]
Rownum = 1×5
1 4 4 1 2
Columnnum = [ 1 4 2 3 2]
Columnnum = 1×5
1 4 2 3 2
Board = [ 0 0 0 1 0 ;0 1 1 1 1 ;0 0 1 1 1 ;1 1 0 0 1 ;0 0 1 0 0]
Board = 5×5
0 0 0 1 0 0 1 1 1 1 0 0 1 1 1 1 1 0 0 1 0 0 1 0 0
would apreciate any help
John D'Errico on 12 Oct 2021
Surprisingly, I actually wrote a nonogram solver. Not that difficult, and pretty fast to run. I won't post it, because this is probably homework, if you need it that badly. I'm sure there are many solution methods. My approach involved an exhaustive search, but one that is quickly pruned back iteratively. As I said, it is pretty efficient, and should work for 20x20 grids pretty easily, it might even go to 25x25.
So as a hint, consider any row (or column). If you know how any bits are turned on in that row, can you list all possible candidates for that row/column? That is, write a simple function that will return the set of all possible such candidates.
Now apply that tool to each row, AND column.
Finally, find a way to resolve which sets of candidates can work together, to solve the global problem. That is, you can look at the rows, and then see how those choices work with the possile columns you have found. Go back and forth, until a solution drops out. This simple ad hoc scheme works amazingly well.

John D'Errico on 20 Nov 2021
Edited: John D'Errico on 20 Nov 2021
Now roughly a month since the original post, and nobody has answered. I was not sure if this could be a student problem, so I gave nothing more than soem hints as to how I would write a nonogram solver. I've not bothered to do many of them since I wrote my own solver anyway. Funny how that works. Once I saw the problem was in principle solved, the puzzles were no longer of interest to me. ;-)
Anyway, I'll attach to this response a partial solution. In fact, I might argue what I'll attach is perhaps the most important part of a solution.
So, first, let me get my terminology straight. A nonogram puzzle is one where in an array of say 10x10, we assume the solution is a binary array. 1 where a bit is turned on, 0 where it is turned off.
For each row (and scolumn) of the puzzle, we are now told information, about the length of the substrings that are turned on. Fr example, in the string '0001101111', we would be told there are substrings of length 2 and 4 (in that order.) The puzzle comes down to the fact that we do not know where those substrings live in that total expanse of 10 bits.
So I will post the code here for something I call rowpossibles. It will apply to columns too. I'll show a couple of examples of its use below.
Suppose, for example, that I told you, in one row of a 10x10 grid, that a substring existed of length 9? I would use the rowpossibles function as such:
[tbin,tdec,tprobs,tcertain,tcertainind] = rowpossibles(10,)
tbin =
2×10 char array
'0111111111'
'1111111110'
tdec =
511 1022
tprobs =
0.5000 1.0000 1.0000 1.0000 1.0000 1.0000 1.0000 1.0000 1.0000 0.5000
tcertain =
1×10 logical array
0 1 1 1 1 1 1 1 1 0
tcertainind =
2 3 4 5 6 7 8 9
rowpossibles has 5 output arguments, all of which are potentially valuable. That is, if we know there must be a substring of length 9, then there are only two possible configurations for the solution in this row. It MUST be either the binary string '0111111111' or the string '1111111110'. Those are the only two possible solutions.
What information can we further glean from this? Now we know certainly that some of those bits are always turned on. So we might think of that as a string like this: '?11111111?'. A 1 indicates a bit known to be on, a ? indicates there a bit where we are uncertain.
So tcertainind lists the indices of the bits we know are certainly turned on.
The trick to using rowpossibles in my solver is to apply it to every row, of the puzzle. It will tell which bits are turned on, and which ones were turned off, and even give me a probability assessment about the bits where it is uncertain. After every call to rowpossibles, I fill in the informatino about what I know about that row into the grid.
Then my solver applies this same tool to every column, filling in what it learns as it goes. But now when I look at the columns of the array, I have already learned information from those previous calls for each row.
So, suppose I know that in some row of a 15x15 puzzle, that I have subbstrings turned on of length [3 1 2 4]. But now, assume that I also know from previous efforts, that bits 3 and 14 are definitely turned on, and that bit 7 is definitely turned off? I'll create this vector encoding that information.
priorinfo = nans(1,15);
priorinfo([3 14]) = 1;priorinfo(7) = 0;
priorinfo
priorinfo =
NaN NaN 1 NaN NaN NaN 0 NaN NaN NaN NaN NaN NaN 1 NaN
It has a NaN where I am unsure about the bits in that position, 1 where I know the bit is turned on, and 0 where it is off.
rowpossibles tells me now, there are 9 possible configurations for that row. We can see them here:
[tbin,tdec,tprobs,tcertain,tcertainind] = rowpossibles(15,[3 1 2 4],priorinfo)
tbin =
9×15 char array
'011101001101111'
'011101011001111'
'011101011011110'
'111001001101111'
'111001011001111'
'111001011011110'
'111010001101111'
'111010011001111'
'111010011011110'
tdec =
1719 1767 1774 3255 3303 3310 3383 3431 3438
tprobs =
Columns 1 through 13
0.6667 1.0000 1.0000 0.3333 0.3333 0.6667 0 0.6667 1.0000 0.3333 0.3333 1.0000 1.0000
Columns 14 through 15
1.0000 0.6667
tcertain =
1×15 logical array
0 1 1 0 0 0 0 0 1 0 0 1 1 1 0
tcertainind =
2 3 9 12 13 14
But where before, we kew only that bits 3 and 14 were definitely turned on, now we know that bits [2 3 9 12 13 14] must all be turned on.
I suppose we could try to learn if there are any bits that are certainly turned off:
find(all(tbin == '0',1))
ans =
7
But we are given no more information about that status, only that bit #7 is still definitely off.
Finally, consider a 15x15 puzzle that I tried the other day, finding I had gotten stuck at a point, where it seemed I was unable to completely solve the puzzle. (I know it was solvable, only that I had temporarily gotten stuck.) So I threw the puzzle into my nonosolve utility. Why write software if not to use it?
nono = nonosolve(15,{3 2 [4 1 2] 4 [4 2] [5 1 5] [1 1 1 4] [3 1 2 3] [2 1 1 1 4] [2 6 2 2] [3 2 2 1] [4 2] [2 2 1] [3 1 2 1] [4 2 2]},...
{[1 1 3 3] [2 1 4 3] [2 3 1 2] [1 1 1 1 1] [2 2] [1 1 1] [2 4] [4 3] [1 3 2] [3 2 5] [3 3 1] [1 5 1] [1 4 3] [1 1 1 5 1] [1 1 2 2]})
nono =
struct with fields:
n: 15
rowinfo: {1×15 cell}
colinfo: {1×15 cell}
solution: [15×15 double]
rowprobabilities: [15×15 double]
colprobabilities: [15×15 double]
You can see the input tells the code is a 15x15 problem. The second argument is a cell array where the information about each row is provided. The third argument contains the information about all 15 columns, again as a cell array.
It returns nono.solution (in about 2 seconds) as an array. To make it a bit more readable, I'll turn it into a character array.
char(nono.solution + '0')
ans =
15×15 char array
'000000000001110'
'011000000000000'
'111100000100011'
'000000111100000'
'000011110110000'
'111110010011111'
'001001010111100'
'011100101101110'
'110010101001111'
'110111111011011'
'111000110110010'
'000000011110110'
'110000001100100'
'111000000101101'
'111100000110011'
I never did post the complete solver on the File Exchange, probably because the interface requires the user to do a lot of typing to pass in all the information about every row and column. With some effort, I could probably have put it all into a gui to make that easier, but I had already solved the problem at that point, making it no longer a problem of interest to me. :)
I have attached one piece of my code though. It might help you.

R2021b

Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!