Bagaimana saya bisa menghasilkan teka-teki Sudoku?

Saya mencoba membuat generator puzzle Sudoku. Ini jauh lebih sulit dari yang saya harapkan dan semakin saya masuk ke dalamnya, semakin sulit!

Pendekatan saya saat ini adalah untuk membagi masalah menjadi 2 langkah:

1. Hasilkan puzzle Sudoku yang lengkap (terpecahkan).
2. Hapus angka sampai dapat dipecahkan dan hanya memiliki 1 solusi.

Pada langkah 1, karena saya menggunakan metode brute force, saya menghadapi beberapa masalah run time. Apakah ada cara optimal untuk mengisi teka-teki Sudoku yang lengkap?

Pada langkah 2, algoritme apa yang harus saya gunakan untuk "memusingkan" sudoku yang terpecahkan?

Saya memiliki permainan Sudoku terlaris di toko aplikasi iOS. Inilah cara saya membuat puzzle.

Pertama saya punya aplikasi penghasil puzzle. Tapi itu bukan bagian dari kode permainan. Ini adalah aplikasi yang berdiri sendiri yang saya gunakan untuk membuat teka-teki. Ini sangat dimodifikasi sehingga saya dapat mengaturnya untuk membuat jenis pola yang berbeda, peringkat kesulitan, jumlah pemberian, dll. Menghasilkan teka-teki dan mendapatkan tingkat kesulitan yang konsisten sulit dilakukan dengan cepat dan membutuhkan waktu lebih lama daripada yang ingin ditunggu pemain. Jadi, saya menghasilkan apa yang saya sebut "seed puzzle" dan itulah yang digunakan oleh kode game untuk menghasilkan puzzle yang dimainkan orang.

Saya tidak menjawab bagaimana cara membuat kode generator di sini. Anda dapat google dan menemukan banyak kode generator puzzle online. Mulai dari sana. Tetapi untuk membuat game yang bagus, Anda harus membuat game yang bagus. Game saya tidak menghasilkan teka-teki dengan cepat.

Cara kerja aplikasi penghasil teka-teki saya adalah ia menghasilkan ribuan teka-teki per menit, tetapi tidak semuanya baik dan tidak semua cocok dengan tingkat kesulitan tertentu. Generator membuat puzzle, kemudian memecahkannya dan mencari tahu tingkat kesulitannya, dan skor puzzle berdasarkan teknik yang diperlukan untuk memecahkan puzzle, dan menentukan apakah tebakan diperlukan untuk menyelesaikannya (yang biasanya buruk). Itu mengeluarkan setiap puzzle yang tidak cocok dengan kriteria. Untuk teka-teki yang sulit tetapi tidak mustahil, pada mesin yang cepat, dibutuhkan waktu satu jam untuk menghasilkan 100 teka-teki yang sesuai dengan spesifikasi saya yang sebenarnya. Inilah sebabnya saya tidak melakukan ini di aplikasi. Menghasilkan puzzle dengan cepat dengan spesifikasi yang sulit itu tidak akan berfungsi untuk kualitas puzzle yang saya miliki di aplikasi saya.

Teka-teki adalah string, panjang 162 karakter, 81 karakter dengan angka dan garis putus-putus atau titik-titik di mana titik kosong akan berada, kemudian 81 karakter dengan solusinya. Lalu kolom untuk masing-masing statistik, seperti berapa banyak lajang, ganda, dll.

Output saya dari semua sesi generasi adalah garis dibatasi koma dengan statistik sebagai kolom. Saya mungkin akan mengambil 10.000 teka-teki, membawanya untuk unggul, dan mengurutkannya berdasarkan kesulitan. Kemudian bawa mereka ke dalam aplikasi untuk melihatnya di papan permainan. Saya juga melihat mereka untuk daya tarik visual dan pola yang terlihat pada teka-teki. Lalu saya memilih tangan dari mereka.

