From Daan
Jump to: navigation, search
m (→‎Frames voor Almost Squares)
 
(50 intermediate revisions by 3 users not shown)
Line 1: Line 1:
  
−
Dit wordt de Almost Squares - pagina
+
Dit is de Almost Squares - pagina.
  
 
==Introductie==
 
==Introductie==
  
−
Tiling Almost Squares van orde n (ASn) is het plaatsen van tegels 1x2, 2x3, ... , nxn+1 in een frame.
+
Tiling Almost Squares van orde n (TASn) is het plaatsen van tegels 1x2, 2x3, ... , nx(n+1) in een frame. Het frame is "exact-fit", d.w.z. de oppervlakte van de tegels is precies even groot als die van het frame, en als er een oplossing is, liggen de tegels in het frame naadloos tegen elkaar aan zonder te overlappen.
  
  
−
Almost Squares in Almost Squares (ASQAS) is een subest van AS waarbij het frame zelf ook een almost-square is. Er zijn precies vijf instanties van ASQAS (1,3,8,20 en34) en ze hebben allemaal oplossingen.
+
Almost Squares in Almost Squares (ASQAS) is een subset van AS waarbij het frame zelf ook een almost-square is. Er zijn precies vijf instanties van ASQAS (1,3,8,20 en 34) en ze hebben allemaal oplossingen.
−
 
 
  
 
==Frames voor Almost Squares==
 
==Frames voor Almost Squares==
Line 14: Line 13:
 
De volgende framedimensies hebben precies genoeg oppervlakte om de tegels te kunnen inpassen, en de smalste van de twee dimensies is nog groot genoeg om de breedste tegel te kunnen passen.
 
