Задача про Fферзей

Hishnik

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

Victor__v

Эм, на работу нужен фортер?
А это проверка мыслительных способностей?

Hishnik

Victor__v писал(а):

Эм, на работу нужен фортер?
А это проверка мыслительных способностей?

Это задачи с прошедшей "внутренней" студенческой олимпиады. Студенты в целом справились...

dmitri

Код:

CREATE MARKS 46 ALLOT
: MINIT MARKS 46 ERASE ;
: MARK? ( i -- flag ) MARKS + DUP C@ -1 ROT C! ;
: HOR? ( hor vert -- flag ) DROP MARK? ;
: VERT? ( hor vert -- flag ) NIP 8 + MARK? ;
: DIAG1? ( hor vert -- flag ) + 16 + MARK? ;
: DIAG2? ( hor vert -- flag ) 7 SWAP - + 31 + MARK? ;
: >COORD ( addr - hor vert ) DUP C@ [CHAR] A - SWAP 1+ C@ [CHAR] 1 - ;
: OVERLAP? ( addr -- flag )
   >COORD 2DUP HOR? >R 2DUP VERT? >R 2DUP DIAG1? >R DIAG2? R> OR 2R> OR OR ;
: SAFE? ( addr u -- flag )
   MINIT 0 ROT ROT 1+ 3 / 0 ?DO DUP OVERLAP? ROT OR SWAP 3 + LOOP DROP 0= ;

S" A7 B4 C2 D8 E6 F1 G3 H5" SAFE? .
S" D5 B7" SAFE? .

Слово SAFE? возвращает TRUE, если размещение каждого из ферзей является безопасным для остальных ферзей. Работает в spf4 и в gforth.

chess

Работает в spf4

Код:

: safe? { \ [ 16 ] x [ 16 ] y sx sy sd sn sm -- true|xy|false  }
8 0 DO 10 /MOD 2DUP x I + C! y I + C! x I + 8 + C! y I + 8 + C! LOOP
BEGIN
 0 TO sx 0 TO sy 0 TO sd
 7 sn - sm + sm DO 8 sn - sm + I 1+ DO x J + C@ x I + C@ = IF 1 TO sx LEAVE THEN LOOP LOOP
 7 sn - sm + sm DO 8 sn - sm + I 1+ DO y J + C@ y I + C@ = IF 1 TO sy LEAVE THEN LOOP LOOP
 7 sn - sm + sm DO 8 sn - sm + I 1+ DO x J + C@ x I + C@ - ABS J y + C@ I y + C@ - ABS =
 IF 1 TO sd LEAVE THEN LOOP LOOP
 sx sy sd OR OR TO sn
 sm 1+ TO sm
 sn 0= sm 16 > OR
UNTIL
sm 16 >
IF   FALSE
ELSE sm 1-
     IF   sm 2- x + C@ 10 * sm 2- y + C@ +
     ELSE TRUE
     THEN
THEN
;

13 25 32 48 56 64 77 81 safe? \ 8 безопасны
13 23 32 48 56 64 77 81 safe? \ 7 безопасны, если убрать 1-го
13 22 32 48 56 65 77 81 safe? \ невозможно сделать безопасными 7, если убрав 1-го

log

Код:

Ok ( 4294967295(-1) 23 0 )

TRUE - 8 ферзей не угрожают друг другу,
Число ( 23 ) 2 - координата по горизонтали, 3 - координата по вертикали для ферзя, которого нужно убрать, чтобы
оставшиеся 7 ферзей не угрожали друг другу,
FALSE - нельзя убрав только 1-го ферзя сделать позицию оставшихся 7 ферзей безопасной
ПС. Число позиций c 8-мю ферзями, когда убрав 1-го ферзя остальные 7 ферзей не угрожают друг другу 92*8*56=41216

chess

Гораздо проще найти решение для нахождения всех безопасных позиций (92 штуки).

Код:

CREATE i 8 ALLOT
: Do 9 1 DLIT, POSTPONE DO POSTPONE I ; IMMEDIATE
: i!  i + C! ;
: y.  i OVER [CHAR] a + EMIT + C@ . ;
: ferzi
Do 0 i! Do 1 i! Do 2 i! Do 3 i! Do 4 i! Do 5 i! Do 6 i! Do 7 i!
       7 0 DO 8 I 1+ DO J i + C@ I i + C@ = LOOP LOOP 27 0 DO OR LOOP
       7 0 DO 8 I 1+ DO I J - J i + C@  I i + C@  - ABS = LOOP LOOP 28 0 DO OR LOOP 0=
       IF 8 0 DO I y. LOOP CR THEN
LOOP LOOP LOOP LOOP LOOP LOOP LOOP LOOP
;
ferzi

log

Код:

