Пример алгоритма 8-Queens?

Вот простая Java-реализация наивного рекурсивного алгоритма; это должно быть поучительно.

public class NQueens {
    final static int N = 4;
    static int[] position = new int[N];

    public static void main(String[] args) {
        solve(0);
    }

    static boolean isSafe(int k, int p) {
//      for (int i = 1; i <= k; i++) {
//          int other = position[k - i];
//          if (other == p || other == p - i || other == p + i) {
//              return false;
//          }
//      }
        return true;
    }
    static void solve(int k) {
        if (k == N) {
            System.out.println(java.util.Arrays.toString(position));
        } else {
            for (char p = 0; p < N; p++) {
                if (isSafe(k, p)) {
                    position[k] = p;
                    solve(k+1);
                }
            }
        }
    }
}

Обратите внимание, что isSafe сейчас содержит закомментированные строки; это сделано специально. С комментариями этих строк программа становится рекурсивным генератором N-кортежей, где каждое значение находится между 0 (включительно) и N (исключительно). То есть программа как есть генерирует следующий вывод:

[0, 0, 0, 0]
[0, 0, 0, 1]
[0, 0, 0, 2]
[0, 0, 0, 3]
[0, 0, 1, 0]
[0, 0, 1, 1]
[0, 0, 1, 2]
[0, 0, 1, 3]
:
:
[3, 3, 3, 0]
[3, 3, 3, 1]
[3, 3, 3, 2]
[3, 3, 3, 3]

Эта генерация N-кортежей является конкретной подзадачей проблемы NQueens. В stackoverflow уже есть много вопросов о том, как писать N-вложенные циклы, когда вы не знаете, что такое N. Я чувствую, что полезно временно остановиться на этой проблеме и сначала понять ее решение, закомментировав isSafe просто return true;, чтобы сначала понять, что делает рекурсия.

Как только вы убедитесь, что этот рекурсивный генератор кортежей работает, просто раскомментируйте эти строки, и вы получите простой, наивный, но работающий решатель NQueens. С раскомментированными строками N=5 и isSafe программа теперь генерирует следующий вывод:

[0, 2, 4, 1, 3]
[0, 3, 1, 4, 2]
[1, 3, 0, 2, 4]
[1, 4, 2, 0, 3]
[2, 0, 3, 1, 4]
[2, 4, 1, 3, 0]
[3, 0, 2, 4, 1]
[3, 1, 4, 2, 0]
[4, 1, 3, 0, 2]
[4, 2, 0, 3, 1]

Каждая строка является решением задачи о пяти ферзях. i-й элемент массива обозначает позицию строки i-го ферзя, расположенного в i-м столбце (все индексы отсчитываются от 0). Итак, первое решение выглядит на доске так:

[0,2,4,1,3]

 Q · · · ·
 · · · Q ·
 · Q · · ·
 · · · · Q
 · · Q · ·

Я оставлю это в качестве упражнения, чтобы понять, почему isSafe работает, и как распечатать макет платы, и как реализовать более быстрые, но более сложные рекурсивные алгоритмы.

Приятного обучения.

Суть проблемы восьми ферзей часто состоит в том, чтобы проиллюстрировать силу поиска в сочетании с отсечением. Вы можете в значительной степени выполнить поиск методом грубой силы в пространстве поиска, но исключить любое частичное решение, когда оно нарушает ограничения решения (т. Е. Один ферзь проверяет другого).

Просто используя эту обрезку, 8-ферзей легко решить.

Если вам нужны более эффективные решения, которые были бы полезны, например, для. 100 или 1000 ферзей — это совсем другая история, и вы можете посмотреть на материал в википедии. Но для 8-ферзей достаточно грубой силы и обрезки. (т. е. выполнить поиск в глубину пространства поиска, исключив любой промежуточный узел, который включает ферзя под шахом).

чтобы разместить ферзя в строке r:

if r = 0 then you're done -- return ok
for each c [1 .. 8]:
  if (r,c) is safe:
    mark (r,c)
    if you can place queen on row r-1 then return ok
    unmark (r,c)  (if you're here, this c won't work)