De volgende framedimensies hebben precies genoeg oppervlakte om de tegels te kunnen inpassen, en de smalste van de twee dimensies is nog groot genoeg om de breedste tegel te kunnen passen.
  
 +
{| class="wikitable" style="text-align: right; margin-left: 1em; margin-bottom: 1em; font-size: 85%;"
 +
|+Eligible frames voor Almost Squares n=1...34
 +
! n
 +
! area
 +
! #Eligible Frames
 +
! Eligible Frames
 +
! Remarks
 +
|-
 +
!1
 +
|2 
 +
|1 
 +
|1x2
 +
|1 trivial solution
 +
|-
 +
!2
 +
|8 
 +
|1 
 +
|2x4
 +
|1 trivial solution
 +
|-
 +
!3
 +
|20
 +
|1
 +
|4x5
 +
|1 trivial solution
 +
|-
 +
!4
 +
|40
 +
|2
 +
|4x10, 5x8
 +
|4x10: 3 oplossingen, 5x8: 2 oplossingen
 +
|-
 +
!5
 +
|70
 +
|2
 +
|5x14, 7x10
 +
|5x14: 6 oplossingen, 7x10: geen oplossingen
 +
|-
 +
!6
 +
|112
 +
|2
 +
|7x16, 8x14
 +
|geen oplossingen
 +
|-
 +
!7
 +
|168
 +
|3
 +
|7x24, 8x21, 12x14
 +
| 12x14: 33 oplossingen, anderen geen oplossingen.
 +
|-
 +
!8
 +
|240
 +
|4
 +
|8x30, 10x24, 12x20, 15x16
 +
|15x16: 10 oplossingen, anderen geen oplossingen.
 +
|-
 +
!9
 +
|330
 +
|3
 +
|10x33, 11x30, 15x22
 +
| Geen oplossingen.
 +
|-
 +
!10
 +
|440
 +
|3
 +
|10x44, 11x40, 20x22
 +
| Geen oplossingen.
 +
|-
 +
!11
 +
|572
 +
|3
 +
|11x52, 13x44, 22x26
 +
| 22x26:4 oplossingen, anderen geen oplossingen.
 +
|-
 +
!12
 +
|728
 +
|3
 +
|13x56, 14x52, 26x28
 +
|Geen oplossingen, zelfs 26x28 niet.
 +
|-
 +
!13
 +
|910
 +
|2
 +
|13x70, 26x35
 +
|13x70: geen opl. 26x35: 42 oplossingen.
 +
|-
 +
!14
 +
|1120
 +
|5     
 +
|14x80, 16x70, 20x56, 28x40, 32x35
 +
|28x40: 3 oplossingen, 1 singelton. 32x35: 72 oplossingen. De anderen geen oplossingen.
 +
|-
 +
!15
 +
|1360
 +
|4
 +
|16x85, 17x80, 20x68, 34x40
 +
|34x40: 4 oplossingen (in 1 bag).
 +
|-
 +
!16
 +
|1632
 +
|4
 +
|16x102, 17x96, 32x51, 34x48
 +
|32x51: 456 oplossingen, de anderen geen.
 +
|-
 +
!17
 +
|1938
 +
|4
 +
|17x114, 19x102, 34x57 38x51
 +
|34x57: 16 oplossingen, de anderen geen.
 +
|-
 +
!18
 +
|2280
 +
|6
 +
|19x120, 20x114, 24x95, 30x76, 38x60, 40x57
 +
|30x76 heeft 384016 oplossingen incsp. (needs check), de anderen geen.
 +
|-
 +
!19
 +
|2660
 +
|5
 +
|19x140, 20x133, 28x95, 35x76, 38x70
 +
|35x76: 526, 38x70: 24 (met part.ret.)
 +
|-
 +
!20
 +
|3080
 +
|7
 +
|20x154, 22x140, 28x110, 35x88, 40x77, 44x70, 55x56
 +
|-
 +
!21
 +
|3542
 +
|3
 +
|22x161, 23x154, 46x77
 +
|-
 +
!22
 +
|4048
 +
|4
 +
|22x184, 23x176, 44x92, 46x88
 +
|-
 +
!23
 +
|4600
 +
|5
 +
|23x200, 25x184, 40x115, 46x100, 50x92
 +
|-
 +
!24
 +
|5200
 +
|6
 +
|25x208, 26x200, 40x130, 50x104, 52x100, 65x80
 +
|-
 +
!25
 +
|5850
 +
|8
 +
|25x234, 26x225, 30x195, 39x150, 45x130, 50x117, 65x90, 75x78
 +
|-
 +
!26
 +
|6552
 +
|10
 +
|26x252, 28x234, 36x182, 39x168, 42x156, 52x126, 56x117, 63x104,72x91, 78x84
 +
|-
 +
!27
 +
|7308
 +
|7
 +
|28x261, 29x252, 36x203, 42x174, 58x126, 63x116, 84x87
 +
|-
 +
!28
 +
|8120
 +
|7
 +
|28x290, 29x280, 35x232, 40x203, 56x145, 58x140, 70x116
 +
|-
 +
!29
 +
|8990
 +
|4
 +
|29x310, 31x290, 58x155, 62x145
 +
|-
 +
!30
 +
|9920
 +
|6
 +
|31x320, 32x310, 40x248, 62x160, 64x155, 80x124
 +
|-
 +
!31
 +
|10912
 +
|5
 +
|31x352, 32x341, 44x248, 62x176, 88x124
 +
|-
 +
!32
 +
|11968
 +
|6
 +
|32x374, 34x352, 44x272, 64x187, 68x176, 88x136
 +
|-
 +
!33
 +
|13090
 +
|7     
 +
|34x385, 35x374, 55x238, 70x187, 77x170, 85x154, 110x119
 +
|-
 +
!34
 +
|14280
 +
|14
 +
|34x420, 35x408, 40x357, 42x340, 51x280, 56x255, 60x238, 68x210,70x204, 84x170, 85x168, 102x140, 105x136, 119x120
 +
|}
 +
 +
== Vierkante frames ==
 +
 +
{| class="wikitable" style="text-align: right; margin-left: 1em; margin-bottom: 1em; font-size: 85%;"
 +
|+Vierkante frames voor Almost Squares n<100000
 +
! n
 +
! area
 +
! Frame
 +
|-
 +
!4208
 +
| 24855099040
 +
| 157665x157665
 +
|-
 +
!11708
 +
| 535103954040
 +
| 731508x731508     
 +
|-
 +
!12090
 +
| 589203619160
 +
| 767596x767596
 +
|-
 +
!16708
 +
| 1554999024040
 +
| 1246996x1246996
 +
|-
 +
!17006
 +
| 1639690494112
 +
| 1280504x120504     
 +
|-
 +
!20043
 +
| 2684305408380
 +
|1638385x1638385     
 +
|-
 +
!31351
 +
| 10272460884952
 +
| 3205068x3205068 
 +
|-   
 +
!46760
 +
| 34082395787440
 +
| 5838013x5838013
 +
|-
 +
!47232
 +
| 35124919450368
 +
| 5926628x5926628
 +
|-
 +
!50832
 +
| 43784053769568
 +
| 6616952x 6616952
 +
|-
 +
!54284
 +
| 34082395787440
 +
| 7302291x7302291
 +
|-
 +
!57084
 +
| 53323453848280
 +
|7302291x7302291
 +
|-
 +
!67450
 +
|102292530755800
 +
|10113977x10113977
 +
|-
 +
!73113
 +
| 130280788510810
 +
| 11414061x11414061
 +
|-
 +
!77221
 +
| 153497703155942
 +
| 12389419x12389419
 +
|-
 +
!84130
 +
| 198493778245320
 +
| 14088782x14088782
 +
|-
 +
!84781
 +
| 203137319391662
 +
| 14252625x14252625
 +
|-
 +
!84900
 +
| 203993891066600
 +
| 14282643x14282643
 +
|-
 +
!92511
 +
| 263920396623072
 +
| 16245627x16245627
 +
|-
 +
!93345
 +
| 271122701364130
 +
| 16465804x16465804
 +
|}
 +
 +
