Test Set 1

Bài toán có một vài trường hợp bất khả thi. Nếu thử nghiệm với một số lưới nhỏ, ngoài lưới \(2 \times 2\) đã xuất hiện trong ví dụ, ta có thể nhận thấy các trường hợp \(2 \times 3\), \(2 \times 4\) và \(3 \times 3\) đều không có lời giải. (Do tính đối xứng, các trường hợp \(3 \times 2\) và \(4 \times 2\) cũng bất khả thi.)

Trong lưới \(2 \times 3\), có thể thấy ô giữa của hàng trên cùng hàng, cùng cột hoặc cùng đường chéo với mọi ô khác; điều tương tự cũng đúng với ô trung tâm của lưới \(3 \times 3\). Trong mỗi trường hợp, ta không thể đi từ ô đó đến bất kỳ ô nào khác, cũng không thể đi theo chiều ngược lại, nên lưới không có lời giải.

Trong lưới \(2 \times 4\), hãy thử bắt đầu tại ô thứ hai của hàng trên. Khi đó, ta buộc phải thực hiện một chuỗi ba bước đi và cuối cùng đến ô thứ ba của hàng dưới, nơi không còn bước đi nào khác; ta không bao giờ có thể thoát khỏi tập hợp bốn ô vừa thăm. Vì điều tương tự cũng đúng với tập hợp bốn ô còn lại, bài toán không có lời giải.

Tuy nhiên, tất cả các trường hợp khác trong Test Set 1 đều có lời giải. Một chiến lược là chủ yếu thực hiện các "nước đi của quân mã" — đi hai ô đơn vị theo một hướng và một ô đơn vị theo hướng kia. Ta có thể không giải được một lưới nếu chỉ dùng nước đi của quân mã — xem bài viết này để biết thêm thông tin — nên cũng có thể xen kẽ các bước đi hợp lệ khác. Chẳng hạn, ta có thể giải trường hợp \(3 \times 4\) bằng cách thăm các ô theo thứ tự sau:

02 05 10 07
09 12 01 04
06 03 08 11

Và đây là một lời giải cho trường hợp \(3 \times 5\), trong đó có nhiều bước đi rộng hơn nước đi của quân mã:

04 14 09 12 07
06 11 01 15 03
02 08 13 10 05

Do tính đối xứng, các trường hợp duy nhất còn lại là \(2 \times 5\), \(4 \times 4\) và \(4 \times 5\); ta có thể tự tìm lời giải cho chúng hoặc sử dụng thuật toán vét cạn.

Test Set 2

Có nhiều chiến lược để xử lý Test Set 2. Một nhóm phương pháp là xây dựng. Ví dụ, ta có thể thiết kế các lời giải tổng quát cho lưới \(2 \times N\) và \(3 \times N\) với \(N\) tùy ý, rồi chia lưới thành các dải ngang có chiều cao \(2\), cộng thêm một dải có chiều cao \(3\) nếu cần. Tiếc rằng việc thực hiện đúng ý tưởng này có thể khá phức tạp. Ta phải bảo đảm lời giải của các bài toán con không vi phạm quy tắc — bước đi cuối cùng trong một bài toán con không được cùng hàng, cùng cột hoặc cùng đường chéo với bước đi đầu tiên trong bài toán con khác. Hơn nữa, ngay cả việc tìm ra lời giải tổng quát cho \(2 \times N\) và \(3 \times N\) cũng có thể gây khó khăn.

Lời giải xây dựng thành công đầu tiên của đội ngũ Code Jam bao gồm nhiều trường hợp cho \(2 \times N\) (tùy theo \(N\) là số lẻ, đồng dư \(0\) modulo \(4\), hay đồng dư \(2\) modulo \(4\)), và nhiều trường hợp cho \(3 \times N\) (bằng cách thêm từng cặp cột vào bên trái và bên phải các lời giải \(3 \times 4\) và \(3 \times 5\) được viết cứng, rồi di chuyển qua lại giữa các cột đó để tránh vi phạm quy tắc). Mỗi lời giải như vậy cũng được bố trí để bắt đầu gần mép trái và kết thúc gần mép phải của mỗi dải, nhằm tránh các tương tác theo đường chéo giữa các bài toán con hoặc các dải.

