Bagaimana saya bisa tahu jika permainan puzzle saya selalu memungkinkan?

68

Saya telah membuat semacam permainan puzzle di mana tujuannya adalah untuk menyingkirkan semua ubin putih. Anda dapat mencobanya di akhir pertanyaan.

Setiap kali, papan dihasilkan secara acak dengan ubin putih di tempat-tempat acak pada kotak 5 * 5. Anda dapat mengeklik ubin apa saja pada kisi itu dan itu akan mengubah warna dan semua ubin menyentuhnya di sisinya. Dilema saya adalah kenyataan bahwa saya tidak tahu apakah itu akan menghasilkan papan yang mustahil. Apa cara terbaik untuk memeriksa hal-hal seperti ini?

function newgame() {
 moves = 0;
    document.getElementById("moves").innerHTML = "Moves: "+moves;

  for (var i = 0; i < 25; i++) {
   if (Math.random() >= 0.5) {
$(document.getElementsByClassName('block')[i]).toggleClass("b1 b2")
   }
}
}
newgame();
function toggle(a,b) {  
  moves += 1;
  document.getElementById("moves").innerHTML = "Moves: "+moves;
$(document.getElementsByClassName('block')[a+(b*5)]).toggleClass("b1 b2");

if (a<4) {$(document.getElementsByClassName('block')[(a+1)+(b*5)]).toggleClass("b1 b2")}
  
  
if (a>0) {$(document.getElementsByClassName('block')[(a-1)+(b*5)]).toggleClass("b1 b2")}
  
  
if (b<4) {$(document.getElementsByClassName('block')[a+((b+1)*5)]).toggleClass("b1 b2")}
  
if (b>0) {$(document.getElementsByClassName('block')[a+((b-1)*5)]).toggleClass("b1 b2")}
}
body {
  background-color: #000000;
}

.game {
  float: left;
  background-color: #000000;
  width: 300px;
  height: 300px;
  overflow: hidden;
  overflow-x: hidden;
  user-select: none;
  display: inline-block;
}

.container {
  border-color: #ffffff;
  border-width: 5px;
  border-style: solid;
  border-radius: 5px;
  width: 600px;
  height: 300px;
  text-align: center;
}

.side {
  float: left;
  background-color: #000000;
  width: 300px;
  height: 300px;
  overflow: hidden;
  overflow-x: hidden;
  user-select: none;
  display: inline-block;
}

.block {
  transition: background-color 0.2s;
  float: left;
}

.b1:hover {
  background-color: #444444;
  cursor: pointer;
}

.b2:hover {
  background-color: #bbbbbb;
  cursor: pointer;
}

.row {
  width: 300px;
  overflow: auto;
  overflow-x: hidden;
}

.b1 {
  display: inline-block;
  height: 50px;
  width: 50px;
  background-color: #000000;
  border-color: #000000;
  border-width: 5px;
  border-style: solid;
}




.b2 {
  display: inline-block;
  height: 50px;
  width: 50px;
  background-color: #ffffff;
  border-color: #000000;
  border-width: 5px;
  border-style: solid;
}



.title {
  width: 200px;
  height: 50px;
  color: #ffffff;
  font-size: 55px;
  font-weight: bold;
  font-family: Arial;
  display: table-cell;
  vertical-align: middle;
}

.button {
  cursor: pointer;
  width: 200px;
  height: 50px;
  background-color: #000000;
  border-color: #ffffff;
  border-style: solid;
  border-width: 5px;
  color: #ffffff;
  font-size: 25px;
  font-weight: bold;
  font-family: Arial;
  display: table-cell;
  vertical-align: middle;
  border-radius: 5px;
  transition: background-color 0.3s, color 0.3s;
}

.button:hover {
  background-color: #ffffff;
  color: #000000;
}

.sidetable {
  padding: 30px 0px;
  height: 200px;
}


