Thuật toán giải Sudoku (Backtracking)

Giới thiệu

Sudoku là lưới 9x9 chia thành 9 ô 3x3. Quy tắc: dùng chữ số 1-9, không lặp trong hàng, cột, ô 3x3.

Dùng backtracking: điền số vào ô trống, kiểm tra hợp lệ. Nếu không hợp lệ thử số khác. Nếu 1-9 đều thất bại, backtrack về ô trước.

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

Đầu vào: Ma trận 9x9, ô trống đánh dấu 0. 
Đầu ra: Lưới Sudoku đã giải. Nếu vô nghiệm trả về false.
3 1 6 | 5 7 8 | 4 9 2
5 2 9 | 1 3 4 | 7 6 8
4 8 7 | 6 2 9 | 5 3 1
------------------------
2 6 3 | 4 1 5 | 9 8 7
9 7 4 | 8 6 3 | 1 2 5
8 5 1 | 7 9 2 | 6 4 3
------------------------
1 3 8 | 9 4 7 | 2 5 6
6 9 2 | 3 5 1 | 8 7 4
7 4 5 | 2 8 6 | 3 1 9

Thuật toán

isPresentInCol(col, num)

Đầu vào: Cột, số cần kiểm tra.

Đầu ra: True nếu số có trong cột.

Begin
  với mỗi hàng r trong lưới làm:
    nếu grid[r][col] = num thì return true
  done
  return false
End

isPresentInRow(row, num)

Begin
  với mỗi cột c trong lưới làm:
    nếu grid[row][c] = num thì return true
  done
  return false
End

isPresentInBox(boxStartRow, boxStartCol, num)

Begin
  với hàng r từ boxStartRow đến +3, cột c từ boxStartCol đến +3 làm:
    nếu grid[r][c] = num thì return true
  done
  return false
End

findEmptyPlace(row, col)

Begin
  với mỗi hàng, cột trong lưới làm:
    nếu grid[r][c] = 0 thì return true
  done
  return false
End

isValidPlace(row, col, num)

Begin
  nếu isPresentInRow(row,num) VÀ isPresentInCol(col,num) VÀ isPresentInBox(row-row%3, col-col%3, num) đều false thì return true
End

solveSudoku(Grid)

Begin
  nếu không còn ô trống thì return true
  với số 1 đến 9 làm:
    nếu isValidPlace(row, col, number) thì
      grid[row][col] := number
      nếu solveSudoku = true thì return true
      grid[row][col] := 0  // backtrack
  done
  return false
End

Ví dụ (C++)

#include <iostream>
#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) {
  for (int row = 0; row < N; row++) if (grid[row][col] == num) return true;
  return false;
}

bool isPresentInRow(int row, int num) {
  for (int col = 0; col < N; col++) if (grid[row][col] == num) return true;
  return false;
}

bool isPresentInBox(int boxStartRow, int boxStartCol, int num) {
  for (int row = 0; row < 3; row++)
    for (int col = 0; col < 3; col++)
      if (grid[row+boxStartRow][col+boxStartCol] == num) return true;
  return false;
}

void sudokuGrid() {
  for (int row = 0; row < N; row++) {
    for (int col = 0; col < N; col++) {
      if(col == 3 || col == 6) cout << " | ";
      cout << grid[row][col] << " ";
    }
    if(row == 2 || row == 5) {
      cout << endl;
      for(int i = 0; i < N; i++) cout << "---";
    }
    cout << endl;
  }
}

bool findEmptyPlace(int &row, int &col) {
  for (row = 0; row < N; row++)
    for (col = 0; col < N; col++)
      if (grid[row][col] == 0) return true;
  return false;
}

bool isValidPlace(int row, int col, int num) {
  return !isPresentInRow(row, num) && !isPresentInCol(col, num) && !isPresentInBox(row - row%3, col - col%3, num);
}

bool solveSudoku() {
  int row, col;
  if (!findEmptyPlace(row, col)) return true;
  for (int num = 1; num <= 9; num++) {
    if (isValidPlace(row, col, num)) {
      grid[row][col] = num;
      if (solveSudoku()) return true;
      grid[row][col] = 0;
    }
  }
  return false;
}

int main() {
  if (solveSudoku()) sudokuGrid();
  else cout << "No solution exists";
}

Kết quả đầu ra

3 1 6 | 5 7 8 | 4 9 2
5 2 9 | 1 3 4 | 7 6 8
4 8 7 | 6 2 9 | 5 3 1
------------------------
2 6 3 | 4 1 5 | 9 8 7
9 7 4 | 8 6 3 | 1 2 5
8 5 1 | 7 9 2 | 6 4 3
------------------------
1 3 8 | 9 4 7 | 2 5 6
6 9 2 | 3 5 1 | 8 7 4
7 4 5 | 2 8 6 | 3 1 9