The New Sudoku Players' Forum

[Vadimkinu]

Hello All!

Please try my board puzzle for Android platform, it's free and ad free
play.google.com/store/apps/details?id=ru.vafgames.finship
Picture:


There are two board sizes 5x5 and 6x6, number of levels w/o any limit. You will discover 6x6 to be very challenging.
Thank you!

[Smythe Dakota]

I'm not sure I understand the rules, even after looking at your web page.

It was a while before I realized that the vertical bars along the bottom represent bonds, the same as the horizontal bars along the right side. At first I thought they were the digit 1, and I couldn't figure out why there were three digits at the bottom of each column but only two digits at the right of each row.

Now that I've figured that out, my next guess is that the object is to add atoms wherever necessary so that, in the final picture, the number of molecules and bonds in each row and column matches the numbers at the right and bottom.

But I still have a question. If I place an atom, does that also automatically generate a bond between the new atom and (any and all) atoms that are adjacent to it, vertically and horizontally?

I can't try your electronic version because I don't have a smart phone. My cell is a flip phone (remember those?). So I'm trying to work it out on paper.

Bill Smythe

[Smythe Dakota]

.... If I place an atom, does that also automatically generate a bond between the new atom and (any and all) atoms that are adjacent to it, vertically and horizontally? ....

Now I realize that assumption is incorrect. In your sample puzzle, that assumption leads to a non-existent solution.

So my next hypothesis is that bonds are not automatic, but may be placed manually. There is no requirement that atoms in adjacent cells have a bond between them. However, at the end, the entire puzzle must be connected, i.e. it must be possible to get from any atom to any other atom via a sequence of horizontal and vertical bonds.

If all of that is correct, I now have one more question: Are circular bonds (such as benzene rings) allowed? For example, in your sample puzzle, would it be permissible to add an atom at r3c1, and bonds between it and the atoms at r2c1 and r4c1?

Bill Smythe

[Smythe Dakota]

Upon still further study, now I'm even more confused.

I'll re-display the picture below for everybody's convenience.



Since two atoms must be added to the top row, and one to the bottom row, and none to any other rows, AND since two atoms must be added to the first column, and one to the third column, and none to any other columns, it follows that atoms must be added at r1c1, r1c3, and r5c1.

Now, what about the bonds?

The top row needs three new bonds, so that's easy: r1c1-r1c2, r1c2-r1c3, and r1c3-r1c4.

The bottom row needs two new bonds, so that's easy too: r5c1-r5c2, and r5c2-r5c4. But the latter is a non-adjacent bond. That requires me to further modify my original assumptions. Apparently, bonds don't have to be between two adjacent atoms, as long as there are no other atoms between the two in the same row (or column).

That takes care of the horizontal bonds.

Vertically, everything is already OK, except in the leftmost column, which needs two new bonds. These could be r1c1-r2c1 and r4c1-r5c1. But r2c1-r4c1 is also a legal bond, at least if non-adjacent vertical bonds are allowed, in the same way that non-adjacent horizontal bonds are apparently allowed (judging by the previously mentioned r5c2-r5c4).

Thus, the puzzle apparently has multiple solutions, which is a definite NO-NO in the puzzle business (whether sudoku, kakuro, or any other puzzle).

On top of that, the resulting solution is not connected. The rightmost column is isolated from the rest of the puzzle. That's a peculiar molecule!

And, there are circles (benzene-ring-type configurations) in all the solutions.

It seems to me, it ought to be back to the drawing board for this type of puzzle, or at least for this example. The improved version should also include a clarification of the rules.

Bill Smythe

[Mathimagics]

I can't try your electronic version because I don't have a smart phone. My cell is a flip phone (remember those?). So I'm trying to work it out on paper.

Same here!

Mine is still 2G. But they are switching off the 2G network in Australia soon, which is a real bummer ...

Anyway, my first impression was that it's a variation of a puzzle I'm developing.

If that is in fact the case, then the objective is create a single molecule that has the required number of atoms in each row/col match the clues, and ditto for the required number of connections in each row/col.

And there should be no circuits, ie: between any pair of atoms there should be exactly one path of connections that lets you get from one to the other.

Could that be it?

(PS) Oh, I now see that you have already established that circuits exist in the solution (but how do you know the solution without running the app?)

[Smythe Dakota]

.... but how do you know the solution without running the app?

The same way I solve sudoku and kakuro puzzles -- on paper!

.... Anyway, my first impression was that it's a variation of a puzzle I'm developing. .... If that is in fact the case, then the objective is create a single molecule that has the required number of atoms in each row/col match the clues, and ditto for the required number of connections in each row/col. .... And there should be no circuits .... Could that be it? ....

Those were my initial assumptions, too. Following those assumptions, I worked it out as follows:

