Di Math Stack Exchange, saya mengajukan pertanyaan tentang wilayah terkecil yang dapat berisi semua n-omino gratis .
Saya ingin menambahkan urutan ini ke dalam Ensiklopedia On-Line dari Urutan Integer begitu saya memiliki lebih banyak istilah.
Contoh
Wilayah sembilan sel adalah subset terkecil dari bidang yang dapat berisi semua dua belas omino 5 bebas , seperti diilustrasikan di bawah ini. (Polyomino gratis adalah salah satu yang dapat diputar dan dibalik.)
(Wilayah dua belas sel adalah subset terkecil dari bidang yang dapat berisi semua 35 omino 6 bebas ).
Tantangan
Hitung batas atas pada daerah terkecil dari bidang yang dapat berisi semua n-omino sebagai fungsi dari n.
Tabel seperti itu dimulai:
n | size
--+-------
1 | 1*
2 | 2*
3 | 4*
4 | 6*
5 | 9*
6 | 12*
7 | 37
8 | 50
9 | 65
*These values are the smallest possible.
Contoh pengiriman
1-omino: 1
#
2-omino: 2
##
3-omino: 4
###
#
4-omino: 6
####
##
5-omino: 9
#
#####
###
6-omino: 12
####
######
##
7-omino: <= 37
#######
######
######
######
######
######
Mencetak gol
Jalankan program Anda selama yang Anda inginkan, dan poskan daftar batas atas Anda bersama dengan bentuk yang mencapai masing-masing.
Pemenang akan menjadi peserta yang tabelnya secara leksikografis paling awal (dengan "tak terbatas" ditambahkan pada pengiriman yang lebih pendek.) Jika dua peserta mengirimkan hasil yang sama, maka pengiriman sebelumnya akan menang.
Misalnya, jika pengirimannya
Aliyah: [1,2,4,6,12,30,50]
Brian: [1,2,4,6,12,37,49,65]
Clare: [1,2,4,6,12,30]
lalu Aliyah menang. Dia mengalahkan Brian karena 30 <37, dan dia mengalahkan Clare karena 50 <tak terbatas.
sumber
Jawaban:
C # dan SAT: 1, 2, 4, 6, 9, 12, 17, 20, 26, 31, 37, 43
Jika kita membatasi kotak pembatas, ada ekspresi yang cukup jelas dari masalah dalam hal SAT : setiap terjemahan dari masing-masing orientasi setiap polyomino gratis adalah konjungsi yang besar; untuk setiap polyomino kami membentuk disjungsi atas konjungsi-koneksinya; dan kemudian kami meminta setiap disjungsi menjadi benar dan jumlah total sel yang digunakan terbatas.
Untuk membatasi jumlah sel, versi awal saya membuat penambah lengkap; kemudian saya menggunakan bitonic sort untuk penghitungan unary (mirip dengan jawaban ini sebelumnya tetapi digeneralisasi); akhirnya saya memutuskan pendekatan yang dijelaskan oleh Bailleux dan Boufkhad dalam pengkodean CNF efisien dari kardinalitas Boolean .
Saya ingin membuat posting mandiri, jadi saya menggali implementasi C # dari pemecah SAT dengan lisensi BSD yang canggih sekitar 15 tahun yang lalu, menggantikan implementasi daftar NIH dengan
System.Collections.Generic.List<T>
(mendapatkan faktor 2 dalam kecepatan), memutarnya dari 50kB menjadi 31kB agar sesuai dengan batas pos 64kB, dan kemudian melakukan beberapa pekerjaan agresif untuk mengurangi penggunaan memori. Kode ini jelas dapat diadaptasi untuk menghasilkan file DIMACS yang kemudian dapat diteruskan ke pemecah yang lebih modern.Solusi ditemukan
Untuk menemukan 43 untuk n = 12 butuh lebih dari 7,5 jam.
Kode polyomino
Kode pemecah SAT
Optimalitas
Solusi berbeda
Menghitung solusi untuk masalah SAT sangat mudah, jika kadang lambat: Anda menemukan solusi, tambahkan klausa baru yang secara langsung mengesampingkannya, dan jalankan kembali. Di sini mudah untuk menghasilkan kelas ekivalensi solusi di bawah simetri persegi panjang, sehingga kode berikut cukup untuk menghasilkan semua solusi yang berbeda.
sumber
Untuk memulai prosesnya, inilah jawaban cepat (tapi tidak terlalu optimal).
Pola:
Ambil segitiga dengan panjang n - 1, tempelkan bujur sangkar ekstra ke sudut, dan potong persegi bawah.
Bukti bahwa semua n-ominos cocok:
Perhatikan bahwa setiap n-omino dapat masuk ke dalam persegi panjang dengan panjang + lebar paling banyak n +1.
Jika n-omino cocok dalam sebuah persegi panjang dengan panjang + lebar paling banyak n, itu cocok di segitiga (yang merupakan gabungan dari semua persegi panjang seperti itu). Jika kebetulan menggunakan cut-off square, transposing itu akan masuk dalam segitiga.
Kalau tidak, kami memiliki rantai dengan paling banyak satu cabang. Kita selalu dapat memasukkan salah satu ujung rantai ke dalam kotak tambahan (buktikan ini dengan kasus kerja), dan sisanya cocok ke dalam persegi panjang dengan panjang + lebar paling banyak n, mengurangi kasus di atas.
Satu-satunya kasus di mana hal di atas tidak berfungsi adalah kasus di mana kami menggunakan kotak ekstra dan kotak cut-off. Hanya ada satu n-omino (L panjang), dan yang cocok di dalam segitiga berubah.
Kode (Python 2):
Meja:
sumber
C #, skor: 1, 2, 4, 6, 9, 12, 17, 20, 26, 31, 38, 44
Format output dari program ini sedikit lebih kompak.
Ini menggunakan pendekatan acak unggulan, dan saya telah mengoptimalkan benih. Saya menerapkan batasan kotak terikat yang masuk akal dan konsisten dengan data yang diketahui untuk nilai-nilai kecil n. Jika kendala itu memang valid maka
1, 1, 2, 2, 2, 6, 63, 6
.Demo online
sumber
Penempatan serakah dalam urutan acak
Wilayah yang ditemukan diberikan di bawah ini, serta program karat yang menghasilkannya. Sebut saja dengan parameter baris perintah sama dengan n yang ingin Anda cari. Saya sudah menjalankannya hingga n = 10 sejauh ini. Perhatikan bahwa ini belum dioptimalkan untuk kecepatan, saya akan melakukannya nanti dan mungkin mempercepat banyak hal.
Algoritma ini sangat mudah, saya mengocok poliomino dalam urutan acak (diunggulkan), kemudian menempatkannya satu per satu pada posisi dengan tumpang tindih maksimum yang mungkin dengan wilayah sejauh ini. Saya melakukan ini 100 kali dan menampilkan daerah dengan hasil terbaik
Daerah
Program
Catatan: diperlukan setiap malam, tapi ganti benih untuk menyingkirkannya, jika Anda peduli.
sumber