Backtracking #5: sudoku Solve

Bạn đã quen vs bài toán sudoku rồi nhỉ

Đây là một bài cao cấp hơn của bài sudokuChecking

Cho một bảng 9×9 thể hiện trạng thái hiện tại của bảng sudoku. Hãy tìm phương án điền số vào bảng để thỏa mãn. Do có nhiều phương án điền, nên kết quả là phương án điền số có thứ tự từ điển nhỏ nhất

Thứ tự từ điển được tính như 1 xâu viết liên tục các ô từ trái qua phải, từ trên xuống dưới

Ví dụ:

Đầu vào/Đầu ra:

• [Thời gian chạy] 1 giây
• [Đầu vào] array.string matrix
  Mảng gồm 9 xâu kí tự, mỗi xâu kí tự có độ dài là 9 chứa các kí tự từ 0-9, trong đó số 0 có nghĩa là ô trống (chưa điền số)
  
  Đảm bảo dữ liệu đúng đắn, tức là trạng thái khởi tạo không có các số trùng nhau ở chung hàng, chung cột hay chung ô vuông nhỏ 3*3
• [Đầu ra] array.string matrix
  Bảng sau khi đã điền đủ các số