Có cách nào dễ hơn không? Hãy lùi lại một bước. Bài toán đặt ra một số ràng buộc, nhưng ta có thể nhận thấy việc giải bằng tay các trường hợp lớn hơn của Test Set 1 không quá khó. Điều này gợi ý rằng có nhiều lời giải khả dĩ, và ta có thể kỳ vọng số lượng đó còn tăng khi kích thước lưới lớn hơn. (Ta có thể dùng định lý Ore để chứng minh sự tồn tại của ít nhất một lời giải đối với các lưới đủ lớn.) Vì vậy, trực giác lúc này có thể gợi ý rằng phương pháp tốt nhất là một dạng vét cạn nào đó.

Ta có thể cân nhắc các lời giải quay lui. Một điều đáng lo là các lời giải này, dù duyệt theo chiều rộng hay chiều sâu, đều tiến hành theo một trật tự có thể khiến ta dễ rơi vào những "tàn cuộc" khó, nơi không thể thỏa mãn các ràng buộc. Ví dụ, nếu lời giải bằng cách nào đó đã xử lý tất cả các ô trừ hàng dưới cùng của lưới, thì mọi hy vọng của vũ trụ đều đã tiêu tan!

Ta vẫn có thể thử các lời giải đó, hoặc nhờ đến người bạn đôi khi hữu ích của mình: tính ngẫu nhiên! Ta chọn ngẫu nhiên một ô bắt đầu, liên tục chọn đồng xác suất một bước đi hợp lệ trong số tất cả các bước được phép từ ô hiện tại, và nếu hết bước đi khả dụng thì bỏ cuộc rồi bắt đầu lại. Với mọi trường hợp ngoại trừ các trường hợp bất khả thi đã nêu ở trên, phương pháp này tìm được lời giải rất nhanh.

Nhiều bài toán không thể được tiếp cận bằng lời giải ngẫu nhiên hoặc vét cạn, nhưng nhận biết được những bài toán có thể áp dụng các phương pháp đó (trong Code Jam hoặc ngoài đời thực) là một kỹ năng hữu ích!

Thậm chí còn có một thuật toán tham lam

Chúng tôi còn biết đến các phương pháp khác. Ví dụ, chúng tôi biết có ít nhất một cách cài đặt ý tưởng sau đây giải được mọi bộ test có thể xuất hiện trong giới hạn của Test Set 1 và 2: liên tục chọn theo chiến lược tham lam một ô chưa thăm có số lượng "hàng xóm" chưa thăm lớn nhất, trong đó hàng xóm của một ô được định nghĩa là các ô cùng hàng, cùng cột hoặc cùng đường chéo với ô đó. (Ta có thể loại riêng các trường hợp bất khả thi từ trước vì số lượng của chúng không nhiều, hoặc suy ra tính bất khả thi bằng cách so sánh số ô chưa thăm với số lượng hàng xóm chưa thăm lớn nhất.)

Mặc dù không đưa ra chứng minh ở đây, về mặt trực giác, việc ngăn không cho bất kỳ hàng, cột hoặc đường chéo nào có quá nhiều ô chưa thăm so với các hàng, cột và đường chéo khác là có lợi. Ví dụ, nếu ta đã gần kết thúc hành trình mà phần lớn các ô chưa thăm còn lại nằm trong cùng một cột, ta chắc chắn thất bại.

Vì số lượng bộ test có thể có của bài toán này tương đối nhỏ, việc kiểm tra tất cả để xác minh một lời giải hoạt động không quá khó, và điều đó có thể dễ hơn nhiều so với chứng minh tính đúng đắn! Đây là một sự xa xỉ hiếm có đối với một bài Code Jam!

Dữ liệu kiểm thử

Chúng tôi khuyên bạn luyện tập gỡ lỗi lời giải mà không xem dữ liệu kiểm thử.

Nguồn

Phần phân tích này được dịch đầy đủ từ lời giải chính thức của Google Code Jam 2019, Vòng 1A — Pylons.