Bài toán Nonogram

Bài viết được đăng lại từ đây: https://hackmd.io/@alexisparis/itknowledge2

Đặt vấn đề

Bài viết này dự kiến sẽ được hoàn thành vào dịp cận Halloween (hoặc là run rủi sẽ rơi vào đúng hôm Halloween, không chắc nữa), vậy nên trước hết tôi xin dành một lời chúc đến các bạn đọc một mùa Halloween vui vẻ (đặc biệt là các bạn trẻ đang trải nghiệm trực tiếp cảm giác cầm lồng đèn Jack O'Lantern và đi gõ cửa các nhà tại các nước Âu Mỹ, hoặc là những người được gõ cửa và chào đón bằng câu "Trick or Treat"/"Un bonbon ou Un sort").

Nếu các bạn còn nhớ về chuỗi những quảng cáo trò chơi rác đã từng gặp qua, đỉnh điểm là vào năm 2023 (chính xác là tôi gặp nó rất thường xuyên và ở IP trong nước Pháp), các bạn sẽ hình dung được cách tôi tạo ra bức hình bên trên. Với các hàng và cột gắn liền với một dãy số định sẵn, chúng ta sẽ tô đen các ô trong một bức khung trắng, sao cho số lượng và bố cục của ô đen ở mỗi hàng và cột thỏa mãn các dãy số gắn liền với chúng (và phải đảm bảo rằng nó đã được chuẩn bị một cách logic nhất).

Loại puzzle trên có rất nhiều tên gọi, từ Picross, Logigraphe, Hanjie, Griddler, Nonogram, Logimage, hay gắn với đồ án năm 3 (năm cuối) Đại học của tôi với cách gọi Tomographie discrète. Theo những gì tôi lượm vu vơ trên Wikipedia tiếng Anh, nó có liên quan đến giải thưởng của biên tập viên đồ họa người Nhật Bản Non Ishida về việc tạo ra một bức tranh lưới từ các hệ thống ánh sáng tòa nhà chọc trời, và trực tiếp khai sinh bởi nhà thiết kế puzzle đồng hương Tetsuya Nishio trong cùng khoảng thời gian. Đồ án của tôi, cũng như của sinh viên năm 3 Cử nhân tại Đại học Sorbonne niên khóa 2023-2024, chính là tạo ra một thuật toán giải quyết các puzzle như thế trên cơ sở một file .txt cung cấp sẵn các dãy số tương ứng với hàng và cột.

Ở đây tôi sẽ gọi nó là Nonogram - một cách gọi quen mồm từ những ngày đầu mày mò thực hiện bài lập trình, bắt nguồn từ tên ứng dụng game tôi đã tải về để chơi liên tục trong một tuần đầu. Trong bài này, tôi sẽ xen kẽ hai phương pháp giải vấn đề: Phương pháp tối ưu (Optimal method) và Phương pháp gắn với bản năng người chơi (Instinct-based method).

Tiếp cận bài toán

Giải quyết một chuỗi ô

Đối với một chuỗi ô, có thể là một hàng hoặc một cột của khung trò chơi, vấn đề đặt ra cho mỗi ô là nên chọn tô màu đen hay màu trắng. Việc này được thực hiện lên trên hai trường hợp khái quát: một chuỗi ô trống không và một chuỗi ô đã được tô màu một ít.

Chúng ta mô hình hóa vấn đề trên bằng giải thuật đệ quy nhị nguyên dưới đây:

Ta gọi $L\in\{0,1,2\}^m$ là chuỗi $m$ ô tô màu theo dãy số tương ứng $s$, với:

• $0$ tương ứng với ô chưa được tô.
• $1$ tương ứng với ô được tô trắng.
• $2$ tương ứng với ô được tô đen.

Gọi $l\in\Bbb N$ là chỉ mục định vị dãy số $s=(s_l)_{l=1}$.

Gọi $j\in\Bbb N$ là chỉ mục định vị chuỗi ô $L=(L_j)_{j=0}$.

Hàm $T(L,s,j,l)$ sẽ trả ra giá trị đúng ($\top$) và sai ($\bot$) dựa trên chuỗi.

Chúng ta sẽ bắt đầu giải thuật với giá trị lớn nhất của các chỉ mục: $T(L,s,|L|-1,|s|)$

1. Bước cơ sở:

   1. $l=0$: Khi mọi giá trị trong dãy số đã được tuân thủ. Chúng ta liệt kê hai trường hợp dưới đây:

      • $j=0$: Không còn ô nào phía trước ô hiện tại $L_j$:

      $$T(L,s,0,0)=\top$$

      • $j>0$: Còn một cơ số ô ở phía trước ô hiện tại $L_j$:
        • Nếu tồn tại bất kì ô $L_i$ ($i<j$) đã được tô đen, vậy có nghĩa là các ô trong chuỗi $L$ đã bị tô không hợp lệ:

        $$T(L,s,j,0)=\bot$$

        • Nếu không, chuỗi ô được mặc nhiên tô đúng:

        $$T(L,s,j,0)=\top$$

   2. $j<s_l-1$: Số ô của chuỗi còn lại được xem xét nhỏ hơn với giá trị ở thứ tự $l$ trong dãy số. Không nghi ngờ gì, chuỗi được tô không hợp lệ:

   $$T(L,s,j,l)=\bot$$

   3. $j=s_l-1$: Số ô của chuỗi còn lại được xem xét bằng đúng với giá trị ở thứ tự $l$ trong dãy số Chúng ta liệt kê hai trường hợp dưới đây:
      • $l=1$: Giá trị được so sánh của dãy số là giá trị ở hàng đầu Chúng ta sẽ xem xét trong $j+1$ ô còn lại như sau:
        • Nếu trong số đó có ô đã được tô trắng, vậy nghĩa là chuỗi đang không được tô hợp lệ:

        $$T(L,s,j,1)=\bot$$

        • Nếu không, chuỗi ô vẫn được xác định là tô hợp lệ:

        $$T(L,s,j,1)=\top$$

      • $l>1$: Giá trị được so sánh của dãy số không phải là giá trị ở hàng đầu Không nghi ngờ gì, chuỗi đã bị tô không hợp lệ:

      $$T(L,s,j,l)=\bot$$

2. Bước đệ quy

   1. Nếu ô $j$ đã được tô trắng, công việc tiếp theo của ta là đệ quy để kiểm tra các ô phía trước với cùng giá trị trong dãy số:

   $$T(L,s,j,l)=T(L,s,j-1,l)$$

   2. Nếu ô $j$ đã được tô đen, chúng ta xem xét chuỗi $s_l+1$ ô phía trước, trên giả định ô $L_j$ là ô phía cùng bên phải trong chuỗi ô đen. Để diễn giải cho dễ hiểu, ta xem xét nhóm ô từ $L_{j-s_l}$ đến $L_{j-1}$.

      • Nếu ô $L_{j-s_l}$ đã được tô đen, điều này có nghĩa là trong mọi trường hợp, ô $L_j$ không thể được tô đen vì sẽ không thể tạo ra chuỗi thỏa mãn giá trị $s_l$:

      $$T(L,s,j,l)=\bot$$

      • Trong chuỗi ô từ $L_{j-s_l+1}$ đến $L_{j-1}$, điều này có nghĩa là không thể tô đen các ô kế tiếp để thỏa mãn việc ô $L_j$ là ô cuối chuỗi:

      $$T(L,s,j,l)=\bot$$

      • Nếu không phạm phải bất kỳ quy tắc nào phía trên, chúng ta sẽ đệ quy kiểm tra tiếp các ô trước đó cùng với giá trị phía trước trong dãy số:

      $$T(L,s,j,l)=T(L,s,j-s_l-1,l-1)$$

   3. Nếu ô chưa được tô, ta có hai hàm $T_1(j,l)$ và $T_2(j,l)$ tương ứng với hai trường hợp 1 và 2 của bước đệ quy:

   $$T(L,s,j,l)=T_1(L,s,j,l)\lor T_2(L,s,j,l)$$

Tóm lại, giá trị của $T(L,s,j,l)$ theo $j$ và $l$ tương ứng:

$$T(L,s,j,l)=\begin{cases}\top,&j=0\land l=0\\\lnot\exists i(i<j\land L_i=2),&j>0\land l=0\\\bot,&j>0\land l>0\land j<s_l-1\\\lnot\exists i(i<j\land L_i=1),&j>0\land l=1\land j=s_l-1\\\bot,&j>0\land l>1\land j=s_l-1\\T(L,s,j-1,l),&j>0\land l>1\land L_j=1\\\begin{cases}T(L,s,j-s_l-1,l-1)\\L_{j-s_l}\neq2\\\lnot\exists i(j-s_l<i<j\land L_i=1)\end{cases},&j>0\land l>1\land L_j=2\end{cases}$$

Độ khó của chuỗi ô

Hàm $T(L,s,j,l)$ nêu trên có tác dụng xác định việc tô màu chuỗi ô có hợp lệ hay không. Tuy nhiên, một chuỗi ô có thể có nhiều cách tô khác nhau cùng thỏa mãn một dãy số.

Ta hãy xem xét các ví dụ dưới đây về việc tô màu theo các dãy số $s$ lên trên một chuỗi gồm 11 ô vuông $L=$ ⬜⬜⬜⬜⬜⬜⬜⬜⬜⬜⬜.

Ví dụ 1: $s=(8)$

Chúng ta có các cách tô như sau:

• Cách 1:
• Cách 2:
• Cách 3:
• Cách 4:

Ví dụ 2: $s=(3,5)$

Chúng ta có các cách tô như sau:

• Cách 1:
• Cách 2:
• Cách 3:
• Cách 4:
• Cách 5:
• Cách 6:

Ví dụ 3: $s=(2,3,2)$

Chúng ta có các cách tô như sau:

• Cách 1:
• Cách 2:
• Cách 3:
• Cách 4:
• Cách 5:
• Cách 6:
• Cách 7:
• Cách 8:
• Cách 9:
• Cách 9:

Ví dụ 4: $s=(3)$

Chúng ta có các cách tô như sau:

• Cách 1:
• Cách 2:
• Cách 3:
• Cách 4:
• Cách 5:
• Cách 6:
• Cách 7:
• Cách 8:
• Cách 9:

Ví dụ 5: $s=(3, 2)$

Chúng ta có các cách tô như sau:

• Cách 1:
• Cách 2:
• Cách 3:
• Cách 4:
• Cách 5:
• Cách 6:
• Cách 7:
• Cách 8:
• Cách 9:
• Cách 10:
• Cách 11:
• Cách 12:
• Cách 13:
• Cách 14:
• Cách 15:
• Cách 16:
• Cách 17:
• Cách 18:
• Cách 19:
• Cách 20:
• Cách 21:

Ví dụ 6: Một số trường hợp cụ thể chỉ có một cách tô

1. $s=()$:

2. $s=(11)$:

3. $s=(3,7)$:

4. $s=(2,4,3)$:

5. $s=(1,1,1,1,1,1)$:

Thông qua các ví dụ trên, chúng ta có thể đưa ra các kết luận như sau: Độ khó của chuỗi ô phụ thuộc vào tổng các giá trị trong dãy số và độ dài của dãy.

Trong trường hợp dãy số trống ($s=()$) hoặc dãy số một giá trị duy nhất ($s=(s_1)$) tương ứng với độ dài của chuỗi ($s_1=|L|$), ta chỉ có duy nhất một cách tô chuỗi.

Nếu độ dài và các giá trị của dãy đảm bảo được đầu và cuối chuỗi được tô đen và giữa các chuỗi con chỉ cần một ô tô trắng để phân cách, thì chuỗi cũng chỉ có duy nhất một cách tô.

Đối với dãy số chỉ có một giá trị, số cách tô phụ thuộc vào độ lớn của giá trị ấy. Khi độ lớn của giá trị càng nhỏ, số cách tô màu chuỗi càng tăng.

Đối với dãy số có từ hai giá trị trở lên, ta đặt $\gamma=\sum_{s_j\in s}s_j+|s|-1$.

Số ô trắng tối thiểu để ngăn cách các chuỗi con được tô đen là $|s|-1$.

Giá trị của $\gamma$ càng nhỏ thì số cách tô màu chuỗi càng tăng.

Bổ đề: Bài toán chia kẹo Euler (Stars and Bars counting method)

Cho phương trình $\sum_{i=1}^kx_i=n$ với tập nghiệm $S\subset\left\{x:=(x_i)_{i=1}^k\vert x\in\Bbb N^k\right\}$

Tập nghiệm $S$ có độ lớn là $C_{n+k-1}^{k-1}=\frac{(n+k-1)!}{(k-1)!n!}$

Chứng minh

Gọi $f(n,k)$ số nghiệm của phương trình $\sum_{i=1}^kx_i=n$. Mệnh đề $\Pi(n,k)$ đúng nếu $f(n,k)=C_{n+k-1}^{k-1}$.

1. Bước cơ sở: Nếu $n=1$ và $k=1$, tổng số nghiệm của phương trình $x_1=0$ là $f(1,1)=1=C_1^0=C_{1+1-1}^{1-1}$. Mệnh đề $\Pi(1,1)$ đúng.

2. Bước quy nạp: Giả sử $x_k=t\in\{i\}_{i=1}^n$, bằng quy tắc chuyển vế chúng ta có: $\sum_{i=1}^{k-1}x_i=n-t$. Số nghiệm lúc này là $f(n-t,k-1)$. Vậy $f(n,k)=\sum_{t=0}^nf(n-t,k-1)$. Giả sử mệnh đề $\Pi(n-t,k-1)$ đúng, ta có: $f(n-t,k-1)=C_{n-t+k-2}^{k-2}$. Ta vì vậy có:

$$\begin{array}{l}f(n,k)&=\sum_{t=0}^nf(n-t,k-1)\\&=\sum_{t=0}^nC_{n-t+k-2}^{k-2}\\&=\sum_{t=0}^n\frac{(n-t+k-2)!}{(k-2)!(n-t)!}\\&=\frac{(n+k-1)!}{(k-1)!n!}\\&=C_{n+k-1}^{k-1}\end{array}$$

Bằng cách chứng minh quy nạp, ta kết luận mệnh đề $\Pi(n,k)$ thỏa mãn với mọi giá trị của $n$ và $k$.

Định luật

Áp dụng bổ đề

Khi một chuỗi ô được tô màu theo dãy số, giả sử tồn tại trên chuỗi các "khe" được ngăn cách bởi các chuỗi con được tô đen, bao gồm 2 khe ở hai đầu chuỗi, và các khe ở giữa. Mỗi khe nằm ở giữa đều mặc định chứa một ô trắng ban đầu, các khe ngoài cùng được mặc định trống rỗng.

Bài toán được đặt ra: Làm sao xếp các ô trắng còn lại vào các khe.

Gọi $k$ là số khe, ta có $k=|s|$.

Gọi $n$ là tổng số ô trắng "tự do", ta có $n=|L|-\gamma$ với $\gamma$ đã được nêu phía trên.

Gọi $x_i$ là số ô trắng nằm trong các khe, ta có phương trình $\sum_{i=1}^kx_i=n$.

Như vậy ta có định luật:

Đặt $n=|L|-\gamma=|L|-(\sum_{s_j\in s}s_j+|s|-1)$.

Đặt $k=|s|+1$.

Số cách tô màu chuỗi $L$ thỏa mãn dãy số là $C_{n+k-1}^{k-1}$

Hệ quả

Quan sát ví dụ 1, ta thấy năm ô từ $L_3$ đến $L_7$ đều được tô đen trong tất cả các cách tô.

Quan sát ví dụ 2, ta thấy bốn ô $L_2$ và $L_6$ đến $L_8$ đều được tô đen trong tất cả các cách tô.

Quan sát ví dụ 3, ta thấy duy nhất ô $L_5$ được tô đen trong tất cả các cách tô.

Quan sát ví dụ 4 và 5, không có ô nào được tô cố định màu qua các cách.

Ta lý giải vấn đề này như sau: Một ô được tô màu đen cố định khi không thể tô màu trắng trong bất kỳ cách tô nào.

Với mỗi chuỗi con tô theo dãy số, sự chênh lệch trong việc tô phụ thuộc vào số ô trắng "tự do". Nói cách khác, quay trở lại phần bổ đề trên, sự chênh lệch nằm ở việc tồn tại một khe có nhiều ô trắng "tự do" nhất được bỏ vào, trong khi các khe khác không có

Như vậy, tổng số ô được tô đen cố định là $\max(0,\sum_{s_j\in s}s_j-n.|s|)$, từ đó một chuỗi con sẽ có các ô tô đen cố định khi và chỉ khi $s_j>n$.

Một chuỗi ô có độ khó thấp nhất là chuỗi ô không có ô trắng "tự do", vì thế ta có hệ quả:

Chuỗi ô chỉ có 1 cách tô duy nhất để thỏa mãn dãy số $L$ khi và chỉ khi $\gamma=|L|$.

Xác định chỉ mục các ô tô đen cố định.

Để xác định vùng tô cố định của một chuỗi con trên chuỗi ô, ta có công thức:

$$j_l^*\in[\delta_l+n,\delta_l+s_l]$$

Với $\delta_l=\sum_{0<i<l}(s_i+i)$ là số ô tối thiểu được tô từ trái sang cho đến khi tô chuỗi $s_l$.

Các thuật ngữ

Quy hoạch động

Quy hoạch động (Dynamic programming) được định nghĩa là chia vấn đề thành các vấn đề nhỏ, sao cho giữa các vấn đề nhỏ không có sự độc lập với nhau. Để thực thi mô típ này, một cấu trúc dữ liệu được sử dụng để lưu trữ các kết quả của vấn đề nhỏ, sao cho chúng được tái sử dụng ở các vấn đề nhỏ khác và cả những vấn đề lớn hơn.

Thông thường, các trang web tôi đọc qua đều sử dụng Fibonacci làm ví dụ cho việc áp dụng phương pháp trên:

$$F_k=\begin{cases}0,&k=0\\1,&k=1\\F_{k-1}+F_{k-2},&k>1\end{cases}$$

Bằng phương pháp đệ quy truyền thống, ta có:

Hàm $\text{Fibonacci}(k)$ như sau:

• Nếu $k=0$ thì:
  • Trả ra $0$.
• Còn nếu $k=1$ thì:
  • Trả ra $1$.
• Kết thúc điều kiện
• Trả ra $\text{Fibonacci}(k-1)+\text{Fibonacci}(k-2)$

Kết thúc hàm

Sự đệ quy của hàm tạo ra một cây nhị phân với số nút đệ quy là $O(2^k)$.

Ở mỗi nút, phần phi đệ quy không có vòng lặp, nên độ phức tạp cục bộ là $O(1)$.

Vậy độ phức tạp chung của hàm là $O(2^k)$.

Ta có hai cách tiếp cận quy hoạch động sau đây

1. Phương pháp top-down memoization (giải quyết từ trên xuống dưới và ghi nhớ thông qua phép đệ quy):

Gọi $\text{memory}\gets(m_i)_{i=0}^{k}$ với giá trị khởi tạo của $m_0$ là $0$, $m_1$ là $1$ và các giá trị khác được khởi tạo là $-1$. Hàm $\text{Fibonacci}(k)$ như sau:

• Nếu $k\leq1$ thì:
  • Trả ra $m_k$.
• Nếu không:
  • Nếu $m_k=-1$ thì:
    • $m_k\gets\text{Fibonacci}(k-1)+\text{Fibonacci}(k-2)$.
  • Kết thúc điều kiện
• Kết thúc điều kiện
• Trả ra $m_k$.

Kết thúc hàm

2. Phương pháp bottom-up tabulation (giải quyết từ dưới lên trên để làm cơ sở thông qua phép lặp):

Gọi $\text{memory}\gets(m_i)_{i=0}^{k}$ với giá trị khởi tạo của giá trị $m_i$ là $-1$. Hàm $\text{Fibonacci}(k)$ như sau:

• Với mọi $i\in\{j\}_{j=0}^k$ tiến hành:
  • Nếu $i=0$ thì:
    • $m_i\gets0$.
  • Còn nếu $i=1$ thì:
    • $m_i\gets1$.
  • Nếu không:
    • $m_i\gets m_{i-1}+m_{i-2}$.
  • Kết thúc điều kiện
• Kết thúc vòng lặp
• Trả ra $m_k$.

Kết thúc hàm

Đặc điểm của phương pháp quy hoạch động chính là mỗi bài toán con sẽ chỉ được tính toán đúng một lần. Vì thế độ phức tạp của hai hàm $\text{Fibonacci}(k)$ trên là $O(k)$.

Như vậy là phương pháp quy hoạch động rõ ràng tối ưu về mặt thời gian.

Vì vậy, giải thuật quy hoạch động thường được sử dụng trong các trường hợp sau:

• Các bài toán con "gối nhau": Khi kết quả từ bài toán con này hoàn toàn có thể tái sử dụng cho bài toán con kia.
• Tối ưu hóa cấu trúc con nhằm tối ưu hóa bài toán lớn: Thường thấy trong các bài toán lên kế hoạch và đồ thị.

Giải thuật tham lam

Giải thuật tham lam (Greedy algorithm) là giải thuật giải quyết một vấn đề dựa trên các lựa chọn đã được xếp hạng, phương pháp tối ưu nhất trong thời điểm sẽ được chọn và áp dụng rồi không được đề cập lại sau đó.

Một ví dụ cho dạng thuật toán này là thuật toán Kruskal, dùng để tìm cây khung nhỏ nhất trong đồ thị.

Đầu vào: Đồ thị vô hướng $G=(V,E,c)$ với $V$ là tập hợp các đỉnh, $E$ là tập hợp các cạnh và $c$ đo giá trị mỗi cạnh.

Đầu ra: Cây khung ngắn nhất $T=(V_T,E_T)$ xuất phát từ đồ thị $G$.

• $V_T\gets V$.
• $E_T\gets\emptyset$.
• $L=(L_k)_{k=1}^{|E|}|_{i<j\implies c(L_i)\leq c(L_j)}$
• Với mọi $e:=\{u,v\}\in L$ tiến hành:
  • Nếu chưa tồn tại con đường từ $u$ sang $v$ thì:
    • $E_T\gets E_T\cup\{e\}$.
  • Kết thúc điều kiện
• Kết thúc vòng lặp

Trong thuật toán nêu trên, các cạnh của đồ thị $G$ đã được sắp xếp theo thứ tự tăng dần của giá trị.

Giải quyết một chuỗi ô

Phương pháp 1

Vì ở tất cả các cách, có thể tồn tại các ô được tô đen cố định trong chuỗi. Vì vậy, phương pháp nguyên thủy nhất được sử dụng đến chính là "vét cạn" (brute force): Qua mỗi lần giải quyết chuỗi, chúng ta tổng hợp tất cả các cách tô màu để tìm ra các ô được tô cố định.

Ta có đoạn mã giả sau:

Hàm $\text{ToMau}(L,s,j,l)$ như sau:

• Nếu $l=0$ thì:
  • Với mọi $i<j$ tiến hành:
    • Nếu $L_i=2$ thì:
      • Trả ra $\bot$.
    • Kết thúc điều kiện
  • Kết thúc vòng lặp
  • Với mọi $i<j$ tiến hành:
    • Nếu $L_i=0$ thì:
      • $L_i\gets 1$.
    • Kết thúc điều kiện
  • Kết thúc vòng lặp
• Nếu không:
  • Nếu $j<s_l-1$ thì:
    • Trả ra $\bot$.
  • Còn nếu $j=s_l-1$ thì:
    • Với mọi $i<j$ tiến hành:
      • Nếu $L_i=1$ thì:
        • Trả ra $\bot$.
      • Kết thúc điều kiện
    • Kết thúc vòng lặp
    • Với mọi $i<j$ tiến hành:
      • Nếu $L_i=0$ thì:
        • $L_i\gets 1$.
      • Kết thúc điều kiện
    • Kết thúc vòng lặp
  • Nếu không:
    • Nếu $L_j=1$ thì:
      • Trả ra $\text{ToMau}(L,s,j-1,l)$.
    • Còn nếu $L_j=2$ thì:
      • Nếu $L_{j-s_l}=2$ thì:
        • Trả ra $\bot$.
      • Kết thúc điều kiện
      • Với mọi $i\in\{k\}_{k=j-s_l+1}^{j-1}$ tiến hành:
        • Nếu $L_j=1$ thì:
          • Trả ra $\bot$.
        • Kết thúc điều kiện
      • Kết thúc vòng lặp
      • Với mọi $i\in\{k\}_{k=j-s_l+1}^{j-1}$ tiến hành:
        • Nếu $L_j=0$ thì:
          • $L_j\gets1$.
        • Kết thúc điều kiện
      • Kết thúc vòng lặp
      • Trả ra $T(L,s,j-s_l-1,l-1)$.
    • Nếu không:
      • $L^1\gets L_{0:j+1}[L_j\gets1]$.
      • $L^2\gets L_{0:j+1}[L_j\gets2]$.
      • $b_1\gets\text{ToMau}(L^1,s,j,l)$.
      • $b_2\gets\text{ToMau}(L^2,s,j,l)$.
      • Nếu $\lnot b_1\land\lnot b_2$ thì:
        • Trả ra $\bot$.
      • Còn nếu $b_1\land\lnot b_2$ thì:
        • Với mọi $i\in\{k\}_{k=0}^{j}$ tiến hành:
          • Nếu $L_i=0\land L^1_i\neq0$ thì:
            • $L_i\gets L^1_i$.
          • Kết thúc điều kiện
        • Kết thúc vòng lặp
      • Còn nếu $b_2\land\lnot b_1$ thì:
        • Với mọi $i\in\{k\}_{k=0}^{j}$ tiến hành:
          • Nếu $L_i=0\land L^1_i\neq0$ thì:
            • $L_i\gets L^2_i$.
          • Kết thúc điều kiện
        • Kết thúc vòng lặp
      • Nếu không:
        • Với mọi $i\in\{k\}_{k=0}^{j-1}$ tiến hành:
          • Nếu $L_i=0\land L^1_i\neq0\land L^1_i=L^2_i$ thì:
            • $L_i\gets L^1_i$.
          • Kết thúc điều kiện
        • Kết thúc vòng lặp
      • Kết thúc điều kiện
    • Kết thúc điều kiện
  • Kết thúc điều kiện
• Kết thúc điều kiện
• Trả ra $\top$.

Kết thúc hàm

Nhìn tổng quan, thuật toán này được xây dựng trên nền tảng của hàm $T(L,s,j,l)$ được đề cập ở đầu bài. Bên cạnh phương pháp xác định tô đúng, tô sai, ở mỗi công đoạn của hàm có thêm giai đoạn truy ngược (backtracking) để bổ sung và hoàn thiện.

Tính chất

Tính chất 1: Thuật toán $\text{ToMau}(L,s,j,l)$ chỉ tô các ô trống bên trong chuỗi $L_{0:j+1}$, không đụng vào các ô có sẵn màu.

Chứng minh (Phản chứng):

Giả sử tồn tại ô $L_i$ nằm giữa $L_0$ và $L_j$ là ô được chỉnh sửa màu. Gọi $L'$ là phiên bản cũ sao cho $L'_i\neq 0$ và $L'_i\neq L_i$.

Nếu $L'_i=1$ thì hàm $\text{ToMau}(L',s,i,l)$ sẽ trực tiếp trả đệ quy ra $\text{ToMau}(L',s,i-1,l)$.

Còn nếu $L'_i=2$ thì xảy ra 2 trường hợp:

• $L'_i$ là ô cuối chuỗi con. Nếu $L'_i$ là ô hợp lệ dựa trên các điều kiện phía trước thì hàm sẽ trả đệ quy về $\text{ToMau}(L',s,i-s_l-1,l-1)$, nếu không sẽ tự động trả ra $\bot$ và kết thúc chương trình.

• $L'_i$ là ô phía trước chuỗi nhận $L_k$ ($k>i$) là ô cuối. Vòng lặp của $\text{ToMau}(L',s,k,l)$ sẽ bỏ qua $L'_i$.

Vì vậy, không có cách nào để $L'_i$ trở thành $L_i$. Điều này trái với giả thuyết ban đầu.

Tính chất 2: Thuật toán $\text{ToMau}(L,s,j,l)$ đảm bảo hoàn thiện các ô đen cố định bên trong chuỗi $L_{0:j+1}$ rỗng.

Chứng minh (Phản chứng):

Giả sử tồn tại ô $L_i$ nằm giữa $L_0$ và $L_j$ là ô đen cố định nhưng không được tô vào trong chuỗi rỗng. Vì là ô đen nên chắc chắn sẽ chỉ được tô khi $l>0$.

Nếu $L_i$ nhận $L_j$ là ô đen cuối chuỗi, $L_i$ sẽ được tô đen qua vòng lặp truy ngược của $\text{ToMau}(L,s,j,l)$.

Nếu $L_j$ là ô rỗng, vì là ô đen cố định nên sẽ $L^1_i=L^2_i=2$, từ đó $L_i$ cũng sẽ được tô đen qua vòng lặp truy ngược.

Điều này chứng tỏ giả thiết trên không tồn tại.

Độ phức tạp

Trường hợp 1: Ở các bước cơ sở

Khi tiến hành chạy thuật toán, các bước cơ sở tiến hành các vòng lặp để kiểm tra:

• Các ô phía trước có hợp lệ chưa.
• Các ô phía trước có được tô đầy đủ không.

Độ phức tạp của bước cơ sở là $c_0=O(j)$.

Trường hợp 2: Ở các bước đệ quy

Khi $L_j=1$, thuật toán trả đệ quy thẳng về $(j-1,l)$. Độ phức tạp là $c_{j,L_j=1}=1+c_{j-1}\in O(j)$.

Khi $L_j=2$, thuật toán trả đệ quy về $(j-s_l-1,l-1)$ sau $|s_l|$ vòng lặp kiểm tra các ô phía trước. Vậy độ phức tạp là $c_{j,L_j=2}=|s_j|+c_{j-s_l-1}\approx1+c_{j-1}$.

Khi $L_j=0$, thuật toán sẽ chia hai trường hợp thông qua hai nút đệ quy song song rồi sử dụng vòng lặp truy ngược để tổng hợp. Vậy độ phức tạp là $c_j=j+c_{j,L_j=1}+c_{j,L_j=2}=j+2c_{j-1}\in O(j2^j)$

Độ phức tạp của phương pháp 1 là $O(m2^m)$.

Phương pháp 2

Đối với phương pháp này, chúng ta sẽ sử dụng nguyên bản hàm nhị nguyên $T$ ở đầu bài viết, thay vì cải biên lại như ở trong phương pháp 1.

Ta có đoạn mã giả như sau:

Hàm $\text{ToMau}(L,s)$ như sau:

• Với mọi $i\in\{k\}_{i=0}^{|L|-1}$ tiến hành:
  • Nếu $L_i=0$ thì:
    • $b_1\gets T(L[L_i\gets1],s,j,l)$.
    • $b_2\gets T(L[L_i\gets2],s,j,l)$.
    • Nếu $\lnot b_1\land\lnot b_2$ thì:
      • Trả ra $\bot$.
    • Còn nếu $b_1\land\lnot b_2$ thì:
      • $L_i\gets1$.
    • Còn nếu $b_2\land\lnot b_1$ thì:
      • $L_i\gets2$.
    • Kết thúc điều kiện
  • Nếu không:
    • $b\gets T(L,s,j,l)$.
    • Nếu $\lnot b$ thì:
      • Trả ra $\bot$.
    • Kết thúc điều kiện
  • Kết thúc điều kiện
• Kết thúc vòng lặp
• Trả ra $\top$.

Kết thúc hàm

Về cơ bản, phương pháp này cũng có tính chất vét cạn: Ở đây thay vì thử hết các khả năng tô màu của cả chuỗi, thì gói gọn lại trong thử hết khả năng tô màu từng ô và kết luận.

Tính chất

Tính chất 1: Thuật toán $\text{ToMau}(L,s,j,l)$ chỉ tô các ô trống bên trong chuỗi $L_{0:j+1}$, không đụng vào các ô có sẵn màu.

Chứng minh (Phản chứng):

Giả sử tồn tại ô $L_i$ nằm giữa $L_0$ và $L_j$ là ô được chỉnh sửa màu. Gọi $L'$ là phiên bản cũ sao cho $L'_i\neq 0$ và $L'_i\neq L_i$.

Nếu $L'_i$ hiển thị màu không tô được, thuật toán sẽ ngắt luôn vòng lặp và trả ra $\bot$.

Nếu $L'_i$ hiển thị màu tô được, thì trên lý thuyết $L_i$ sẽ không được tô và để trống, vì hai màu đều thỏa mãn điều kiện của chuỗi ô.

Những điều trên chứng tỏ giả thiết không tồn tại.

Tính chất 2: Thuật toán $\text{ToMau}(L,s,j,l)$ đảm bảo hoàn thiện các ô đen cố định bên trong chuỗi $L_{0:j+1}$ rỗng.

Chứng minh (Phản chứng):

Giả sử tồn tại ô $L_i$ nằm giữa $L_0$ và $L_j$ là ô đen cố định nhưng không được tô vào trong chuỗi rỗng. Vì là ô đen nên chắc chắn sẽ chỉ được tô khi $l>0$.

Nếu $L_i$ không được tô, điều này có nghĩa là $L_i=1$ cũng hợp lệ.

Nếu $L_i=1$ hợp lệ, nghĩa là $L_i$ không phải là ô đen cố định. Điều này trái với giả thiết ban đầu.

Độ phức tạp

Độ phức tạp của $T(L,s,j,l)$:

Ở các trường hợp cơ sở, trong trường hợp tệ nhất, thuật toán vẫn phải thực hiện vòng lặp $O(j)$ để kiểm tra các ô. Vậy $c_{0,0}=O(j)$.

Ở trường hợp đệ quy, ta thấy các trường hợp ô $L_j$ đã tô màu cũng giống với phương pháp 1, trừ việc có backtracking. Độ phức tạp của thuật toán vì thế vẫn là $c_{j,l}=1+c_{j-1,l}\in O(j)$.

Trường hợp $L_j$ chưa được tô màu, độ phức tạp là: $c_{j,l}=1+2c_{j-1,l}\in O(2^j)$.

Vì $L$ có độ dài $m$, nên độ phức tạp là $O(2^m)$.

Độ phức tạp của $\text{ToMau}$:

Vì hàm sử dụng vòng lặp qua các ô, số vòng lặp là $\Theta(m)$.

Nhân số vòng lặp với số lần đệ quy, ta có: $\Theta(m).2.O(2^m)=O(m2^m)$.

Độ phức tạp của phương pháp 2 là $O(m2^m)$.

So sánh hai phương pháp trên

Hai phương pháp trên đều có độ phức tạp là $Om2^m)$, giải quyết được vấn đề tô chuỗi ô thông qua thỏa mãn 2 tính chất: Tô các ô trống trên cơ sở tôn trọng sự tồn tại các màu có sẵn, và đảm bảo tô các ô đen cố định khi chuỗi rỗng.

