Solution to Seven Piece Hex Puzzle Using Database Technology
This is a solution to the seven hexagonal piece puzzle shown above.
The puzzle came to me through my deceased father-in-law. The object is to match the sides of each hex piece to adjacent sides having matching numbers. I found it to be a very interesting puzzle to solve. Of course once I did solve it, I was even more interested in solving it on my computer.
I had a false start in excel which I probably could have concluded, but I found a much cleaner solution using my database knowledge which I'll share with you now.
I had mysql 4.0.26 available so that's what the sql is targeted for, though you could easily change the statements to fit the database of your choice.
First I created the database and told mysql to connect to that database:
create database Puzzle;
use Puzzle
Next I created the Piece table to store the ID and sequence of numbers in clockwise direction starting with one. These choices were arbitrary. I could just as easily chosen to go counter-clockwise and start at two:
create table Piece (
ID varchar(1) NOT NULL default '',
Description varchar(6) NOT NULL default '',
primary key (ID)
)type=myisam;
Now for the problem solving part. Note that the puzzle places the pieces such that only three sides of each piece must match touching pieces. So each sequence of three sides (in clockwise order) can be stored to represent the possible combinations of touching pieces. Creation of this Sequence table is as follows:
create table Sequence (
Piece_ID varchar(1) NOT NULL default '',
Seq_ID varchar(1) NOT NULL default '',
Seq varchar(3) NOT NULL default '',
primary key (Piece_ID,Seq_ID)
)type=myisam;
Pieces are now inserted:
insert into Piece values ('1','146235');
insert into Piece values ('2','143652');
insert into Piece values ('3','165432');
insert into Piece values ('4','162453');
insert into Piece values ('5','123456');
insert into Piece values ('6','164253');
insert into Piece values ('7','165324');
Next come the Sequences:
insert into Sequence values ('1','1','514');
insert into Sequence values ('1','2','623');
insert into Sequence values ('1','3','235');
insert into Sequence values ('1','4','146');
insert into Sequence values ('1','5','351');
insert into Sequence values ('1','6','462');
insert into Sequence values ('2','1','214');
insert into Sequence values ('2','2','521');
insert into Sequence values ('2','3','436');
insert into Sequence values ('2','4','143');
insert into Sequence values ('2','5','652');
insert into Sequence values ('2','6','365');
insert into Sequence values ('3','1','216');
insert into Sequence values ('3','2','321');
insert into Sequence values ('3','3','432');
insert into Sequence values ('3','4','543');
insert into Sequence values ('3','5','654');
insert into Sequence values ('3','6','165');
insert into Sequence values ('4','1','316');
insert into Sequence values ('4','2','624');
insert into Sequence values ('4','3','531');
insert into Sequence values ('4','4','245');
insert into Sequence values ('4','5','453');
insert into Sequence values ('4','6','162');
insert into Sequence values ('5','1','612');
insert into Sequence values ('5','2','123');
insert into Sequence values ('5','3','234');
insert into Sequence values ('5','4','345');
insert into Sequence values ('5','5','456');
insert into Sequence values ('5','6','561');
insert into Sequence values ('6','1','316');
insert into Sequence values ('6','2','425');
insert into Sequence values ('6','3','531');
insert into Sequence values ('6','4','642');
insert into Sequence values ('6','5','253');
insert into Sequence values ('6','6','164');
insert into Sequence values ('7','1','416');
insert into Sequence values ('7','2','324');
insert into Sequence values ('7','3','532');
insert into Sequence values ('7','4','241');
insert into Sequence values ('7','5','653');
insert into Sequence values ('7','6','165');
I know I could have added keys, but these tables aren't big enough to worry about that.
I could have used a stored procedure here, but for simplicity I'm just setting two variables and cut/pasting the sql into the mysql session. I could also have wrapped the stored procedure in code and include queries to check for success/failure instead of just manually looking at the results.
So here's the setup based on the idea of starting with each piece in the center of the puzzle, then starting on side number one and continuing clockwise around the puzzle with all valid combinations remaining:
1:
set @Center='1';
set @Tile='146235';
2:
set @Center='2';
set @Tile='143652';
3:
set @Center='3';
set @Tile='165432';
4:
set @Center='4';
set @Tile='162453';
5:
set @Center='5';
set @Tile='123456';
6:
set @Center='6';
set @Tile='164253';
7:
set @Center='7';
set @Tile='165324';
Now the sequence of code for each center in turn. Note that Opt1 stores all valid sequences where side one is center, Opt2 stores all valid remaining sequences for the next side of the center tile being checked, etc.:
drop table if exists opt1;
drop table if exists opt2;
drop table if exists opt3;
drop table if exists opt4;
drop table if exists opt5;
drop table if exists opt6;
create table Opt1 select * from Sequence where Piece_ID <> @Center and Seq_ID=
left(@Tile,1) and left(Seq,1)<>mid(@Tile,2,1) and right(Seq,1)<>right(@Tile,1);
create table Opt2 select Opt1.Piece_ID as Opt1_Piece_ID,Sequence.* from
Opt1 left outer join Sequence on right(Sequence.Seq,1)=left(Opt1.Seq,1) where
Sequence.Seq_ID=mid(@Tile,2,1) and Sequence.Piece_ID<>@Center;
create table Opt3 select Opt1_Piece_ID,Opt2.Piece_ID as Opt2_Piece_ID,
Sequence.* from Opt2 left outer join Sequence on right(Sequence.Seq,1)=
left(Opt2.Seq,1)
where Sequence.Seq_ID=mid(@Tile,3,1) and Sequence.Piece_ID <> Opt2.Piece_ID and
Sequence.Piece_ID<> Opt1_Piece_ID and
Sequence.Piece_ID<>@Center;
create table Opt4 select Opt1_Piece_ID,Opt2_Piece_ID,Opt3.Piece_ID as Opt3_Piece_ID,Sequence.*
from Opt3 left outer join Sequence on right(Sequence.Seq,1)=left(Opt3.Seq,1)
where Sequence.Seq_ID=mid(@Tile,4,1) and
Sequence.Piece_ID <> Opt3.Piece_ID and
Sequence.Piece_ID <> Opt2_Piece_ID and
Sequence.Piece_ID <> Opt1_Piece_ID and
Sequence.Piece_ID<>@Center;
create table Opt5 select Opt1_Piece_ID,Opt2_Piece_ID,Opt3_Piece_ID,Opt4.Piece_ID as Opt4_Piece_ID,
Sequence.*
from Opt4 left outer join Sequence on right(Sequence.Seq,1)=left(Opt4.Seq,1)
where Sequence.Seq_ID=mid(@Tile,5,1) and
Sequence.Piece_ID <> Opt4.Piece_ID and
Sequence.Piece_ID <> Opt3_Piece_ID and
Sequence.Piece_ID <> Opt2_Piece_ID and
Sequence.Piece_ID <> Opt1_Piece_ID and
Sequence.Piece_ID<>@Center;
create table Opt6 select Opt1_Piece_ID,Opt2_Piece_ID,Opt3_Piece_ID,Opt4_Piece_ID,
Opt5.Piece_ID as Opt5_Piece_ID,Sequence.*
from Opt5 left outer join Sequence on right(Sequence.Seq,1)=left(Opt5.Seq,1)
left outer join Opt1 on Opt1_Piece_ID = Opt1.Piece_ID
where Sequence.Seq_ID=mid(@Tile,6,1) and
Sequence.Piece_ID <> Opt5.Piece_ID and
Sequence.Piece_ID <> Opt4_Piece_ID and
Sequence.Piece_ID <> Opt3_Piece_ID and
Sequence.Piece_ID <> Opt2_Piece_ID and
Sequence.Piece_ID <> Opt1_Piece_ID and
right(Opt1.Seq,1)=left(Sequence.Seq,1) and
Sequence.Piece_ID<>@Center;
So the first run looks like this:
mysql> set @Center='1';
Query OK, 0 rows affected (0.05 sec)
mysql> set @Tile='146235';
Query OK, 0 rows affected (0.00 sec)
mysql> drop table if exists opt1;
Query OK, 0 rows affected (0.00 sec)
mysql> drop table if exists opt2;
Query OK, 0 rows affected (0.00 sec)
mysql> drop table if exists opt3;
Query OK, 0 rows affected (0.00 sec)
mysql> drop table if exists opt4;
Query OK, 0 rows affected (0.00 sec)
mysql> drop table if exists opt5;
Query OK, 0 rows affected (0.00 sec)
mysql> drop table if exists opt6;
Query OK, 0 rows affected (0.00 sec)
mysql>
mysql> create table Opt1 select * from Sequence where Piece_ID <> @Center and Se
q_ID=
-> left(@Tile,1) and left(Seq,1)<>mid(@Tile,2,1) and right(Seq,1)<>right(@Ti
le,1);
Query OK, 5 rows affected (0.22 sec)
Records: 5 Duplicates: 0 Warnings: 0
mysql>
mysql> create table Opt2 select Opt1.Piece_ID as Opt1_Piece_ID,Sequence.* from
-> Opt1 left outer join Sequence on right(Sequence.Seq,1)=left(Opt1.Seq,1) w
here
-> Sequence.Seq_ID=mid(@Tile,2,1) and Sequence.Piece_ID<>@Center;
Query OK, 6 rows affected (0.08 sec)
Records: 6 Duplicates: 0 Warnings: 0
mysql>
mysql> create table Opt3 select Opt1_Piece_ID,Opt2.Piece_ID as Opt2_Piece_ID,
-> Sequence.* from Opt2 left outer join Sequence on right(Sequence.Seq,1)=
-> left(Opt2.Seq,1)
-> where Sequence.Seq_ID=mid(@Tile,3,1) and Sequence.Piece_ID <> Opt2.Piece_
ID and
-> Sequence.Piece_ID<> Opt1_Piece_ID and
-> Sequence.Piece_ID<>@Center;
Query OK, 6 rows affected (0.05 sec)
Records: 6 Duplicates: 0 Warnings: 0
mysql>
mysql> create table Opt4 select Opt1_Piece_ID,Opt2_Piece_ID,Opt3.Piece_ID as Opt
3_Piece_ID,Sequence.*
-> from Opt3 left outer join Sequence on right(Sequence.Seq,1)=left(Opt3.Seq
,1)
-> where Sequence.Seq_ID=mid(@Tile,4,1) and
-> Sequence.Piece_ID <> Opt3.Piece_ID and
-> Sequence.Piece_ID <> Opt2_Piece_ID and
-> Sequence.Piece_ID <> Opt1_Piece_ID and
-> Sequence.Piece_ID<>@Center;
Query OK, 5 rows affected (0.05 sec)
Records: 5 Duplicates: 0 Warnings: 0
mysql>
mysql> create table Opt5 select Opt1_Piece_ID,Opt2_Piece_ID,Opt3_Piece_ID,Opt4.P
iece_ID as Opt4_Piece_ID,
-> Sequence.*
-> from Opt4 left outer join Sequence on right(Sequence.Seq,1)=left(Opt4.Seq
,1)
-> where Sequence.Seq_ID=mid(@Tile,5,1) and
-> Sequence.Piece_ID <> Opt4.Piece_ID and
-> Sequence.Piece_ID <> Opt3_Piece_ID and
-> Sequence.Piece_ID <> Opt2_Piece_ID and
-> Sequence.Piece_ID <> Opt1_Piece_ID and
-> Sequence.Piece_ID<>@Center;
Query OK, 2 rows affected (0.03 sec)
Records: 2 Duplicates: 0 Warnings: 0
mysql>
mysql> create table Opt6 select Opt1_Piece_ID,Opt2_Piece_ID,Opt3_Piece_ID,Opt4_P
iece_ID,
-> Opt5.Piece_ID as Opt5_Piece_ID,Sequence.*
-> from Opt5 left outer join Sequence on right(Sequence.Seq,1)=left(Opt5.Seq
,1)
-> left outer join Opt1 on Opt1_Piece_ID = Opt1.Piece_ID
-> where Sequence.Seq_ID=mid(@Tile,6,1) and
-> Sequence.Piece_ID <> Opt5.Piece_ID and
-> Sequence.Piece_ID <> Opt4_Piece_ID and
-> Sequence.Piece_ID <> Opt3_Piece_ID and
-> Sequence.Piece_ID <> Opt2_Piece_ID and
-> Sequence.Piece_ID <> Opt1_Piece_ID and
-> right(Opt1.Seq,1)=left(Sequence.Seq,1) and
-> Sequence.Piece_ID<>@Center;
Query OK, 0 rows affected (0.05 sec)
Records: 0 Duplicates: 0 Warnings: 0
mysql> select * from Opt5;
+---------------+---------------+---------------+---------------+----------+----
----+------+
| Opt1_Piece_ID | Opt2_Piece_ID | Opt3_Piece_ID | Opt4_Piece_ID | Piece_ID | Seq
_ID | Seq |
+---------------+---------------+---------------+---------------+----------+----
----+------+
| 6 | 3 | 2 | 5 | 4 | 3
| 531 |
| 4 | 3 | 2 | 5 | 6 | 3
| 531 |
+---------------+---------------+---------------+---------------+----------+----
----+------+
2 rows in set (0.00 sec)
You can step through all the Center pieces to find that there is only one solution:
mysql> set @Center='4';
Query OK, 0 rows affected (0.00 sec)
mysql> set @Tile='162453';
Query OK, 0 rows affected (0.00 sec)
mysql> drop table if exists opt1;
Query OK, 0 rows affected (0.00 sec)
mysql> drop table if exists opt2;
Query OK, 0 rows affected (0.00 sec)
mysql> drop table if exists opt3;
Query OK, 0 rows affected (0.00 sec)
mysql> drop table if exists opt4;
Query OK, 0 rows affected (0.00 sec)
mysql> drop table if exists opt5;
Query OK, 0 rows affected (0.02 sec)
mysql> drop table if exists opt6;
Query OK, 0 rows affected (0.00 sec)
mysql>
mysql> create table Opt1 select * from Sequence where Piece_ID <> @Center and Se
q_ID=
-> left(@Tile,1) and left(Seq,1)<>mid(@Tile,2,1) and right(Seq,1)<>right(@Ti
le,1);
Query OK, 5 rows affected (0.05 sec)
Records: 5 Duplicates: 0 Warnings: 0
mysql>
mysql> create table Opt2 select Opt1.Piece_ID as Opt1_Piece_ID,Sequence.* from
-> Opt1 left outer join Sequence on right(Sequence.Seq,1)=left(Opt1.Seq,1) w
here
-> Sequence.Seq_ID=mid(@Tile,2,1) and Sequence.Piece_ID<>@Center;
Query OK, 6 rows affected (0.03 sec)
Records: 6 Duplicates: 0 Warnings: 0
mysql>
mysql> create table Opt3 select Opt1_Piece_ID,Opt2.Piece_ID as Opt2_Piece_ID,
-> Sequence.* from Opt2 left outer join Sequence on right(Sequence.Seq,1)=
-> left(Opt2.Seq,1)
-> where Sequence.Seq_ID=mid(@Tile,3,1) and Sequence.Piece_ID <> Opt2.Piece_
ID and
-> Sequence.Piece_ID<> Opt1_Piece_ID and
-> Sequence.Piece_ID<>@Center;
Query OK, 8 rows affected (0.05 sec)
Records: 8 Duplicates: 0 Warnings: 0
mysql>
mysql> create table Opt4 select Opt1_Piece_ID,Opt2_Piece_ID,Opt3.Piece_ID as Opt
3_Piece_ID,Sequence.*
-> from Opt3 left outer join Sequence on right(Sequence.Seq,1)=left(Opt3.Seq
,1)
-> where Sequence.Seq_ID=mid(@Tile,4,1) and
-> Sequence.Piece_ID <> Opt3.Piece_ID and
-> Sequence.Piece_ID <> Opt2_Piece_ID and
-> Sequence.Piece_ID <> Opt1_Piece_ID and
-> Sequence.Piece_ID<>@Center;
Query OK, 8 rows affected (0.05 sec)
Records: 8 Duplicates: 0 Warnings: 0
mysql>
mysql> create table Opt5 select Opt1_Piece_ID,Opt2_Piece_ID,Opt3_Piece_ID,Opt4.P
iece_ID as Opt4_Piece_ID,
-> Sequence.*
-> from Opt4 left outer join Sequence on right(Sequence.Seq,1)=left(Opt4.Seq
,1)
-> where Sequence.Seq_ID=mid(@Tile,5,1) and
-> Sequence.Piece_ID <> Opt4.Piece_ID and
-> Sequence.Piece_ID <> Opt3_Piece_ID and
-> Sequence.Piece_ID <> Opt2_Piece_ID and
-> Sequence.Piece_ID <> Opt1_Piece_ID and
-> Sequence.Piece_ID<>@Center;
Query OK, 4 rows affected (0.05 sec)
Records: 4 Duplicates: 0 Warnings: 0
mysql>
mysql> create table Opt6 select Opt1_Piece_ID,Opt2_Piece_ID,Opt3_Piece_ID,Opt4_P
iece_ID,
-> Opt5.Piece_ID as Opt5_Piece_ID,Sequence.*
-> from Opt5 left outer join Sequence on right(Sequence.Seq,1)=left(Opt5.Seq
,1)
-> left outer join Opt1 on Opt1_Piece_ID = Opt1.Piece_ID
-> where Sequence.Seq_ID=mid(@Tile,6,1) and
-> Sequence.Piece_ID <> Opt5.Piece_ID and
-> Sequence.Piece_ID <> Opt4_Piece_ID and
-> Sequence.Piece_ID <> Opt3_Piece_ID and
-> Sequence.Piece_ID <> Opt2_Piece_ID and
-> Sequence.Piece_ID <> Opt1_Piece_ID and
-> right(Opt1.Seq,1)=left(Sequence.Seq,1) and
-> Sequence.Piece_ID<>@Center;
Query OK, 1 row affected (0.06 sec)
Records: 1 Duplicates: 0 Warnings: 0
mysql> select * from Opt6;
+---------------+---------------+---------------+---------------+---------------
+----------+--------+------+
| Opt1_Piece_ID | Opt2_Piece_ID | Opt3_Piece_ID | Opt4_Piece_ID | Opt5_Piece_ID
| Piece_ID | Seq_ID | Seq |
+---------------+---------------+---------------+---------------+---------------
+----------+--------+------+
| 1 | 7 | 2 | 5 | 6
| 3 | 3 | 432 |
+---------------+---------------+---------------+---------------+---------------
+----------+--------+------+
1 row in set (0.00 sec)
----+------+
I encourage you to print out the image of the game and try to solve the puzzle yourself (or better yet cut out and label your own hexes), first manually, then with database technology. Perhaps you'll come up with something different, or at least you can step through the process I've described to help see how this line of thinking can carry over to many problems of this type.
I hope you enjoyed this article. Feel free to contact me with any constructive comments, questions, or remarks.
Jeff Doak
