Home » Other » General » Can anyone solve this puzzle using SQL?
|
|
|
|
| Re: Can anyone solve this puzzle using SQL? [message #356829 is a reply to message #356827] |
Sun, 02 November 2008 13:00   |
 |
Kevin Meade
Messages: 2103
Registered: December 1999
Location: Connecticut USA
|
Senior Member |
|
|
THis is a good example problem for modeling. This problem reminds me of the craze twenty years ago that delt with building expert systems. It was remarked in more than one paper/book, that it was alway possible to build an expert system using the correct database design, but that relational databases were prehapes not the best implementation vehicle for these types of problems. Maybe that was true maybe not. Maybe relational database flexibility and capabilities have changed sufficiently since then to alter the opiions of those who made these statements.
In then end though puzzles like these still remain as a good way to showcase database design and problem analysis skills.
Your solution must start with a basic examiniation of the problem. You need to articulate two things to begin:
| Quote: | 1) what are the omponents of the problem.
2) how will you recognize you have a solution.
|
For exmaple, I would start you off notiing:
| Quote: | 1) your problem has some number of disks (1 thru 7 in this case)
2) each disk has some number of colors (six on each disk in this case)
3) each disk has the same colors
4) however, the colors are not arranged on each disk in the same location each time (ie.disks are not identical)
5) you have locations to which each disk can be slotted
6) disks can change slots if necessary to yeild a solution
7) colors on the disks can be identified by a name
 colors on the disks can be identified by a number
