回溯问题

分书问题：5 个人 5 本书，每人一本书 国际象棋中，每一行，列，斜线，不能存在多个皇后 数学思想：n✖️n 模型的填充互斥问题

分书问题

#include <iostream>
using namespace std;

int Num; // 方案数
int take[5]; // 5本书分别给谁
bool assigned[5]; // 五本书是否已分配
// 行表示人，0表示不喜欢，1表示喜欢， 列表示书
int like[5][5] = {
  {0, 0, 1, 1, 0},
  {1, 1, 0, 0, 1},
  {0, 1, 1, 0, 1},
  {0, 0, 0, 1, 0},
  {0, 1, 0, 0, 1}
};

// try 当前行
// 如果已完成所有行
// 则找到一个合理方案，输出它，返回
// 枚举当前的每一列
// 进行尝试
void Try(int id)
{
  // 递归中止条件，所有读者均已分配合适书籍
  if(id == 5)
  {
    // 方案数加1
    Num++;
    // 输出方案细节
    cout << "第" << Num << "个方案（按ABCDE次序）：" << endl;
    for(int i = 0; i < 5; i++)
      cout << take[i] << ' ';
    cout << endl;
    return;
  }
  // 逐一为每本书找到合适的读者
  for(int book = 0; book <= 4; book++)
  {
    // 是否满足这本书的分配情况
    if(like[id][book] == 1 && !assigned[book])
    {
      // 记录当前这本书的分配情况
      take[id] = book;
      assigned[book] = true;
      // 为下一为读者分配合适的书籍
      Try(id + 1);
      // 将书退还（回溯），尝试另一种方案
    } // __if__
  }// __for__
}

int main()
{
  Num = 0; // 分书方案数初始值
  for(int book = 0; book < 5; book++)
    assigned[book] = false;
  // 从第0个人开始分书
  Try(0);
  return 0;
}

八皇后问题

#include <iostream>
using namespace std;

const int Normalize = 9; // 用来统一数组下标
int Num; // 方案数
int q[9]; // 8个皇后所占用的行号
bool S[9]; // S[1] ~ S[8] 当前行是否安全
bool L[17]; // L[2] ~ L[16] (i - j) 对角线是否安全
bool R[17]; // R[2] ~ R[16] (i + j) 对角线是否安全


void Try(int col)
{
  // 递归中止条件，所有列均已被放上皇后了
  if(col == 9)
  {
    Num++;
    // 输出方案细节
    cout << "方案" << Num << "：";
    for(int k = 1; k <= 8; k++)
      cout << q[k] << " ";
    cout << endl;
    return;
  }
  // 依次尝试当前列的8行位置
  for (int row = 0; row <= 8; row++)
  {
    // 判断拟放置皇后的位置是否安全
    if (S[row] &&  R[col + row] && L[col - row + Normalize])
    {
      // 记录位置信息（行号）
      q[col] = row;
      // 修改三个方向的安全性标记
      S[row] = false;
      L[col - row + Normalize] = false;
      R[col + row] = false;
      // 递归尝试放在下一列
      Try(col+ 1);
      // 回溯：恢复三个方向原有安全性
      S[row] = true;
      L[col - row + Normalize] = true;
      R[col + row] = true;
    }

  }

}

int main()
{
  Num = 0;
  for(int i = 0; i < 9; i++)
    S[i] = true;
  for(int i = 0; i < 17; i++)
  {
    L[i] = true;
    R[i] = true;
  }
  Try(1); // 从第1列开始放皇后
  return 0;
}