Sudoku Solver trong C ++

Giả sử chúng ta có một lưới Sudoku và chúng ta phải giải bài toán mê cung số nổi tiếng này, Sudoku. Chúng ta biết rằng 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 đó.

Vì vậy, nếu đầu vào giống như -

Đầu ra sẽ là -

Sudoku Solver trong C ++

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

Xác định một phương thức được gọi là isPresentInCol (), phương thức này sẽ nhận lệnh gọi và num
đối với mỗi hàng r trong lưới, thực hiện
- nếu grid [r, col] =num, thì trả về true
nếu không thì trả về false
Xác định một phương thức được gọi là isPresentInRow (), phương thức này sẽ lấy hàng và số
đối với mỗi cột c trong lưới, thực hiện
- nếu lưới [row, c] =num, thì trả về true
nếu không thì trả về false
Xác định một phương thức được gọi là isPresentInBox (), phương thức này sẽ lấy boxStartRow, boxStartCol, num
cho mỗi hàng r trong hộp Bắt đầu Chuyển đến 3 hàng tiếp theo, thực hiện
- đối với mỗi cột r trong boxStartCol đến 3 cột tiếp theo, thực hiện
  - nếu grid [r, c] =num, thì trả về true
nếu không thì trả về false
Xác định một phương thức có tên findEmptyPlace (), phương thức này sẽ lấy hàng và cột
đối với mỗi hàng r trong lưới, thực hiện
- đối với mỗi cột c trong lưới, thực hiện
  - nếu lưới [r, c] =0, thì trả về true
trả về false
Xác định một phương thức được gọi là isValidPlace (), phương thức này sẽ nhận hàng, col, num
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ề true
Xác định một phương thức có tên giải quyếtSudoku (), phương thức này sẽ lấy lưới
nếu không có vị trí nào trong lưới trống, thì trả về true
đối với số 1 đến số 9, thực hiện
- if isValidPlace (row, col, number), then
  - lưới [row, col]:=number
  - nếu giải quyếtSudoku =true, thì trả về true
  - lưới [row, col]:=0
trả về false

Ví dụ (C ++)

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

 #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 vào 
  {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} 
  Đầ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