The Museum of HP Calculators

HP Forum Archive 19

[ Return to Index | Top of Index ]

Off-Topic: Who can solve this?
Message #1 Posted by Matthias Wehrli on 27 Feb 2010, 1:22 p.m.

Who can solve this sudoku for me? Maybe someone is interested in programming a special solver ;)

http://www.hp-collection.org/Sudoku.png

The sudoku needs digits from 1 to 9 and operates with the relation symbols "< is less than" and "> is more than"

Yours Matthias

Edited: 27 Feb 2010, 1:23 p.m.

      
Re: Off-Topic: Who can solve this?
Message #2 Posted by Eric Smith on 27 Feb 2010, 4:38 p.m.,
in response to message #1 by Matthias Wehrli

Is this four ovelapping sudoku puzzles?

            
Re: Off-Topic: Who can solve this?
Message #3 Posted by Matthias Wehrli on 27 Feb 2010, 4:45 p.m.,
in response to message #2 by Eric Smith

Hi Eric

I do not know what you mean. you simply have to insert the digits 1 to 9so that every relation sysmbol is correct.

Matthias

                  
Re: Off-Topic: Who can solve this?
Message #4 Posted by Eric Smith on 27 Feb 2010, 7:02 p.m.,
in response to message #3 by Matthias Wehrli

So there isn't a limitation as to how many of each digit are used in each row, column, etc.?

      
Re: Off-Topic: Who can solve this?
Message #5 Posted by Vieira, Luiz C. (Brazil) on 27 Feb 2010, 5:16 p.m.,
in response to message #1 by Matthias Wehrli

Hi;

I felt dizzy twice: by looking at the drawing and by thinking of the the possibilities of starting over...

I particularly do not like games neither mind puzzles, but I like to understand their solutions. In some cases there is a rational line in finding one or another solution, in others is just a matter of being lucky enough choosing the starting direction.

I thought about starting with '5' (upper, leftmost digit in the top) because the set is symmetrical and '5' is right in the middle of it: 1,2,3,4,5,6,7,8,9 and the '>' and '<' alternate with each other in the first line. Then I thought: 'Too simple minded solution...' and tried to 'see' how would the numbers evolve in the picture. That´s when I felt the second dizziness and gave up.

Success and thanks for bringing it up! And if someone finds a rational way to solve it by reasoning, please, let me know the solution. Otherwise, if it is just a matter of starting with the right numbers, then the chances to make it wrong are way bigger than to make it right, and in this case, the solution cannot be explained, only shown.

That´s why I prefer trying to solve problems of the real world.

Luiz (Brazil)

Edited: 27 Feb 2010, 5:17 p.m.

      
Re: Off-Topic: Who can solve this?
Message #6 Posted by Paul Dale on 27 Feb 2010, 11:46 p.m.,
in response to message #1 by Matthias Wehrli

I don't know the limitations on the placements of the digits. I'd assume that each 3x3 square has the digits 1 through 9 as per a traditional sudoku. A sudoku is normally a 9x9 grid with each row and column also including the digits 1 through 9, clearly this isn't the case here. It kind of looks like four sudoku puzzles overlapped at the corners.

Despite that, it doesn't look too horrible. Every nine digit must have all neighbours less than (given the lack of equalities). Likewise every 1 digit must have all neighbours greater. These two rules ought to net a few digits in the grids. Then a lot of deductive logic follows...

If I get bored enough I might give it a go....

- Pauli

            
Re: Off-Topic: Who can solve this?
Message #7 Posted by Paul Dale on 28 Feb 2010, 7:21 a.m.,
in response to message #6 by Paul Dale