#moves {
  width: 200px;
  height: 50px;
  color: #aaaaaa;
  font-size: 30px;
  font-weight: bold;
  font-family: Arial;
  display: table-cell;
  vertical-align: middle;
}
<script src="https://ajax.googleapis.com/ajax/libs/jquery/2.1.1/jquery.min.js"></script>
<center>
  <div class="container">
  
  
  <div class="game"><div class="row"><div onclick="toggle(0,0);" class="block b1"></div><div onclick="toggle(1,0);" class="block b1"></div><div onclick="toggle(2,0);" class="block b1"></div><div onclick="toggle(3,0);" class="block b1"></div><div onclick="toggle(4,0);" class="block b1"></div></div><div class="row"><div onclick="toggle(0,1);" class="block b1"></div><div onclick="toggle(1,1);" class="block b1"></div><div onclick="toggle(2,1);" class="block b1"></div><div onclick="toggle(3,1);" class="block b1"></div><div onclick="toggle(4,1);" class="block b1"></div></div><div class="row"><div onclick="toggle(0,2);" class="block b1"></div><div onclick="toggle(1,2);" class="block b1"></div><div onclick="toggle(2,2);" class="block b1"></div><div onclick="toggle(3,2);" class="block b1"></div><div onclick="toggle(4,2);" class="block b1"></div></div><div class="row"><div onclick="toggle(0,3);" class="block b1"></div><div onclick="toggle(1,3);" class="block b1"></div><div onclick="toggle(2,3);" class="block b1"></div><div onclick="toggle(3,3);" class="block b1"></div><div onclick="toggle(4,3);" class="block b1"></div></div><div class="row"><div onclick="toggle(0,4);" class="block b1"></div><div onclick="toggle(1,4);" class="block b1"></div><div onclick="toggle(2,4);" class="block b1"></div><div onclick="toggle(3,4);" class="block b1"></div><div onclick="toggle(4,4);" class="block b1"></div></div></div>
    
    <div class="side">
      <center class="sidetable">
        <div class="title">Tiles</div>
        <br>
        <div class="button" onclick="newgame()">New Game</div>
        <br><br>
        <div id="moves">Moves: 0</div>
      </center>
    </div>
    
  </div>
    </center>

Qwerty
sumber
9
Jika Anda tertarik dengan jenis permainan puzzle ini, lihatlah Koleksi Puzzle Portable Simon Tatham . Terlepas dari jenis ini (disebut Balik di sana), Anda dapat menemukan varian banyak teka-teki Jepang dan lainnya. Semuanya di bawah lisensi BSD dan mungkin bacaan yang menarik.
Dubu
10
Bagaimana dengan rekayasa ulang itu? Mulai dengan papan kosong, lalu otomatiskan, ucapkan 20 klik pada kuadrat acak. Dengan begitu Anda tahu pasti ada solusi di akhirnya.
AJFaraday
3
Aku ingin terus bermain, tetapi karena pertanyaanmu, ketidakpastian apakah aku benar-benar akan menang atau tidak sedang makan padaku! Game menyenangkan :)
MrDuk
@MrDuk codepen.io/qwertyquerty/pen/WMGwVW inilah proyek yang sudah selesai! Yang ini sudah diperbaiki, dan dipoles. Saya juga membuat aplikasi elektron.
Qwerty
@Qwerty ketika saya mencoba melihat Pena Anda dalam tampilan halaman penuh, saya mendapat pesan "Pemilik Pena ini perlu memverifikasi alamat email mereka untuk mengaktifkan Tampilan Halaman Penuh." Harap verifikasi alamat email Anda di CodePen sehingga saya dapat menikmati permainan Anda di jendela penuh! :)
stephenwade

Jawaban:

161

Ini adalah jenis permainan di mana gerakan yang sama dilakukan dua kali membalikkan papan ke keadaan sebelumnya. Jadi untuk memastikan papan dapat dipecahkan, buat dengan memutar secara terbalik. Mulailah dengan papan yang dipecahkan (kosong), kemudian mulailah secara terprogram "mengklik" secara acak beberapa kali, atau sampai papan memiliki jumlah kotak putih yang diinginkan. Salah satu solusinya adalah dengan hanya melakukan gerakan yang sama dalam urutan terbalik. Solusi lain yang lebih pendek mungkin ada, tetapi Anda dijamin memiliki setidaknya satu.