Tuy nhiên chúng ta sẽ đi sâu vào phân tích các "vấn đề con" ở hai phương pháp.

Ở phương pháp 1, thuật toán tô màu trực tiếp trên các ô đan xen với việc kiểm tra tính hợp lệ của màu sắc. Khi nút đệ quy thực hiện trên ô rỗng, thuật toán chia ra làm hai chuỗi phụ độc lập với nhau, sau đó truy ngược để tổng hợp các nút giống nhau giữa các chuỗi phụ.

Ở phương pháp 2, thuật toán giải quyết từng ô trong chuỗi thông qua phép lặp và thử. Ở mỗi ô $L_j$, khi ô có màu, thuật toán chỉ thuần túy kiểm tra lại tính hợp lệ của toàn chuỗi, còn ở ô rỗng thì sẽ lại chia ra làm các chuỗi phụ để thử nghiệm. Đặc điểm của các chuỗi phụ này là có chung dữ liệu của chuỗi con $L_{0:j}$.

Vì vậy, ta nhận định: Phương pháp 2 chia thành các bài toán con không độc lập với nhau về dữ liệu. Đây chính là tiền đề để ta áp dụng quy hoạch động vào giải chuỗi.

Phương pháp tối ưu

Áp dụng quy hoạch động

Chúng ta sẽ áp dụng phương pháp top-down memoization lên trên phương pháp 2.

