Skip to content

Instantly share code, notes, and snippets.

@kostrse
Last active August 29, 2015 14:04
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
Star You must be signed in to star a gist
Save kostrse/b01cbe3cb1afe13da52c to your computer and use it in GitHub Desktop.
Queens Puzzle
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);
}
}
}
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