Solusi lain, yang jauh lebih kompleks, adalah mendefinisikan algoritma penyelesaian yang melewati semua status permainan yang mungkin dari posisi awal Anda untuk mencoba menemukan solusinya. Ini akan membutuhkan waktu lebih lama untuk diimplementasikan dan dijalankan, tetapi akan memungkinkan papan untuk benar-benar dihasilkan secara acak. Saya tidak akan membahas secara spesifik solusi ini, karena itu bukan ide yang bagus.

Ed Marty
sumber
22
@Qwerty: untuk masalah spesifik Anda, mengklik kotak yang sama dua kali membatalkannya, jadi tidak pernah ada alasan untuk mengklik kotak apa pun lebih dari sekali. Anda mungkin ingin memilih sejumlah kotak untuk diklik tanpa mengulangi, atau mempertimbangkan solusi yang memberikan peluang klik-klik sebesar XX% untuk setiap kotak di papan tulis. (Ed: Jawaban yang bagus, +1!)
Jeff Bowman
3
Saya telah membuat game yang hampir sama persis sebelumnya dan akhirnya menggunakan pendekatan ini. Saya memasukkan animasi di awal yang menunjukkan kondisi terpecahkan pergi ke keadaan tidak terpecahkan dengan cepat; itu cantik.
Jared Goguen
1
@JaredGoguen aneh, saya menambahkan itu dan kembali ke sini untuk melihat komentar Anda.
Qwerty
4
@JeffBowman Memang, himpunan game yang dapat dipecahkan dapat diperlakukan sebagai nilai 25-bit, dengan masing-masing bit sesuai dengan kuadrat yang merupakan jumlah kali itu dibalik mod 2. Jadi seseorang dapat menghasilkan angka acak di kisaran 0. 0,33,554,432 dan kemudian menghitung nilai setiap kotak di papan dari itu dalam waktu singkat.
Monty Harder
7
Untuk apa nilainya, sementara ini adalah jawaban yang benar untuk pertanyaan matematika tentang bagaimana menjawab masalah ini, ini biasanya merupakan praktik yang meragukan dari sudut pandang desain. Generasi semacam ini, tanpa rencana khusus untuk itu, umumnya mengarah pada teka-teki yang terasa sangat 'sama', tanpa titik minat tertentu atau tema pemersatu. Dimungkinkan untuk 'secara prosedural menghasilkan' contoh masalah yang menarik untuk permainan puzzle, tetapi biasanya membutuhkan tampilan yang jauh lebih sulit pada apa fitur menarik dari teka-teki Anda.
Steven Stadnicki
92

Meskipun jawaban di atas cerdas (dan mungkin bagaimana saya akan melakukannya), permainan khusus ini sangat terkenal. Ini disebut Lights Out , dan telah dipecahkan secara matematis. Ada solusi jika dan hanya jika dua jumlah dari berbagai elemen (diberikan pada halaman wikipedia) tambahkan ke nol mod 2 (yaitu bilangan genap). Secara umum, aljabar linear kecil harus memberikan kondisi solusi yang serupa untuk game di papan mana pun.

