Programming in Scala S23.2 The n-queens problem

LINQ_Method_QueryExp.csx

Func<(int, int), (int, int), bool> inCheck = (q1, q2) => q1.Item1 == q2.Item1 || q1.Item2 == q2.Item2 || Math.Abs(q1.Item1 - q2.Item1) == Math.Abs(q1.Item2 - q2.Item2);

Func<(int, int), IEnumerable<(int, int)>, bool> isSafe = (queen, queens) => queens.All(q => !inCheck(queen, q));

Func<int, IEnumerable<IEnumerable<(int, int)>>> queens = n => {
    Func<int, IEnumerable<IEnumerable<(int, int)>>> placeQueens = null;
    placeQueens = k => {
        if (k == 0){
            return Enumerable.Repeat(Enumerable.Empty<(int, int)>(), 1);
        } else {
            return placeQueens(k - 1)
            .SelectMany(queens => 
                Enumerable.Range(1, n)
                .Select(column => (k, column))
                .Where(queen => isSafe(queen, queens))
                .Select(queen => Enumerable.Repeat(queen, 1).Concat(queens)));
        }
    };
    return placeQueens(n);
};

Func<int, IEnumerable<IEnumerable<(int, int)>>> queens2 = n => {
    Func<int, IEnumerable<IEnumerable<(int, int)>>> placeQueens = null;
    placeQueens = k => {
        if (k == 0){
            return Enumerable.Repeat(Enumerable.Empty<(int, int)>(), 1);
        } else {
            return from queens in placeQueens(k - 1)
                   from column in Enumerable.Range(1, n)
                   let queen = (k, column)
                   where isSafe(queen, queens)
                   select Enumerable.Repeat(queen, 1).Concat(queens);
        }
    };
    return placeQueens(n);
};

Enumerable.Range(1, 9)
    .Select(
        i => Enumerable.SequenceEqual(
            queens(i).SelectMany(x => x), 
            queens2(i).SelectMany(x => x)))
    .All(x => x)

scala_flatmap.scala

def queens(n: Int): List[List[(Int, Int)]] = { 
  def placeQueens(k: Int): List[List[(Int, Int)]] =
  	if (k == 0) 
  		List(List()) 
  	else 
  		for { 
        queens <- placeQueens(k - 1) 
        column <- 1 to n 
        queen = (k, column) 
        if isSafe(queen, queens) 
      } yield queen :: queens 
  placeQueens(n) 
}


def queens2(n: Int): List[List[(Int, Int)]] = { 
  def placeQueens(k: Int): List[List[(Int, Int)]] =
  	if (k == 0) 
  		List(List()) 
  	else 
  		placeQueens(k - 1)
  			.flatMap(queens => 
                 (1 to n)
                 .map(column => (k, column))
                 .filter(queen => isSafe(queen, queens))
                 .map(queen => queen::queens))
  placeQueens(n) 
}

def isSafe(queen: (Int, Int), queens: List[(Int, Int)]) = 
	queens forall (q => !inCheck(queen, q)) 

def inCheck(q1: (Int, Int), q2: (Int, Int)) = 
	q1._1 == q2._1 || // same row 
	q1._2 == q2._2 || // same column 
	(q1._1 - q2._1).abs == (q1._2 - q2._2).abs // on diagonal 

queens(4)
queens2(4)