9) colors on the disks can also be identifed on each disk by their relative position to some "absolute zero" (say white)
|
The above would be a good start on the problem space characteristics. Notice in particular although we can identify each spot on each disk by using (disk,color) or (disk,spot number) or (disk,relative offset), this does not help us in delaring a solution. We must place disks into slots first in order to construct an actual puzzle with the affect such that spots on disks in a puzzle are idetifiable by (slot, color) or (slot, spot number), or (slot, relative offset) given that we know into which slot each disk havs been placed.
The above suggest it is possible to deliniate all possible puzzle variations for any given puzzle in a clear way. Each variation would be disks in specific slots in specific orientations. Each variation cold be checked to see if it meets solution criteria.
This leads us next to define what makes a solution "correct", in terms of the items above. If you can't do that then you are missing something necessary to the problem solution that you have not yet modeled. Might I suggest that a solution would be found where a specific set of spots match a specific set of conditions.
Lastly, in coding an actual SQL solution, you might wish to look at RELATIONAL DIVISION as one possible approach. Understanding the nature of relational division will aid you in understanding what SET problems are about, and the difficulties in solving SET problems. Ulitmately you will find that a relational division solution will be way to slow to be practiical for large problem spaces (and this one might be large), at which point you may wsh to turn to a plsql memory based solution where you use arrays to hold data and do lookups into the arrays to find an answer.
Good luck, Kevin
|
|
|
|
| Re: Can anyone solve this puzzle using SQL? [message #356865 is a reply to message #356829] |
Sun, 02 November 2008 22:46 |
rleishman
Messages: 3728
Registered: October 2005
Location: Melbourne, Australia
|
Senior Member |
|
|
Don't know about SQL.
But by my reckoning, there are 7 possibilities for choosing the central disk.
Then if we number the remaining positions 1-6, we get:
- For Position 1, there are 6 possibilities for choosing a disk. Since the colour must match the central disk, there is only one rotational possibility.
- For position 2, there are 5 remaining possibilities for choosing a disk. Again, the colour must match the central disk, so there is only 1 rotational possibility.
- etc.
In all, thats 7 x 6 x 5 x 4 x 3 x 2 x 1 = 7! = 5040 possibilities.
That's not exactly heaps. Since a lot of combinations would prove unmatched on the 3rd disk placement, most attempts would take no more than around 1 or 2 seconds, a brute-force manual solution should take you no more than a couple of hours.
I don't reckon I could program it that fast.
Ross Leishman
|
|
|
|
|
|
| Re: Can anyone solve this puzzle using SQL? [message #357620 is a reply to message #357002] |
Thu, 06 November 2008 01:18 |
rleishman
Messages: 3728
Registered: October 2005
Location: Melbourne, Australia
|
Senior Member |
|
|
OK - I detect a challenge. Or maybe I'm being a bit sensitive about it ...
But as an '80s Rubik's Cube geek, I now cannot resist.
First we need some data. I'll define the following TYPE:
create or replace type dp as object (
disk integer
, colour varchar2(10)
, lcolour varchar2(10)
, rcolour varchar2(10)
)
/
This represents a coloured spot on a disk. If we number the disks in the photo; the middle disk is #1, the top disk (slightly to the right) is #2, and #3 through #7 clockwise from the top.
The tuple (1, 'White','Yellow','Blue') means the WHITE spot on DISK1 (currently in the centre) has a YELLOW spot to its left and a BLUE spot to its right.
We can define all 7 disks as follows:
SELECT *
FROM table(dparr(
dp(1, 'White','Yellow','Blue')
, dp(1, 'Blue','White','Green')
, dp(1, 'Green','Blue','Red')
, dp(1, 'Red','Green','Black')
, dp(1, 'Black','Red','Yellow')
, dp(1, 'Yellow','Black','White')
, dp(2, 'White','Red','Blue')
, dp(2, 'Blue','White','Black')
, dp(2, 'Black','Blue','Yellow')
, dp(2, 'Yellow','Black','Green')
, dp(2, 'Green','Yellow','Red')
, dp(2, 'Red','Green','White')
, dp(3, 'White','Blue','Red')
, dp(3, 'Red','White','Green')
, dp(3, 'Green','Red','Yellow')
, dp(3, 'Yellow','Green','Black')
, dp(3, 'Black','Yellow','Blue')
, dp(3, 'Blue','Black','White')
, dp(4, 'White','Red','Black')
, dp(4, 'Black','White','Green')
, dp(4, 'Green','Black','Blue')
, dp(4, 'Blue','Green','Yellow')
, dp(4, 'Yellow','Blue','Red')
, dp(4, 'Red','Yellow','White')
, dp(5, 'White','Red','Green')
, dp(5, 'Green','White','Black')
, dp(5, 'Black','Green','Blue')
, dp(5, 'Blue','Black','Yellow')
, dp(5, 'Yellow','Blue','Red')
, dp(5, 'Red','Yellow','White')
, dp(6, 'White','Red','Blue')
, dp(6, 'Blue','White','Yellow')
, dp(6, 'Yellow','Blue','Green')
, dp(6, 'Green','Yellow','Black')
, dp(6, 'Black','Green','Red')
, dp(6, 'Red','Black','White')
, dp(7, 'White','Black','Green')
, dp(7, 'Green','White','Yellow')
, dp(7, 'Yellow','Green','Blue')
, dp(7, 'Blue','Yellow','Red')
, dp(7, 'Red','Blue','Black')
, dp(7, 'Black','Red','White')
))
DISK COLOUR LCOLOUR RCOLOUR
---------- ---------- ---------- ----------
1 White Yellow Blue
1 Blue White Green
1 Green Blue Red
1 Red Green Black
1 Black Red Yellow
1 Yellow Black White
2 White Red Blue
2 Blue White Black
2 Black Blue Yellow
2 Yellow Black Green
2 Green Yellow Red
2 Red Green White
3 White Blue Red
3 Red White Green
3 Green Red Yellow
3 Yellow Green Black
3 Black Yellow Blue
3 Blue Black White
4 White Red Black
4 Black White Green
4 Green Black Blue
4 Blue Green Yellow
4 Yellow Blue Red
4 Red Yellow White
5 White Red Green
5 Green White Black
5 Black Green Blue
5 Blue Black Yellow
5 Yellow Blue Red
5 Red Yellow White
6 White Red Blue
6 Blue White Yellow
6 Yellow Blue Green
6 Green Yellow Black
6 Black Green Red
6 Red Black White
7 White Black Green
7 Green White Yellow
7 Yellow Green Blue
7 Blue Yellow Red
7 Red Blue Black
7 Black Red White
42 rows selected.
Now for the Solution.
We need a starting point: since every disk has every colour, it is fair to say that the SOLUTION will have a white dot on the centre disk (this is true of any colour and any disk, but we have to start somewhere).
So the set of all possible starting points is:
1 with disks as (
2 SELECT *
3 FROM table(dparr(
4 dp(1, 'White','Yellow','Blue')
5 , dp(1, 'Blue','White','Green')
: : : :
44 , dp(7, 'Red','Blue','Black')
45 , dp(7, 'Black','Red','White')
46 ))
47 )
48 SELECT *
49 FROM disks d01
50* where d01.colour = 'White'
DISK COLOUR LCOLOUR RCOLOUR
---------- ---------- ---------- ----------
1 White Yellow Blue
2 White Red Blue
3 White Blue Red
4 White Red Black
5 White Red Green
6 White Red Blue
7 White Black Green
7 rows selected.
In this SQL we have only selected the WHITE spot on the middle disk. We are going to need all of the spots for our solution, so lets join them in:
1 with disks as (
2 SELECT *
3 FROM table(dparr(
4 dp(1, 'White','Yellow','Blue')
5 , dp(1, 'Blue','White','Green')
6 , dp(1, 'Green','Blue','Red')
: : : :
44 , dp(7, 'Red','Blue','Black')
45 , dp(7, 'Black','Red','White')
46 ))
47 )
48 SELECT d01.disk, d01.colour as spot1, d02.colour as spot2, d03.colour as spot3
49 , d04.colour as spot4, d05.colour as spot5, d06.colour as spot6
50 FROM disks d01
51 JOIN disks d02 ON d02.colour = d01.rcolour
52 AND d02.disk = d01.disk
53 JOIN disks d03 ON d03.colour = d02.rcolour
54 AND d03.disk = d02.disk
55 JOIN disks d04 ON d04.colour = d03.rcolour
56 AND d04.disk = d03.disk
57 JOIN disks d05 ON d05.colour = d04.rcolour
58 AND d05.disk = d04.disk
59 JOIN disks d06 ON d06.colour = d05.rcolour
60 AND d06.disk = d05.disk
61* where d01.colour = 'White'
DISK SPOT1 SPOT2 SPOT3 SPOT4 SPOT5 SPOT6
---------- ---------- ---------- ---------- ---------- ---------- ----------
4 White Black Green Blue Yellow Red
1 White Blue Green Red Black Yellow
2 White Blue Black Yellow Green Red
6 White Blue Yellow Green Black Red
5 White Green Black Blue Yellow Red
7 White Green Yellow Blue Red Black
3 White Red Green Yellow Black Blue
7 rows selected.
So that's seven possible choices for the central disk, with the spots listed in clockwise order starting with WHITE.
Now we need to start positioning the other disks. Starting with the WHITE spot on the central disk, we could join any of the 6 remaining disks. In the above SQL, the WHITE spot is represented by the table alias D01 - we want to join all of the spots of matching colour EXCEPT the centre disk, which has already been used:
1 with disks as (
2 SELECT *
3 FROM table(dparr(
4 dp(1, 'White','Yellow','Blue')
5 , dp(1, 'Blue','White','Green')
: : : :
44 , dp(7, 'Red','Blue','Black')
45 , dp(7, 'Black','Red','White')
46 ))
47 )
48 SELECT d01.disk AS CENTRE, d1.disk AS POS1
49 FROM disks d01
50 JOIN disks d02 ON d02.colour = d01.rcolour
51 AND d02.disk = d01.disk
52 JOIN disks d03 ON d03.colour = d02.rcolour
53 AND d03.disk = d02.disk
54 JOIN disks d04 ON d04.colour = d03.rcolour
55 AND d04.disk = d03.disk
56 JOIN disks d05 ON d05.colour = d04.rcolour
57 AND d05.disk = d04.disk
58 JOIN disks d06 ON d06.colour = d05.rcolour
59 AND d06.disk = d05.disk
60 JOIN disks d1 ON d1.colour = d01.colour
61 AND d1.disk <> d01.disk
62* where d01.colour = 'White'
CENTRE POS1
---------- ----------
7 4
7 2
7 5
7 1
7 6
7 3
3 1
3 2
3 4
3 7
3 5
3 6
2 7
2 4
2 6
2 3
2 5
2 1
4 3
4 7
4 2
4 1
4 5
4 6
5 6
5 4
5 7
5 3
5 2
5 1
6 5
6 7
6 1
6 4
6 2
6 3
1 6
1 2
1 3
1 7
1 5
1 4
42 rows selected.
This means there are 42 (7 x 6) different combinations of centre disk plus another disk that matches the WHITE spot.
Now we join in a third disk. This one has to match the spot to the RIGHT of the WHITE spot on the centre disk AND the colour of the spot to the LEFT of the WHITE spot on the disk at POS1.
1 with disks as (
2 SELECT *
3 FROM table(dparr(
4 dp(1, 'White','Yellow','Blue')
5 , dp(1, 'Blue','White','Green')
6 , dp(1, 'Green','Blue','Red')
: : : :
44 , dp(7, 'Red','Blue','Black')
45 , dp(7, 'Black','Red','White')
46 ))
47 )
48 SELECT d01.disk as centre, d1.disk as pos1, d2.disk as pos2
49 FROM disks d01
50 JOIN disks d02 ON d02.colour = d01.rcolour
51 AND d02.disk = d01.disk
52 JOIN disks d03 ON d03.colour = d02.rcolour
53 AND d03.disk = d02.disk
54 JOIN disks d04 ON d04.colour = d03.rcolour
55 AND d04.disk = d03.disk
56 JOIN disks d05 ON d05.colour = d04.rcolour
57 AND d05.disk = d04.disk
58 JOIN disks d06 ON d06.colour = d05.rcolour
59 AND d06.disk = d05.disk
60 JOIN disks d1 ON d1.colour = d01.colour
61 AND d1.disk <> d01.disk
62 JOIN disks d2 ON d2.colour = d02.colour
63 AND d2.rcolour = d1.lcolour
64 AND d2.disk <> d01.disk
65 AND d2.disk <> d1.disk
66* where d01.colour = 'White'
CENTRE POS1 POS2
---------- ---------- ----------
7 4 1
7 4 2
7 6 1
7 2 1
7 1 3
7 5 2
7 5 1
7 6 2
7 3 4
3 7 1
2 4 7
2 1 6
2 1 4
2 6 7
2 1 5
2 5 7
4 1 2
4 5 6
4 2 6
4 3 5
5 4 1
5 1 7
5 2 1
5 4 2
5 6 1
5 7 6
5 1 3
5 3 4
5 6 2
6 1 5
6 5 7
6 4 7
6 2 7
6 7 2
6 1 4
1 6 7
1 7 2
1 5 7
1 2 7
1 4 7
40 rows selected.
WOW! Now that we have placed 3 disks, we've gone from 42 combinations down to 40 combinations. There are 210 (7x6x5) possible arrangements, but 170 of them FAIL to match the coloured spot to the left of the WHITE one on disk 2.
Now we continue with this approach for POSITIONS 3, 4, and 5. Position 6 (the final position) is special - it must match up to the centre disk, position 5 AND position 1.
1 with disks as (
2 SELECT *
3 FROM table(dparr(
4 dp(1, 'White','Yellow','Blue')
5 , dp(1, 'Blue','White','Green')
6 , dp(1, 'Green','Blue','Red')
7 , dp(1, 'Red','Green','Black')
8 , dp(1, 'Black','Red','Yellow')
9 , dp(1, 'Yellow','Black','White')
10 , dp(2, 'White','Red','Blue')
11 , dp(2, 'Blue','White','Black')
12 , dp(2, 'Black','Blue','Yellow')
13 , dp(2, 'Yellow','Black','Green')
14 , dp(2, 'Green','Yellow','Red')
15 , dp(2, 'Red','Green','White')
16 , dp(3, 'White','Blue','Red')
17 , dp(3, 'Red','White','Green')
18 , dp(3, 'Green','Red','Yellow')
19 , dp(3, 'Yellow','Green','Black')
20 , dp(3, 'Black','Yellow','Blue')
21 , dp(3, 'Blue','Black','White')
22 , dp(4, 'White','Red','Black')
23 , dp(4, 'Black','White','Green')
24 , dp(4, 'Green','Black','Blue')
25 , dp(4, 'Blue','Green','Yellow')
26 , dp(4, 'Yellow','Blue','Red')
27 , dp(4, 'Red','Yellow','White')
28 , dp(5, 'White','Red','Green')
29 , dp(5, 'Green','White','Black')
30 , dp(5, 'Black','Green','Blue')
31 , dp(5, 'Blue','Black','Yellow')
32 , dp(5, 'Yellow','Blue','Red')
33 , dp(5, 'Red','Yellow','White')
34 , dp(6, 'White','Red','Blue')
35 , dp(6, 'Blue','White','Yellow')
36 , dp(6, 'Yellow','Blue','Green')
37 , dp(6, 'Green','Yellow','Black')
38 , dp(6, 'Black','Green','Red')
39 , dp(6, 'Red','Black','White')
40 , dp(7, 'White','Black','Green')
41 , dp(7, 'Green','White','Yellow')
42 , dp(7, 'Yellow','Green','Blue')
43 , dp(7, 'Blue','Yellow','Red')
44 , dp(7, 'Red','Blue','Black')
45 , dp(7, 'Black','Red','White')
46 ))
47 )
48 SELECT d01.disk, d1.disk, d2.disk, d3.disk, d4.disk, d5.disk, d6.disk
49 FROM disks d01
50 JOIN disks d02 ON d02.colour = d01.rcolour
51 AND d02.disk = d01.disk
52 JOIN disks d03 ON d03.colour = d02.rcolour
53 AND d03.disk = d02.disk
54 JOIN disks d04 ON d04.colour = d03.rcolour
55 AND d04.disk = d03.disk
56 JOIN disks d05 ON d05.colour = d04.rcolour
57 AND d05.disk = d04.disk
58 JOIN disks d06 ON d06.colour = d05.rcolour
59 AND d06.disk = d05.disk
60 JOIN disks d1 ON d1.colour = d01.colour
61 AND d1.disk <> d01.disk
62 JOIN disks d2 ON d2.colour = d02.colour
63 AND d2.rcolour = d1.lcolour
64 AND d2.disk <> d01.disk
65 AND d2.disk <> d1.disk
66 JOIN disks d3 ON d3.colour = d03.colour
67 AND d3.rcolour = d2.lcolour
68 AND d3.disk <> d01.disk
69 AND d3.disk <> d1.disk
70 AND d3.disk <> d2.disk
71 JOIN disks d4 ON d4.colour = d04.colour
72 AND d4.rcolour = d3.lcolour
73 AND d4.disk <> d01.disk
74 AND d4.disk <> d1.disk
75 AND d4.disk <> d2.disk
76 AND d4.disk <> d3.disk
77 JOIN disks d5 ON d5.colour = d05.colour
78 AND d5.rcolour = d4.lcolour
79 AND d5.disk <> d01.disk
80 AND d5.disk <> d1.disk
81 AND d5.disk <> d2.disk
82 AND d5.disk <> d3.disk
83 AND d5.disk <> d4.disk
84 JOIN disks d6 ON d6.colour = d06.colour
85 AND d6.rcolour = d5.lcolour
86 AND d6.lcolour = d1.rcolour
87 AND d6.disk <> d01.disk
88 AND d6.disk <> d1.disk
89 AND d6.disk <> d2.disk
90 AND d6.disk <> d3.disk
91 AND d6.disk <> d4.disk
92 AND d6.disk <> d5.disk
93* where d01.colour = 'White'
DISK DISK DISK DISK DISK DISK DISK
---------- ---------- ---------- ---------- ---------- ---------- ----------
5 6 1 3 4 2 7
There's the solution (I hope). I haven't tested it by printing the picture and cutting out the disks, but I am encouraged by the fact that it returned 1 row.
This is how you would verify the solution.
- Print the picture
- Number the disks in the picture from 1 to 7. 1 is the centre disk, 2-7 are numbered clockwise from the top right.
- Cut out the disks.
- Place disk 5 in the centre - WHITE spot pointing straight UP.
- Place disk 6 at the top with its WHITE spot matching that of disk 5.
- Place disk 1 to the right (clockwise) of disk 6, with the coloured spots matching disks 5 and 6.
- Repeat for disks 3, 4, 2, and 7 working in a clockwise direction
This took me about an hour to do and 40 minutes to write up here. I'm not convinced brute force would have been slower, but it would certainly have been duller.
Ross Leishman
|
|
|
|
|
|
| Re: Can anyone solve this puzzle using SQL? [message #357753 is a reply to message #356826] |
Thu, 06 November 2008 08:16 |
|
Kevin Meade
Messages: 2103
Registered: December 1999
Location: Connecticut USA
|
Senior Member |
|
|
You know, after thinking about this for a few minutes, I feel compeled to speak more.
This is without a doubt, one of the top 10 best posts I have seen on OraFAQ in my seven years of visiting this site. Not because it has some slick code technique, but because it shows clearly how problems are solved in the anlaysis and design phases and not in the coding phase.
You can be the greatest coder in the world, knowing any number of languages expertly and how to use every feature in any of them, but if you can't analyze a problem well, you are doomed.
Indeed, in every problem there is always a critical thought that will help you see the answer, because it has the right perspective, and it usually has something to do with how you see some particular central piece of data. Ross, the key to yours is your use of the three color table. It is the key to what defines a solution, expressed well. This shows how you thought about the problem space way better than I and came up with the perspective on the problem that made for a great solution.
If there is a postings HALL-OF-FAME of POST-OF-THE-DAY area on OraFAQ, then I'd like to see this one go in it. Anybody know? If not, then we maybe the site moderator or someone can figure out how to create and manage one.
Again, this post shows how we make our money in problem analysis and design. Don't go that? Then work on it, or find some other way to pay your bills.
Kevin
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
| Re: Can anyone solve this puzzle using SQL? [message #358163 is a reply to message #358142] |
Sun, 09 November 2008 19:31 |
rleishman
Messages: 3728
Registered: October 2005
Location: Melbourne, Australia
|
Senior Member |
|
|
M&M Cookies wouldn't last long enough to take a photo in my house.
My youngest targets them at the cafe and nibbles of the M&Ms, leaving the biscuit. Some are stuck in pretty tight and thwart levering out with tiny fingers. I showed him how to break it in two so that the M&M is now at an edge and can be pecked out with teeth. I got one of those all-too-rare 2YO looks that said 'You legend; I have much to learn.'
|
|
|
|
Goto Forum:
Current Time: Tue Nov 26 10:06:55 CST 2024
|
] 
Blog
Search
Help
Members
Register
Login
Home
