From Daan
Jump to: navigation, search
(→‎Frames voor Almost Squares)
m (→‎Frames voor Almost Squares)
 
(30 intermediate revisions by 3 users not shown)
Line 4: Line 4:
 
==Introductie==
 
==Introductie==
  
−
Tiling Almost Squares van orde n (ASn) is het plaatsen van tegels 1x2, 2x3, ... , nx(n+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; float:left; margin-left: 1em; margin-bottom: 1em; font-size: 85%;"
+
{| class="wikitable" style="text-align: right; margin-left: 1em; margin-bottom: 1em; font-size: 85%;"
 
|+Eligible frames voor Almost Squares n=1...34  
 
|+Eligible frames voor Almost Squares n=1...34  
 
! n
 
! n
Line 20: Line 19:
 
! #Eligible Frames
 
! #Eligible Frames
 
! Eligible Frames
 
! Eligible Frames
 +
! Remarks
 
|-
 
|-
 
!1
 
!1
Line 25: Line 25:
 
|1   
 
|1   
 
|1x2  
 
|1x2  
 +
|1 trivial solution
 
|-
 
|-
 
!2
 
!2
Line 30: Line 31:
 
|1   
 
|1   
 
|2x4  
 
|2x4  
 +
|1 trivial solution
 
|-
 
|-
 
!3
 
!3
Line 35: Line 37:
 
|1
 
|1
 
|4x5
 
|4x5
 +
|1 trivial solution
 
|-
 
|-
 
!4
 
!4
Line 40: Line 43:
 
|2
 
|2
 
|4x10, 5x8
 
|4x10, 5x8
 +
|4x10: 3 oplossingen, 5x8: 2 oplossingen
 
|-
 
|-
 
!5
 
!5
Line 45: Line 49:
 
|2
 
|2
 
|5x14, 7x10
 
|5x14, 7x10
 +
|5x14: 6 oplossingen, 7x10: geen oplossingen
 
|-
 
|-
 
!6
 
!6
Line 50: Line 55:
 
|2
 
|2
 
|7x16, 8x14
 
|7x16, 8x14
 +
|geen oplossingen
 
|-
 
|-
 
!7
 
!7
Line 55: Line 61:
 
|3
 
|3
 
|7x24, 8x21, 12x14
 
|7x24, 8x21, 12x14
 +
| 12x14: 33 oplossingen, anderen geen oplossingen.
 
|-
 
|-
 
!8
 
!8
Line 60: Line 67:
 
|4
 
|4
 
|8x30, 10x24, 12x20, 15x16
 
|8x30, 10x24, 12x20, 15x16
 +
|15x16: 10 oplossingen, anderen geen oplossingen.
 
|-
 
|-
 
!9
 
!9
Line 65: Line 73:
 
|3
 
|3
 
|10x33, 11x30, 15x22
 
|10x33, 11x30, 15x22
 +
| Geen oplossingen.
 
|-
 
|-
 
!10
 
!10
Line 70: Line 79:
 
|3
 
|3
 
|10x44, 11x40, 20x22
 
|10x44, 11x40, 20x22
 +
| Geen oplossingen.
 
|-
 
|-
 
!11
 
!11
Line 75: Line 85:
 
|3
 
|3
 
|11x52, 13x44, 22x26
 
|11x52, 13x44, 22x26
 +
| 22x26:4 oplossingen, anderen geen oplossingen.
 
|-
 
|-
 
!12
 
!12
Line 80: Line 91:
 
|3
 
|3
 
|13x56, 14x52, 26x28
 
|13x56, 14x52, 26x28
 +
|Geen oplossingen, zelfs 26x28 niet.
 
|-
 
|-
 
!13
 
!13
Line 85: Line 97:
 
|2
 
|2
 
|13x70, 26x35
 
|13x70, 26x35
 +
|13x70: geen opl. 26x35: 42 oplossingen.
 
|-
 
|-
 
!14
 
!14
Line 90: Line 103:
 
|5       
 
|5       
 
|14x80, 16x70, 20x56, 28x40, 32x35
 
|14x80, 16x70, 20x56, 28x40, 32x35
 +
|28x40: 3 oplossingen, 1 singelton. 32x35: 72 oplossingen. De anderen geen oplossingen.
 
|-
 
|-
 
!15
 
!15
Line 95: Line 109:
 
|4
 
|4
 
|16x85, 17x80, 20x68, 34x40
 
|16x85, 17x80, 20x68, 34x40
 +
|34x40: 4 oplossingen (in 1 bag).
 
|-
 
|-
 
!16
 
!16
Line 100: Line 115:
 
|4
 
|4
 
|16x102, 17x96, 32x51, 34x48
 
|16x102, 17x96, 32x51, 34x48
 +
|32x51: 456 oplossingen, de anderen geen.
 
|-
 
|-
 
!17
 
!17
Line 105: Line 121:
 
|4
 
|4
 
|17x114, 19x102, 34x57 38x51
 
|17x114, 19x102, 34x57 38x51
 +
|34x57: 16 oplossingen, de anderen geen.
 
|-
 
|-
 
!18
 
!18
Line 110: Line 127:
 
|6
 
|6
 
|19x120, 20x114, 24x95, 30x76, 38x60, 40x57
 
|19x120, 20x114, 24x95, 30x76, 38x60, 40x57
 +
|30x76 heeft 384016 oplossingen incsp. (needs check), de anderen geen.
 
|-
 
|-
 
!19
 
!19
Line 115: Line 133:
 
|5
 
|5
 
|19x140, 20x133, 28x95, 35x76, 38x70
 
|19x140, 20x133, 28x95, 35x76, 38x70
 +
|35x76: 526, 38x70: 24 (met part.ret.)
 
|-
 
|-
 
!20
 
!20
Line 192: Line 211:
 
|}
 
|}
  
 +
== Vierkante frames ==
  
−
Nog even voor de leuk:
+
{| class="wikitable" style="text-align: right; margin-left: 1em; margin-bottom: 1em; font-size: 85%;"
−
 
+
|+Vierkante frames voor Almost Squares n<100000
−
 
 
−
{| class="wikitable" style="text-align: right; float:left; margin-left: 1em; margin-bottom: 1em; font-size: 85%;"
 
−
|+Some frames for very high Slmost Squares  
 
 
! n
 
! n
−
! #Eligible Frames
+
! area
−
! Eligible Frame
+
! 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
 
|-
 
|-
−
!1000 
+
!93345
−
| onbekend 
+
| 271122701364130
−
| 18200x18370
+
| 16465804x16465804
 
|}
 
|}
 +
 +
== Zie ook ==
 +
* [[Almost Almost Squares]]
 +
* [[Almost Almost Almost Squares]]
 +
 +
* [[AI-course]]

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"