Robert Mastragostino
sumber
2
Agak menyedihkan mengetahui bahwa itu sudah dibuat. Saya pikir saya sedang melakukan sesuatu.
Qwerty
39
@Qwerty hanya ada sedikit ide orisinal, dan Anda tentu tidak perlu memiliki satu untuk menjadi sukses (cf Rovio, King).
Stop Harming Monica
14
Game khusus ini ada, tetapi Anda selalu dapat memperluas ide! Tambahkan lebih banyak fitur! Tambahkan aturan berbeda untuk apa yang terjadi ketika Anda mengklik di suatu tempat, seperti warna yang ditambahkan bersama-sama berdasarkan dari mana itu diaktifkan / dinonaktifkan. Tambahkan "alat" berbeda yang harus Anda gunakan. Tambahkan papan non-persegi panjang! Banyak hal menyenangkan untuk dilakukan. Ingatlah bahwa suatu gerakan harus selalu terbalik dengan sendirinya.
Ed Marty
7
@OrangeDog: Bahkan 'Lamp Out' tidak asli, itu hanya nama merek yang mulai populer di tahun 90-an. Artikel wikipedia, misalnya, mencantumkan ini dan ini
BlueRaja - Danny Pflughoeft
1
Jawaban mana yang Anda sebut sebagai "jawaban di atas"? Sama sekali tidak jelas, karena di layar saya, hanya ada satu jawaban di atas Anda. Ingat bahwa jawaban mengubah urutan tergantung pada suara dan opsi pengguna. Anda harus selalu menautkan ke jawaban spesifik alih-alih merujuk ke sesuatu "di atas".
David Richerby
13

Pergi sebaliknya ketika menghasilkan puzzle Anda.

Alih-alih secara acak memilih ubin dan mengubahnya dari putih menjadi hitam, mulai dari batu tulis kosong, kemudian pilih ubin tapi bukannya beralih bahwa ubin hitam, membuatnya seolah-olah pengguna yang dipilih itu, mengakibatkan membalik semua ubin lainnya di sekitarnya.

Dengan cara ini Anda akan dijamin memiliki setidaknya satu solusi: pengguna harus membatalkan apa yang pemain "AI" Anda lakukan untuk membuat level.

Vaillancourt
sumber
7

Ed dan Alexandre punya hak untuk itu.

Tapi jika Anda tidak ingin tahu jika setiap solusi yang mungkin, ada cara.

Ada sejumlah kemungkinan teka-teki

Mengklik pada kotak yang sama dua kali menghasilkan hasil yang sama dengan tidak mengkliknya sama sekali, tidak peduli berapa banyak klik yang dibuat di antara mereka. Itu berarti bahwa setiap solusi dapat dideskripsikan dengan memberikan setiap kotak nilai biner dari 'diklik' atau 'tidak diklik'. Demikian pula, setiap teka-teki dapat dideskripsikan dengan memberikan nilai kuadrat 'toggled' atau 'not toggled' kepada setiap kotak. Itu berarti ada 2 ^ 25 kemungkinan teka-teki, dan 2 ^ 25 kemungkinan solusi. Jika Anda dapat membuktikan bahwa setiap solusi memecahkan teka-teki unik maka harus ada solusi untuk setiap teka-teki. Demikian pula, jika Anda menemukan dua solusi yang memecahkan puzzle yang sama maka tidak ada solusi untuk setiap puzzle.

Juga, 2 ^ 25 adalah 33.554.432. Itu cukup banyak, tetapi itu bukan angka yang tidak dapat dikelola. Algoritme yang baik dan komputer yang bagus mungkin dapat memaksa hal itu dalam beberapa jam, terutama ketika Anda menganggap bahwa setengah dari teka-teki tersebut adalah kebalikan dari setengah lainnya.

