LearnToBecomeAnExpert

Tiếp tục series về giải thuật đệ quy , mình giới thiệu các bạn về bài toán n quân hậu (n Queens). Đối với bạn đã từng chơi cờ vua thì chắc các bạn cũng hình dung ra bài toán như thế nào và cũng biết cách giải quyết vấn đề đó trên bàn cờ, hôm nay mình sẽ giải quyết nó bằng ngôn ngữ lập trình. Cụ thể là thuật toán quay lui. Giới thiệu đôi chút về bài toán: Cho bàn cờ kích thước nxn và n con hậu, hãy tìm cách đặt n con hậu trên bàn cờ sao cho n con hậu không ăn được nhau, quân hậu trong bàn cờ vua có thể đi thẳng, ngang, chéo trên khắp bàn cờ nhé!. Hình bên dưới là một trường hợp bàn cờ vua kích thước 8x8 và 8 con hậu được đặt vào vị trí thỏa mãn bài toán mà thuật giải tìm được (hình ảnh được lấy từ Wikipedia ). +expand source //bài toán n quân hậu //lưu ý hàng, cột bắt đầu từ 0 đến n-1 void  Queen( int  a[],  int  n,  int  r) //mảng a[] để lưu giá trị...

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     if  (k == a[x][i])  return  0;    if  (k == a[i][y])  return  0;  }   for  ( int  i = x / 3 * 3; i     for  ( int  j = ...