Bài toán Sudoku

Trong bài này mình sẽ hướng dẫn các bạn giải bài toán siêu kinh điển Sudoku bằng giải thuật quay lui.
Cách chơi: Bàn cờ hình vuông được chia làm 9x9 ô vuông nhỏ, trong đó có một số ô vuông được đánh số từ 1->9 trước. Nhiệm vụ của chúng ta là điền tiếp các số từ 1->9 vào các ô còn lại sao cho: hàng ngang, hàng dọc và các khối vuông 3x3 của bàn cờ là các số khác nhau từ 1->9 (Hình ảnh được lấy từ wikipedia).

Ý tưởng: Ta coi Sudoku là một ma trận 9x9 và dùng giải thuật quay lui để thử từng giá trị vào các ô trống theo từng hàng.

Code C/C++

bool Feasible(int a[][9], int x, int y, int k)
{
 for (int i = 0; i < 9; i++){
  if (k == a[x][i]) return 0;
  if (k == a[i][y]) return 0;
 }
 for (int i = x / 3 * 3; i <= x / 3 * 3 + 2; i++)
  for (int j = y / 3 * 3; j <= y / 3 * 3 + 2; j++)
   if (k == a[i][j]) return 0;
 return 1;
}
void SUDOKU(int a[][9], int x, int y)
{
 if (y == 9)
 {
  if (x == 8)
   exit(0);
  return SUDOKU(a, x + 1, 0);
 }
 else if (a[x][y] == 0)//nếu a[x][y] chưa được điền số nào
 {
  for (int k = 1; k <= 9; k++)
  {
   if (Feasible(a, x, y, k))//nếu giá trị k thỏa mãn
   {
    a[x][y] = k;
    SUDOKU(a, x, y + 1);
    a[x][y] = 0;
   }
  }
 }
 else
  SUDOKU(a, x, y + 1);
}

Kết quả: đây là thành quả của mình, thật là tuyệt vời. Còn các bạn thì sao, hãy để lại comment để mọi người cùng trao đổi nhé!

Video demo