задача о восьми ферзях на шахматном поле

Форум Программирование Общие вопросы программирования (Dev)

Обучение, бизнес-тренинг, курсы

1. user1200135 05.05.19 10:15 Сейчас в теме

Недавно решил попробовать себя в качестве разработчика, поэтому прошу не пинать- я в этом деле ноль. Давно знаю задачу о восьми ферзях на шахматном поле, точно знаю что это классическая задача для программистов. Попытался решить самостоятельно, естественно не получилось, прошу помощи. Охота разобраться с тем как это должно работать. Ребята на работе сказали что смотреть нужно в сторону циклов. Привожу код того как я пытался решить эту задачу:

Процедура ИсключениеПоГоризонтали(Фигура,Клетка,горизонталь,вертикаль,ГорЛево,ГорПраво,МатрицаПоля)
	Пока   ГорЛево>=0 Цикл
	  МатрицаПоля[ГорЛево][вертикаль]= клетка;
	  Сообщить ("("+ГорЛево+")"+"("+вертикаль+")"+МатрицаПоля[ГорЛево][вертикаль]);
	ГорЛево= ГорЛево-1;
	КонецЦикла;
	Пока ГорПраво<=7 Цикл 
		МатрицаПоля[ГорПраво][вертикаль]= клетка;
		Сообщить ("("+ГорПраво+")"+"("+вертикаль+")"+МатрицаПоля[ГорПраво][вертикаль]);
	ГорПраво=ГорПраво+1;
	КонецЦикла;
КонецПроцедуры
Процедура ИсключениеПоВертикали(Фигура,Клетка,горизонталь,вертикаль,ВертВниз,ВертВверх,МатрицаПоля) 
	Пока   ВертВниз>=0 Цикл
	  МатрицаПоля[горизонталь][ВертВниз]= клетка;
	  Сообщить ("("+горизонталь+")"+"("+ВертВниз+")"+МатрицаПоля[горизонталь][ВертВниз]);
	ВертВниз= ВертВниз-1;
	КонецЦикла;
	Пока ВертВверх<=7 Цикл 
		МатрицаПоля[горизонталь][ВертВверх]= клетка;
		Сообщить ("("+горизонталь+")"+"("+ВертВверх+")"+МатрицаПоля[горизонталь][ВертВверх]);
	ВертВверх=ВертВверх+1;
	КонецЦикла;

КонецПроцедуры
Процедура ИсключениеПоДиагонали (Фигура,Клетка,горизонталь,вертикаль,ВертВнизД,ВертВверхД,ГорЛевоД,ГорПравоД,МатрицаПоля)
	Пока   ВертВнизД>=0 и ГорЛевоД>=0 цикл
		МатрицаПоля[ГорЛевоД][ВертВнизД]=Клетка;
		Сообщить("("+ГорЛевоД+")"+"("+ВертВнизД+")"+МатрицаПоля[ГорЛевоД][ВертВнизД]);
		   ВертВнизД=ВертВнизД-1;
		   ГорЛевоД=ГорЛевоД-1;
	КонецЦикла;
	Пока   ГорПравоД<=7 и ВертВверхД<=7 Цикл 
		МатрицаПоля[ГорПравоД][ВертВверхД]=Клетка;
		Сообщить ("("+ГорПравоД+")"+"("+ВертВверхД+")"+МатрицаПоля[ГорПравоД][ВертВверхД]);
		   ГорПравоД=ГорПравоД+1;
		   ВертВверхД=ВертВверхД+1;
    КонецЦикла;
