📖 Bài giảng & lời giải: đây là Bài tập 3 trong bài giảng Thuật toán qua trò chơi 3: Sudoku trên blog Lập trình thuật toán – có lý thuyết, mô phỏng từng bước, gợi ý và code C++ / Python.

⚠️ Lưu ý: hãy đảm bảo em đã thật sự cố gắng tự làm bài trước, rồi mới xem gợi ý và lời giải nhé!

🎓 Khóa học Lập trình Thuật toán thi đấu của thầy Nguyễn Việt Nam Sơn – 111 buổi video, kèm cặp cá nhân, luyện thi chuyên Tin · HSG Tin học · Tin học trẻ · đội tuyển quốc gia · Olympic/ICPC. 👉 Xem chi tiết khóa học · Thành tích học viên

📞 Đăng ký học: Zalo 0767 666 702 · Facebook Nguyễn Việt Nam Sơn · 🌐 laptrinhthuattoan.blogspot.com

Sudoku $4 \times 4$: điền các số từ 1 đến 4 vào bàn $4 \times 4$ sao cho mỗi hàng, mỗi cột và mỗi khối $2 \times 2$ (bàn được chia thành 4 khối $2 \times 2$ ở bốn góc) chứa đủ các số 1, 2, 3, 4.

Cho một bàn đã điền sẵn một số ô (ô trống ghi là $0$). Dữ liệu bảo đảm có ít nhất một lời giải. Hãy in ra một lời giải; nếu có nhiều lời giải, in lời giải nhỏ nhất theo thứ tự từ điển khi đọc 16 số của bàn lần lượt từ trái sang phải, từ hàng trên xuống hàng dưới như một dãy số.

Dữ liệu vào

Gồm 4 dòng, mỗi dòng 4 số nguyên từ $0$ đến $4$, cách nhau bởi dấu cách.

Kết quả

In ra 4 dòng, mỗi dòng 4 số của bàn đã điền đầy đủ, cách nhau một dấu cách.

Sample Input

0 0 1 2
0 0 0 0
3 0 0 0
0 0 2 0

Sample Output

4 3 1 2 
2 1 3 4 
3 2 4 1 
1 4 2 3