Induktaj algoritmoj

Ĉiu plurkvadrato de ordo n+1 povas esti ricevita per aldono de kvadrato al plurkvadrato de ordo n. Ĉi tio donas algoritmojn por generado de plurkvadratoj indukte.

Plej simple, por donita listo de plurkvadratoj de ordo n, kvadratoj povas esti aldonataj apud ĉiu plurkvadrato en ĉiu ebla pozicio, kaj la rezultantaj plurkvadratoj de ordo n+1 estas aldonataj al la listo se ne estas la samo jam trovita. Ĉi tiu maniero povas esti uzata al numerigi liberajn aŭ fiksitajn plurkvadratojn.

Pli malnaiva maniero, priskribita de Redelmeier, estas uzata de multaj aŭtoroj kiel maniero de kalkulado de plurkvadratoj sen postulo ke ĉiuj plurkvadratoj de ordo n estas konservita por ke numerigi tiujn de ordo n+1. La maniero estas ankaŭ uzata kiel bazo por pruvo de superaj baroj pri kvantoj de plurkvadratoj (vidu sube). La baza ideo estas ke oni komencu kun sola kvadrato, kaj de tie, rikure adiciu kvadratojn. Dependante de la detaloj, ĝi povas kalkuli ĉiun n-kvadraton n fojojn, po unu startante de ĉiu el ĝiaj n kvadratoj, aŭ povas esti aranĝita kalkuli ĉiun nur unufoje.

La plej simpla realigo engaĝas aldonon de kvadrato po unu en fojo. Komencu kun komenca kvadrato, nombrigu la najbarajn kvadratojn, laŭhorloĝnadle de la supro, 1, 2, 3 kaj 4. Nun prenu nombron inter 1 kaj 4, kaj aldonu kvadraton je tiu situo. Nombrigu la nenombritaj najbarajn kvadratojn, startante de 5. Tiam, prenu nombron pli grandan ol la antaŭe prenita nombro, kaj aldonu tie kvadraton. Daŭru prenante nombron pli grandan ol la nombro kie antaŭ estis ĵus aldonita kvadrato, aldonu ankoraŭ unu kvadraton kaj numerigu la novajn najbarajn kvadratojn. Kiam n kvadratoj estas kreitaj, n-kvadrato estas kreita.

Ĉi tiu maniero certigas ke ĉiu fiksita plurkvadrato estas kalkulita akurate n fojojn, po unu por ĉiu startanta kvadrato. Ĝi povas esti optimumigita tiel ke ĝi kalkulu ĉiun plurkvadraton nur unufoje. Startante kun la komenca kvadrato, deklaru ĝin al esti la suba-maldekstra kvadrato de la plurkvadrato. Ne nombrigu kvadratojn kiuj estas en pli suba linio, aŭ maldekstre de la unua kvadrato en la sama linio. Ĉi tio estas la versio priskribita de Redelmeier.

Se necesas kalkuli liberajn plurkvadratojn anstataŭe, tiam oni povas kontroli simetriojn post kreo de ĉiu n-kvadrato. Tamen, estas pli rapide generi simetriajn plurkvadratojn aparte (per variado de ĉi tiu maniero) kaj tiel difini la kvanton de liberaj plurkvadratoj per lemo de Burnside.

Tradono-matrica maniero

La plej moderna algoritmo por kalkulado de fiksitaj plurkvadratoj estis esplorita de Iwan Jensen. Ĝi estas plibonigo de maniero de Andrew Conway, ĝi estas eksponente pli rapida ol la antaŭaj manieroj (tamen, ĝia rula tempo estas ankoraŭ eksponenta funkcio de n).

Ambaŭ versioj de Conway kaj Jensen de la tradono-matrica maniero engaĝas kalkuladon de la kvanto de plurkvadratoj kiuj havas certan larĝon. Sumigo de la kvantoj por ĉiuj larĝoj donas la tutecan kvanton de plurkvadratoj. La baza ideo de la maniero estas ke eblaj komencaj linioj estas konsiderataj, kaj tiam difini la minimuman kvanton de kvadratoj bezonataj por plenumi la plurkvadrato de la donita larĝo. Kombinite kun uzo de generantaj funkcioj, ĉi tiu tekniko estas povas kalkuli multajn plurkvadratojn en unu kalkulaĵo, tial kapable ruliĝi je multaj fojoj pli rapide ol manieroj kiuj devas generi ĉiun plurkvadraton aparte.

