The New Sudoku Players' Forum

[udosuk]

I have recently encountered a puzzle which is practically a one-dimensional version of Sudoku.

The puzzle goes like this - you're given a line of 27 cells, and the goal is to fill each cell with a value from 1 to 9. Each value must appear exactly 3 times, and the special constraint is there must be exactly n cells spaced between each cell holding value n.

To demonstrate this special constraint, let's try a smaller example: with a line of 6 cells, fill in the values 1 to 3, exactly twice for each. Then it seems the following is the only possible solution (barring reflection):

Code: Select all

2 3 1 2 1 3

1 cell between the two 1s, 2 cells between the two 2s, 3 cells between the two 3s.

Another smaller example: with a line of 8 cells, fill in the values 1 to 4, exactly twice for each. Then the following should be the only possible solution (again, barring reflection):

Code: Select all

2 3 4 2 1 3 1 4

1 cell between the two 1s, 2 cells between the two 2s, 3 cells between the two 3s, 4 cells between the two 4s.

So, I was told the following 3 puzzles each gives a unique solution, and these are essentially all the possible solution lines for the case of 3x9=27 cells (barring reflection):

Code: Select all

_ _ _:_ _ _:_ _ _|_ _ _:_ _ _:_ _ 4|_ _ _:_ _ _:_ _ _

_ _ _:_ _ _:_ _ _|_ _ _:_ _ _:_ _ 5|_ _ _:_ _ _:_ _ _

_ _ _:_ _ _:_ _ _|_ _ _:_ _ _:_ _ 6|_ _ _:_ _ _:_ _ _

Some questions:

1. Are these problems only solvable by computer programs? Is there any logical approach to find out the answer, or is T&E the only possible way?

2. If some more clues are given, can these puzzles be made more solvable to a competent human Sudoku player? If so, what is the minimum number of clues to make them "human solvable"?

3. Can this puzzle be generalised to a two-dimensional version? If so what are the new rules?

4. I've also been told that for the case of 3x10=30 cells, there are only 5 possible solution lines (barring reflection). But I don't have any idea on how to work them out. Can any programming guru help me out on this?

Thanks heaps in advance!

[evert]

where did you encounter it?

[udosuk]

where did you encounter it?

From an old puzzle book.

Anyway, I'm still waiting for some programming gurus such as gsf & JPF to help verify that there are only 3 solutions for the 3x9 version and find/verify the 5 solutions for the 3x10 version...

If anyone wants to see the 3 solutions for the 3x9 version, they can either PM me or wait for roughly a week.

[Smythe Dakota]

I don't know, but would it help to visualize the problem in the following graphical way?

You have a line of 27 marble-sized holes in the top surface of your desk, each hole 1 inch from the next in a straight line. You also have a set of 9 very thin rulers, each with marble-sized holes an inch apart. These 9 rulers have respectively 5, 7, 9, 11, 13, 15, 17, 19, and 21 holes. Each ruler has 3 marbles glued into 3 of its holes -- the two holes on each end and the hole in the exact middle. Each ruler is barely long enough to accommodate all of its holes, i.e. each end of each ruler is very close to the hole nearest that end.

The problem is then to fit all nine of these rulers simultaneously over the holes in your desk, each ruler on top of the next, in such a way that each hole in your desk is filled with exactly one of the marbles glued into the rulers. Of course, no two marbles are allowed to lie on top of the same hole in the desk, as they would then bump into each other.

Bill Smythe

[udosuk]

Yes, good observation Bill.

In fact, if you can print transparent slides in your printer/photocopy machine, you can print out "strips" with the following format:

Code: Select all

+-+-+-+-+-+
|1| |1| |1|
+-+-+-+-+-+

+-+-+-+-+-+-+-+
|2| | |2| | |2|
+-+-+-+-+-+-+-+

+-+-+-+-+-+-+-+-+-+
|3| | | |3| | | |3|
+-+-+-+-+-+-+-+-+-+

+-+-+-+-+-+-+-+-+-+-+-+
|4| | | | |4| | | | |4|
+-+-+-+-+-+-+-+-+-+-+-+

