Các thuật toán giải Sudoku

Trong phần này, chúng ta sẽ cố gắng giải bài toán mê cung số nổi tiếng gọi là Sudoku. Sudoku là một lưới số 9 x 9 và toàn bộ lưới cũng được chia thành các ô 3 x 3 Có một số quy tắc để giải Sudoku.

Chúng ta phải sử dụng các chữ số từ 1 đến 9 để giải quyết vấn đề này.

Không thể lặp lại một chữ số trong một hàng, một cột hoặc trong một hộp 3 x 3.

Sử dụng thuật toán backtracking, chúng tôi sẽ cố gắng giải quyết vấn đề Sudoku. Khi một số ô được điền bằng một chữ số, nó sẽ kiểm tra xem nó có hợp lệ hay không. Khi nó không hợp lệ, nó sẽ kiểm tra các số khác. Nếu tất cả các số được chọn từ 1-9 và không tìm thấy chữ số hợp lệ nào để đặt, nó sẽ chuyển về tùy chọn trước đó.

Đầu vào và Đầu ra

 Đầu vào:Điều này sẽ lấy ma trận 9 x 9 làm lưới Sudoku. Một số giá trị được đặt trong lưới. Các khoảng trống được ký hiệu bằng 0.  Đầu ra:Ma trận cuối cùng (lưới Sudoku) chứa các số. Nếu giải pháp không tồn tại, nó sẽ trả về false.3 1 6 | 5 7 8 | 4 9 25 2 9 | 1 3 4 | 7 6 84 8 7 | 6 2 9 | 5 3 1 ------------------------ 2 6 3 | 4 1 5 | 9 8 79 7 4 | 8 6 3 | 1 2 58 5 1 | 7 9 2 | 6 4 3 ------------------------ 1 3 8 | 9 4 7 | 2 5 66 9 2 | 3 5 1 | 8 7 47 4 5 | 2 8 6 | 3 1 9 

Thuật toán

isPresentInCol (col, num)

Đầu vào: Cột và số được nhắm mục tiêu.

Đầu ra - Đúng khi số có trong cột nhất định.

 Bắt đầu cho mỗi hàng r trong lưới, thực hiện if grid [r, col] =num, sau đó trả về true, xong trả về false nếu không 

  isPresentInRow (hàng, số)  
 

  Đầu vào -  Hàng và số được nhắm mục tiêu. 
 

  Đầu ra -  Đúng khi số có trong cột nhất định. 
 
 Bắt đầu cho mỗi cột c trong lưới, thực hiện if grid [row, c] =num, sau đó trả về true, hoàn thành trả về false nếu không 

  isPresentInBox (boxStartRow, boxStartCol, num)  
 

  Đầu vào -  Hàng và cột bắt đầu của hộp 3 x 3 và số được nhắm mục tiêu. 
 

  Đầu ra -  Đúng khi số này có trong hộp. 
 
 Bắt đầu cho mỗi hàng r trong boxStartRow đến 3 hàng tiếp theo, thực hiện cho mỗi cột r trong boxStartCol cho 3 cột tiếp theo, thực hiện nếu grid [r, c] =num, sau đó trả về true, xong trả về false, ngược lại là xong 
 

  findEmptyPlace (hàng, cột)  
 

  Đầu vào: hàng và cột trong lưới. 
 

  Đầu ra -  Nếu lưới [row, col] trống, thì trả về true, ngược lại là false. 
 
 Bắt đầu cho mỗi hàng r trong lưới, thực hiện cho mỗi cột c trong lưới, thực hiện nếu grid [r, c] =0, sau đó trả về true, xong trả về falseEnd 
 

  isValidPlace (hàng, cột, số)  
 

  Đầu vào: Hàng, một cột của lưới và số để kiểm tra. 
 

  Đầu ra: Đúng, khi đặt số tại lưới vị trí [row, col] là hợp lệ. 
 
 Bắt đầu nếu isPresentInRow (row, num) và isPresentInCol (col, num) và isPresntInBox (row - row mod 3, col - col mod 3, num) đều là false, thì trả về trueEnd 
 

  giải quyếtSudoku (Sudoku Grid)  
 

  Đầu vào: Lưới Sudoku chưa được giải đáp. 
 

  Đầu ra: Grid sau khi giải quyết. 
 
 Bắt đầu nếu không có vị trí nào trong lưới trống, sau đó trả về true cho số 1 đến số 9, thực hiện nếu isValidPlace (hàng, col, số), sau đó lưới [hàng, col]:=số nếu giải quyếtSudoku =true, sau đó trả về true grid [row, col]:=0 done trả về falseEnd 
 
 Ví dụ 
 
 #include  #define N 9 using namespace std; int grid [N] [N] ={{3, 0, 6, 5, 0, 8, 4, 0, 0}, {5, 2, 0, 0, 0, 0, 0, 0, 0}, {0, 8, 7, 0, 0, 0, 0, 3, 1}, {0, 0, 3, 0, 1, 0, 0, 8, 0}, {9, 0, 0, 8, 6, 3, 0, 0, 5}, {0, 5, 0, 0, 9, 0, 6, 0, 0}, {1, 3, 0, 0, 0, 0, 2, 5, 0}, {0, 0, 0, 0, 0, 0, 0, 7, 4}, {0, 0, 5, 2, 0, 6, 3, 0, 0}}; bool isPresentInCol (int col, int num) {// kiểm tra xem num có trong col hay không for (int row =0; row  
 Đầu ra 
  3 1 6 | 5 7 8 | 4 9 25 2 9 | 1 3 4 | 7 6 84 8 7 | 6 2 9 | 5 3 1 ------------------------ 2 6 3 | 4 1 5 | 9 8 79 7 4 | 8 6 3 | 1 2 58 5 1 | 7 9 2 | 6 4 3 ------------------------ 1 3 8 | 9 4 7 | 2 5 66 9 2 | 3 5 1 | 8 7 47 4 5 | 2 8 6 | 3 1 9