== Zie ook ==
 +
* [[Almost Almost Squares]]
 +
* [[Almost Almost Almost Squares]]
  
−
index  #eligible frames        eligible frames
+
* [[AI-course]]
−
1      1      1x2
 
−
2      1      2x4
 
−
3      1      4x5
 
−
4      2      4x10,5x8
 
−
5      2      5x14, 7x10
 
−
6      2      7x16,8x14
 
−
7      3      7x24,8x21,12x14
 
−
8      4      8x30, 10x24, 12x20, 15x16
 
−
9      3      10x33, 11x30,15x22
 
−
10      3      10x44,11x40,20x22
 
−
11      3      11x52, 13x44, 22x26
 
−
12      3      13x56, 14x52, 26x28
 
−
13      2      13x70, 26x35
 
−
14      5      14x80, 16x70, 20x56, 28x40, 32x35
 
−
15      4      16x85, 17x80, 20x68, 34x40
 
−
16      4      16x102, 17x96, 32x51, 34x48
 
−
17      4      17x114, 19x102, 34x57 38x51
 
−
18      6      19x120, 20x114, 24x95, 30x76, 38x60, 40x57
 
−
19      5      19x140, 20x133, 28x95, 35x76, 38x70
 
−
20      7      20x154, 22x140, 28x110, 35x88, 40x77, 44x70, 55x56
 
−
21      3      22x161, 23x154, 46x77
 
−
22      4      22x184, 23x176, 44x92, 46x88
 
−
23      5      23x200, 25x184, 40x115, 46x100, 50x92
 
−
24      6      25x208, 26x200, 40x130, 50x104, 52x100, 65x80
 
−
25      8      25x234, 26x225, 30x195, 39x150, 45x130, 50x117, 65x90, 75x78
 
−
26      10      26x252, 28x234, 36x182, 39x168, 42x156, 52x126, 56x117, 63x104,72x91, 78x84
 
−
27      7      28x261, 29x252, 36x203, 42x174, 58x126, 63x116, 84x87
 
−
28      7      28x290, 29x280, 35x232, 40x203, 56x145, 58x140, 70x116
 
−
29      4      29x310, 31x290, 58x155, 62x145
 
−
30      6      31x320, 32x310, 40x248, 62x160, 64x155, 80x124,
 
−
31      5      31x352, 32x341, 44x248, 62x176, 88x124
 
−
32      6      32x374, 34x352, 44x272, 64x187, 68x176, 88x136
 
−
33      7      34x385, 35x374, 55x238, 70x187, 77x170, 85x154, 110x119
 
−
34      14      34x420, 35x408, 40x357, 42x340, 51x280, 56x255, 60x238, 68x210,70x204, 84x170, 85x168, 102x140, 105x136, 119x120
 

Latest revision as of 00:21, 13 January 2013

Dit is de Almost Squares - pagina.

Introductie

Tiling Almost Squares van orde n (TASn) is het plaatsen van tegels 1x2, 2x3, ... , nx(n+1) in een frame. Het frame is "exact-fit", d.w.z. de oppervlakte van de tegels is precies even groot als die van het frame, en als er een oplossing is, liggen de tegels in het frame naadloos tegen elkaar aan zonder te overlappen.


Almost Squares in Almost Squares (ASQAS) is een subset van AS waarbij het frame zelf ook een almost-square is. Er zijn precies vijf instanties van ASQAS (1,3,8,20 en 34) en ze hebben allemaal oplossingen.

Frames voor Almost Squares

De volgende framedimensies hebben precies genoeg oppervlakte om de tegels te kunnen inpassen, en de smalste van de twee dimensies is nog groot genoeg om de breedste tegel te kunnen passen.