Trên cơ sở hàm đệ quy $T(L,s,j,l)$, chúng ta sử dụng một bảng bộ nhớ hai chiều để lưu trữ bộ nhớ các kết quả $T(L,s,j,l)$ mỗi khi trả ra kết quả sai. Gọi $\text{memory}=(m_{j,l})_{j=0,l=0}$ là bộ nhớ hai chiều, được khởi tạo với mọi $m_{j,l}=\top$.

Ở mỗi lần tiến hành $T(L,s,j,l)$, khi $T(L,s,j,l)$ trả ra sai, $\text{memory}$ sẽ ghi nhận $m_{j,l}\gets\bot$.

Ở mỗi nút đệ quy của $T(L,s,j,l)$, điều kiện $\text{memory}=\bot$ sẽ khống chế việc thuật toán đi xa hơn, bởi vậy độ phức tạp của các bài toán con xoay quanh ở các vòng lặp: $O(j)$

Độ phức tạp của phương pháp tối ưu là $O(m^2)$.

Một số cải tiến khác

Cải tiến để một số trường hợp hàm $\text{ToMau}$ chạy ở độ phức tạp $O(m)$: Chúng ta sẽ thêm những ràng buộc ở các trường hợp $|s|=0$ và $\gamma=|L|$.

• Nếu |s|=0 thì:
  • Với mọi $L_i\in L$ tiến hành:
    • $L_i\gets 1$.
  • Kết thúc vòng lặp
  • Trả ra $\top$.
