Could the program find the borders of the four inscription rectangles?
I like the idea, I’ll give it a try. But I still have a few questions:
Here is the starting cipher:
On the left side the four diagonal inscription rectangles. The step with the resize to 17×20 + substitution is not visible in the picture. On the right you can see the cipher redrafted in 20×17 + reading direction north east + substitution undone. Is this the starting situation to be solved? The colors show which fragments belong together. Is that what you mean?
How is this to be broken down into fragments? 68 fragments with 5 characters each? Should the order of the genes be evolved by using the total score as fitness? Or should the fragments be taken from random positions and the score of each fragment be calculated? Or should the fragments have a variable length? Here I am not sure what is meant.
Translated with http://www.DeepL.com/Translator
At 17×3 there are 179840 possible routes just for the start position 0, 0. Again, the search space seems to be way too large. Even with a genetic algorithm that builds the routes on the fly. I don’t see any way to evolve routes. Even if it were a text without substitution.
You could start with a random permutation of the positions of the grid.
The gene represents the sequence of positions (the path or route).
The fitness function starts at the first element of the gene, then follows the sequence until it violates the constraint of adjacency (i.e., neighboring positions in the sequence must be valid moves up, down, left or right). The function would punish such violations.
Mutations of the gene could swap elements to create more valid adjacencies.
I think this approach would generate a lot of unique routes that visit all positions of the grid. But I’m not sure how best to combine it with a measurement of the quality of the resulting plaintext.
BTW I ran the grid route algorithm for square grids. Here are the counts of fully-covering routes:
1×1: 1
2×2: 8
3×3: 40
4×4: 552
5×5: 8648
6×6: 458696
7×7: 27070560
It’s working on 8×8 now and isn’t even done with the first position yet. Not sure it will finish any time soon!
But here’s an interesting result: If you look up the above counts in the (super excellent) On-Line Encyclopedia of Integer Sequences, you get this one:
It is described as: "Number of ways to number the cells of an n X n square grid with 1,2,3,…,n^2 so that successive integers are in adjacent cells (horizontally or vertically). "
And: "Number of directed Hamiltonian paths in (n X n)-grid graph."
They computed it up to 17×17 (yielding 289 positions) which gives a total of 132,857,989,478,318,939,938,880,239,159,473,615,225,331,080 possible routes. So that’d probably be a lower bound on the number of routes in the z340 layout (20×17).
That database is useful, since it has given us some formal language to help describe the problem. I think Hamiltonian paths are what we are looking for in our grid route problem. The route problem is also described in "Numbrix puzzles": https://parade.com/2596/marilynvossavan … s-numbrix/
As it turns out, there is a paper about a genetic algorithm for finding Hamiltonian paths:
https://books.google.com/books?hl=en&lr … 3W4oyHwR3Y
General idea, general idea. The 340 could easily be something like this, and there is a correct path through the message to get a solve but we can’t figure out what the path is.
Here is an example cipher.
EDIT: Spreadsheet notes transferred to post.
step 1 of cipher inscription
step 2 of cipher redraft into 17 x 20; step 3 substitution not shown
Well, actually I have tried to make messages with several smaller inscription rectangles and it won’t work for P19 numbers. But there could be two or three slightly larger unique areas in the message. This is just for a simple example for demonstration.
Redraft into column widths so that the P19 symbols touch each other somehow. In this example, 20 columns and the symbols align diagonally.
EDIT: Spreadsheet notes transferred to post.
step 1 of solution redraft into 20 columns so that P19 bigram repeat symbols touch
portion of gene sequence shown below
read north east and transfer into array; symbols out of sequence purple for demonstration
example gene sequence; alternating clear / shaded to show segments
gene sequence after many generations; solve with rows bound method
They computed it up to 17×17 (yielding 289 positions) which gives a total of 132,857,989,478,318,939,938,880,239,159,473,615,225,331,080 possible routes. So that’d probably be a lower bound on the number of routes in the z340 layout (20×17).
Forget about it, the transposition search space is way too large.
As it turns out, there is a paper about a genetic algorithm for finding Hamiltonian paths:
It is surprising: One thinks there is a very special problem that nobody has analyzed because there has never been an use case before. Immediately we are told better and find a solution on the Internet for exactly that. Apparently there is hardly anything that someone has not already done. But as soon as you look for the most spectacular unsolved problems, you end up with z340. A vicious circle 
I haven’t heard anything about Hamiltonian paths yet and it reminded me of the Travelling Salesman problem. This is also mentioned in the paper. Some time ago I let TSP routes evolve for testing, that worked very well. However, the fitness function is very simple. With the z340, fitness is the scoring of the solver and therefore much more complex in comparison.
I also think that the search space is much too large as Jarlve has already mentioned. Still an interesting problem.
Here is an example cipher.
EDIT: Spreadsheet notes transferred to post.
Thanks for the spreadsheet! Now I understand your approach. That sounds promising, but I haven’t implemented a row bound solver yet. I searched the forum for the description of your concept that Jarlve implemented into AZDecrypt. Unfortunately I can’t find it anymore. It must have been somewhere near this:
viewtopic.php?f=81&t=3196&hilit=row+solver&start=500
General idea, general idea. The 340 could easily be something like this, and there is a correct path through the message to get a solve but we can’t figure out what the path is.
It may well be the case that a possible route in z340 is actually very simple from a geometric point of view, but causes enormous problems with auto solvers. Two or four inscription rectangles are extremely easy to create with pen and paper, but also very difficult to solve. Should z340 be solved at one day, we might be surprised and disappointed how simple Zodiac’s method was.
Redraft into column widths so that the P19 symbols touch each other somehow. In this example, 20 columns and the symbols align diagonally.
I have done many such experiments with Peek-a-boo, including the one you described. Diagonal alignment is also obtained by making columns period 2 (I call this "columns odd before even"). You get 44 bigrams and 5 trigrams on P18 (which again corresponds to a diagonal transposition). Perhaps one day such an observation will lead to a solution, who knows.
Back again to the hamiltonian paths:
From my gut feeling I would exclude 99.9% of all possible routes. Somehow I can’t imagine that Zodiac took an odyssey through the cipher. If there is a route, it’s probably much straighter and has fewer "curves". In this case we have to consider how much effort we want to put into solving such routes. It is clear to me that excluding possibilities only from the gut is a dangerous thing. This reminds me of a popular story that I’ve posted before:
At night a policeman finds a drunk man searching under a lantern for his lost house key. The policeman helps him search, but the two remain unsuccessful. The policeman then asks the man: "Are you sure you lost the key here?". The man answers: "No, but under the lantern at least I have light to look for the key".
Translated with http://www.DeepL.com/Translator
I am curious how large the route search space would be if we imposed constraints on the "twistiness" of the routes.
For example, if you say "do not allow more than 10 turns", how many routes could you make from Z340?
A progressive approach could be:
– Generate all routes consisting of zero turns
– Generate all routes consisting of one turn
– Generate all routes consisting of two turns
– Generate all routes consisting of three turns
…etc…
The first of those would probably result in zero routes (unless you allow the path to wrap around, like a normal reading direction). Then you might have a reasonably countable set of routes for small numbers of turns. Those could be explored and if a solution used PART of such a route, maybe a partial solution could be found.
I am curious how large the route search space would be if we imposed constraints on the "twistiness" of the routes.
That sounds good! The search space would be much smaller. However, there are two things we should keep in mind:
– Shouldn’t we allow "wrap around" in general?
– Suppose we have a 6×6 grid and are looking for a snake route. This starts at the top left and runs zigzag into the lower left square. This requires a total of 10 direction changes. If you allow 10 changes of direction for 36 fields, these are a total of 254186856 possible combinations only for the positions of the fields. The three possible direction changes per field are not yet considered. Isn’t this still too much search space?
Jarlve calls it rows bound.
The rows are independent of each other; there is no connection when starting a new row. If you are using 5 grams to solve, then the fifth symbol from the end of the row will be solved with a 5 gram, but then the fourth from the end with a 4 gram, third from the end with a 3 gram, etc.
The idea is to be able to un-transpose at a certain period, and then try to solve sections of the message instead of the whole thing. For example, if a message is made from an incomplete inscription rectangle, then untranspose, and solve the left half rows bound and the right half rows bound. The half that does not have the mis-alignments should solve.
Maybe by treating each gene segment as an independent row, this could help with mis-alignments, multiple inscription shapes, etc.
Smokie:
The idea is cool. Combining Row bound with genetic algorithms could actually help with misalignments and multiple inscription rectangles. I’d like to implement that, but there is a small problem. To describe what I mean, here’s a short summary of my "z340 career":
– I started some years ago with simple experiments (e.g. flip/mirror and some simple statistics). I did that with C++. That was before I was active here in the forum.
– After that I wrote a quite large cipher library in Python. With this library I was able to perform a lot of transposition methods and calculate statistics. I did this not only because of z340, but also to deepen my Python knowledge.
– Since Python became too slow for me for large tests, I ported my code in C#. My homophonic solver was written in C++ to squeeze out the last However, I wrote my homophonic solver in C++ to squeeze out the last bit of performance.
– Next I made a side trip to Swift /macOS. Here I also used the opportunity to combine z340 with the deepening and learning of a new programming language. The result is quite satisfying..
The problem with the whole story is that I only implemented certain features properly in one programming language at a time. I can handle all the chaos reasonably well, but it is enormously time-consuming to combine features. For example, my C# library is the most versatile, but unfortunately tailored for Peek-a-boo. When transposing ciphers, for example, the colors in the grid and other meta information must also be taken into account. This means that tests with a large search space does not perform very well.
To cut a long story short: If I want to continue working on z340, I just have to make a cut at this point and concentrate on one programming language and one operating system. I have to clean up my code, sort it out and trim it for performance. This takes time, but has many advantages. Tests end up running much faster, and if I focus on the Windows world, I can share tools and source code more effectively, as most people here work on Windows. So it will take some time until I can implement your idea. But I definitely want to do that.
It would be so cool if we would all use a common code base, because then not everyone would have to reinvent the wheel. But I think this will always be a dream =)
Don’t feel bad. I don’t program at all. I did a little javascript programming about a year and a half ago, but went back to spreadsheet work because I could visually see errors easier. And I have other competing interests, like a full time job, a commute, an old house that needs work, and a girlfriend ( not necessarily in that order ). I put the programming on the back burner because even if I did, I figured I would just be duplicating the efforts of others. I am not quite as passionate about the 340 anymore, but still interested. I don’t care very much anymore about who the Zodiac was. I can make some beautiful and very creative spreadsheets though to experiment with basic concepts.
See the two pages or so that follow the first post here.
viewtopic.php?f=81&t=3196&start=1040
I wonder if I could do something similar with the unidirectional gene path idea… I think that efforts at any idea like this could be purely mathematical at first, before getting into cryptography and homophonic substitution.
Right now I have two laptops. One old one and one new, really fast one that is dedicated exclusively to work with AZD and the null skip misalignment efforts.
And I have other competing interests
Yes, me too. Besides, I always have to do something somehow. I rarely manage to just sit on the couch and watch a TV series or something. Usually I do 1-2 other things at the same time. Only a long hike across the forest brings some peace and quietness.
I put the programming on the back burner because even if I did, I figured I would just be duplicating the efforts of others
I can very well understand that. Especially on this point it is a pity that no source code is shared yet. If one wants to combine his ideas with those of others, it is sometimes necessary to duplicate work. For example, I’ll try to implement a row bound solver as well. But there is also an advantage: if several people develop their own solvers, they will automatically use other approaches as well. More diversity is always good.
What is very well shared in this forum, however, is knowledge. In the last days I e.g. mailed with Jarlve and got some good tips for my solver. His advice together with my own ideas have made my solver about twice as fast. Also, the solve rate has been improved.
I am not quite as passionate about the 340 anymore, but still interested. I don’t care very much anymore about who the Zodiac was.
I also think similarly in this point. His crimes would not be so well known without his abstruse letters and ciphers. And his ciphers would not be so popular without his crimes. Both in themselves would be much more unspectacular. Nevertheless, I have fun trying to solve the z340. z340 is more exciting than crossword puzzles or Sudoku. My opinion.
Back to the actual topic of the thread:
I pause working on the solver for the Mac and concentrate on optimizing my existing solver for Windows and cleaning up my source code. With this I want to create a clean foundation for further experiments. This includes your idea with the combination of genetic algorithms and a row bound solver. But this will take some time. I also made an interesting discovery about z340 by luck a while ago, which I would like to take a closer look at. If it wasn’t a dud, I’ll open a new thread the next days.
Translated with http://www.DeepL.com/Translator
