Pemenang ditemukan
Sepertinya kita memiliki pemenang! Kecuali ada yang berencana untuk bertarung dengan pemecah Sudoku tercepat di dunia saat ini, pengguna 53x15 menang dengan Tdoku pemecah yang sangat cepat. Bagi siapa pun yang masih mengerjakan solver mereka, saya masih akan melakukan benchmark pengiriman baru ketika saya punya waktu.
Tantangan
Tujuan permainan Sudoku adalah untuk mengisi papan dengan angka 1-9, satu di setiap sel, sedemikian rupa sehingga setiap baris, kolom dan kotak hanya berisi masing-masing angka satu kali. Aspek yang sangat penting dari sebuah teka-teki Sudoku adalah bahwa seharusnya hanya ada satu solusi yang valid.
Tujuan dari tantangan ini sederhana, Anda harus menyelesaikan serangkaian teka-teki Sudoku secepat mungkin. Namun, Anda tidak hanya akan menyelesaikan Sudoku lama, Anda akan memecahkan teka-teki Sudoku paling sulit yang ada, Sudokus 17-petunjuk. Ini sebuah contoh:
Aturan
Bahasa
Anda bebas menggunakan bahasa apa pun. Jika saya tidak memiliki kompiler yang diinstal untuk bahasa Anda , Anda harus dapat memberikan satu set instruksi baris perintah yang diperlukan untuk menginstal lingkungan di mana skrip Anda dapat dijalankan di Linux .
Mesin benchmark
Benchmark akan dijalankan pada Dell XPS 9560, 2.8GHz Intel Core i7-7700HQ (peningkatan 3,8GHz) 4 core, 8 thread, 16GB RAM. GTX 1050 4GB. Mesin menjalankan Ubuntu 19.04. Inilah uname
hasilnya, untuk siapa saja yang tertarik.
Linux 5.0.0-25-generic #26-Ubuntu SMP Thu Aug 1 12:04:58 UTC 2019 x86_64 x86_64 x86_64 GNU/Linux
Memasukkan
Input akan diberikan sebagai file. Itu dapat ditemukan di sini . File ini berisi 49151 teka-teki Sudoku. Baris pertama file adalah jumlah puzzle, dan setiap baris setelahnya adalah 81 karakter dan mewakili puzzle. Sel yang tidak diketahui adalah 0
, dan sel yang diketahui adalah 1-9
.
Program Anda harus dapat menggunakan nama file sebagai argumen, atau meminta input file dari STDIN , untuk memfasilitasi pengecekan manual atas solusi Anda. Harap sertakan instruksi bagaimana program Anda mengambil input.
Pengaturan waktu / penilaian
Dari diskusi di komentar, dan beberapa refleksi, kriteria penilaian telah diubah menjadi waktu seluruh program Anda. Program Anda harus menghasilkan file output dengan hash yang benar bahkan selama penilaian resmi. Ini tidak mengganggu solusi apa pun yang ada, dan tidak mengubah peringkat saat ini. Setiap pemikiran tentang sistem penilaian dihargai.
Jika dua solusi memiliki skor yang sama untuk menjalankan individual, saya akan menjalankan beberapa tolok ukur, dan waktu rata-rata akan menjadi skor akhir. Jika skor rata-rata berbeda kurang dari 2%, saya akan menganggap itu seri.
Jika solusi Anda membutuhkan waktu lebih dari satu jam untuk berjalan, itu tidak akan diberi skor secara resmi. Dalam kasus tersebut, Anda bertanggung jawab untuk melaporkan mesin yang menjalankannya, dan skor Anda. Untuk pemecah yang dioptimalkan, ini seharusnya tidak menjadi masalah.
EDIT : Saya mendapat perhatian bahwa meskipun sulit, masalah yang ada bukanlah yang paling sulit. Jika waktu tersedia, saya akan mencoba membandingkan solusi yang disajikan di sini dengan set puzzle yang lebih sulit, dan menambahkan skor untuk setiap pengiriman. Namun, ini tidak akan menjadi penilaian resmi, dan hanya untuk bersenang-senang.
Verifikasi
Solusi Anda akan diverifikasi oleh checksum MD5 / SHA256. Skrip Anda harus dapat menghasilkan file yang berisi semua teka-teki dan solusinya. Namun, file juga akan diperiksa secara manual, jadi jangan mencoba untuk mendapatkan tabrakan hash. File output Anda harus sesuai:
MD5: 41704fd7d8fd0723a45ffbb2dbbfa488
SHA256:0bc8dda364db7b99f389b42383e37b411d9fa022204d124cb3c8959eba252f05
File akan berada dalam format:
<num_puzzles>
<unsolved_puzzle#1>,<solved_puzzle#1>
<unsolved_puzzle#2>,<solved_puzzle#2>
...
<unsolved_puzzle#n>,<solved_puzzle#n>
dengan single trailing newline.
Apa yang tidak diizinkan?
Anda sama sekali tidak diizinkan untuk solusi hard-code . Algoritme Anda harus dapat diterapkan pada serangkaian teka-teki Sudoku apa pun, baik Sudokus yang mudah maupun yang lebih sulit. Namun, itu sepenuhnya baik-baik saja jika solusi Anda lambat untuk teka-teki yang lebih mudah.
Anda tidak diizinkan memiliki program non-deterministik . Anda diizinkan untuk menggunakan generator nomor acak, tetapi benih generator harus diperbaiki. Aturan ini adalah untuk memastikan bahwa pengukuran lebih tepat, dan memiliki varian yang lebih sedikit. (Terima kasih kepada Peter Taylor untuk tipnya)
Anda tidak diperbolehkan menggunakan sumber daya eksternal atau permintaan web apa pun selama runtime program Anda. Semuanya harus mandiri. Ini tidak berlaku untuk pustaka dan paket yang diinstal, yang diizinkan.
Info lain
Jika Anda ingin set tes lain untuk memeriksa solusi Anda, berikut adalah 10.000 Sudokus yang lebih mudah . Inilah solusinya .
MD5: 3cb465ef6077c4fcab5bd6ae3bc50d62
SHA256:0bc8dda364db7b99f389b42383e37b411d9fa022204d124cb3c8959eba252f05
Jika Anda memiliki pertanyaan, jangan ragu untuk bertanya, dan saya akan mencoba untuk menjelaskan kesalahpahaman.
Jawaban:
C ++ - skor resmi 0.201s
Menggunakan Tdoku ( kode ; desain ; tolok ukur ) memberikan hasil ini:
Tdoku telah dioptimalkan untuk contoh keras Sudoku. Tetapi perhatikan, berlawanan dengan pernyataan masalah, bahwa 17 teka-teki petunjuk jauh dari Sudoku yang paling sulit. Sebenarnya mereka termasuk yang termudah, dengan mayoritas tidak memerlukan backtracking sama sekali. Lihat beberapa dataset benchmark lain di proyek Tdoku untuk puzzle yang sebenarnya sulit.
Juga perhatikan bahwa meskipun Tdoku adalah pemecah tercepat yang saya ketahui untuk puzzle keras, itu bukan yang tercepat untuk 17 puzzle petunjuk. Untuk ini saya pikir yang tercepat adalah proyek karat ini , turunan dari JCZSolve, yang dioptimalkan untuk 17 teka-teki petunjuk selama pengembangan. Tergantung pada platformnya mungkin 5-25% lebih cepat dari Tdoku untuk teka-teki ini.
sumber
Node.js ,
8.231s6.735s skor resmiMengambil nama file sebagai argumen. File input mungkin sudah berisi solusi dalam format yang dijelaskan dalam tantangan, dalam hal mana program akan membandingkannya dengan solusi sendiri.
Hasilnya disimpan dalam 'sudoku.log' .
Kode
Contoh output
Diuji pada Intel Core i7 7500U @ 2.70 GHz.
sumber
Python 3 (dengan dlx ) 4 menit 46,870 skor resmi
(single core i7-3610QM di sini)
Jelas bisa dikalahkan dengan bahasa yang dikompilasi seperti C, dan memanfaatkan threading, tapi ini awal ...
sudoku
adalah modul yang saya letakkan di github (disalin di bagiandlx
bawah tulisan ini) yang menggunakan di bawah tenda.Pemakaian
sudoku.py
suatu tempat di jalur Anda (dari tautan hub git atau salin dari bawah)testSolver.py
suatu tempat di jalur AndaMemotong output seperti yang diperlukan dalam spec tantangan ke file jika perlu:
sudoku.py (ya ada fitur tambahan di sini selain untuk menyelesaikan)
sumber
Python 3 + Z3 - 10 menit skor resmi 45.657
sekitar 1000-an di laptop saya.
Instal ketergantungan
Lari
Saya tidak yakin bagaimana meningkatkan kinerjanya, karena itu baru saja dipecahkan secara ajaib ...
sumber
C -
2.228s1.690s skor resmiberdasarkan @ Arnauld
kompilasi dan jalankan:
sumber
C - 12mnt 28.374s skor resmi
berjalan sekitar
30m15m pada i5-7200U saya dan menghasilkan hash md5 yang benarkompilasi (sebaiknya dengan dentang v6) dan jalankan:
sumber
memcpy
di sana dan beberapa rekursi terjadi. Saya akan mencoba memverifikasi hari ini.Java - 4.056 skor resmi
Gagasan utama ini adalah untuk tidak pernah mengalokasikan memori ketika tidak diperlukan. Satu-satunya pengecualian adalah primitif, yang harus dioptimalkan oleh kompiler. Segala sesuatu yang lain disimpan sebagai masker dan array operasi yang dilakukan di setiap langkah, yang dapat dibatalkan ketika langkah rekursi selesai.
Sekitar setengah dari semua sudokus diselesaikan sepenuhnya tanpa mundur, tetapi jika saya mendorong angka itu lebih tinggi secara keseluruhan waktu tampaknya lebih lambat. Saya berencana om menulis ulang ini dalam C ++ dan mengoptimalkan lebih jauh, tetapi pemecah ini menjadi raksasa.
Saya ingin menerapkan cache sebanyak mungkin, yang mengarah pada beberapa masalah. Misalnya, jika ada dua sel pada baris yang sama yang hanya dapat memiliki nomor 6, maka kami telah mencapai kasus yang tidak mungkin, dan harus kembali ke pengulangan. Tetapi karena saya menghitung semua opsi dalam satu sapuan, dan kemudian menempatkan angka dalam sel dengan hanya satu kemungkinan, saya tidak mengecek apakah saya telah meletakkan angka di baris yang sama sebelumnya. Ini mengarah pada solusi yang mustahil.
Dengan segala sesuatu yang terkandung dalam array yang ditentukan di atas, penggunaan memori pemecah yang sebenarnya adalah sekitar 216 kB. Bagian utama dari penggunaan memori berasal dari array yang berisi semua teka-teki, dan penangan I / O di Jawa.
EDIT : Saya memiliki versi yang diterjemahkan ke C ++ sekarang, tetapi tidak jauh lebih cepat. Waktu resmi sekitar 3,5 detik, yang bukan peningkatan besar. Saya pikir masalah utama dengan implementasi saya adalah bahwa saya menjaga topeng saya sebagai array daripada bitmask. Saya akan mencoba menganalisis solusi Arnauld untuk melihat apa yang bisa dilakukan untuk memperbaikinya.
sumber
C ++ dengan Minisat (2.2.1-5) - skor resmi 11.735s
Ini sama sekali tidak secepat algoritma khusus, tetapi pendekatan yang berbeda, titik referensi yang menarik, dan mudah dimengerti.
$ clang ++ -o selesaikan -lminisat solver_minisat.cc
sumber