Menambang Hexcellent

13

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 Xtambang 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.

Game sederhana

(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.

Posting Rock Garf Hunter
sumber
Jadi selalu harus ada 6 tepi antara 6 simpul input?
Bergi
@Bergi tepi di antara sel-sel nilai berlebihan, karena tidak ada artinya
H.PWiz
@ H.PWiz Tetapi " {3}aturan" mengatakan " semua tambang ini berbatasan satu sama lain dalam jalur berkelanjutan " - tanpa tepi tidak ada jalur.
Bergi
@Bergi tetapi tugasnya adalah membuat grafik sedemikian rupa sehingga ada 6 sel yang bertindak " seolah-olah mereka terhubung dengan aturan Hexcells {3}". Mereka tidak perlu terhubung
H.PWiz
1
@Pavel General minesweeper adalah bahasa pemrograman sejauh yang saya ketahui. Ini mungkin sangat esoteris, tapi saya pikir itu tidak terlalu jauh dari golf bukti .
Post Rock Garf Hunter

Jawaban:

15

7 5 simpul, 14 10 tepi

(Grafik dibuat dengan alat dan cat online ini .)

A- Fadalah enam simpul kami, dan Jmerupakan simpul penolong. Tiga- 1node menegakkan bahwa node yang berlawanan berbeda, sedangkan 2-node memastikan itu A, Cdan Etidak bisa semua tambang, atau semua kosong.

Edit: -2 simpul berkat CalculatorFeline dan H.PWiz!

Laikoni
sumber
1
Anda dapat menghapus 2 simpul.
CalculatorFeline
Perhatikan bahwa struktur 2-J juga memastikan bahwa ACE tidak semuanya kosong.
CalculatorFeline
3

9 Vertices, 17 Tepi

Dimana? adalah sel nilai, yang bukan merupakan salah satu yang 6kita pedulikan, kita perlu subgraf berikut.

    ___________
?  /    ?      \?
 \|    /|\     /
  3¯¯¯¯ 1 ¯¯¯¯2
  |\    |    /|
  | \ /¯|¯¯¯¯ |
  |  X  |     |
 /  / \_|___  \
A__/    B   \__C

Keterampilan ASCII-art saya mengerikan.

Dengan orang-orang 6 simpul mengatur: ABCdapat 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

  B  C
A      D
  F  E
H.Piz
sumber
Akan jauh lebih kecil jika Anda memeriksa A,C,Ebukan A,B,C.
CalculatorFeline
@CalculatorFeline Saya tidak bisa melihat mengapa ...
H.PWiz
Jika Anda menghapus perangkat centang ABC dari solusi Anda, itu hampir berfungsi, kecuali itu juga memungkinkan ACEdan BDF. Dalam hal itu, jumlah ranjau di ACEadalah 0 atau 3, tetapi dalam solusi yang valid adalah 1 atau 2. Ini memungkinkan Anda untuk memiliki skor 5.
CalculatorFeline
@CalculatorFeline Kanan, dan itu akan menjadi jawaban Laikoni minus 2. Saya mengerti sekarang. Ini jelas sulit disampaikan dengan teks
H.PWiz
@ CalculatorFeline Karena tidak mengandung ide utama kiriman saya, saya tidak akan mempostingnya. Saya pikir Laikoni akan
H.PWiz
3

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.

  A   B
   \ /
F---3---C
   / \
  E   D

Kemudian, kami memasang 012 sensor pada pasangan sel nilai (AB, BC, CD, DE, EF, FA). Struktur sensor 012 di bawah ini.

O   ?---1---?
 \ /       /
  2---?---1
 / \
A   B

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.

CalculatorFeline
sumber
Berapa output untuk setiap 012sensor? Juga, saya hanya menghitung 6 node di012
H.PWiz
Ada 2 simpul, 2 1 simpul, 3? node, dan C (yang bukan merupakan salah satu dari node ABCDEF, hanya output dari sensor).
CalculatorFeline
2
@CalculatorFeline Mengerti, mungkin mengganti nama Cmenjadi O, karena C ada diABCDEF
H.PWiz
Fakta menyenangkan: Solusi ini bersifat planar.
CalculatorFeline