Kvankam ĉi tiu algoritmo havas relative bonan rulan tempon, la manko de ĝi estas ke ĝi uzas eksponente kreskantan kvanton de memoro (multaj gigabajtoj de memoro estas bezonata por n pli granda ol 50), estas multe pli peza por programado ol la aliaj manieroj, kaj ne povas aktuale esti uzata por kalkuli liberajn plurkvadratojn.

Fiksitaj plurkvadratoj

Teoriaj argumentoj kaj ciferecaj kalkuloj donas pritakson

${\displaystyle A_{n}\sim {\frac {c\lambda ^{n}}{n}}}$

kie λ=4,0626 kaj c=0,3169. Tamen, ĉi tiu rezulto estas ne pruvita kaj la valoroj de λ kaj c estas nur pritaksoj.

La sciataj teoriaj rezultoj estas ne sufiĉe specifaj por ĉi tiu pritakso. Estas pruvite ke ekzistas limeso

${\displaystyle \lim _{n\rightarrow \infty }(A_{n})^{1/n}=\lambda }$

En aliaj vortoj, A_n kreskas eksponente. La plej bona sciata suba baro por λ estas 3,980137. La plej bona sciata supera baro por λ, ne plibonigita ekde la 1970-aj jaroj, estas 4,65.

Por trovi suban baron, simpla sed efika maniero estas kunmeto de plurkvadratoj. Difinu la supro-dekstran kvadraton al esti la plej dekstra kvadrato en la plej supra linio de la plurkvadrato. Difinu la subo-maldekstran kvadraton simile. Tiam, la supro-dekstra kvadrato de ĉiu plurkvadrato de amplekso n povas ligiĝi al la subo-maldekstra kvadrato de ĉiu plurkvadrato de amplekso m por produkti unikan (n+m)-kvadraton. Ĉi tio montras ke A_nA_m≤A_n+m . Uzante ĉi tiun kondiĉon, eblas montri ke ${\displaystyle \lambda \geq (A_{n})^{1/n}}$ por ĉiu n. Plibonigo de ĉi tiu ideo kombinita kun datumoj por A_n donas la suban baron donitan pli supre.

La supera baro estas ricevita per ĝeneraligo de la indukta maniero de numerigo de plurkvadratoj. Anstataŭ aldono de unu kvadrato je fojo, oni aldonas akumuliĝon de kvadratoj je fojo. Ĉi tio estas ofte priskribata kiel aldono de branĉetoj. Per pruvo ke ĉiu n-kvadrato estas vico de branĉetoj, kaj per pruvo de limigoj pri la kombinaĵoj de eblaj branĉetoj, oni ricevas superan baron por la kvanto de n-kvadratoj. Ekzemple, en la algoritmo de konstruado donita pli supre, je ĉiu paŝo oni devas elekti pli grandan nombron, kaj maksimume tri novaj nombroj estas aldonataj (pro tio ke maksimume tri nenombritaj kvadratoj estas najbaraj al ĉiu nombrita kvadrato). Ĉi tio povas esti uzata por ricevi superan baron de 6,75. Uzante 2,8 milionojn branĉetojn, Klarner kaj Rivest ricevis superan baron 4,65.

Liberaj plurkvadratoj

Proksimumadoj por la kvanto de fiksitaj plurkvadratoj kaj liberaj plurkvadratoj estas simple rilatantaj un al la alia. Libera plurkvadrato sen simetrioj (turnado aŭ reflekto) respektivas al 8 malsamaj fiksitaj plurkvadratoj, kaj por granda n, plejparto de n-kvadratoj ne havas simetriojn. Pro tio, la kvanto de fiksitaj n-kvadratoj estas proksimume je 8 fojoj pli granda ol la kvanto de libera n-kvadratoj. Ankaŭ, ĉi tiu proksimumado iĝas eksponente pli precizan kiam n pligrandiĝas.

Specialaj klasoj de plurkvadratoj

Akurataj formuloj estas konataj por kalkulado de kvantoj de plurkvadratoj de specialaj klasoj, kiel la klaso de konveksaj plurkvadratoj kaj la klaso de direktitaj plurkvadratoj.