I got bored enough -- something about most of our office having been made redundant on Tuesday :-(

It is four sudoku puzzles with common corners. The key things here are each 3x3 square with semi-bold borders has the digits 1 through 9. Each row and column of the 9x9 bold squares has the digits 1 through 9.

Anyway, it is possible to progress. Start by considering '9'. Any square containing this must be greater than all adjacent squares. Search the grid for a 3x3 square which has one square greater than everything and no others. E.g. the middle square in the second from the bottom row or the bottom right corner on the lower puzzle. Fill these with '9'. Then some deduction will allow you to completely fill all nines.

Next, do the same thing for '1'. Find a 3x3 square with only one place less than all its neighbours. E.g. the bottom right square in the lower puzzle. Fill these with '1'. Some more deduction will allow you to fill every '1' in the puzzle in.

Consider '8'. Any square that is less than a blank cannot hold an '8'. So we've got to locate squares that are greater than all their neighbours (excepting possibly a '9'). The same bottom right square is an example here too. Some more searching and deduction allows every '8' bar two to be placed.

Do the same things for '2'. Again all can be placed.

You should have the idea by now. Continue with the other numbers.

- Pauli

                  
Re: Off-Topic: Who can solve this?
Message #8 Posted by Allen on 28 Feb 2010, 10:01 a.m.,
in response to message #7 by Paul Dale

I"m looking into a graphical method by which "line length" is used to find the topology of each grid. Starting with a "peak" you can move downhill, counting each line length only once, and so find some useful relations. This square shows the easiest one for "9". The numbers are counting steps, not the number that should be in the grid.

                        
Re: Off-Topic: Who can solve this?
Message #9 Posted by Vieira, Luiz C. (Brazil) on 28 Feb 2010, 11:25 a.m.,
in response to message #8 by Allen

Hi, allen;

this makes sense to me. First I thought the numbers you placed were the ones to fill the squares, then I saw they were the 'filling' sequence. If we start with 9, choosing were to place 6 and 5 (left-right or right-left) depends on the relations with the other 9-squares square, right? Would it be some Operational Research problem? Should G.A.M.S. be used to solve it?

Good luck to you all!

Luiz (Brazil)

Edited: 28 Feb 2010, 11:26 a.m.

      
Re: Off-Topic: Who can solve this?
Message #10 Posted by Eric Smith on 28 Feb 2010, 9:37 p.m.,
in response to message #1 by Matthias Wehrli

I'm working on a solver for it. I typed in a representation of the puzzle in plain text to work from, using A and V to represent the vertical inequalities, but it's tedious work and rather error-prone. Would anyone care to check my work? I think the easiest way would be for someone else to create the same thing, then we can diff them.

My text is: 

             < > < > < > < >
            A V A V A A A V V
             > < > < < > > <
            A A A V V V V A V
             < > > > < > < <
            V V V A A V A A V
             > > < < > < < >
            A A A V V A V V A
             > < > < < > < >
            V A V A A V A V V
             < > < > > < > <
            A V A A A V V A V
 > < > < < < > < < > > < > > < < > < < <
A A A A A V V V V A A V V A A A A A V V V
 > < > < > < > > < > > < < < < < > > > <
V A V A V A V A V V V A A A A V V V A A A
 > > < > < > < > < < > < > < > < > < > <
V V V V V V A A A       V A V V V A A A A
 > > < > < > < <         < > > < < < > <
V V A A A V A V V       A A V A A A V V A
 < < > < > < > <         < > < < < > < <
A A V V V A A A V       V V A A A A A A V
 < < > > < > > <         > < < < < > < >
A A V A A V V A V       A A A V V V A A V
 < > < < > < > > < > < > > < > > < < < >
V A V V V A V A A V A V V A A A A A V V V
 < > > < > > < > > < > > < < < > < > < >
V A V A V V A V A A V V A V V V A A A V V
 < > < < > < < < > > < < > > > < < > > >
            A V V V A A V A A
             > < > < < < < >
            V A A A A A V V V
             < < > < < > < >
            A V V A A A A V A
             > < < < < > > <
            A A A A V V A V V
             > > < > < > > <
            V A A V A V V A A
             > < > < > < < >
            V V V A V A A A A
             < < < > < < < <

(I caught one error and updated this.)

Edited: 28 Feb 2010, 11:27 p.m.

            
Re: Off-Topic: Who can solve this?
Message #11 Posted by Eric Smith on 1 Mar 2010, 1:19 a.m.,
in response to message #10 by Eric Smith

My solver reports that there are eight solutions to this puzzle, rather than a single unique solution. Here's the first solution it found:

            2 7 4 5 3 6 1 9 8            
            3 1 5 4 8 9 6 2 7            
            6 9 8 2 1 7 3 4 5            
            4 2 1 6 9 5 7 8 3            
            7 3 9 1 2 8 5 6 4            
            5 8 6 7 4 3 9 1 2            
3 1 6 2 4 8 9 5 7 8 6 2 4 3 1 5 6 2 7 8 9
9 2 7 5 6 1 8 4 3 9 7 1 2 5 6 8 9 7 3 1 4
8 5 4 9 3 7 1 6 2 3 5 4 8 7 9 3 4 1 5 2 6
7 4 1 6 2 5 3 8 9       6 8 5 1 2 3 9 4 7
2 3 9 7 8 4 5 1 6       7 9 2 4 5 6 1 3 8
5 6 8 3 1 9 7 2 4       3 1 4 7 8 9 2 6 5
6 7 5 8 9 2 4 3 1 9 6 8 5 2 7 6 1 4 8 9 3
4 8 3 1 7 6 2 9 5 3 7 4 1 6 8 9 3 5 4 7 2
1 9 2 4 5 3 6 7 8 5 1 2 9 4 3 2 7 8 6 5 1
            7 4 6 1 2 3 8 9 5            
            3 8 9 4 5 6 2 7 1            
            5 1 2 7 8 9 4 3 6            
            9 5 3 8 4 7 6 1 2            
            8 6 7 2 9 1 3 5 4            
            1 2 4 6 3 5 7 8 9

Edited: 1 Mar 2010, 1:32 a.m.

                  
combinations vs. permutations
Message #12 Posted by mike reed on 3 Mar 2010, 10:07 a.m.,
in response to message #11 by Eric Smith

Eric - I suspect your solver may be reporting combinations, not permutations... I don't think there is more than one unique solution to this puzzle, but with it's 90 degree rotations, the mirror solution, and its rotations - that gives you eight combinations. It was a fun puzzle to solve - took me about 45 minutes and a pencil. I did not use any calculating or computational devices.

                        
Re: combinations vs. permutations
Message #13 Posted by Eric Smith on 4 Mar 2010, 8:41 p.m.,
in response to message #12 by mike reed

No, there aren't any rotations, etc., that satisfy the inequalities, because the inequalities are not arranged symmetrically around the puzzle. The eight solutions my solver found are very similar, differing mainly by a few values near the bottom of the puzzle.

I have not manually verified all eight solutions, so it is possible that my solver has a bug. I can send all eight to anyone that cares to try to verify them, or post them here if there is general interest.

Edited: 5 Mar 2010, 3:19 a.m. after one or more responses were posted

                              
Re: combinations vs. permutations
Message #14 Posted by Eric Smith on 5 Mar 2010, 3:19 a.m.,
in response to message #13 by Eric Smith

The eight solutions are the possible combinations of three independent variations in different parts of the puzzle.

Solution 1:

 1:              2 7 4[5 3 6]1 9 8            
 2:              3 1 5 4 8 9 6 2 7            
 3:              6 9 8 2 1 7 3 4 5            
 4:              4 2 1[6 9 5]7 8 3            
 5:              7 3 9 1 2 8 5 6 4            
 6:              5 8 6 7 4 3 9 1 2            
 7: [3 1 6 2 4]8 9 5 7 8 6 2 4 3 1 5 6 2 7 8 9
 8:  9 2 7 5 6 1 8 4 3 9 7 1 2 5 6 8 9 7 3 1 4
 9:  8 5[4 9 3]7 1 6 2 3 5 4 8 7 9 3 4 1 5 2 6
10:  7 4 1 6 2 5 3 8 9       6 8 5 1 2 3 9 4 7
11:  2 3 9 7 8 4 5 1 6       7 9 2 4 5 6 1 3 8
12:  5 6 8 3 1 9 7 2 4       3 1 4 7 8 9 2 6 5
13:  6 7 5 8 9 2 4 3 1 9 6 8 5 2 7 6 1 4 8 9 3
14: [4 8 3]1 7 6 2 9 5 3 7 4 1 6 8 9 3 5 4 7 2
15:  1 9 2 4 5 3 6 7 8 5 1 2 9 4 3 2 7 8 6 5 1
16:              7 4 6 1 2 3 8 9 5            
17:              3 8 9 4 5 6 2 7 1            
18:              5 1 2 7 8 9 4 3 6            
19:              9 5[3 8 4]7 6 1 2            
20:              8 6 7 2 9 1 3 5 4            
21:              1 2[4 6 3]5 7 8 9            

Locations of possible alternates are marked above with
brackets.

Solution 2:  replace line 19 [3 8 4] with [4 8 3]
             replace line 21 [4 6 3] with [3 6 4]

Solution 3:  replace line 7 [3 1 6 2 4] with [4 1 6 2 3]
             replace line 9 [4 9 3] with [3 9 4]
             replace line 14 [4 8 3] with [3 8 4]

Solution 4:  replace line 1 [5 3 6] with [6 3 5]
             replace line 4 [6 9 5] with [5 9 6]

Solution 5:  apply the changes of both Solutions 2 and 3

Solution 6:  apply the changes of both Solutions 2 and 4

Solution 7:  apply the changes of both Solutions 3 and 4

Solution 8:  apply the changes of Solutions 2, 3, and 4

[ Return to Index | Top of Index ]

Go back to the main exhibit hall