КонецПроцедуры
Процедура ИсключениеПоДиагоналиОбр (Фигура,Клетка,горизонталь,вертикаль,ВертВнизДОБр,ВертВверхДОБр,ГорЛевоДОБр,ГорПравоДОБр,МатрицаПоля)
	Пока  ГорЛевоДОБр>=0 и ВертВверхДОБр<=7 цикл
		МатрицаПоля[ГорЛевоДОБр][ВертВверхДОБр]=Клетка;
		Сообщить("("+ГорЛевоДОБр+")"+"("+ВертВверхДОБр+")"+МатрицаПоля[ГорЛевоДОБр][ВертВверхДОБр]);
		   ВертВверхДОБр=ВертВверхДОБр+1;
		   ГорЛевоДОБр=ГорЛевоДОБр-1;
	КонецЦикла;
	Пока   ГорПравоДОБр<=7 и ВертВнизДОБр<=0 Цикл 
		МатрицаПоля[ГорПравоДОБр][ВертВнизДОБр]=Клетка;
		Сообщить ("("+ГорПравоДОБр+")"+"("+ВертВнизДОБр+")"+МатрицаПоля[ГорПравоДОБр][ВертВнизДОБр]);
		   ГорПравоДОБр=ГорПравоДОБр+1;
		   ВертВнизДОБр=ВертВнизДОБр-1;
    КонецЦикла;
КонецПроцедуры
Процедура  ОбходМассива(МатрицаПоля)
	Для каждого ЭлементМассива из  МатрицаПоля Цикл 
       Сообщить ("["+ЭлементМассива[0]+"]"+"["+ЭлементМассива[1]+"]"+"["+ЭлементМассива[2]+"]"+"["+ЭлементМассива[3]+"]"+"["+ЭлементМассива[4]+"]"+
	   "["+ЭлементМассива[5]+"]"+"["+ЭлементМассива[6]+"]"+
	   "["+ЭлементМассива[7]+"]")
		
	КонецЦикла;
КонецПроцедуры




МатрицаПоля = новый Массив (8,8);

Фигура = Истина;
Клетка= Ложь;
горизонталь=3;
вертикаль=3;


МатрицаПоля[горизонталь][вертикаль]= Фигура ;
ГорЛево= Горизонталь-1 ;
ГорПраво= Горизонталь+1 ;
ВертВниз=вертикаль-1;
ВертВверх=вертикаль+1;


ГорЛевоД= Горизонталь-1 ;
ГорПравоД= Горизонталь+1 ;
ВертВнизД=вертикаль-1;
ВертВверхД=вертикаль+1;  

ГорЛевоДОБр= Горизонталь-1 ;
ГорПравоДОБр= Горизонталь+1 ;
ВертВнизДОБр=вертикаль-1;
ВертВверхДОБр=вертикаль+1;



ИсключениеПоГоризонтали(Фигура,Клетка,горизонталь,вертикаль,ГорЛево,ГорПраво,МатрицаПоля);
ИсключениеПоВертикали(Фигура,Клетка,горизонталь,вертикаль,ВертВниз,ВертВверх,МатрицаПоля) ;
ИсключениеПоДиагонали (Фигура,Клетка,горизонталь,вертикаль,ВертВнизД,ВертВверхД,ГорЛевоД,ГорПравоД,МатрицаПоля);
ИсключениеПоДиагоналиОбр (Фигура,Клетка,горизонталь,вертикаль,ВертВнизДОБр,ВертВверхДОБр,ГорЛевоДОБр,ГорПравоДОБр,МатрицаПоля);
ОбходМассива(МатрицаПоля);

Показать

Буду рад любым ответам. Задача действительно интересная и абсолютно для меня пока что не понятная.

По теме из базы знаний

Минимализмы

Ответы

Подписаться на ответы Инфостарт бот

Свернуть все

6. VladimirB 17 05.05.19 18:31 Сейчас в теме

(1) https://forany.xyz/a-16?pg=11

2. nayd 10 05.05.19 10:53 Сейчас в теме

Сформулируйте задачу, которую хотите решить, полностью.

- Построить одно, любое решение задачи.
- Аналитически доказать, что решение существует.
- Определить количество решений.
- Построить все возможные решения.
- Одна из типовых задач по программированию алгоритмов перебора: создать компьютерную программу, находящую все возможные решения задачи.