• Còn nếu $\gamma=|L|$ thì:
  • $l=1$.
  • $\text{done}\gets0$.
  • Với mọi $L_i\in L$ tiến hành:
    • Nếu $\text{done}=|s_l|$ thì:
      • $l\gets l+1$.
      • $\text{done}\gets0$.
      • $L_i\gets1$.
    • Nếu không:
      • $\text{done}\gets\text{done+1}$.
      • $L_i\gets2$.
    • Kết thúc điều kiện
  • Kết thúc vòng lặp
• Kết thúc điều kiện

Cải tiến để một số trường hợp hàm $\text{ToMau}$ chạy ở độ phức tạp $O(\log m)$: Đối với chuỗi ô rỗng toàn phần, chúng ta tính toán số ô trắng tự do $n$, sau đó lặp qua $s$ để tìm ra các chỉ mục của những ô tô đen cố định thông qua công thức toán nêu trên. Sau đó, chúng ta lặp qua danh sách chỉ mục trên để tô đen các ô, thay vì gọi các hàm đệ quy ban đầu.

Giải quyết toàn bộ khung

Áp dụng phương pháp giải chuỗi ô

Ta đến với mã giả sau đây:

Đầu vào: Ma trận rỗng $\mathcal M$, danh sách dãy số hàng $\mathcal S_v$, danh sách dãy số cột $\mathcal S_h$.