• In the top row, only 2 atoms are shown, but the clue calls for 4. The added 2 must be in the 1st and 3rd locations -- not the 5th, because column 5 already has 3 atoms, as specified by the clue for that column.
• In the bottom row, only 2 atoms are shown, but the clue calls for 3. The added 1 must be in the 1st location, because the other two locations are in columns 3 and 5, which already have the required number of atoms.
• Having added the above atoms in r1c1, r1c3, and r5c1, all rows and columns now have the required number of atoms. So it's time to turn attention to the bonds.
• The top row needs 3 bonds, and there are only 3 places to put them -- in the 3 spaces between r1c1-r1c2-r1c3-r1c4.
• The bottom row needs 2 bonds, and there are only 2 places to put them -- in the 2 spaces between r5c1-r5c2-r5c4.
• Now all rows and columns have the required number of atoms and bonds, except for column 1, which needs 2 bonds. These can be any two of r1c1-r2c1, r2c1-r4c1, r4c1-r5c1. Since there are three ways to do this, the solution is not unique.
• Further, this solution (these solutions) all have circuits, and all leave a disconnected "molecule", in that column 5 is separated from the rest of the picture.

This reasoning proves that there are no solutions satisfying the desideratum that "there should be exactly one path of connections that lets you get from one to the other". It also proves that, even among solutions not satisfying the desideratum, there are 3 solutions, not just 1, which violates the uniqueness rule that, by general agreement, permeates all of puzzle-land.

Bill Smythe

[Mathimagics]

Ok, you've done a pretty thorough job there.

I only had the briefest look, but I can see now that my "connnected acyclic graph" postulate can't be true in any case because 17 vertices (atoms) implies 16 edges (bonds), and the bonds here add up to 17. When I first looked I added them up wrongly to 16 and thought "aha!"

Since edges > (vertices - 1), the graph must contain cycles, regardless of whether it is connected.

[Smythe Dakota]

So we're both left wondering what the original poster had in mind.

I had never noticed that, in a connected graph with no circuits, the number of vertices must equal the number of edges plus one, but now that you said it, it's trivially easy to see why this must be the case.

More generally, whether the graph is connected or not, if there are no circuits, then the number of vertices must equal the number of edges plus the number of connected chunks. (A connected graph consists of just one chunk.) This is assuming that "isolated vertices" (a "vertex" with no edges) are not allowed.

Bill Smythe

[Mathimagics]

It's convenient to regard isolated vertices as (trivial) components (chunks). Thus for an acyclic graph your formula, which translates to

NE = NV - NC

applies without exception.

[Smythe Dakota]

It's convenient to regard isolated vertices as (trivial) components (chunks). ....

Hmm, you're right, of course. In fact, it's not only convenient, it's necessary, because what else could an isolated vertex be regarded as?

Bill Smythe

[Vadimkinu]

Hello Guys!

Sorry for late response.
There may be a number of molecules and atoms (single items) on the board. Each column and line has two numbers - first one shows number of bonds if any (between neighbous atoms) and number of atoms. Program generate random levels, but minimum and maximum atom's number is limited, otherwise in some cases there are more than single solution.Trivial example is each column and number has only 1 atom and 0 bonds. There are many solutions, ex. two diagonals.

Kind regards,
Vadim

[Smythe Dakota]

.... in some cases there are more than single solution. ....

In the world of puzzles, such as sudoku and kakuro which these discussion boards are about, it is regarded as a big no-no to have a puzzle with multiple solutions. You should make sure that any puzzle you put on your website has just a single solution.

Imagine what happens if a visitor to a sudoku or kakuro website is not aware that there may be multiple solutions. He will get only so far, and then he will believe that the puzzle is really, really hard because he cannot establish logically what the next digit might be. The site has then bamboozled him unfairly. Please don't do that.

Bill Smythe

[Vadimkinu]

Hello Bill!

Please advise why PUZZLE must have only single solution?
Could you give me proof of this criteria?

It's evident that gameplay often does not suffer from the fact that logical game has multiple solutions. Rubik'd cube, chess, { sudoku in principle} do have multiple silutions (http://www.ams.org/notices/200706/tx070600708p.pdf).

I tested generated by my algorithm variants and found that on 5x5 board with total number of atoms from 7 to 17 probability of multiple solutions is less than 1%. So I could filter this 1% of variants from playing programmably, but as I already wrote - gameplay does not suffer and gamer still has to think to solve.

Kind regards,
Vadim

[JasonLion]

Having a single solution is a social agreement, not something you could ever "prove". It is traditional to either have a single solution, or to change to problem definition to be to enumerate all of the solutions. You are of course free to define things any way you wish. But if you wish to have others solve your puzzles it is polite to comply with standard practices in the puzzle community.