3. nayd 10 05.05.19 10:59 Сейчас в теме

Втупую перебирать все варианты - долго по времени и неоптимально. Поэтому нужно оптимизировать и уменьшать количество вариантов.
Вот, например, подсказка, как решить нахождение всех возможных расстановок:

Один из типовых алгоритмов решения задачи — использование поиска с возвратом: первый ферзь ставится на первую горизонталь, затем каждый следующий пытаются поставить на следующую так, чтобы его не били ранее установленные ферзи. Если на очередном этапе постановки свободных полей не оказывается, происходит возврат на шаг назад — переставляется ранее установленный ферзь.

https://ru.wikipedia.org/wiki/%D0%97%D0%B0%D0%B4%D0%B0%D1%87%D0%B0_%D0%BE_%D0%B2%D0%BE%D1%81%D1%8C%D0%BC%D0%B8_%D1%84%D0%B5%D1%80%D0%B7%D1%8F%D1%85

4. user1200135 05.05.19 11:41 Сейчас в теме

задача стоит в том как вообще средствами встроенного языка эту задачу решить. Допустим найти хотя бы одно решение, ибо у меня не получилось пока даже одно найти

5. nayd 10 05.05.19 12:04 Сейчас в теме

(4) ОК. Наша задача "найти хотя бы одно решение расположения 8 ферзей на доске 8х8".
Можем действовать методом перебора.
Или одним из методов решения этой задачи, приведенных в книга по шахматным задачкам.

Расположим ферзей ходом коня со второй вертикали по (n/2 - 2)-ю, начиная с третьей горизонтали, и далее с (n/2 + 3)-й вертикали по (n - 1)-ю, начиная с шестой горизонтали. В результате свободными останутся шесть вертикалей и шесть горизонталей доски, на которых шесть ферзей должны занять поля с такими координатами: (1, n - 3), (n/2 - 1, 1); (n/2, n - 1), (n/2 + 1, 2), (n/2 + 2, n), (n, 4).

Подставьте сюда n = 8

Оставьте у себя:
МатрицаПоля = новый Массив (8,8);
И затем проставьте координаты ферзей:
МатрицаПоля[1][2] = Истина;
МатрицаПоля[6][5] = Истина;
МатрицаПоля[0][4] = Истина;
МатрицаПоля[2][0] = Истина;
МатрицаПоля[3][6] = Истина;
МатрицаПоля[4][1] = Истина;
МатрицаПоля[5][7] = Истина;
МатрицаПоля[7][3] = Истина;

Интереснее, конечно, методом перебора. Как я описал в (3) сообщении

7. acanta 05.05.19 18:42 Сейчас в теме

(5) интереснее вручную.

8. user1200135 05.05.19 20:11 Сейчас в теме

вручную интреснее однозначно, может кто то может рассказать как реализовать метод перебора в данной задаче? выложенному мною коду при запуске становиться понятно что после четвертого выставленного ферзя схема ломается потому что нет проверки на уже расставленные фигуры и я не понимаю как средствами языка это доделать. Вроде существует

Попытка
исключение 
конецПопытки

, но я не понимаю как эта конструкция работает, а из того что вычитал похоже что эта конструкция не прокатит в данном конкретном случае. Может кто то уже решал задачу? Ответ уважаемого Nayd мне в принципе понятен, но например, решая такую задачу на какой нибудь олимпиаде, вряд ли под рукой будет справочник по шахматному делу... Решение этой задачи в других языках есть в свободном доступе на том же YouTube для C++.

9. catv 05.05.19 20:46 Сейчас в теме

Поле может подпадать под удар нескольких фигур. Ячейка массива:
0 - свободно; +100 ставим фигуру; +1 добавляем возможность удара одной фигуры; -100 снимаем фигуру; -1 снимаем удар одной фигуры

Оставьте свое сообщение

E-mail: