Агуулгыг алгасах

15 тоглоом: Шийдийн оршин тогтнох

Энэ тоглоомыг $4 \times 4$ самбар дээр тоглоно. Энэ самбар дээр 1-ээс 15 хүртэл дугаарласан $15$ тоглоомын хавтан байна. Нэг нүд хоосон үлдэнэ (0-оор тэмдэглэсэн). Та хавтангуудын нэгийг чөлөөт зай руу дахин дахин зөөж самбарыг доор үзүүлсэн байрлалд оруулах хэрэгтэй:

$$\begin{matrix} 1 & 2 & 3 & 4 \\ 5 & 6 & 7 & 8 \\ 9 & 10 & 11 & 12 \\ 13 & 14 & 15 & 0 \end{matrix}$$

"15 тоглоом"-ыг 1880 онд Нойес Чапман зохион бүтээсэн.

Шийдийн оршин тогтнох

Дараах бодлогыг авч үзье: самбар дээрх байрлал өгөгдсөн үед шийдэлд хүргэх нүүдлийн дараалал оршин байгаа эсэхийг тодорхойл.

Самбар дээр ямар нэг байрлалтай байг:

$$\begin{matrix} a_1 & a_2 & a_3 & a_4 \\ a_5 & a_6 & a_7 & a_8 \\ a_9 & a_{10} & a_{11} & a_{12} \\ a_{13} & a_{14} & a_{15} & a_{16} \end{matrix}$$

энд элементүүдийн нэг нь тэгтэй тэнцүү бөгөөд хоосон нүдийг заана $a_z = 0$

Дараах сэлгэмэлийг авч үзье:

$$a_1 a_2 ... a_{z-1} a_{z+1} ... a_{15} a_{16}$$

өөрөөр хэлбэл тэг элементгүй самбар дээрх байрлалд харгалзах тоонуудын сэлгэмэл

Энэ сэлгэмэл дэх инверсийн тоог $N$ гэе (өөрөөр хэлбэл $i < j$ боловч $a_i > a_j$ байх $a_i$ ба $a_j$ элементүүдийн тоо).

Хоосон элемент байрлах мөрийн индексийг $K$ гэе (өөрөөр хэлбэл бидний тохироогоор $K = (z - 1) \div \ 4 + 1$).

Тэгвэл $N + K$ тэгш байвал, зөвхөн тэр үед л шийд оршин байна.

Implementation

The algorithm above can be illustrated with the following program code:

int a[16];
for (int i=0; i<16; ++i)
    cin >> a[i];

int inv = 0;
for (int i=0; i<16; ++i)
    if (a[i])
        for (int j=0; j<i; ++j)
            if (a[j] > a[i])
                ++inv;
for (int i=0; i<16; ++i)
    if (a[i] == 0)
        inv += 1 + i / 4;

puts ((inv & 1) ? "No Solution" : "Solution Exists");

Баталгаа

1879 онд Жонсон $N + K$ сондгой бол шийд оршин байхгүйг баталсан бөгөөд мөн онд Стори $N + K$ тэгш байх бүх байрлал шийдтэй болохыг баталсан.

Гэвч эдгээр бүх баталгаа нэлээд төвөгтэй байсан.

1999 онд Арчер хамаагүй энгийн баталгаа санал болгосон (түүний өгүүллийг эндээс татаж авч болно).

Дасгал бодлогууд