• Khởi tạo $\mathscr L$ là tập hợp các chỉ mục hàng.
• Khởi tạo $\mathscr C$ là tập hợp các chỉ mục cột.
• Khi $\mathscr L\neq\emptyset\land\mathscr C\neq\emptyset$ tiến hành:
  • Với mọi $i\in\mathscr L$ tiến hành:
    • Tô màu hàng $i$ của ma trận $\mathcal M$ dựa trên dãy số $\mathcal S_v[i]$.
    • Nếu hàm tô màu trả ra $\bot$ thì:
      • Trả ra $\bot,()$. //$()$ là ma trận rỗng
    • Kết thúc điều kiện
    • Thêm chỉ mục các ô trong hàng được tô mới vào tập hợp $\mathscr C$.
    • Loại bỏ $i$ ra khỏi tập hợp $\mathscr L$.
  • Kết thúc vòng lặp
  • Với mọi $j\in\mathscr C$ tiến hành:
    • Tô màu hàng $j$ của ma trận $\mathcal M$ dựa trên dãy số $\mathcal S_h[j]$.
    • Nếu hàm tô màu trả ra $\bot$ thì:
      • Trả ra $\bot,()$.
    • Kết thúc điều kiện
    • Thêm chỉ mục các ô trong cột được tô mới vào tập hợp $\mathscr L$.
    • Loại bỏ $j$ ra khỏi tập hợp $\mathscr C$.
  • Kết thúc vòng lặp