Eligible frames voor Almost Squares n=1...34
n area #Eligible Frames Eligible Frames Remarks
1 2 1 1x2 1 trivial solution
2 8 1 2x4 1 trivial solution
3 20 1 4x5 1 trivial solution
4 40 2 4x10, 5x8 4x10: 3 oplossingen, 5x8: 2 oplossingen
5 70 2 5x14, 7x10 5x14: 6 oplossingen, 7x10: geen oplossingen
6 112 2 7x16, 8x14 geen oplossingen
7 168 3 7x24, 8x21, 12x14 12x14: 33 oplossingen, anderen geen oplossingen.
8 240 4 8x30, 10x24, 12x20, 15x16 15x16: 10 oplossingen, anderen geen oplossingen.
9 330 3 10x33, 11x30, 15x22 Geen oplossingen.
10 440 3 10x44, 11x40, 20x22 Geen oplossingen.
11 572 3 11x52, 13x44, 22x26 22x26:4 oplossingen, anderen geen oplossingen.
12 728 3 13x56, 14x52, 26x28 Geen oplossingen, zelfs 26x28 niet.
13 910 2 13x70, 26x35 13x70: geen opl. 26x35: 42 oplossingen.
14 1120 5 14x80, 16x70, 20x56, 28x40, 32x35 28x40: 3 oplossingen, 1 singelton. 32x35: 72 oplossingen. De anderen geen oplossingen.
15 1360 4 16x85, 17x80, 20x68, 34x40 34x40: 4 oplossingen (in 1 bag).
16 1632 4 16x102, 17x96, 32x51, 34x48 32x51: 456 oplossingen, de anderen geen.
17 1938 4 17x114, 19x102, 34x57 38x51 34x57: 16 oplossingen, de anderen geen.
18 2280 6 19x120, 20x114, 24x95, 30x76, 38x60, 40x57 30x76 heeft 384016 oplossingen incsp. (needs check), de anderen geen.
19 2660 5 19x140, 20x133, 28x95, 35x76, 38x70 35x76: 526, 38x70: 24 (met part.ret.)
20 3080 7 20x154, 22x140, 28x110, 35x88, 40x77, 44x70, 55x56
21 3542 3 22x161, 23x154, 46x77
22 4048 4 22x184, 23x176, 44x92, 46x88
23 4600 5 23x200, 25x184, 40x115, 46x100, 50x92
24 5200 6 25x208, 26x200, 40x130, 50x104, 52x100, 65x80
25 5850 8 25x234, 26x225, 30x195, 39x150, 45x130, 50x117, 65x90, 75x78
26 6552 10 26x252, 28x234, 36x182, 39x168, 42x156, 52x126, 56x117, 63x104,72x91, 78x84
27 7308 7 28x261, 29x252, 36x203, 42x174, 58x126, 63x116, 84x87
28 8120 7 28x290, 29x280, 35x232, 40x203, 56x145, 58x140, 70x116
29 8990 4 29x310, 31x290, 58x155, 62x145
30 9920 6 31x320, 32x310, 40x248, 62x160, 64x155, 80x124
31 10912 5 31x352, 32x341, 44x248, 62x176, 88x124
32 11968 6 32x374, 34x352, 44x272, 64x187, 68x176, 88x136
33 13090 7 34x385, 35x374, 55x238, 70x187, 77x170, 85x154, 110x119
34 14280 14 34x420, 35x408, 40x357, 42x340, 51x280, 56x255, 60x238, 68x210,70x204, 84x170, 85x168, 102x140, 105x136, 119x120

Vierkante frames

Vierkante frames voor Almost Squares n<100000
n area Frame
4208 24855099040 157665x157665
11708 535103954040 731508x731508
12090 589203619160 767596x767596
16708 1554999024040 1246996x1246996
17006 1639690494112 1280504x120504
20043 2684305408380 1638385x1638385
31351 10272460884952 3205068x3205068
46760 34082395787440 5838013x5838013
47232 35124919450368 5926628x5926628
50832 43784053769568 6616952x 6616952
54284 34082395787440 7302291x7302291
57084 53323453848280 7302291x7302291
67450 102292530755800 10113977x10113977
73113 130280788510810 11414061x11414061
77221 153497703155942 12389419x12389419
84130 198493778245320 14088782x14088782
84781 203137319391662 14252625x14252625
84900 203993891066600 14282643x14282643
92511 263920396623072 16245627x16245627
93345 271122701364130 16465804x16465804

Zie ook

Retrieved from "http://heuristieken.nl/wiki/index.php?title=Almost_Squares&oldid=337"