Rauhalliset ratsut

Kuinka monella tavalla voidaan kaksi valkeaa ja kaksi mustaa hevosta asettaa nxn-shakkilaudalle, siten että uhkauksia ei ole?

- Samanväriset saavat uhata toisiaan, eriväriset eivät.
- Samanväriset hevoset ovat identtisen näköiset eli niistä ei pysty sanomaan kumpi on kumpi (eli niiden järjestyksellä laudalla ei ole väliä). Eriväriset tietenkin on erotettavissa.
- Laudan asento on kiinnitetty (joten kiertosymmetriset, kuten myös peilisymmetrisetkin, asettelut lasketaan erillisinä).
Ilmoita


Helppo laskea pienellä Python ohjelmalla. Lopussa (n>15) alkaa hidastumaan, joten kannattaa ajaa Pypyllä.

n
2: 6
3: 244
4: 4232
5: 37464
6: 204662
7: 824996
8: 2688240
9: 7487972
10: 18497750
11: 41565432
12: 86511416
13: 169026560
14: 313175622
15: 554622140
16: 944700752
17: 1555473036
18: 2485913030
19: 3869378672
20: 5882535480
2 VASTAUSTA:
Jos joku epäilee tulosten oikeellisuutta, niin alla on kaikki 244 vaihtoehtoa 3x3 laudalla. Laudan ruudut on numeroitu

0,1,2
3,4,5
6,7,8

Alla olevien nelinumeroisten lukujen kaksi ensimmäistä numeroa kertoo valkoisten ratsujen sijainnit ja kaksi jälkimmäistä mustien ratsujen sijainnit. Tarkistakaa muutama tapaus!

0123, 0124, 0134, 0214, 0216, 0218, 0246, 0248, 0268, 0314, 0316, 0346, 0412, 0413, 0416, 0418, 0423, 0426, 0428, 0436, 0438, 0468, 0512, 0513, 0514, 0518, 0523, 0524, 0528, 0534, 0538, 0548, 0623, 0624, 0628, 0634, 0638, 0648, 0713, 0714, 0716, 0718, 0734, 0736, 0738, 0746, 0748, 0768, 0824, 0826, 0846, 1204, 1205, 1245, 1304, 1305, 1307, 1345, 1347, 1357, 1402, 1403, 1405, 1407, 1423, 1425, 1427, 1435, 1437, 1457, 1523, 1524, 1527, 1534, 1537, 1547, 1602, 1603, 1604, 1607, 1623, 1624, 1627, 1634, 1637, 1647, 1734, 1735, 1745, 1802, 1804, 1805, 1807, 1824, 1825, 1827, 1845, 1847, 1857, 2301, 2304, 2305, 2306, 2314, 2315, 2316, 2345, 2346, 2356, 2401, 2405, 2406, 2408, 2415, 2416, 2418, 2456, 2458, 2468, 2514, 2518, 2548, 2604, 2608, 2648, 2714, 2715, 2716, 2718, 2745, 2746, 2748, 2756, 2758, 2768, 2804, 2805, 2806, 2845, 2846, 2856, 3401, 3405, 3406, 3407, 3415, 3416, 3417, 3456, 3457, 3467, 3514, 3517, 3547, 3604, 3607, 3647, 3714, 3715, 3716, 3745, 3746, 3756, 3804, 3805, 3806, 3807, 3845, 3846, 3847, 3856, 3857, 3867, 4512, 4513, 4517, 4518, 4523, 4527, 4528, 4537, 4538, 4578, 4602, 4603, 4607, 4608, 4623, 4627, 4628, 4637, 4638, 4678, 4713, 4715, 4716, 4718, 4735, 4736, 4738, 4756, 4758, 4768, 4802, 4805, 4806, 4807, 4825, 4826, 4827, 4856, 4857, 4867, 5623, 5624, 5627, 5628, 5634, 5637, 5638, 5647, 5648, 5678, 5713, 5714, 5718, 5734, 5738, 5748, 5824, 5827, 5847, 6734, 6738, 6748, 6802, 6804, 6807, 6824, 6827, 6847, 7845, 7846, 7856
Täysin oikein! Tai siis ainakin itse saan samat, joten luultavasti :D.

Vakioaikainen algoritmi on kuitenkin olemassa ja sen löytäminen aika mielenkiintoinen pähkinä.

Esimerkiksi:

n=100: 2490750884432120
n=1000: 249990524114158110222320
n=100000: 2499999990500240011474408001065372794320

Noiden lukujen muoto tietenkin kielii siitä, että siellä on jokin johtava termi. Johan se on nähtävissä siitäkin, että kun lauta kasvaa suureksi, tulee uhkauksien merkitys entistä mitättömämmäksi ja ratsut saavat sijaita melkein kuinka vaan laudalla. No, en nyt paljasta enempää, mutta innostuin vähän ja kirjoitin juttua vastaavasta neljän saman värisen ratsun tehtävästä:
https://membolicsythod.home.blog/2019/06/17/rauhalliset-ratsut/
Kannattaa kokeilla vastaavaa tehtävää ensin kolmelle ratsulle, joka sen alkuperäinen muoto ohjelmointiputkassa olikin, missä tähän tehtävään törmäsin: https://www.ohjelmointiputka.net/postit/tehtava.php?tunnus=kunhev