• Kết thúc vòng lặp
• Nếu tồn tại một ô trong ma trận chưa được tô thì:
  • Trả ra $\varnothing,\mathcal M$.
• Kết thúc điều kiện
• Trả ra $\top,\mathcal M$.

Bước giải quyết khung trên đây áp dụng phương pháp bottom-up memoization: Các hàng và cột được giải lần lượt từ thấp lên cao, cho đến khi không còn hàng và cột nào có thể giải quyết thêm nữa.

Gọi $(\mathscr l,\mathscr c)$ là kích thước hàng × cột của ma trận $\mathcal M$.

Đặt $m=\max(\mathscr l,\mathscr c)$

Vậy độ phức tạp của thuật toán, trên cơ sở áp dụng hàm tô màu tối ưu, là $\Theta(\mathscr l^3+\mathscr c^3)$ hoặc $\Theta(m^3)$.

Áp dụng giải thuật tham lam

Khi chủ thể giải quyết bài toán là máy tính, các chỉ mục được thực hiện theo thứ tự từ nhỏ đến lớn. Tuy nhiên, người chơi thực tế không giải quyết bài toán như vậy. Họ có khuynh hướng chọn lựa hàng và cột "dễ giải quyết" để xử lý trước.

Vì vậy, chúng ta sẽ áp dụng giải thuật tham lam như sau, để phương pháp giải gắn với bản năng của con người hơn.

