Đề bài yêu cầu xác định ma trận sudoku dựa trên ma trận đầu vào 9x9. Với giá trị 0 là giá trị cần phải điền số phù hợp sao cho mỗi hàng, mỗi cột, mỗi hình vuông con 3x3 chỉ tồn tại duy nhất 1 số từ 1 đến 9. Nếu k thể tìm được ma trận phù hợp với đề bài in ra "No solution".
Sample Input
Giải thuật:
Tại một ô tọa độ i, j sẽ có 2 trường hợp.
- Đã được điền (có giá trị khác 0) thì hãy chuyển sang ô tiếp theo i, j+1 hoặc i+1, 0 (trường hợp xuống dòng).
- Chưa được điền thử giá trị k (trong khoảng từ 1 - 9) kiểm tra k xem đã tồn tại trong hàng, cột, hoặc hình vuông 3x3 chưa nếu chưa thì set giá trị tại ô i,j là k và chuyển đến ô tiếp theo i, j+1 hoặc i+1, 0 (trường hợp xuống dòng).
Nếu i, j có thể đi qua ô tọa độ 8,8 (vì ma trận kích thước 9x9) thì tồn tại solution và in ra ma trận.
Sử dụng 1 cờ flag để thoát khỏi hàm backtrack khi đã tìm được solution.
Tại một ô tọa độ i, j sẽ có 2 trường hợp.
- Đã được điền (có giá trị khác 0) thì hãy chuyển sang ô tiếp theo i, j+1 hoặc i+1, 0 (trường hợp xuống dòng).
- Chưa được điền thử giá trị k (trong khoảng từ 1 - 9) kiểm tra k xem đã tồn tại trong hàng, cột, hoặc hình vuông 3x3 chưa nếu chưa thì set giá trị tại ô i,j là k và chuyển đến ô tiếp theo i, j+1 hoặc i+1, 0 (trường hợp xuống dòng).
Nếu i, j có thể đi qua ô tọa độ 8,8 (vì ma trận kích thước 9x9) thì tồn tại solution và in ra ma trận.
Sử dụng 1 cờ flag để thoát khỏi hàm backtrack khi đã tìm được solution.
Solution C++ 4.3.2