Hexcells adalah game berbasiskan Minesweeper yang dimainkan di segi enam. (Pengungkapan penuh: Saya tidak ada sangkut pautnya dengan Hexcells. Sebenarnya saya tidak terlalu menyukai permainan itu.) Sebagian besar aturan Hexcells dapat dengan mudah diungkapkan dalam Generalized Minesweeper (Minesweeper bermain pada grafik yang berubah-ubah). Salah satu yang paling sulit adalah {X}
dan -X-
aturan.
The {X}
Aturan memberitahu kita bahwa sel berbatasan X
tambang dan bahwa semua tambang ini berbatasan satu sama lain di jalur yang berkelanjutan. Sebagai contoh jika kita memiliki papan:
? ?
? {3} ?
? ?
6 kemungkinan untuk penempatan tambang adalah
* . . . . . . * * * * *
* {3} . * {3} . . {3} * . {3} * . {3} * * {3} .
* . * * * * . * . . . .
Tujuan Anda adalah untuk menerapkan aturan {3}
dalam Minesweeper umum.
Spesifik
Generalized Minesweeper adalah Minesweeper yang dimainkan pada grafik arbitrer. Grafik memiliki dua jenis titik, "indikator" atau "nilai". Nilai dapat berupa hidup atau mati (tambang atau tak berguna) namun kondisinya tidak diketahui oleh pemain. Indikator memberi tahu pemain berapa banyak simpul yang berdekatan berada di (tambang) dan tidak dihitung sebagai tambang itu sendiri.
Misalnya papan berikut untuk Generalized Minesweeper memberi tahu kita bahwa sel A dan B keduanya merupakan ranjau atau tidak ada ranjau.
(Dalam diagram indikator ditandai abu-abu sementara nilainya putih)
Tidak seperti di kapal penyapu ranjau normal di mana Anda mengklik nilai yang tidak aktif untuk mengungkapkan indikator, tidak ada mekanik seperti itu di Generalized Minesweeper. Seorang pemain hanya menentukan keadaan grafik yang dapat memenuhi indikatornya.
Tujuan Anda adalah untuk membangun struktur di Generalized Minesweeper sedemikian rupa sehingga ada 6 sel khusus yang hanya dapat memiliki status yang memenuhi seolah-olah mereka terhubung dengan aturan Hexcells {3}
. Ketika Anda menulis solusi Anda, Anda seharusnya tidak memiliki nilai spesifik dalam pikiran untuk sel-sel nilai. (Untuk menjawab pertanyaan H.PWiz, beberapa sel nilai mungkin dapat dikurangkan dari negara, tetapi Anda selalu dapat meningkatkan skor Anda dengan menghapus sel-sel tersebut)
Mencetak gol
Jawaban Anda akan dinilai dengan jumlah simpul dalam grafik akhir minus 6 (untuk 6 input) dengan skor yang lebih rendah menjadi lebih baik. Jika dua jawaban mengikat dalam metrik ini, pemutus dasi adalah jumlah ujung.
Solvabilitas
Masalah ini dapat dipecahkan, saya punya solusi untuk masalah ini dan saya akan mempostingnya setelah tantangan ini berumur seminggu.
sumber
{3}
aturan" mengatakan " semua tambang ini berbatasan satu sama lain dalam jalur berkelanjutan " - tanpa tepi tidak ada jalur.{3}
". Mereka tidak perlu terhubungJawaban:
75 simpul,1410 tepi(Grafik dibuat dengan alat dan cat online ini .)
A
-F
adalah enam simpul kami, danJ
merupakan simpul penolong. Tiga-1
node menegakkan bahwa node yang berlawanan berbeda, sedangkan2
-node memastikan ituA
,C
danE
tidak bisa semua tambang, atau semua kosong.Edit: -2 simpul berkat CalculatorFeline dan H.PWiz!
sumber
9 Vertices, 17 Tepi
Dimana? adalah sel nilai, yang bukan merupakan salah satu yang
6
kita pedulikan, kita perlu subgraf berikut.Keterampilan ASCII-art saya mengerikan.
Dengan orang-orang 6 simpul mengatur:
ABC
dapat memiliki status berikut:111
,110
,011
,000
,100
,001
Dengan sel-sel yang sesuai dengan segi enam berikut, semua kita kemudian perlu 3 sel indikator yang lebih
A-1-D
,B-1-E
,C-1-F
sumber
A,C,E
bukanA,B,C
.ACE
danBDF
. Dalam hal itu, jumlah ranjau diACE
adalah 0 atau 3, tetapi dalam solusi yang valid adalah 1 atau 2. Ini memungkinkan Anda untuk memiliki skor 5.44 simpul, 66 tepi
Pertama, kita mulai dengan cincin 6 sel nilai yang semuanya terhubung ke 3. Sel-sel ini akan menjadi sel dengan
{3}
aturan.Kemudian, kami memasang 012 sensor pada pasangan sel nilai (AB, BC, CD, DE, EF, FA). Struktur sensor 012 di bawah ini.
A dan B adalah input ke sensor dan O adalah output. Itu? sel adalah sel nilai generik. O akan menjadi tambang jika salah satu dari A dan B adalah tambang dan mengosongkannya. Kemudian, kami menghubungkan 2 simpul ke semua output sensor. Ini memastikan bahwa ada tepat 2 pasang dengan tepat 1 tambang, dan dapat dibuktikan bahwa satu-satunya konfigurasi yang memuaskan ini adalah yang memuaskan
{3}
. Setiap sensor membutuhkan 7 node, jadi 6 sensor membutuhkan 42. Tambahkan 3 node yang terhubung ke ABCDEF dan 2 node yang terhubung ke output dan Anda mendapatkan 44.Solusi ini juga dapat diadaptasi untuk
{1}
-{5}
dengan mengubah 3 simpul ke beberapa nilai lainnya.sumber
012
sensor? Juga, saya hanya menghitung 6 node di012
C
menjadiO
, karenaC
ada diABCDEF