Một chuỗi ô ra sao được gọi là "dễ giải"? Qua toàn bộ những gì chúng ta phân tích từ đầu bài, có hai giá trị quyết định đến độ khó của chuỗi ô:

• Số ô trống trong chuỗi
• Giá trị $n=|L|-\gamma$: tương ứng với số ô trắng tự do trong chuỗi.

Bởi thế, ta đề xuất cách chấm điểm chuỗi ô như sau:

$$\text{score}_L=\min(|\{i|L_i\in L\land L_i=0\}|,|L|-\gamma)$$

Ở mỗi vòng lặp trong bước giải khung, chúng ta sắp xếp thứ tự các chỉ mục trong $\mathscr L$ và $\mathscr C$ theo thứ tự tăng dần của giá trị $\text{score}$, sau đó tiến hành tô màu các chuỗi ô theo thứ tự trên.

Câu hỏi: Giải thuật tham lam có tối ưu hóa việc giải quyết trò chơi không?

Đáp án: Trên lý thuyết, việc sắp xếp lại các chỉ mục theo thứ tự có độ phức tạp là $O(m)$. Hơn nữa, điều này thực hiện trước khi mỗi vòng lặp xảy ra, và không làm giảm đi số vòng lặp bắt buộc. Vì vậy thuật toán vẫn là $\Theta(m^3)$ và không tối ưu được phép giải trên máy tính.

