【C++】バックトラッキングでグリッドの8つのマスに1〜8の数字を条件付きで配置する方法

この記事では、図の中にある8つの丸（マス）に「1」から「8」までの数字を、「数列上で隣り合う数字同士がグリッド上でも隣接しない」という条件を満たすように配置する問題を、C++で解く方法を解説します。

問題の概要

たとえば、入力として次のような3×4のグリッドが与えられたとします。「0」は使用しないマス、「-1」はまだ数字が置かれていない空きマスを表します。

この場合の出力は次のようになります。

  3 5
7 1 8 2
  4 6

この結果では、たとえば「1」と「2」、「7」と「8」のように数列で連続する数字が、グリッド上で上下左右・斜めに隣り合わないように配置されています。

解法のアプローチ：バックトラッキング

この種の制約充足問題は、バックトラッキング（探索の巻き戻し）を使うのが定番です。全体の流れは以下の通りです。

• グリッドのサイズは N = 3、M = 4 とします。
• 未使用のマスを表す定数 NOTCONSIDERED = -1 を定義します。
• present_in_grid(): 指定した数字がすでにグリッド内に存在するかどうかを判定します。
• isSafe(): 現在のマス（row, col）に数字 num を置いてもよいかを、周囲のマスとの差が1以下にならないかチェックして判定します。
• search_free_location(): まだ埋まっていないマス（NOTCONSIDERED のマス）を探します。
• Solve(): 空きマスがなければ解発見（true を返す）。そうでなければ、1〜8の各数字について isSafe() で安全確認を行い、安全ならその数字を仮置きして再帰的に Solve() を呼び出します。失敗したらマスを NOTCONSIDERED に戻して次の候補を試します。

isSafe() のポイント

グリッドの端や角では隣接するマスの位置が異なるため、isSafe() 内ではマスの座標（row, col）ごとに場合分けをして、実際に隣接しているマスだけをチェックしています。これにより、配列外参照を避けつつ正しく制約を検証できます。

C++での実装例

それでは、実際のコードを見てみましょう。

#include <cmath>
#include <iostream>
#define N 3
#define M 4
#define NOTCONSIDERED -1
using namespace std;
bool present_in_grid(int grid[N][M], int num) {
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++)
            if (grid[i][j] == num)
                return true;
    }
    return false;
}
bool isSafe(int grid[N][M], int row, int col, int num) {
    if (row == 0 && col == 1) {
        if (present_in_grid(grid, num) || (abs(num - grid[row][col + 1]) <= 1) || (abs(num - grid[row + 1][col]) <= 1) || (abs(num - grid[row + 1][col - 1]) <= 1) || (abs(num - grid[row + 1][col + 1]) <= 1))
            return false;
    }
    else if (row == 0 && col == 2) {
        if (present_in_grid(grid, num) || (abs(num - grid[row][col - 1]) <= 1) || (abs(num - grid[row + 1][col]) <= 1) || (abs(num - grid[row + 1][col + 1]) <= 1) || (abs(num - grid[row + 1][col - 1]) <= 1))
            return false;
    }
    else if (row == 1 && col == 0) {
        if (present_in_grid(grid, num) || (abs(num - grid[row - 1][col + 1]) <= 1) || (abs(num - grid[row][col + 1]) <= 1) || (abs(num - grid[row + 1][col + 1]) <= 1))
            return false;
    }
    else if (row == 1 && col == 3) {
        if (present_in_grid(grid, num) || (abs(num - grid[row - 1][col - 1]) <= 1) || (abs(num - grid[row][col - 1]) <= 1) || (abs(num - grid[row + 1][col - 1]) <= 1))
            return false;
    }
    else if (row == 2 && col == 1) {
       if (present_in_grid(grid, num) || (abs(num - grid[row - 1][col - 1]) <= 1) || (abs(num - grid[row - 1][col]) <= 1) || (abs(num - grid[row - 1][col + 1]) <= 1) || (abs(num - grid[row][col + 1]) <= 1))
           return false;
    }
    else if (row == 2 && col == 2) {
        if (present_in_grid(grid, num) || (abs(num - grid[row][col - 1]) <= 1) || (abs(num - grid[row - 1][col]) <= 1) || (abs(num - grid[row - 1][col + 1]) <= 1) || (abs(num - grid[row - 1][col - 1]) <= 1))
            return false;
    }
    else if (row == 1 && col == 1) {
        if (present_in_grid(grid, num) || (abs(num - grid[row][col - 1]) <= 1) || (abs(num - grid[row - 1][col]) <= 1) || (abs(num - grid[row - 1][col + 1]) <= 1) || (abs(num - grid[row][col + 1]) <= 1) || (abs(num - grid[row + 1][col + 1]) <= 1) || (abs(num - grid[row + 1][col]) <= 1))
            return false;
    }
    else if (row == 1 && col == 2) {
        if (present_in_grid(grid, num) || (abs(num - grid[row][col - 1]) <= 1) || (abs(num - grid[row - 1][col]) <= 1) || (abs(num - grid[row + 1][col - 1]) <= 1) || (abs(num - grid[row][col + 1]) <= 1) || (abs(num - grid[row - 1][col - 1]) <= 1) || (abs(num - grid[row + 1][col]) <= 1))
            return false;
    }
    return true;
}
bool search_free_location(int grid[N][M], int& row, int& col) {
    for (row = 0; row < N; row++)
    for (col = 0; col < M; col++) {
        if (grid[row][col] == NOTCONSIDERED)
            return true;
    }
    return false;
}
void show_res(int grid[N][M]) {
    for (int i = 0; i < N; i++) {
        if (i == 0 || i == N - 1)
            cout << " ";
        for (int j = 0; j < M; j++) {
            if (grid[i][j] == 0)
                cout << " ";
            else
                cout << grid[i][j] << " ";
        }
        cout << endl;
    }
}
bool Solve(int grid[N][M]) {
    int row, col;
    if (!search_free_location(grid, row, col))
    return true;
    for (int num = 1; num <= 8; num++) {
        if (isSafe(grid, row, col, num)) {
            grid[row][col] = num;
            if (Solve(grid))
                return true;
            grid[row][col] = NOTCONSIDERED;
        }
    }
    return false;
}
int main(){
    int grid[N][M] = { { 0, -1, -1, 0 },
        { -1, -1, -1, -1 },
        { 0, -1, -1, 0 } };
    if (Solve(grid))
        show_res(grid);
    else
        cout << "Not possible";
}

入力

{ { 0, -1, -1, 0 },
{ -1, -1, -1, -1},
{ 0, -1, -1, 0 }}

出力

  3 5
7 1 8 2
  4 6

まとめ

このプログラムは、典型的なバックトラッキングの構造（候補を試す → 再帰的に探索 → 失敗したら元に戻す）をそのまま活用しています。isSafe() の隣接チェックを一般化すれば、任意サイズのグリッドにも対応できるので、応用の幅は広いでしょう。