a1 b5 c8 d6 e3 f7 g2 h4
a1 b6 c8 d3 e7 f4 g2 h5
a1 b7 c4 d6 e8 f2 g5 h3
a1 b7 c5 d8 e2 f4 g6 h3
a2 b4 c6 d8 e3 f1 g7 h5
a2 b5 c7 d1 e3 f8 g6 h4
a2 b5 c7 d4 e1 f8 g6 h3
a2 b6 c1 d7 e4 f8 g3 h5
a2 b6 c8 d3 e1 f4 g7 h5
a2 b7 c3 d6 e8 f5 g1 h4
a2 b7 c5 d8 e1 f4 g6 h3
a2 b8 c6 d1 e3 f5 g7 h4
a3 b1 c7 d5 e8 f2 g4 h6
a3 b5 c2 d8 e1 f7 g4 h6
a3 b5 c2 d8 e6 f4 g7 h1
a3 b5 c7 d1 e4 f2 g8 h6
a3 b5 c8 d4 e1 f7 g2 h6
a3 b6 c2 d5 e8 f1 g7 h4
a3 b6 c2 d7 e1 f4 g8 h5
a3 b6 c2 d7 e5 f1 g8 h4
a3 b6 c4 d1 e8 f5 g7 h2
a3 b6 c4 d2 e8 f5 g7 h1
a3 b6 c8 d1 e4 f7 g5 h2
a3 b6 c8 d1 e5 f7 g2 h4
a3 b6 c8 d2 e4 f1 g7 h5
a3 b7 c2 d8 e5 f1 g4 h6
a3 b7 c2 d8 e6 f4 g1 h5
a3 b8 c4 d7 e1 f6 g2 h5
a4 b1 c5 d8 e2 f7 g3 h6
a4 b1 c5 d8 e6 f3 g7 h2
a4 b2 c5 d8 e6 f1 g3 h7
a4 b2 c7 d3 e6 f8 g1 h5
a4 b2 c7 d3 e6 f8 g5 h1
a4 b2 c7 d5 e1 f8 g6 h3
a4 b2 c8 d5 e7 f1 g3 h6
a4 b2 c8 d6 e1 f3 g5 h7
a4 b6 c1 d5 e2 f8 g3 h7
a4 b6 c8 d2 e7 f1 g3 h5
a4 b6 c8 d3 e1 f7 g5 h2
a4 b7 c1 d8 e5 f2 g6 h3
a4 b7 c3 d8 e2 f5 g1 h6
a4 b7 c5 d2 e6 f1 g3 h8
a4 b7 c5 d3 e1 f6 g8 h2
a4 b8 c1 d3 e6 f2 g7 h5
a4 b8 c1 d5 e7 f2 g6 h3
a4 b8 c5 d3 e1 f7 g2 h6
a5 b1 c4 d6 e8 f2 g7 h3
a5 b1 c8 d4 e2 f7 g3 h6
a5 b1 c8 d6 e3 f7 g2 h4
a5 b2 c4 d6 e8 f3 g1 h7
a5 b2 c4 d7 e3 f8 g6 h1
a5 b2 c6 d1 e7 f4 g8 h3
a5 b2 c8 d1 e4 f7 g3 h6
a5 b3 c1 d6 e8 f2 g4 h7
a5 b3 c1 d7 e2 f8 g6 h4
a5 b3 c8 d4 e7 f1 g6 h2
a5 b7 c1 d3 e8 f6 g4 h2
a5 b7 c1 d4 e2 f8 g6 h3
a5 b7 c2 d4 e8 f1 g3 h6
a5 b7 c2 d6 e3 f1 g4 h8
a5 b7 c2 d6 e3 f1 g8 h4
a5 b7 c4 d1 e3 f8 g6 h2
a5 b8 c4 d1 e3 f6 g2 h7
a5 b8 c4 d1 e7 f2 g6 h3
a6 b1 c5 d2 e8 f3 g7 h4
a6 b2 c7 d1 e3 f5 g8 h4
a6 b2 c7 d1 e4 f8 g5 h3
a6 b3 c1 d7 e5 f8 g2 h4
a6 b3 c1 d8 e4 f2 g7 h5
a6 b3 c1 d8 e5 f2 g4 h7
a6 b3 c5 d7 e1 f4 g2 h8
a6 b3 c5 d8 e1 f4 g2 h7
a6 b3 c7 d2 e4 f8 g1 h5
a6 b3 c7 d2 e8 f5 g1 h4
a6 b3 c7 d4 e1 f8 g2 h5
a6 b4 c1 d5 e8 f2 g7 h3
a6 b4 c2 d8 e5 f7 g1 h3
a6 b4 c7 d1 e3 f5 g2 h8
a6 b4 c7 d1 e8 f2 g5 h3
a6 b8 c2 d4 e1 f7 g5 h3
a7 b1 c3 d8 e6 f4 g2 h5
a7 b2 c4 d1 e8 f5 g3 h6
a7 b2 c6 d3 e1 f4 g8 h5
a7 b3 c1 d6 e8 f5 g2 h4
a7 b3 c8 d2 e5 f1 g6 h4
a7 b4 c2 d5 e8 f1 g3 h6
a7 b4 c2 d8 e6 f1 g3 h5
a7 b5 c3 d1 e6 f8 g2 h4
a8 b2 c4 d1 e7 f5 g3 h6
a8 b2 c5 d3 e1 f7 g4 h6
a8 b3 c1 d6 e2 f5 g7 h4
a8 b4 c1 d3 e6 f2 g7 h5

Hishnik

Генерация всех перестановок не отвечает на второй интересный вопрос - "можно ли удалить с доски одного ферзя, чтобы размещение остальных стало безопасным". Это уже ближе к вопросам проектирования, когда надо определить, что добавить в программу (или убрать из требований), чтобы проблема решилась с минимальными усилиями.

Ну и интересно, почему бектрекинга среди решений не видно

Victor__v

Hishnik писал(а):

Ну и интересно, почему бектрекинга среди решений не видно

Наверно потому что его :shuffle;

единственный "адепт" на форуме только начал его изучать

Задача про Fферзей

Кто сейчас на конференции