Lupus Arcanist
sumber
4
Lebih dari setengahnya adalah "terbalik" - selain pantulan horizontal, Anda juga memiliki pantulan dan rotasi vertikal.
Clockwork-Muse
@ Clockwork-Muse, ya, tapi itu lebih sulit untuk menghitung angka pastinya, karena sementara desain asimetris dapat diputar dan dibalik dalam 8 permutasi, desain simetris memiliki permutasi yang lebih sedikit. Jadi saya hanya menyebutkan pembalik putih / hitam, karena setiap solusi memiliki tepat 1 terbalik. (Meskipun untuk itu terbalik untuk bekerja, Anda harus membuktikan bahwa Anda dapat membalik seluruh papan)
Arcanist Lupus
Ternyata, seperti yang dikatakan Robert Mastragostino dalam jawabannya, ini sebenarnya adalah masalah yang diketahui dan dipelajari dengan baik. Setiap puzzle yang dapat dipecahkan memiliki 4 solusi tepat, dan sebagian besar papan acak tidak dapat dipecahkan. Mencari semua ruang itu mungkin menyenangkan, tetapi karena sudah ada bukti ( math.ksu.edu/math551/math551a.f06/lights_out.pdf ) Anda juga dapat melakukan beberapa produk titik dan memiliki jawaban yang sama dalam beberapa mikrodetik. :)
GrandOpener
Waktu Matematika: Jika Anda ingin menghitung jumlah papan yang berbeda (terlepas dari solvabilitas), dengan mempertimbangkan semua simetri, maka lemma Burnside adalah cara yang harus diambil: Ada 16 simetri (satu sepele, tiga rotasi, empat refleksi, dan kemudian masing-masing dari 8 dikombinasikan dengan inversi on / off), dan untuk masing-masing simetri beberapa papan sepenuhnya tidak berubah. Jika Anda mengambil rata-rata papan yang sepenuhnya tidak berubah per simetri, itu sama dengan jumlah papan yang berbeda.
Arthur
1
@PeterTaylor Pasti akan memakan waktu lebih lama untuk kode simulator daripada menjalankan hasilnya.
corsiKa
4

Jawaban umum:

  1. Buat matriks ukuran (# bergerak) x (# lampu).
  2. Letakkan 1 dalam sel jika membuat gerakan yang sesuai dengan baris itu mengubah cahaya yang sesuai dengan kolom itu, 0 sebaliknya.
  3. Lakukan eliminasi Gauss-Jordan (modulo 2) pada matriks.
  4. Jika matriks yang dihasilkan memiliki 1 tunggal di setiap kolom, dan setiap baris memiliki paling banyak 1, maka setiap kisi di solvable.
Mark Tilford
sumber
1

Yang lain telah menyebutkan cara untuk menemukan apakah teka-teki yang Anda buat secara acak dapat dipecahkan. pertanyaan yang juga harus Anda tanyakan adalah apakah Anda benar-benar ingin puzzle yang dihasilkan secara acak.

Teka-teki yang dihasilkan secara acak semua memiliki kelemahan inti yang sama: Kesulitan mereka cukup banyak yang tidak terduga. Teka-teki yang mungkin Anda dapatkan bisa berkisar dari yang sudah dipecahkan, ke sepele (solusi jelas) ke sulit (solusi tidak jelas) hingga tidak mungkin (puzzle tidak dapat dipecahkan sama sekali). Karena kesulitannya tidak dapat diprediksi, itu membuat pengalaman yang tidak memuaskan bagi pemain, terutama jika mereka melakukan banyak teka-teki berturut-turut. Mereka sangat tidak mungkin mendapatkan kurva kesulitan yang mulus, yang bisa membuat mereka bosan atau frustrasi tergantung pada teka-teki apa yang mereka dapatkan.

Masalah lain dari generasi acak adalah bahwa waktu yang dibutuhkan untuk menginisialisasi puzzle tidak dapat diprediksi. Secara umum, Anda akan mendapatkan teka-teki yang dapat dipecahkan (hampir) segera, tetapi dengan sedikit nasib buruk, teka-teki Anda yang dihasilkan secara acak mungkin berakhir pada rentetan teka-teki yang tidak dapat diselesaikan.

Salah satu cara untuk memecahkan kedua hal ini adalah dengan memiliki vektor yang telah ditentukan dari setiap teka-teki yang dapat dipecahkan yang tersedia, disusun menjadi kelompok-kelompok kesulitan, dan kemudian memilih teka-teki acak dari teka-teki yang dapat dipecahkan berdasarkan kesulitan. Dengan cara ini, Anda akan yakin bahwa setiap puzzle dapat dipecahkan, bahwa kesulitannya dapat diprediksi dan bahwa generasi akan dilakukan dalam waktu yang konstan.

Nzall
sumber