Saya menyebutnya puzzle awal dan inilah yang saya maksud. Angka-angka dalam permainan sudoku benar-benar hanya token. Alih-alih menjadi angka 1-9 mereka bisa menjadi warna atau simbol atau huruf. Jadi teka-teki benih saya bukan angka, melainkan huruf ai. Setiap puzzle awal diubah dengan cepat untuk membuat puzzle yang dapat dimainkan:

1. Mengacak angka / token. Ketika saya mengubah huruf ai kembali ke angka 1-9 tabel pencarian acak. Artinya a tidak selalu 1. Itu saja menciptakan sekitar 300.000 variasi pada setiap puzzle.
2. Putar puzzle dengan 90, 180 atau 270 derajat. Itu menambah 4 variasi lagi.
3. Tutup puzzle secara horizontal, vertikal, atau keduanya. Itu menambah 4 variasi lagi.

Oleh karena itu setiap puzzle benih dapat membuat variasi 5.806.080. Saya sudah menguji ini di lapangan dengan pemain sungguhan. Orang tidak tahu mereka pada dasarnya memainkan puzzle yang sama. Sebenarnya tidak mungkin. Hanya jika mereka memperhatikan bahwa pola givens berada dalam adalah sama setiap kali. Tetapi dengan bahkan 100 biji yang berbeda tidak akan ada yang memperhatikan. Jutaan pengguna game saya belum. Saya juga sudah mengujinya dengan aplikasi solver. Aplikasi pemecah tidak akan memecahkan teka-teki dengan cara yang sama ketika diputar atau dijatuhkan. Bahkan kadang-kadang akan menganalisisnya sebagai peringkat kesulitan yang berbeda meskipun secara teknis teka-teki yang sama.

Namun, Big Bad Sudoku Book memiliki 10 dari 1000's teka-teki benih di 5 tingkat kesulitan, dan beberapa jenis pola puzzle. Ini berarti ada miliaran teka-teki di gim saya. Dengan setiap 10.000 teka-teki benih ada 58.060.800.000 teka-teki yang berbeda.

Di Sudoku Book versi 4 (yang akan keluar 2016) saya menemukan cara untuk dapat menentukan puzzle yang tepat dari 58 miliar itu dan mendapatkan puzzle yang sama pada perangkat masing-masing pemain.

Pada langkah (1) Hasilkan puzzle Sudoku yang lengkap (terpecahkan), karena saya menggunakan metode brute force, saya menghadapi beberapa masalah run time. Apakah ada cara optimal untuk mengisi teka-teki Sudoku yang lengkap?

Ada cara mudah untuk mengisi teka-teki Sudoku lengkap - pengisian grup dan pergantian lingkaran.

1. Isi baris pertama dengan sembilan angka berbeda.
2. Isi baris kedua yang merupakan pergeseran baris pertama dengan tiga slot.
3. Isi baris ketiga yang merupakan pergeseran baris kedua sebanyak tiga slot.
4. Isi baris keempat yang merupakan pergeseran yang ketiga dengan satu slot.

line 1: 8 9 3  2 7 6  4 5 1
line 2: 2 7 6  4 5 1  8 9 3 (shift 3)
line 3: 4 5 1  8 9 3  2 7 6 (shift 3)

line 4: 5 1 8  9 3 2  7 6 4 (shift 1)
line 5: 9 3 2  7 6 4  5 1 8 (shift 3)
line 6: 7 6 4  5 1 8  9 3 2 (shift 3)

line 7: 6 4 5  1 8 9  3 2 7 (shift 1)
line 8: 1 8 9  3 2 7  6 4 5 (shift 3)
line 9: 3 2 7  6 4 5  1 8 9 (shift 3)

Untuk mencegah pengguna memperhatikan pola yang jelas, mungkin ide yang baik untuk mengacak urutan baris dan kolom sehingga tidak ada lagi pola. Selama semua 9 angka di setiap baris / kolom bergerak bersama sebagai satu unit atom, papan Sudoku akan selalu tetap valid.