+-+-+-+-+-+-+-+-+-+-+-+-+-+
|5| | | | | |5| | | | | |5|
+-+-+-+-+-+-+-+-+-+-+-+-+-+

+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|6| | | | | | |6| | | | | | |6|
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|7| | | | | | | |7| | | | | | | |7|
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|8| | | | | | | | |8| | | | | | | | |8|
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|9| | | | | | | | | |9| | | | | | | | | |9|
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

(It's very easy to use Excel to make a nice printout of these strips, but I'll let the readers do it themselves.)

And then you can play around with them trying to form a long continuous strip full of numbers. Should make a nice toy!

[udosuk]

Whew... Got impatient and brute forced the results myself. Turns out I still remember how to write programs!

Yep, there are only 3 (non-mirrored) solutions for triples of 1..9, 5 solutions for triples of 1..10. Also, if we throw in a triple of 0s (so they must be on 3 consecutive cells, i.e. "000"), we can have 9 solutions for 0..8, 20 solutions for 0..9, and 33 solutions for 0..10. So we can have a 33x33 square, with each row one solution line which is essentially different to all other lines!

Also note that 6 of the 20 solutions of 0..9 are also solutions of 1..9 with "000" added on one end, and similarly 10 of the 33 solutions are solutions of 1..10 with "000" appended.

Also, I've investigated the (simpler) cases of pairs instead of triples. With pairs of 1..3 and 1..4 I've already shown the unique solutions above. To my surprise there is no possible solution for 1..5 & 1..6, but 26 solutions for 1..7! I'll list them out as below:

Code: Select all

14156742352637
14167345236275
15146735423627
15163745326427
15167245236473
15173465324726
16135743625427
16172452634753
17125623475364
17126425374635
23627345161475
23726351417654
24723645317165
25623745361417
26325734615147
26327435614175
26721514637543
27423564371516
34673245261715
35723625417164
36713145627425
41617435263275
41716425327635
46171435623725
52462754316137
52642753461317

Pairs of 1..8 lead to at least 150 essentially different solutions, and it starts to get uninteresting since I'm only looking for problems with ~50 or fewer solutions.

Also, we can throw in pairs of 0s ("00"). 0..3 and 0..4 have 3 & 5 solutions respectively, as below:

Code: Select all

00231213
00312132
12132003

0023421314
0041312432
1214230043
1312432004
2412134003

Obviously, there is no solution for 0..5 and 0..6 (because there is no solution for 1..5 & 1..6). 0..7 yields at least 252 solutions, so is again uninteresting.

I'll leave the solutions to the triples as a challenge to you guys. You can always PM me if you are curious but can't work them out.

[Smythe Dakota]

Here'a another way of looking at the problem. (No doubt you're way ahead of me.) You have nine diagonal lines, each having an equation of the form y = mx + b (m is slope, b is y-intercept). The nine values for m are respectively 2, 3, 4, 5, 6, 7, 8, 9, 10.

Find nine corresponding values for b (necessarily integers in the range 0 through 22 inclusive) such that the nine diagonal lines intersect the three vertical lines x=0, x=1, x=2 in 27 points, all having integer y-coordinates in the range 0 through 26 inclusive, and no two having the same y-coordinate.

This view seems to lend itself to a brute force approach, quite similar, I'm guessing, to the one you came up with.

Bill Smythe

[udosuk]

Bill, thanks for your Cartesian insights. I just simply wrote a program with nested for-loops to brute-force the combinations. Nothing fancy at all and should be a piece of cake to most programming gurus here (perhaps that's the reason why they aren't replying at all).

I did some more investigations and explored the possibilities of any similar puzzle that has a essential unique solution. If you're bored and want some challenging fun, I suggest you try to make the transparent strips I described above (should be cheaper than marbled-rulers ), and try to perform the following task:

1. Use triples of 1..8 except 6 to form a 21-long strip.

2. Use triples of 0..8 except 3 to form a 24-long strip.

3. Use triples of 0..9 except 4 to form a 27-long strip.

All of these 3 should each yield a unique solution barring reflection.