La difino de konveksa (fakte, kvazaŭ-konveksa) plurkvadrato estas malsama de la kutima difino de konvekseco. Plurkvadrato estas kolumno-konveksa se ĝia intersekco kun ĉiu vertikalo estas konveksa, do tio estas ke ĉiu kolumno ne havas truojn. Simile, plurkvadrato estas linio-konveksa se ĝia intersekco kun ĉiu horizontalo estas konveksa. Plurkvadrato estas dirita al esti konveksa se ĝi estas linie kaj kolumne konveksa.

Plurkvadrato estas direktita se ĝi enhavas kvadraton, nomatan kiel la radiko, tian ke ĉiu la alia kvadrato povas esti atingita per movadoj supren aŭ dekstren je unu kvadrato, sen laso de la plurkvadrato.

Direktitaj plurkvadratoj, kolumnaj (aŭ liniaj) konveksaj plurkvadratoj, kaj konveksaj plurkvadratoj estas efike kalkulataj per areo n, kaj ankaŭ per iuj la aliaj parametroj kiel perimetro, uzante generantajn funkciojn.

Kahelado de regionoj kun aroj de plurkvadratoj

Enigmoj kutime petas kaheli donitan regionon kun donita aro de plurkvadratoj. Tipa ekzemplo estas al kaheli 6×10 ortangulon kun la 12 5-kvadratoj; la 2339 solvaĵoj al ĉi tio estas trovitaj en 1960. Por kahelado en kiu multaj kopioj de la plurkvadratoj el la aro estas permesitaj, Golomb donas hierarkion de malsamaj regionoj kiujn la aro povas kaheli, kiel ortanguloj, bendoj kaj la tuta ebeno, kaj montras ke la demando de tio ĉu la ebeno povas esti kahelita per plurkvadratoj de donita aro estas nedecidebla, per surĵeto de aroj de kahelaro de Wang al aroj de plurkvadratoj.

Kahelado de regionoj kun kopioj de sola plurkvadrato

Alia klaso de problemoj demandas ĉu kopioj de donita plurkvadrato povas kaheli ortangulon, kaj kiajn ortangulajn ili povas kaheli. Ĉi tiuj problemoj estas multe studitaj por apartaj plurkvadratoj, kaj tabeloj de rezultoj por apartaj plurkvadratoj estas haveblaj. Klarner kaj Göbel montris ke por ĉiu plurkvadrato estas finia aro de primaj ortanguloj kiujn ĝi kahelas, tiel ke ĉiuj la aliaj ortanguloj kiuj ĝi kahelas povas esti kahelitaj per ĉi tiuj primaj ortanguloj.

Preter ortanguloj, Golomb donis hierarkion por solaj plurkvadratoj: plurkvadrato povas kaheli ortangulon, duonon de bendo, kurban bendon, pligrandigitan kopion de si, kvaronebenon, bendon, duonebenon, tutan ebenon, certajn kombinaĵojn, aŭ nenion el ĉi tio. Estas certaj implikacioj inter ĉi tiuj, ambaŭ evidentaj (ekzemple, se plurkvadrato kahelas duonebenon do ĝi kahelas la tutan ebenon) kaj malpli evidentaj (ekzemple, se plurkvadrato kahelas pligrandigitan kopion de si do ĝi kahelas kvaronebenon). Plurkvadratoj de ordoj supren ĝis 6 estas priskribitaj en ĉi tiu hierarkio (kun nesolvita tiam la statuso de unu 6-kvadrato, poste estis trovite ke ĝi kahelas ortangulon).

Kahelado de ebeno kun kopioj de sola plurkvadrato

Ĉiuj plurkvadratoj de ordoj 1 ... 6 kahelas ebenon, ĉiuj 7-kvadratoj krom 4 kahelas ebenon. David Bird trovis ke ĉiuj 8-kvadratoj krom 26 kahelas ebenon. Rawsthorne trovis ke ĉiuj 9-plurkvadratoj krom 235 kahelas ebenon. Ĉi tiaj rezultoj estas etenditaj al pli alta ordoj de Rhoads (al ordo 14) kaj aliaj. Plurkvadrataj kahelaroj de ebeno estas klasifikitaj per la simetrioj kaj per la kvanto de aspektoj (orientiĝoj) en kiuj la kaheloj aperas en ili.