Seberapa keras varian dari teka-teki Sudoku?

Sudoku adalah puzzle terkenal yang dikenal sebagai NP-complete dan ini adalah kasus khusus masalah yang lebih umum yang dikenal sebagai kotak Latin. Solusi yang benar dari$N \times N$ kuadrat terdiri dari mengisi setiap baris dan setiap kolom dengan angka dari $1$ untuk $N$ dengan ketentuan bahwa setiap angka muncul tepat sekali di baris atau kolom apa pun.

Saya mendefinisikan masalah baru. Masukan adalah solusi yang benar dari$N \times N$Teka-teki Sudoku (lebih umum masalah persegi Latin). Saya ingin memutuskan apakah ada permutasi baris dan permutasi kolom sehingga tidak ada baris dan tidak ada kolom yang mengandung tiga kali lipat berturut-turut.

Contoh untuk baris tanpa triple berturut-turut adalah 9 5 6 2 3 8 4 7 1. Contoh untuk baris dengan triple berturut-turut adalah 8 9 5 2 3 4 7 6 1. Triple adalah 2 3 4.

Saya menduga masalahnya NP-hard tetapi saya tidak dapat menemukan pengurangan.

Seberapa sulitkah memecahkan varian teka-teki Sudoku ini? Apakah ini NP-lengkap?

EDIT : Untuk memperjelas, permutasi yang sama harus diterapkan ke kolom dan baris.

Ketika permutasi baris dan kolom berbeda dan tiga kali lipat berturut-turut harus meningkat: Jawabannya selalu YA.

Misalkan matriks memiliki ukuran $N\times N$. Pertimbangkan permutasi acak kolom. Setiap baris (dengan sendirinya) adalah permutasi acak. Probabilitas bahwa jumlahnya$i,i+1,i+2$ muncul di posisi $t,t+1,t+2$ adalah $1/(N(N-1)(N-2))$. Ada$N-2$ pilihan untuk $t$ dan $i$, dan $N$baris yang berbeda. Oleh karena itu jumlah yang diharapkan dari tiga kali lipat berturut-turut adalah$N(N-2)^2/(N(N-1)(N-2)) < 1$. Kami menyimpulkan bahwa ada beberapa permutasi kolom, di mana tidak ada tiga kali lipat berturut-turut di salah satu baris. Sekarang ulangi argumen yang sama untuk kolom - perhatikan bahwa permutasi baris tidak dapat membuat triple berturut-turut di dalamnya.

Ketika permutasi baris dan kolom sama, dan tiga kali lipat berturut-turut dapat meningkat atau menurun: Jawabannya masih YA, cukup besar $N$.

Idenya adalah untuk menggunakan versi miring dari lemma lokal Lovász , melalui makalah Lu dan Székely Menggunakan lemma lokal Lovász dalam ruang injeksi acak . Dalam bukti sebelumnya, kami mempertimbangkan acara$X_{\ell,i,t,\sigma}$ untuk $\sigma \in \{\pm 1\}$, yang untuk satu baris $\ell$ (baik baris atau kolom), sebutkan itu $\ell(i+\sigma\delta)=t+\delta$ untuk $\delta \in \{0,1,2\}$. Ini adalah contoh dari peristiwa kanonik yang dipertimbangkan oleh Lu dan Székely: jika permutasi acak (permutasi pada baris dan kolom) adalah$\pi$, maka mereka berbentuk $\pi(t)=j_0,\pi(t+1)=j_1,\pi(t+2)=j_2$dimana $j_\delta = \ell^{-1}(i+\sigma\delta)$. Dua acara$X_{\ell,i,t,\sigma},X_{\ell',i',t',\sigma'}$ konflik jika$\{t,t+1,t+2\} \cap \{t',t'+1,t'+2\} \neq \emptyset$ atau $\{j_0,j_1,j_2\} \cap \{j'_0,j'_1,j'_2\} \neq \emptyset$(Ini sebenarnya hanya kondisi yang diperlukan). Setiap acara paling banyak bertentangan$2N\cdot 2\cdot 2\cdot 5 - 1= 40N-1$ acara lainnya ($2N$garis, dua orientasi, dua cara untuk konflik, lima posisi yang saling bertentangan). Sementara acara yang tidak bertentangan pada umumnya tergantung, menggunakan versi miring dari lemma lokal Lovász kita dapat mengabaikan ini, dan biarkan grafik ketergantungan kita menyertakan tepi hanya untuk peristiwa yang bertentangan. Karena probabilitas bahwa setiap peristiwa terjadi adalah$p = 1/(N(N-1)(N-2))$ dan ukuran masing-masing lingkungan $d \leq 40N-1$, lemma berlaku kapan saja $ep(d+1) \leq 1$, itu adalah

$$40eN \leq N(N-1)(N-2).$$ Kondisi ini dipenuhi $N \geq 12$. Kami menyimpulkan itu untuk$N \geq 12$, permutasi yang diperlukan selalu ada. Menggunakan versi konstruktif LLL baru-baru ini, kita bahkan dapat menemukannya secara efisien.