Задача о 8 ферзях с помощью алгоритма Лас Вегас

[polygraph]

Здравствуйте, подскажите , пожалуйста, как можно реализовать алгоритм для задачи о 8 ферзях (где условие такое, что ферзи не должны бить друг друга) с помощью алгоритма Лас Вегас на с++

[polygraph]

Немного материала нашёл
можно применить алгоритм Лас-Вегаса; на самом деле это более эффективно, чем возврат. Разместите 8 ферзей на шахматной доске, чтобы никто не напал на другую. Помните, что ферзь атакует другие фигуры в том же ряду, столбце и диагоналях. Предположим, что k строк, 0 ≤ k ≤ 8, успешно заняты ферзями. Если k = 8, то остановимся успешно. В противном случае перейдите к строке k + 1. Подсчитайте все позиции в этом ряду, не атакованные существующими ферзями. Если таковых нет, то не получится. В противном случае выберите один случайным образом, увеличьте k и повторите. Обратите внимание, что алгоритмы просто не работают, если ферзь не может быть размещен. Но этот процесс можно повторять, и каждый раз будет генерироваться другая аранжировка.

[Desc]

Так а алгоритм Лас-Вегас как выглядит.
Или тот бред, посом выше, и есть алгоритм.
Если так, то как могут столько ферзей разместиться на одном поле?

[BDA]

Если верить Вики (ссылка), то алгоритм Лас-Вегаса:

Выполнить алгоритм A с результатом r до тех пор, пока K(r) не будет истиной.

А текст выше описывает сами алгоритмы A и K. На питоне это будет выглядеть примерно так:

from random import randint

def f(k, e):
    if k == 8:
        print(e)
        for x, _ in e:
            print(('-' * x) + '*' + ('-' * (7 - x)))
        return True
    candidates = []
    for i in range(8):
        for x, y in e:
            if x == i or abs(y - k) == abs(x - i):
                break
        else:
            candidates.append((i, k))
    if candidates:
        e.append(candidates[randint(0, len(candidates) - 1)])
        res = f(k + 1, e)
        if res:
            return True
    return False

def main():
    while True:
        res = f(0, [])
        if res:
            break

main()

На плюсы уж как-нибудь сами переложите

[polygraph]

Сообщение от Desc

Так а алгоритм Лас-Вегас как выглядит.
Или тот бред, посом выше, и есть алгоритм.
Если так, то как могут столько ферзей разместиться на одном поле?

Тот бред, который выше, это алгоритм

[polygraph]

Сообщение от BDA

Если верить Вики (ссылка), то алгоритм Лас-Вегаса:

А текст выше описывает сами алгоритмы A и K. На питоне это будет выглядеть примерно так:

from random import randint

def f(k, e):
    if k == 8:
        print(e)
        for x, _ in e:
            print(('-' * x) + '*' + ('-' * (7 - x)))
        return True
    candidates = []
    for i in range(8):
        for x, y in e:
            if x == i or abs(y - k) == abs(x - i):
                break
        else:
            candidates.append((i, k))
    if candidates:
        e.append(candidates[randint(0, len(candidates) - 1)])
        res = f(k + 1, e)
        if res:
            return True
    return False

def main():
    while True:
        res = f(0, [])
        if res:
            break

main()

На плюсы уж как-нибудь сами переложите

Подскажите, как можно все решения задачи вывести на экран и показать количество решений?
Для задачи 8х8 это будет 92 решения. там почему-то 60 решений показало

[BDA]

Сообщение от polygraph

Для задачи 8х8 это будет 92 решения. там почему-то 60 решений показало

Да, вроде, 92 и показало.

from random import randint

sols = 0

def f(k, e):
    global sols
    if k == 8:
        print(e)
        for x, _ in e:
            print(('-' * x) + '*' + ('-' * (7 - x)))
        sols += 1
        return
    for i in range(8):
        for x, y in e:
            if x == i or abs(y - k) == abs(x - i):
                break
        else:
            new_e = list(e)
            new_e.append((i, k))
            f(k + 1, new_e)

def main():
    f(0, [])
    print("solutions:", sols)

main()

[polygraph]

BDA, спасибо большое

[polygraph]

BDA, ещё, подскажите, в алгоритме Лас Вегас как я понял, должно же быть рандомное заполнение доски ферзями и проверять бьет ли ферзь другого или нет. Так же? А то я просто я не увидел это до 2 программе

[BDA]

Ну да, во второй программе нет рандома, а перебор с возвратом. Только первая программа реализует алгоритм Лас Вегас. Просто таким способом искать все возможные решения может быть достаточно долго.