Generator Sudoku acak

13

Saya ingin menghasilkan Sudoku yang sepenuhnya acak .

Tentukan kisi Sudoku sebagai kisi bulat antara 1 dan 9 tempat beberapa elemen dapat dihilangkan. Kisi adalah teka-teki yang valid jika ada cara unik untuk menyelesaikannya agar sesuai dengan batasan Sudoku (setiap baris, kolom, dan kotak 3 × 3 tidak memiliki elemen berulang) dan minimal dalam hal itu (yaitu jika Anda menghilangkan lagi elemen puzzle memiliki beberapa solusi).9×9193×3

Bagaimana saya bisa menghasilkan teka-teki Sudoku acak, sehingga semua teka-teki Sudoku bisa digunakan?

algorithms randomness sudoku Justin
sumber
Ini terlihat seperti solusi yang layak: dryicons.com/blog/2009/08/14/…
Joe
1
Sekarang ada pertanyaan meta tentang ini. Tolong diskusikan di sana atau dalam obrolan.
Kevin

Jawaban:

15

Menghasilkan distribusi seragam yang tepat dari semua teka-teki sudoku dapat dilakukan dengan cara itu: Anda hanya dapat membuat grid 9x9 secara acak dan kemudian hanya menyimpannya jika itu adalah kotak sudoku yang benar, jika tidak coba lagi.

917

[1,2,..9]9!

Mungkin Anda melihat ke mana saya akan pergi: menjawab masalah ini dengan cara yang cerdas mungkin akan membuat Anda bertanya-tanya tentang simetri yang mendasari grid sudoku. Banyak pekerjaan yang dilakukan dalam arah ini untuk membuktikan fakta bahwa 17 adalah jumlah minimal petunjuk untuk sudoku ( lihat artikel ini ) dan Anda dapat pergi ke sini untuk melihat penghitungan tepat ini dari 5.472.730.538 kelas dari 3.359.232 kisi yang serupa, yang menggunakan ini simetri:

  1. Permutasi digit
  2. Permutasi baris (band dan baris di dalam setiap band)
  3. Hal yang sama untuk kolom
  4. Transposisi

9!,64,64,2

EDIT: untuk mengadaptasi ini ke teka-teki yang tidak lengkap, Anda dapat memilih secara acak bagian dari kisi Anda, periksa apakah solusinya unik dengan pemecah sudoku dan coba lagi jika tidak. Ini bukan distribusi yang seragam karena jumlah puzzle yang tidak lengkap dengan solusi unik mungkin berbeda untuk dua kisi. (Saya akan sangat terkejut jika tidak)

jmad
sumber
Tetapi Justin meminta cara membuat puzzle yang tidak lengkap sehingga ada cara unik untuk menyelesaikannya. Bahkan jika Anda menghasilkan kisi 9x9 yang memenuhi batasan Sudoku, tidak jelas mengapa menghapus subset sel tertentu akan memberi Anda teka-teki yang dapat diselesaikan dengan cara yang unik.
Janoma
1
@ Janoma: oh, salahku, aku akan mengedit. Tapi itu tidak terlalu berarti jika seseorang tidak mendefinisikan apa itu puzzle yang tepat. (Apakah kotak dengan hanya satu sel kosong teka-teki?). Apakah kita menginginkan kisi minimal, (yaitu jika Anda menghapus angka, solusinya tidak unik lagi?) Itu pertanyaan yang menarik.
jmad
"Beberapa elemen dapat dihilangkan" cukup tepat (mis. "Satu atau lebih" elemen dapat dihapus). Misalnya, puzzle yang valid dengan satu sel kosong dapat diselesaikan dengan cara yang unik, sedangkan puzzle yang kosong tidak bisa, karena ada lebih dari satu puzzle yang valid. Selain itu, puzzle yang valid dan lengkap dapat diselesaikan dengan cara yang unik (sepele, kosong). Pertanyaan tentang grid minimal juga menarik, tetapi berbeda dari yang satu ini.
Janoma
@ Janoma, jmad: puzzle yang valid biasanya minimal, saya lupa menyebutkan itu.
Gilles 'SANGAT berhenti menjadi jahat'
@Gilles Apakah itu definisi? Saya bertanya-tanya apakah itu memang maksud dari OP. Itu membuat masalahnya jauh lebih sulit :-)
Janoma