Anda mendapatkan puzzle Sudoku yang lengkap. Untuk lebih jelasnya, Anda dapat mencari "make Sudoku".

Ini tidak terlalu sulit, asalkan Anda memiliki pemecah sudoku.

Membuat solver sudoku adalah masalah yang sulit / menarik, jadi yang terbaik adalah menyimpannya untuk pertanyaan yang berbeda. Atau Anda bisa membaca ini dan melihat bagaimana Anda pergi.

1. Untuk menghasilkan teka-teki yang dipecahkan, jalankan saja solver pada papan kosong. Satu-satunya peringatan adalah Anda harus mengacak "tebakan" yang digunakan pemecah, jika tidak, Anda akan berakhir dengan puzzle yang sama setiap kali. Yaitu, pada titik tertentu pemecah akan mencoba nomor untuk sel; mungkin mencobanya dalam urutan ini:1, 2, 3, 4, ... dan pilih yang pertama yang berfungsi. Anda perlu mengacak urutan itu sehingga mencoba, katakan 4, 7, 2, 9, ...,. Proses ini harus secepat pemecah Anda.
2. Untuk menghapus angka, gunakan algoritma ini:
   • Pilih nomor acak yang belum Anda coba hapus sebelumnya
   • Hapus nomornya, jalankan solver Anda dengan ketentuan tambahan bahwa nomor itu tidak bisa menggunakan nomor yang dihapus di sini
   • Jika pemecah menemukan solusi, Anda tidak dapat menghapus nomornya
   • Ulangi, sampai Anda telah menghapus angka yang cukup (atau Anda tidak dapat menghapus lagi)

Ini adalah metode yang sangat sederhana (dan naif), jadi tidak ada jaminan bahwa Anda akan mendapatkan teka-teki kesulitan tertentu - selain dari jumlah angka yang hilang - atau jika Anda bahkan dapat menghapus jumlah angka yang Anda inginkan. Semoga ini bisa membantu.

Saya hanya berpikir itu menarik untuk menunjukkan halaman web ini , karena itu banyak membantu saya untuk pengembangan proyect kami. Membuat sudoku dengan solusi unik jauh dari tugas sederhana. Di tautan, Anda dapat menemukan bagaimana penulisnya (dia benar-benar melakukan pekerjaan yang hebat, bukan saya ya!), Menemukan beberapa strategi berbeda. Anda dapat memiliki ide untuk menghasilkan pemecah Sudoku Anda sendiri.

Sekarang, seiring dengan topik, ada juga cara untuk menghasilkan sudokus serupa, hanya dengan

1. Permutasi dari baris.
2. Solusi sederhana lainnya, adalah mulai dengan mengisi sudoku minimal 17 digit isian (yang terbukti minimun untuk menemukan solusi unik), dan isi berikut strategi yang berbeda (misalnya di tautan sebelumnya strategi dibagi pada kesulitan, Anda dapat melakukan hal serupa), hingga Anda mencapai solusi unik.
3. Ada daftar ahli matematika yang berusaha menemukan sudoku 16 digit awal solusi unik, dengan daftar 17 digit sudokus HUGEEEEEE. Saya tidak ingat apakah ia memiliki copy copy apa pun, tetapi saya cukup yakin, jika Anda dapat menawarkan kepadanya 17 solusi unik, sudoku akan lebih dari senang untuk membiarkan Anda menggunakan datanya.

Ceria dan semoga sukses dengan algoritma: D

Solver saya menggunakan brute force, dan dapat menemukan solusi dalam waktu 20 milidetik. Dengan menggunakan metode penghapusan, yang dijelaskan di atas, generator saya menghasilkan puzzle dalam waktu 200 milidetik.

Biasanya menghasilkan puzzle dengan sekitar 24-34 digit tersisa, dan saya masih tidak tahu bagaimana mereka bisa menghasilkan 17-digit puzzle.