You should have some benchmark and test cases first, and then decide, is algorithm bad, or not.
I don't have good one tool for this purpose atm.
Moderator: BigEvilCorporation
You should have some benchmark and test cases first, and then decide, is algorithm bad, or not.
Code: Select all
_____JJJ____
__EEAAAAO___
__EEAAAAFF__
__EEAAAAFF__
_II_AAAAFFM_
HIIBBBBDDDM_
HP_BBBBDDD__
H_NBBBBDDD__
H_NBBBBDDD__
GGGGLLCCCCK_
_____QCCCCK_
______CCCCK_
Code: Select all
New best solution found that minimizes group count:
Number of groups: 17, Groups per line density: 4.333333
_____JJJ____
__EEAAAAO___
__EEAAAAFF__
__EEAAAAFF__
_II_AAAAFFM_
HIIBBBBDDDM_
HP_BBBBDDD__
H_NBBBBDDD__
H_NBBBBDDD__
GGGGLLCCCCK_
_____QCCCCK_
______CCCCK_
Alternative solution found(1):
Number of groups: 17, Groups per line density: 4.333333
_____KKK____
__EEAAAAO___
__EEAAAAFF__
__EEAAAAFF__
_II_AAAAFFM_
HIIBBBBDDDM_
HP_BBBBDDD__
H_NBBBBDDD__
H_NBBBBDDD__
GGGGLLCCCCJ_
_____QCCCCJ_
______CCCCJ_
Alternative solution found(2):
Number of groups: 17, Groups per line density: 4.333333
_____JJJ____
__EEAAAAO___
__EEAAAAFF__
__EEAAAAFF__
_GG_AAAAFFM_
IGGBBBBDDDM_
IP_BBBBDDD__
I_NBBBBDDD__
I_NBBBBDDD__
HHHHLLCCCCK_
_____QCCCCK_
______CCCCK_
Alternative solution found(3):
Number of groups: 17, Groups per line density: 4.333333
_____KKK____
__EEAAAAO___
__EEAAAAFF__
__EEAAAAFF__
_GG_AAAAFFM_
IGGBBBBDDDM_
IP_BBBBDDD__
I_NBBBBDDD__
I_NBBBBDDD__
HHHHLLCCCCJ_
_____QCCCCJ_
______CCCCJ_
Alternative solution found(4):
Number of groups: 17, Groups per line density: 4.333333
_____JJJ____
__EEAAAAO___
__EEAAAAFF__
__EEAAAAFF__
_HH_AAAAFFM_
GHHBBBBDDDM_
GP_BBBBDDD__
G_NBBBBDDD__
G_NBBBBDDD__
IIIILLCCCCK_
_____QCCCCK_
______CCCCK_
Alternative solution found(5):
Number of groups: 17, Groups per line density: 4.333333
_____KKK____
__EEAAAAO___
__EEAAAAFF__
__EEAAAAFF__
_HH_AAAAFFM_
GHHBBBBDDDM_
GP_BBBBDDD__
G_NBBBBDDD__
G_NBBBBDDD__
IIIILLCCCCJ_
_____QCCCCJ_
______CCCCJ_
Alternative solution found(6):
Number of groups: 17, Groups per line density: 4.333333
_____JJJ____
__EEAAAAO___
__EEAAAAFF__
__EEAAAAFF__
_HH_AAAAFFM_
IHHBBBBDDDM_
IP_BBBBDDD__
I_NBBBBDDD__
I_NBBBBDDD__
GGGGLLCCCCK_
_____QCCCCK_
______CCCCK_
Alternative solution found(7):
Number of groups: 17, Groups per line density: 4.333333
_____KKK____
__EEAAAAO___
__EEAAAAFF__
__EEAAAAFF__
_HH_AAAAFFM_
IHHBBBBDDDM_
IP_BBBBDDD__
I_NBBBBDDD__
I_NBBBBDDD__
GGGGLLCCCCJ_
_____QCCCCJ_
______CCCCJ_
Alternative solution found(8):
Number of groups: 17, Groups per line density: 4.333333
_____JJJ____
__EEAAAAO___
__EEAAAAFF__
__EEAAAAFF__
_GG_AAAAFFM_
HGGBBBBDDDM_
HP_BBBBDDD__
H_NBBBBDDD__
H_NBBBBDDD__
IIIILLCCCCK_
_____QCCCCK_
______CCCCK_
Alternative solution found(9):
Number of groups: 17, Groups per line density: 4.333333
_____KKK____
__EEAAAAO___
__EEAAAAFF__
__EEAAAAFF__
_GG_AAAAFFM_
HGGBBBBDDDM_
HP_BBBBDDD__
H_NBBBBDDD__
H_NBBBBDDD__
IIIILLCCCCJ_
_____QCCCCJ_
______CCCCJ_
Alternative solution found(10):
Number of groups: 17, Groups per line density: 4.333333
_____JJJ____
__EEAAAAO___
__EEAAAAFF__
__EEAAAAFF__
_II_AAAAFFM_
GIIBBBBDDDM_
GP_BBBBDDD__
G_NBBBBDDD__
G_NBBBBDDD__
HHHHLLCCCCK_
_____QCCCCK_
______CCCCK_
Alternative solution found(11):
Number of groups: 17, Groups per line density: 4.333333
_____KKK____
__EEAAAAO___
__EEAAAAFF__
__EEAAAAFF__
_II_AAAAFFM_
GIIBBBBDDDM_
GP_BBBBDDD__
G_NBBBBDDD__
G_NBBBBDDD__
HHHHLLCCCCJ_
_____QCCCCJ_
______CCCCJ_
Alternative solution found(12):
Number of groups: 17, Groups per line density: 4.333333
_____JJJ____
__EEAAAAO___
__EEAAAAFF__
__EEAAAAFF__
_II_AAAAFFM_
HIIBBBBDDDM_
HP_BBBBDDD__
H_NBBBBDDD__
H_NBBBBDDD__
GGGGLLCCCCK_
_____QCCCCK_
______CCCCK_
Alternative solution found(13):
Number of groups: 17, Groups per line density: 4.333333
_____KKK____
__EEAAAAO___
__EEAAAAFF__
__EEAAAAFF__
_II_AAAAFFM_
HIIBBBBDDDM_
HP_BBBBDDD__
H_NBBBBDDD__
H_NBBBBDDD__
GGGGLLCCCCJ_
_____QCCCCJ_
______CCCCJ_
Alternative solution found(14):
Number of groups: 17, Groups per line density: 4.333333
_____JJJ____
__EEAAAAO___
__EEAAAAFF__
__EEAAAAFF__
_GG_AAAAFFM_
IGGBBBBDDDM_
IP_BBBBDDD__
I_NBBBBDDD__
I_NBBBBDDD__
HHHHLLCCCCK_
_____QCCCCK_
______CCCCK_
Alternative solution found(15):
Number of groups: 17, Groups per line density: 4.333333
_____KKK____
__EEAAAAO___
__EEAAAAFF__
__EEAAAAFF__
_GG_AAAAFFM_
IGGBBBBDDDM_
IP_BBBBDDD__
I_NBBBBDDD__
I_NBBBBDDD__
HHHHLLCCCCJ_
_____QCCCCJ_
______CCCCJ_
Alternative solution found(16):
Number of groups: 17, Groups per line density: 4.333333
_____JJJ____
__EEAAAAO___
__EEAAAAFF__
__EEAAAAFF__
_HH_AAAAFFM_
GHHBBBBDDDM_
GP_BBBBDDD__
G_NBBBBDDD__
G_NBBBBDDD__
IIIILLCCCCK_
_____QCCCCK_
______CCCCK_
Alternative solution found(17):
Number of groups: 17, Groups per line density: 4.333333
_____KKK____
__EEAAAAO___
__EEAAAAFF__
__EEAAAAFF__
_HH_AAAAFFM_
GHHBBBBDDDM_
GP_BBBBDDD__
G_NBBBBDDD__
G_NBBBBDDD__
IIIILLCCCCJ_
_____QCCCCJ_
______CCCCJ_
Alternative solution found(18):
Number of groups: 17, Groups per line density: 4.333333
_____JJJ____
__EEAAAAO___
__EEAAAAFF__
__EEAAAAFF__
_HH_AAAAFFM_
IHHBBBBDDDM_
IP_BBBBDDD__
I_NBBBBDDD__
I_NBBBBDDD__
GGGGLLCCCCK_
_____QCCCCK_
______CCCCK_
Alternative solution found(19):
Number of groups: 17, Groups per line density: 4.333333
_____KKK____
__EEAAAAO___
__EEAAAAFF__
__EEAAAAFF__
_HH_AAAAFFM_
IHHBBBBDDDM_
IP_BBBBDDD__
I_NBBBBDDD__
I_NBBBBDDD__
GGGGLLCCCCJ_
_____QCCCCJ_
______CCCCJ_
Alternative solution found(20):
Number of groups: 17, Groups per line density: 4.333333
_____JJJ____
__EEAAAAO___
__EEAAAAFF__
__EEAAAAFF__
_GG_AAAAFFM_
HGGBBBBDDDM_
HP_BBBBDDD__
H_NBBBBDDD__
H_NBBBBDDD__
IIIILLCCCCK_
_____QCCCCK_
______CCCCK_
Alternative solution found(21):
Number of groups: 17, Groups per line density: 4.333333
_____KKK____
__EEAAAAO___
__EEAAAAFF__
__EEAAAAFF__
_GG_AAAAFFM_
HGGBBBBDDDM_
HP_BBBBDDD__
H_NBBBBDDD__
H_NBBBBDDD__
IIIILLCCCCJ_
_____QCCCCJ_
______CCCCJ_
Alternative solution found(22):
Number of groups: 17, Groups per line density: 4.333333
_____JJJ____
__EEAAAAO___
__EEAAAAFF__
__EEAAAAFF__
_II_AAAAFFM_
GIIBBBBDDDM_
GP_BBBBDDD__
G_NBBBBDDD__
G_NBBBBDDD__
HHHHLLCCCCK_
_____QCCCCK_
______CCCCK_
Alternative solution found(23):
Number of groups: 17, Groups per line density: 4.333333
_____KKK____
__EEAAAAO___
__EEAAAAFF__
__EEAAAAFF__
_II_AAAAFFM_
GIIBBBBDDDM_
GP_BBBBDDD__
G_NBBBBDDD__
G_NBBBBDDD__
HHHHLLCCCCJ_
_____QCCCCJ_
______CCCCJ_
Alternative solution found(24):
Number of groups: 17, Groups per line density: 4.333333
_____JJJ____
__EEAAAAO___
__EEAAAAFF__
__EEAAAAFF__
_II_AAAAFFM_
HIIBBBBCCCM_
HP_BBBBCCC__
H_NBBBBCCC__
H_NBBBBCCC__
GGGGLLDDDDK_
_____QDDDDK_
______DDDDK_
Alternative solution found(25):
Number of groups: 17, Groups per line density: 4.333333
_____KKK____
__EEAAAAO___
__EEAAAAFF__
__EEAAAAFF__
_II_AAAAFFM_
HIIBBBBCCCM_
HP_BBBBCCC__
H_NBBBBCCC__
H_NBBBBCCC__
GGGGLLDDDDJ_
_____QDDDDJ_
______DDDDJ_
Alternative solution found(26):
Number of groups: 17, Groups per line density: 4.333333
_____JJJ____
__EEAAAAO___
__EEAAAAFF__
__EEAAAAFF__
_GG_AAAAFFM_
IGGBBBBCCCM_
IP_BBBBCCC__
I_NBBBBCCC__
I_NBBBBCCC__
HHHHLLDDDDK_
_____QDDDDK_
______DDDDK_
Alternative solution found(27):
Number of groups: 17, Groups per line density: 4.333333
_____KKK____
__EEAAAAO___
__EEAAAAFF__
__EEAAAAFF__
_GG_AAAAFFM_
IGGBBBBCCCM_
IP_BBBBCCC__
I_NBBBBCCC__
I_NBBBBCCC__
HHHHLLDDDDJ_
_____QDDDDJ_
______DDDDJ_
Alternative solution found(28):
Number of groups: 17, Groups per line density: 4.333333
_____JJJ____
__EEAAAAO___
__EEAAAAFF__
__EEAAAAFF__
_HH_AAAAFFM_
GHHBBBBCCCM_
GP_BBBBCCC__
G_NBBBBCCC__
G_NBBBBCCC__
IIIILLDDDDK_
_____QDDDDK_
______DDDDK_
Alternative solution found(29):
Number of groups: 17, Groups per line density: 4.333333
_____KKK____
__EEAAAAO___
__EEAAAAFF__
__EEAAAAFF__
_HH_AAAAFFM_
GHHBBBBCCCM_
GP_BBBBCCC__
G_NBBBBCCC__
G_NBBBBCCC__
IIIILLDDDDJ_
_____QDDDDJ_
______DDDDJ_
Alternative solution found(30):
Number of groups: 17, Groups per line density: 4.333333
_____JJJ____
__EEAAAAO___
__EEAAAAFF__
__EEAAAAFF__
_HH_AAAAFFM_
IHHBBBBCCCM_
IP_BBBBCCC__
I_NBBBBCCC__
I_NBBBBCCC__
GGGGLLDDDDK_
_____QDDDDK_
______DDDDK_
Alternative solution found(31):
Number of groups: 17, Groups per line density: 4.333333
_____KKK____
__EEAAAAO___
__EEAAAAFF__
__EEAAAAFF__
_HH_AAAAFFM_
IHHBBBBCCCM_
IP_BBBBCCC__
I_NBBBBCCC__
I_NBBBBCCC__
GGGGLLDDDDJ_
_____QDDDDJ_
______DDDDJ_
Alternative solution found(32):
Number of groups: 17, Groups per line density: 4.333333
_____JJJ____
__EEAAAAO___
__EEAAAAFF__
__EEAAAAFF__
_GG_AAAAFFM_
HGGBBBBCCCM_
HP_BBBBCCC__
H_NBBBBCCC__
H_NBBBBCCC__
IIIILLDDDDK_
_____QDDDDK_
______DDDDK_
Alternative solution found(33):
Number of groups: 17, Groups per line density: 4.333333
_____KKK____
__EEAAAAO___
__EEAAAAFF__
__EEAAAAFF__
_GG_AAAAFFM_
HGGBBBBCCCM_
HP_BBBBCCC__
H_NBBBBCCC__
H_NBBBBCCC__
IIIILLDDDDJ_
_____QDDDDJ_
______DDDDJ_
Alternative solution found(34):
Number of groups: 17, Groups per line density: 4.333333
_____JJJ____
__EEAAAAO___
__EEAAAAFF__
__EEAAAAFF__
_II_AAAAFFM_
GIIBBBBCCCM_
GP_BBBBCCC__
G_NBBBBCCC__
G_NBBBBCCC__
HHHHLLDDDDK_
_____QDDDDK_
______DDDDK_
Alternative solution found(35):
Number of groups: 17, Groups per line density: 4.333333
_____KKK____
__EEAAAAO___
__EEAAAAFF__
__EEAAAAFF__
_II_AAAAFFM_
GIIBBBBCCCM_
GP_BBBBCCC__
G_NBBBBCCC__
G_NBBBBCCC__
HHHHLLDDDDJ_
_____QDDDDJ_
______DDDDJ_
Alternative solution found(36):
Number of groups: 17, Groups per line density: 4.333333
_____JJJ____
__EEAAAAO___
__EEAAAAFF__
__EEAAAAFF__
_II_AAAAFFM_
HIIBBBBCCCM_
HP_BBBBCCC__
H_NBBBBCCC__
H_NBBBBCCC__
GGGGLLDDDDK_
_____QDDDDK_
______DDDDK_
Alternative solution found(37):
Number of groups: 17, Groups per line density: 4.333333
_____KKK____
__EEAAAAO___
__EEAAAAFF__
__EEAAAAFF__
_II_AAAAFFM_
HIIBBBBCCCM_
HP_BBBBCCC__
H_NBBBBCCC__
H_NBBBBCCC__
GGGGLLDDDDJ_
_____QDDDDJ_
______DDDDJ_
Alternative solution found(38):
Number of groups: 17, Groups per line density: 4.333333
_____JJJ____
__EEAAAAO___
__EEAAAAFF__
__EEAAAAFF__
_GG_AAAAFFM_
IGGBBBBCCCM_
IP_BBBBCCC__
I_NBBBBCCC__
I_NBBBBCCC__
HHHHLLDDDDK_
_____QDDDDK_
______DDDDK_
Alternative solution found(39):
Number of groups: 17, Groups per line density: 4.333333
_____KKK____
__EEAAAAO___
__EEAAAAFF__
__EEAAAAFF__
_GG_AAAAFFM_
IGGBBBBCCCM_
IP_BBBBCCC__
I_NBBBBCCC__
I_NBBBBCCC__
HHHHLLDDDDJ_
_____QDDDDJ_
______DDDDJ_
Alternative solution found(40):
Number of groups: 17, Groups per line density: 4.333333
_____JJJ____
__EEAAAAO___
__EEAAAAFF__
__EEAAAAFF__
_HH_AAAAFFM_
GHHBBBBCCCM_
GP_BBBBCCC__
G_NBBBBCCC__
G_NBBBBCCC__
IIIILLDDDDK_
_____QDDDDK_
______DDDDK_
Alternative solution found(41):
Number of groups: 17, Groups per line density: 4.333333
_____KKK____
__EEAAAAO___
__EEAAAAFF__
__EEAAAAFF__
_HH_AAAAFFM_
GHHBBBBCCCM_
GP_BBBBCCC__
G_NBBBBCCC__
G_NBBBBCCC__
IIIILLDDDDJ_
_____QDDDDJ_
______DDDDJ_
Alternative solution found(42):
Number of groups: 17, Groups per line density: 4.333333
_____JJJ____
__EEAAAAO___
__EEAAAAFF__
__EEAAAAFF__
_HH_AAAAFFM_
IHHBBBBCCCM_
IP_BBBBCCC__
I_NBBBBCCC__
I_NBBBBCCC__
GGGGLLDDDDK_
_____QDDDDK_
______DDDDK_
Alternative solution found(43):
Number of groups: 17, Groups per line density: 4.333333
_____KKK____
__EEAAAAO___
__EEAAAAFF__
__EEAAAAFF__
_HH_AAAAFFM_
IHHBBBBCCCM_
IP_BBBBCCC__
I_NBBBBCCC__
I_NBBBBCCC__
GGGGLLDDDDJ_
_____QDDDDJ_
______DDDDJ_
Alternative solution found(44):
Number of groups: 17, Groups per line density: 4.333333
_____JJJ____
__EEAAAAO___
__EEAAAAFF__
__EEAAAAFF__
_GG_AAAAFFM_
HGGBBBBCCCM_
HP_BBBBCCC__
H_NBBBBCCC__
H_NBBBBCCC__
IIIILLDDDDK_
_____QDDDDK_
______DDDDK_
Alternative solution found(45):
Number of groups: 17, Groups per line density: 4.333333
_____KKK____
__EEAAAAO___
__EEAAAAFF__
__EEAAAAFF__
_GG_AAAAFFM_
HGGBBBBCCCM_
HP_BBBBCCC__
H_NBBBBCCC__
H_NBBBBCCC__
IIIILLDDDDJ_
_____QDDDDJ_
______DDDDJ_
Alternative solution found(46):
Number of groups: 17, Groups per line density: 4.333333
_____JJJ____
__EEAAAAO___
__EEAAAAFF__
__EEAAAAFF__
_II_AAAAFFM_
GIIBBBBCCCM_
GP_BBBBCCC__
G_NBBBBCCC__
G_NBBBBCCC__
HHHHLLDDDDK_
_____QDDDDK_
______DDDDK_
Alternative solution found(47):
Number of groups: 17, Groups per line density: 4.333333
_____KKK____
__EEAAAAO___
__EEAAAAFF__
__EEAAAAFF__
_II_AAAAFFM_
GIIBBBBCCCM_
GP_BBBBCCC__
G_NBBBBCCC__
G_NBBBBCCC__
HHHHLLDDDDJ_
_____QDDDDJ_
______DDDDJ_
Best solution found (out of 47 alternatives):
Number of groups: 17, Groups per line density: 4.333333
_____JJJ____
__EEAAAAO___
__EEAAAAFF__
__EEAAAAFF__
_II_AAAAFFM_
HIIBBBBDDDM_
HP_BBBBDDD__
H_NBBBBDDD__
H_NBBBBDDD__
GGGGLLCCCCK_
_____QCCCCK_
______CCCCK_
Group A 4x4: left=4 top=1 right=8 bottom=5
Group B 4x4: left=3 top=5 right=7 bottom=9
Group C 4x3: left=6 top=9 right=10 bottom=12
Group D 3x4: left=7 top=5 right=10 bottom=9
Group E 2x3: left=2 top=1 right=4 bottom=4
Group F 2x3: left=8 top=2 right=10 bottom=5
Group G 4x1: left=0 top=9 right=4 bottom=10
Group H 1x4: left=0 top=5 right=1 bottom=9
Group I 2x2: left=1 top=4 right=3 bottom=6
Group J 3x1: left=5 top=0 right=8 bottom=1
Group K 1x3: left=10 top=9 right=11 bottom=12
Group L 2x1: left=4 top=9 right=6 bottom=10
Group M 1x2: left=10 top=4 right=11 bottom=6
Group N 1x2: left=2 top=7 right=3 bottom=9
Group O 1x1: left=8 top=1 right=9 bottom=2
Group P 1x1: left=1 top=6 right=2 bottom=7
Group Q 1x1: left=5 top=10 right=6 bottom=11
Code: Select all
_____JJJ____
__AAAAFFFF__
__AAAAFFFF__
__AAAAFFFF__
iIIbBBBEEEE_
IIIBBBBEEEE_
IIiBBBBDDD__
HhHHGGGDDD__
HhHHGGGDDD__
HHHHGGGCCCC_
_____KKCCCC_
_____kKCCCC_
Code: Select all
Number of groups: 8, using 22 empty tiles:
__AAAABBBB__
__AAAABBBB__
__AAAABBBB__
__AAAABBBB__
CCCCDDDDGGG_
CCCCDDDDGGG_
CCCCDDDDGGG_
CCCCDDDDGGG_
HHHEEEEFFFF_
HHHEEEEFFFF_
HHHEEEEFFFF_
___EEEEFFFF_
We need arrangement of competition first.BigEvilCorporation wrote: ↑Thu Aug 31, 2017 10:22 amI'm lazy and don't want to read the whole thread - which algo won?
And to be more specific: if you allow empty tiles, how do you make it for starters even decide which empty tiles to look for? Assuming empty tiles can't be used makes things much easier as you don't have to go around trying whether each tile is worth including or not.Miquel wrote: ↑Wed Aug 30, 2017 3:45 pm@flamewing, one of the preconditions was that empty tiles can't be used at all. That's a different problem: for some people wasting 6 empty tiles is not acceptable, for others is desirable, how you coupe with this decision? I mean, were is the limit? how to calculate it for a general case? are you sure, once you introduce this new rule, that you method will produce the optimal? May be there are other six tiles that reduce more group usage.
None =/ Maybe try this one for now:BigEvilCorporation wrote: ↑Thu Aug 31, 2017 10:22 amI'm lazy and don't want to read the whole thread - which algo won?
Code: Select all
_____III____
__EEEAAAA___
__EEEAAAAJ__
__EEEAAAAJ__
_HH_NAAAAJM_
GHHFFFBBBBM_
GO_FFFBBBB__
G_CCCCBBBB__
G_CCCCBBBB__
LLCCCCKDDDD_
_____PKDDDD_
______KDDDD_
Code: Select all
_____HHH____
__EEEAAAA___
__EEEAAAAJ__
__EEEAAAAJ__
_KEEEAAAAJM_
GKCCCCBBBBM_
GKCCCCBBBB__
G_CCCCBBBB__
G_CCCCBBBB__
IIIFFFFDDDD_
_____LLDDDD_
______NDDDD_
Code: Select all
_____III____
__BBBBAAAA__
__BBBBAAAA__
__BBBBAAAA__
FFBBBBAAAAK_
FFDDDDCCCCK_
FFDDDDCCCC__
J_DDDDCCCC__
J_DDDDCCCC__
JHHHHGGEEEE_
_____GGEEEE_
_____GGEEEE_