Project Chess

Module Main
' Задача покрытия шахматной доски
' http://np-soft.ru/npprojects/puzzles/chess/covering.htm
' Укажите:
Field Figure As Integer       ' фигуру, например коня
Field ProblemType As Integer  ' и тип: покрытие или размещение максимального количества фигур

'*******************************
Var ptCovering = -1 ' покрытие
Var ptPlacing = 1   ' размещение

Field N As Integer           ' Размер шахматной доски


Class Move
' Класс хода отностельно текущей позиции
Field dx As Integer
Field dy As Integer

Class Check
' Класс клетки шахматной доски
Var Busy As Boolean ' Переменная занятости клетки фигурой
Var x = 1 + (Me - 1) Mod N
Var y = 1 + (Me - 1) \ N

Con Save As Store(x, y, Busy)

Con Placing As ' Размещение фигур без взаимных ударов 
  ProblemType = ptPlacing And (Figure = fKing Or Figure = fKnight) ==>
    ForAll(m In Move, ' см. также PlacingCastleQueen, PlacingBishopQueen
      Exists(x1 In {x+m.dx},
        Between(x1, 1, N) ==>
          Exists(y1 In {y+m.dy},
            Between(y1, 1, N) ==>
              Busy + Check((y1-1)*N+x1).Busy <= 1)))

Con Covering As ' Клетка должна 
  ProblemType = ptCovering ==> '(в задаче покрытия)
    Busy +          '  либо содержать фигуру
    Sum(m In Move,  ' либо находиться под ударом другой фигуры
      Sum(x1 In {x+m.dx},
        If(Between(x1, 1, N),
          Sum(y1 In {y+m.dy},
            If(Between(y1, 1, N),
              Check((y1-1)*N+x1).Busy, 0)), 0))) > 0

Con Optimum As ' В зависимости от типа задачи минимизируем или максимизирует 
  Maximize(ProblemType*Busy) ' количество занятых клеток

Module Figures
Var fKing = 1   ' Король
Var fQueen = 2  ' Ферзь
Var fCastle = 3 ' Ладья
Var fBishop = 4 ' Слон
Var fKnight = 5 ' Конь

Con Ins As ' Создание клеток шахматной доски
  ForAll(i In {1..N^2}, Append(Check, Me : i))

' В зависимости от фигуры заполняем таблицу угроз (экземпляры Move)
Con InsKing As
  Figure = fKing ==>
    ForAll(dx In {-1..1},
      ForAll(dy In {-1, (dx=0)..1},
        Append(Move, Me : 3*(dx+1) + dy + 2, dx : dx, dy : dy)))

Con InsQueen As
  Figure = fQueen ==>
    ForAll(dx In {-(N-1)..N-1},
      ForAll(dy In {-(N-1).. -(dx=0), (dx=0)..N-1},
        dx=0 Or dy=0 Or Abs(dx)=Abs(dy) ==>
          Append(Move, Me : (dx+N)*2*N+dy, dx : dx, dy : dy)))

Con InsCastle As
  Figure = fCastle ==>
    ForAll(dz In {1..N-1},
      ForAll(k In {1..4},
        Append(Move, Me : dz*4+k,
                     dx : If(k=1, dz, If(k=2, -dz, 0)),
                     dy : If(k=3, dz, If(k=4, -dz, 0)))))

Con InsBishop As
  Figure = fBishop ==>
    ForAll(dz In {1..N-1},
      ForAll(k In {1..4},
        Append(Move, Me : dz*4+k,
                     dx : If(k<=2, dz, -dz),
                     dy : If(k=1 Or k=3, dz, -dz))))
Con InsKnight As
  Figure = fKnight ==>
    ForAll(dx In {-2, -1, 1, 2},
      ForAll(dy In {-2, -1, 1, 2},
        Abs(dx)+Abs(dy) = 3 ==>
          Append(Move, Me : 4*(dx+3)+dy, dx : dx, dy : dy)))

Con PlacingCastleQueen As
  ProblemType = ptPlacing And (Figure = fCastle Or Figure = fQueen) ==> 
  ForAll(x In {1..N},
    Sum(y In {1..N}, Check((y-1)*N+x).Busy) <= 1) And
  ForAll(y In {1..N},
    Sum(x In {1..N}, Check((y-1)*N+x).Busy) <= 1)

Con PlacingBishopQueen As
  ProblemType = ptPlacing And (Figure = fBishop Or Figure = fQueen) ==>
  ForAll(i In {-(N-2).. (N-2)},
    Sum(j In {0..N-Abs(i)-1},
      Check(If(i>=0, i+1, -i*N+1)+j*(N+1)).Busy) <= 1 And
    Sum(j In {0..N-Abs(i)-1}, 
      Check(If(i>=0, N-i, (-i+1)*N)+j*(N-1)).Busy) <= 1)