Vét cạn

Chúng ta có mẫu puzzle như trong hình. Khi chúng ta áp dụng thuần túy phép giải khung như trên, thứ tự tiến hành sẽ là:

• Ở bước giải các hàng:
  • Hàng 1 có $C_{2+2-1}^{2-1}=C_3^1=3$ cách xếp, có $2$ ô trắng tự do tương ứng với dãy số. Do $1\leq 2$ nên không có ô đen cố định. Hàng 1 bị để trống.
  • Hàng 2 có $C_{1+3-1}^{3-1}=C_3^2=3$ cách xếp, có $1$ ô trắng tự do tương ứng với dãy số. Do $1\leq 1$ nên không có ô đen cố định. Hàng 2 bị để trống.
  • $\mathscr L$ trở thành tập rỗng.
• Ở bước giải các cột:
  • Cột 1 có $C_{1+2-1}^{2-1}=C_2^1=2$ cách xếp, có $1$ ô trắng tự do tương ứng với dãy số. Do $1\leq 1$ nên không có ô đen cố định. Cột 1 bị để trống và tương tự với 3 cột còn lại.
  • $\mathscr C$ trở thành tập rỗng. Do không có ô nào được tô nên $\mathscr L$ vẫn là tập rỗng.
• Thuật toán kết thúc và trả ra $\varnothing$ với ma trận để trống toàn tập.

Để giải quyết vấn đề trên, chúng ta sẽ thay thế phần trả ra $\varnothing$ bằng việc trả ra dòng mã giả dưới đây:

• Gọi $m_{ij}$ một ô trống bất kỳ trong ma trận dang dở.
• Tô màu bằng phương pháp giải khung ở trên khi $m_{ij}\gets1$. (Khởi tạo $\begin{cases}\mathscr L\gets\{i\}\\\mathscr C\gets\{j\}\end{cases}$).
• Tô màu bằng phương pháp giải khung ở trên khi $m_{ij}\gets2$. (Khởi tạo $\begin{cases}\mathscr L\gets\{i\}\\\mathscr C\gets\{j\}\end{cases}$).
• Ở mỗi hàm tô màu, đệ quy cho đến khi ma trận giải hết hoặc trả ra $\bot$.

Chúng ta kết thúc với bức hình:

Độ phức tạp của thuật toán vét cạn là $O(2^{m^3})$

Kết luận về cách giải ở người chơi

Từ việc phân tích thao tác của máy tính trong việc giải Nonogram puzzle thông qua các giải thuật khác nhau, ta đi đến kết luận về phương pháp giải của con người:

1. Ở ma trận rỗng, người chơi chọn các hàng và cột có độ khó thấp nhất để giải trước.
2. Người chơi lấp tối đa khung hình bằng các ô tô đen cố định và các ô trắng (nếu có).
3. Khi ma trận được lấp một phần, xu hướng chọn hàng và cột thiên về hàng và cột có ít ô chưa tô màu nhất.
4. Khi không thể giải bằng logic nữa, xu hướng vét cạn sẽ được áp dụng với các ô rỗng.

Tài liệu tham khảo

Về Nonogram: Đồ án học phần LU3IN003 - Algorithmique II niên khóa 2023-2024 của trường Đại học Sorbonne, Paris

Về các giải thuật:

1. Tài liệu học học phần UL3IN003 - Algorithmique II của trường Đại học Sorbonne, Paris bởi các Phó Giáo sư Fanny P. và Olivier S.
2. manhhomienbienthuy - Quy hoạch động - một thuật toán thần thánh
3. Phong Tr. - Thuật toán tham lam - Greedy Algorithm

Về phần Toán học: Nỗ lực cá nhân có sự hỗ trợ của Tiến sĩ Manuel A., ChatGPT và Wikipedia