Tuolla blogissa on muuten juttua myös muista täälläkin palstalla esiintyneistä tehtävistä kuten Vangin pasianssi ja mikäs se toinen oli .. ai niin se suorakaide-tehtävä, mutta en ole vielä julkaissut sitä artikkelia, kannattaa pysyä linjoilla jos kiinnostaa.. :D
+Lisää kommentti
Valkoiset ratsut voidaan asettaa ihan peruskoulumatikalla tarkasti (n^2-1)*n/2 tavalla. Jos n on iso, mustat ratsut voidaan sijoittaa valkoisten sekaan noin (n^2-19)*(n^2-18)/2 tavalla. Nuo kertomalla saadaan ihan hyvät likiarvot:

n = 100: 2490509474145000
n = 1000: 249990500094749914500000
n = 100000: 2499999990500000009474999999145000000000
n = 1000000: 249999999990500000000094749999999914500000000000
n = 10000000: 24999999999990500000000000947499999999991450000000000000

Aika lähellä sinun tarkkoja arvoja.
3 VASTAUSTA:
Poistamalla valkoisten ratsujen reunojen yli menevät ja päällekkäiset varaukset saadaan 1000x1000 kahden ratsun keskimääräiseksi ruutujen varausluvuksi 17.9519861838. Pitää laskea vain valkoisten ratsujen n. 500 miljardia kombinaatiota! Kaavassa 18 korvautuu tuolla ja 19 muuttuu 18.9519861838:ksi. Tulokseksi saadaan

n = 1000: 249990524101190492356608

Alkaa olla kohta tarkempi kuin ihan tarkka luku!
Anonyymi kirjoitti:
Poistamalla valkoisten ratsujen reunojen yli menevät ja päällekkäiset varaukset saadaan 1000x1000 kahden ratsun keskimääräiseksi ruutujen varausluvuksi 17.9519861838. Pitää laskea vain valkoisten ratsujen n. 500 miljardia kombinaatiota! Kaavassa 18 korvautuu tuolla ja 19 muuttuu 18.9519861838:ksi. Tulokseksi saadaan

n = 1000: 249990524101190492356608

Alkaa olla kohta tarkempi kuin ihan tarkka luku!
Olin nopeuttanut ohjelmaa virheellisesti ja ohjelma jätti huomioimatta kaukaisimmat yhteiset uhkaukset. Oikea ruutujen keskimääräinen varausluku onkin 17.9519603276 ja sillä saadaan tulokseksi:

n = 1000: 249990524114118310363136

Kolme oikeaa numero lisää. Tarkka luku näyttää olevan ihan oikea!
(n^2-1)*n/2 * (n^2-a)*(n^2-b)/2
=
1/4 * (n^8 - (1+b+a)n^6 + (a+b+ab)n^4 - (ab)n^2 )

Kun
a = 18.9519861838
b = 17.9519861838,
niin
1+b+a = 37.9 = 38
Kyllä, kyllä oikealta näyttää! Pyöristämällä päästäänkin oikeaan kertoimeen :D

a+b+ab = 377.1 Tämä heittää jo vähän enemmän ja viidennen asteen termi puuttuu välistä. Ratkaisu on siis, paljastettakoon: polynomi!

Voisikohan viidellekin ratsulle vain laskea arvon tarpeeksi monessa pisteessä ja päätellä niistä mikä polynomi ratkaisun on oltava? Se siinä vaan vielä on, että siinä on aina jokin alaraja mistä lähtien polynomi alkaa antamaan arvon ja pitäisi tietää mikä se viiden tapauksessa on ja sitten vielä jotenkin laskea tarpeeksi monessa ja siis tarpeeksi isoissa pisteessä se arvo.
Periaatteessa sitä inkluusio-eksluusio ratkaisuakin voisi koittaa, mutta siinä olisi 5C2 = 10 ehtoa ja niistä tulee melko monia erilaisia leikkaustyyppejä. Miten esimerkiksi 5-ketjujen määrän voi graafilta laskea? Tai no, varmaan niitä voisi eri n:n arvoille laskea ja sitten arvata kaavan, jos siinä näkyy joku systemaattisuus.
+Lisää kommentti

Vastaa alkuperäiseen viestiin

Rauhalliset ratsut

Kuinka monella tavalla voidaan kaksi valkeaa ja kaksi mustaa hevosta asettaa nxn-shakkilaudalle, siten että uhkauksia ei ole?

- Samanväriset saavat uhata toisiaan, eriväriset eivät.
- Samanväriset hevoset ovat identtisen näköiset eli niistä ei pysty sanomaan kumpi on kumpi (eli niiden järjestyksellä laudalla ei ole väliä). Eriväriset tietenkin on erotettavissa.
- Laudan asento on kiinnitetty (joten kiertosymmetriset, kuten myös peilisymmetrisetkin, asettelut lasketaan erillisinä).

5000 merkkiä jäljellä

Rekisteröidy, jos haluat käyttää nimimerkkiä.

Peruuta