return not ok     (if you're here, no c generated a solution)

(r,c) безопасно, если для каждой строки [r+1 .. 8]:

• (ряд, c) не отмечен
• c - (row - r) ‹ 1 или (row, c - (row - r)) не отмечен
• c + (строка - r) > 8 или (строка, c + (строка - r)) не отмечен

Из Википедии:

Эта эвристика находит n ферзей для любых n n ≥ 4 или n = 1:

1. Разделите n на 12. Запомните остаток (n равно 8 для головоломки с восемью ферзями).
2. Напишите список четных чисел от 2 до n по порядку.
3. Если остаток равен 3 или 9, переместите 2 в конец списка.
4. Добавьте нечетные числа от 1 до n по порядку, но, если в остатке 8, поменяйте местами пары (например, 3, 1, 7, 5, 11, 9, …).
5. Если остаток равен 2, поменяйте местами 1 и 3, затем переместите 5 в конец списка.
6. Если остаток равен 3 или 9, переместите 1 и 3 в конец списка.
7. Поместите ферзя из первого столбца в ряд с первым номером в списке, поместите ферзя из второго столбца в ряд со вторым номером в списке и т. д.

Вот простое решение С#, я думаю, оно работает

public static class EightQueens
    {
        static   int[] board = new int[8];
        static int MaxRows = 8, MaxCols = 8;
        public static int[] GetPosition()
        {
            if (GetPosition(0)) return board;
            else return null;
        }
        public static bool IsCollision(int row, int col)
        {
            for (int i = 0; i < col; i++)
            {
                if (board[i] == row) return true; // Same Row
                if ((board[i] + col - i == row) || (board[i] - col + i == row))
                    return true;
            }
            return false;

        }
        public static bool GetPosition(int col)
        {
            if (col == MaxCols) return true;
            for (int row = 0; row < MaxRows; row++)
                if (!IsCollision(row, col))
                {
                    board[col] = row;
                    if (GetPosition(col + 1)) return true;
                }
            return false;

        }
    }

В EWD316 Дейкстра находит решение задачи о восьми королевах. скорее формально. Попробуйте, может вам понравится!

public class NQueensSolver
{
    private readonly List<int[]> _solutions = new List<int[]>();
    private readonly int[] _current;
    public int N { get; private set; }

    public NQueensSolver(int n)
    {
        N = n;
        _current = new int[N];
    }

    public IList<int[]> FindAllFormations()
    {
        PopulateFormations(0);
        return _solutions;
    }

    private void PopulateFormations(int row)
    {
        if (row == N)
        {
            _solutions.Add(_current.ToArray());
            return;
        }

        for (int col = 0; col <= N-1; col++)
        {
            if (Threatened(row, col))
                continue;

            _current[row] = col;
            PopulateFormations(row + 1);
        }
    }

    private bool Threatened(int row, int col)
    {
        for (int i = 0; i <= row - 1; i++)
            if (_current[i] == col || row - i == Math.Abs(col - _current[i]))
                return true;

        return false;
    }
}

Некоторые тесты:

[TestMethod]
public void TestNQueens()
{
  Assert.AreEqual(1, new NQueensSolver(1).FindAllFormations().Count);
  Assert.AreEqual(0, new NQueensSolver(2).FindAllFormations().Count);
  Assert.AreEqual(0, new NQueensSolver(3).FindAllFormations().Count);
  Assert.AreEqual(2, new NQueensSolver(4).FindAllFormations().Count);
  Assert.AreEqual(10, new NQueensSolver(5).FindAllFormations().Count);
  Assert.AreEqual(4, new NQueensSolver(6).FindAllFormations().Count);
  Assert.AreEqual(40, new NQueensSolver(7).FindAllFormations().Count);
  Assert.AreEqual(92, new NQueensSolver(8).FindAllFormations().Count);
  Assert.AreEqual(352, new NQueensSolver(9).FindAllFormations().Count);
  Assert.AreEqual(724, new NQueensSolver(10).FindAllFormations().Count);
}

Это простое решение на С#.

//----N Queens ----
public static bool NQueens(bool[,] board, int x)
{
      for (int y = 0; y < board.GetLength(1); y++)
      {
          if (IsAllowed(board, x, y))
          {
               board[x, y] = true;
               if (x == board.GetLength(0) - 1 || NQueens(board, x + 1))
               {
                   return true;
               }
               board[x, y] = false;
          }
     }
     return false;
}
//verify diagonals, column and row from i=0 to x because from x to down it dont put anything
private static bool IsAllowed(bool[,] board, int x, int y)
{
    for (int i = 0; i <= x; i++)
    {
        if (board[i, y] || (i <= y && board[x - i, y - i]) || (y + i < board.GetLength(0) && board[x - i, y + i]))
        {
            return false;
        }
    }
    return true;
}

В TheWalnut.io есть визуализация N-Королев: это считается ограничением проблема удовлетворения и использует алгоритм локального поиска (с эвристикой минимальных конфликтов) для ее решения. Код (на Javascript) также есть.

Визуализация предназначена для частного случая N == 8, но ее можно изменить на любое N.

Я написал подробный, прокомментированный пример проблемы N Queens в Python и выложить на GitHub. Взглянем!

Я решил это, развернув С++, посмотрите правильные шаги на терминале.

Дополнительные сведения можно найти на странице my queen.cpp.

функция размещения шахмат

void amo::Queen::place(int probing, int n) {
    if (n != row || n != col ) {
        if (chess != nullptr) {
            for (int i=0;i<row;i++) delete *(chess+i);
            delete chess;
        }   
        row = n;
        col = n;
        chess = new int*[n];
        for (int i=0;i<n;i++) {
            *(chess+i) = new int[col];
            for (int j=0; j<col; j++) 
                *(*(chess+i)+j) = 100*(i+1)+j;
        }
    }
    if (probing >= n) {
        ans += 1;
        std::cout << GREEN <<"[Queen::place()]: returns when met the pass-the-end of probing which means deduced one of answer:" << ans << WHITE << std::endl;
        for (std::vector<int>::iterator it=queens.begin(); it!=std::next(queens.begin(), n); it++)
            collect(moves, 1, std::distance(queens.begin(), it), *it);
        traverse(moves);
        moves.clear();
        return;
    }
    for (int pruning=0; pruning<col; pruning++) {
        track++;
        //traverse(probing, pruning);
        //if (probing==n-1 && pruning==col-1) std::cout << RED <<"[Queen::place()]: track:" << track << WHITE << std::endl; //final track=4^4+4^3+4^2+4^1=340 if n=4 or track=3^3+3^2+3^1=39 if n=3
        if (!check(probing, pruning)) {
        //if (false) { //watching all moves
            //std::cout << "[Queen::place()]: going to prune" << WHITE << std::endl;
            /**
             * 'prunes' when met one of dead ends of this probing at this pruning
             */
            continue;
        }
        else { //found one of rights of this probing at this pruning and digs into the one more deeper 
            //std::cout << "[Queen::place()]: going to probe" << WHITE << std::endl;
            if (queens.size() < n) queens.resize(n);
            queens.at(probing) = pruning;
            /**
             * 'probes' one more deeper by making one more call stack returning back here as backtracking and proceeding to another pruning
             */ 
            place(probing+1, n);
        }
    }
    /**
     * 'backtracks'
     */ 
    return;
}

и функция для проверки того, являются ли ходы решениями

bool amo::Queen::check(int row, int column) {
    if (row == 0) {
        //std::cout << CYAN << "okay chess[" << row <<"][" << column << "]" << WHITE << std::endl;
        return true;
    }
    for (std::vector<int>::iterator it=queens.begin(); it!=std::next(queens.begin(), row); it++) {
        int placed_row = std::distance(queens.begin(), it);
        int placed_column = queens.at(placed_row);
        if (placed_column == column) {
            //std::cout << MAGENTA << "not across,   queen[" << placed_row << "][" << placed_column << "] and chess[" << row <<"][" << column << "]" << WHITE << std::endl;
            return false;
        }
        if (std::abs(placed_column-column) == std::abs(placed_row-row)) {
            //std::cout << MAGENTA << "not diagonal, queen[" << placed_row << "][" << placed_column << "] and chess[" << row <<"][" << column << "]" << WHITE << std::endl;
            return false;
        }
    }
    //std::cout << CYAN << "okay chess[" << row <<"][" << column << "]" << WHITE << std::endl;
    return true;
}

SQL:

with tx1 as (select 1 as k union all select t2.k + 1 from tx1 as t2 where t2.k < 8)

select *
from tx1 as x1
join tx1 as x2 on 
    x2.k <> x1.k and 
    x2.k <> x1.k + 1 and x2.k <> x1.k - 1
join tx1 as x3 on 
    x3.k <> x1.k and x3.k <> x2.k and 
    x3.k <> x2.k + 1 and x3.k <> x2.k - 1 and
    x3.k <> x1.k + 2 and x3.k <> x1.k - 2
join tx1 as x4 on 
    x4.k <> x1.k and x4.k <> x2.k and x4.k <> x3.k and
    x4.k <> x3.k + 1 and x4.k <> x3.k - 1 and
    x4.k <> x2.k + 2 and x4.k <> x2.k - 2 and
    x4.k <> x1.k + 3 and x4.k <> x1.k - 3
join tx1 as x5 on 
    x5.k <> x1.k and x5.k <> x2.k and x5.k <> x3.k and x5.k <> x4.k and
    x5.k <> x4.k + 1 and x5.k <> x4.k - 1 and
    x5.k <> x3.k + 2 and x5.k <> x3.k - 2 and
    x5.k <> x2.k + 3 and x5.k <> x2.k - 3 and 
    x5.k <> x1.k + 4 and x5.k <> x1.k - 4
join tx1 as x6 on 
    x6.k <> x1.k and x6.k <> x2.k and x6.k <> x3.k and x6.k <> x4.k and x6.k <> x5.k     and
    x6.k <> x5.k + 1 and x6.k <> x5.k - 1 and
    x6.k <> x4.k + 2 and x6.k <> x4.k - 2 and
    x6.k <> x3.k + 3 and x6.k <> x3.k - 3 and 
    x6.k <> x2.k + 4 and x6.k <> x2.k - 4 and 
    x6.k <> x1.k + 5 and x6.k <> x1.k - 5
join tx1 as x7 on 
    x7.k <> x1.k and x7.k <> x2.k and x7.k <> x3.k and x7.k <> x4.k and x7.k <> x5.k and x7.k <> x6.k and
    x7.k <> x6.k + 1 and x7.k <> x6.k - 1 and
    x7.k <> x5.k + 2 and x7.k <> x5.k - 2 and
    x7.k <> x4.k + 3 and x7.k <> x4.k - 3 and 
    x7.k <> x3.k + 4 and x7.k <> x3.k - 4 and 
    x7.k <> x2.k + 5 and x7.k <> x2.k - 5 and
    x7.k <> x1.k + 6 and x7.k <> x1.k - 6
join tx1 as x8 on 
    x8.k <> x1.k and x8.k <> x2.k and x8.k <> x3.k and x8.k <> x4.k and x8.k <> x5.k and x8.k <> x6.k and x8.k <> x7.k and
    x8.k <> x7.k + 1 and x8.k <> x7.k - 1 and
    x8.k <> x6.k + 2 and x8.k <> x6.k - 2 and
    x8.k <> x5.k + 3 and x8.k <> x5.k - 3 and 
    x8.k <> x4.k + 4 and x8.k <> x4.k - 4 and 
    x8.k <> x3.k + 5 and x8.k <> x3.k - 5 and
    x8.k <> x2.k + 6 and x8.k <> x2.k - 6 and
    x8.k <> x1.k + 7 and x8.k <> x1.k - 7
order by 1,2,3,4,5,6,7,8