Queens Puzzle
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
using System; | |
using System.Collections.Generic; | |
using System.Linq; | |
using System.Text; | |
using System.Threading.Tasks; | |
namespace Algorithms.Maths | |
{ | |
public struct Queen | |
{ | |
public readonly ushort X; | |
public readonly ushort Y; | |
public Queen(int x, int y) | |
{ | |
X = (ushort)x; | |
Y = (ushort)y; | |
} | |
public bool SafeWith(Queen other) | |
{ | |
return X != other.X && Y != other.Y && Math.Abs(X - other.X) != Math.Abs(Y - other.Y); | |
} | |
} | |
public class QueenList | |
{ | |
public readonly Queen Head; | |
public readonly QueenList Tail; | |
public QueenList(Queen head, QueenList tail) | |
{ | |
Head = head; | |
Tail = tail; | |
} | |
} | |
public static class QueenListExtensions | |
{ | |
public static bool SafeWith(this QueenList list, Queen queen) | |
{ | |
while (list != null) | |
{ | |
if (!queen.SafeWith(list.Head)) | |
return false; | |
list = list.Tail; | |
} | |
return true; | |
} | |
} | |
public static class NQueens | |
{ | |
public static IReadOnlyCollection<QueenList> Queens(ushort boardSize) | |
{ | |
return QueensInternal(boardSize, boardSize).ToList(); | |
} | |
private static IEnumerable<QueenList> QueensInternal(int boardSize, int y) | |
{ | |
if (y == 0) | |
return new List<QueenList> { null }; | |
return from placedQueens in QueensInternal(boardSize, y - 1) | |
from proposedQueen in Enumerable.Range(0, boardSize - 1) .Select(x => new Queen(x, y)) | |
where placedQueens.SafeWith(proposedQueen) | |
select new QueenList(proposedQueen, placedQueens); | |
} | |
} | |
} |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
import math._ | |
class Queen(val x: Int, val y : Int) { | |
def safeWith(other: Queen) : Boolean = | |
x != other.x && y != other.y && abs(x - other.x) != abs(y - other.y) | |
} | |
implicit class QueenListExtensions(queens: List[Queen]) { | |
def safeWith(queen: Queen) : Boolean = queens forall (_ safeWith queen) | |
} | |
def nqueens(n: Int): Set[List[Queen]] = { | |
def nqueensInternal(y: Int): Set[List[Queen]] = { | |
if (y == 0) Set(Nil) | |
else | |
for { | |
placedQueens <- nqueensInternal(y - 1) | |
proposedQueen <- 0 until n map (new Queen(_, y)) | |
if placedQueens.safeWith(proposedQueen) | |
} yield proposedQueen :: placedQueens | |
} | |
nqueensInternal(n) | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment