Eight Queens Puzzle in TypeScript’s Type System

A chess piece with a golden crown on its top

What is the Eight Queens puzzle?

/* Generate an array containing number belows `n` */
function range(n: number): number[] {
return Array(n)
.fill(0)
.map((_, i) => i);
}

/* Ensure the last queen in the passed array is safe from the other queens.*/
function validate(queens: number[]): boolean {
const lastPos = queens.length - 1;
const last = queens[lastPos];

return !range(lastPos).some((pos) => {
const stepVal = queens[pos];

return stepVal == last ||
Math.abs(lastPos - pos) == Math.abs(last - stepVal);
});
}

function findSolution(queens: number[], step: number, tableSize: number): number[] | false {
if (step === tableSize) {
return queens;
} else {
return range(tableSize)
.map((i) => [...queens, i + 1])
.filter((q) => validate(q))
.reduce<number[] | false>((acc, newQueens) => {
return acc || findSolution(newQueens, step + 1, tableSize);
}, false);
}
}


console.log(findSolution([], 0, 8)) // display `[1, 5, 8, 6, 3, 7, 2, 4]`

Natural numbers

type Z = { kind: 'Z' } // Represents 0
type S<T> = { kind: 'S', succ: T } // Represents the successor of the natural number T

type N0 = Z // 0
type N1 = S<N0> // 1
type N2 = S<N1> // 2
type N3 = S<N2> // 3
type N4 = S<N3> // 4
type N5 = S<N4> // 5
type N6 = S<N5> // 6
type N7 = S<N6> // 7
type N8 = S<N7> // 8

Operation on natural numbers

Subtraction

// returns n - m,  or 0 if m > n
function sub(n: number, m: number): number {
/* Obviously we could also write `return n - m`
But the goal is to have something translatable at type level,
and `-` doesn't exist at type level. */
if ( m > 0 ) {
if ( n > 0 ) {
return sub(n -1, m -1);
} else {
return 0;
}
} else {
return n;
}
}
// Returns N - M, returns 0 if M > N
type Sub<N, M> =
M extends S<infer PM>?N extends S<infer PN>?Sub<PN, PM>:Z:N;

Other Nat operators

type Eq<A, B> = [A] extends [B] ? ([B] extends [A] ? true : false) : false;
type GT<A, B> = A extends S<infer PA> ? (B extends S<infer PB> ? GT<PA, PB> : true) : false;
type AbsSub<A, B> = GT<A, B> extends true ? Sub<A, B> : Sub<B, A>;

Boolean logic

type Or<A extends boolean, B extends boolean> = A extends true ? true : B;
type Not<A extends boolean> = A extends true ? false : true;

Implementing range function

function range(n: number): number[] {
if ( n > 0 ) {
return [...range(n -1), n - 1]
} else {
return [];
}
}
type RangeTuple<N> = N extends S<infer PN> ? [...RangeTuple<PN>, PN] : [];
type Test1 = RangeTuple<Z> // Test1 is []
type Test2 = RangeTuple<N3> // Test2 is [Z, N1, N2]

Operations on Tuples

type Size<ARR> = ARR extends [infer HEAD, ...infer TAIL] ? S<Size<TAIL>> : Z;
type At<ARR extends unknown[], N> = 
ARR extends [infer HEAD, ...infer TAIL]
? N extends S<infer PN>
? At<TAIL, PN>
: HEAD
: never;

Implementing validate function

stepVal == last || Math.abs(lastPos - pos) == Math.abs(last - stepVal);
type ValidateOnePoint<POS, STEP_VAL, LAST_POS, LAST> = Or<
Eq<STEP_VAL, LAST>,
Eq<AbsSub<LAST_POS, POS>, AbsSub<LAST, STEP_VAL>>
>;
type ValidateOnePointFromArr<POS, LAST_POS, QUEENS extends unknown[]> = ValidateOnePoint<
POS,
At<QUEENS, POS>,
LAST_POS,
At<QUEENS, LAST_POS>
>;
function some<A>(arr: A[], predicate: (a:A) => boolean): boolean {
if(arr.length > 0) {
const [head, ...tail] = arr;
if (predicate(head)) {
return true;
} else {
return some(tail, predicate)
}
} else {
return false
}
}
type SomeInvalidPoint<RANGE, QUEENS extends unknown[]> = RANGE extends [infer HEAD, ...infer TAIL]
? ValidateOnePointFromArr<HEAD, Sub<Size<QUEENS>, N1>, QUEENS> extends true
? true
: SomeInvalidPoint<TAIL, QUEENS>
: false;
type Validate<QUEENS extends unknown[]> = Not<SomeInvalidPoint<RangeTuple<Sub<Size<QUEENS>, N1>>, QUEENS>>;
type TestValidate1 = Validate<[N1, N2]> // equivalent to false
type TestValidate2 = Validate<[N1, N5]> // equivalent to true

Implementing findSolution

function filter<A>(arr: A[], predicate: (a:A) => boolean): A[] {
if(arr.length > 0) {
const [head, ...tail] = arr;
if(predicate(head)) {
return [head, ...filter(tail, predicate)];
} else {
return filter(tail, predicate);
}
} else {
return false;
}
}

function map<A, B>(arr: A[], fn: (a:A) => B): B[] {
if(arr.length > 0) {
const [head, ...tail] = arr;
return [fn(head), ...map(tail, fn)];
} else {
return [];
}
}

function reduce<A,B>(arr: A[], fn: (b:B, a:A) => B, init: B): B {
if (arr.length > 0) {
const [head, ...tail] = arr;
return reduce(tail, fn, fn(init, head));
} else {
return init;
}
}
type FilterValidArr<QUEENS extends unknown[][]> = QUEENS extends [infer HEAD extends unknown[], ...infer TAIL extends unknown[][]]
? Validate<HEAD> extends true
? [HEAD, ...FilterValidArr<TAIL>]
: FilterValidArr<TAIL>
: [];

type MapPossiblePositions<QUEENS extends unknown[], TABLE_SIZE> = TABLE_SIZE extends S<infer PN>
? [...MapPossiblePositions<QUEENS, PN>, [...QUEENS, TABLE_SIZE]]
: [];


type ReduceToOneSolution<INIT, ARR, STEP, TABLE_SIZE> = ARR extends [infer HEAD extends unknown[], ...infer TAIL]
? ReduceToOneSolution<
INIT extends false ? FindSolution<HEAD, S<STEP>, TABLE_SIZE> : INIT,
TAIL,
STEP,
TABLE_SIZE
>
: INIT;
type FindSolution<QUEENS extends unknown[], STEP, TABLE_SIZE> = Eq<STEP, TABLE_SIZE> extends true
? QUEENS
: ReduceToOneSolution<false, FilterValidArr<MapPossiblePositions<QUEENS, TABLE_SIZE>>, STEP, TABLE_SIZE>;

Checking the result

type Result = FindSolution<[], Z, N8>

Should you do that?

--

--

--

I’m a full-stack developer, in love with functional programming and type systems. I’m working currently at Decathlon Canada, in Montreal QC.

Love podcasts or audiobooks? Learn on the go with our new app.

Recommended from Medium

Send multiple requests for data with axios.all( )

Shopify App With Laravel, InertiaJs, and Polaris

Must know in JavaScript

React side bar (but sexy?)

Managing scalable, consistent colors in your css-in-js app with Reshader

MERN Stack

Tutorial: User Authentication with Passport.js

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store
Benoit Lemoine

Benoit Lemoine

I’m a full-stack developer, in love with functional programming and type systems. I’m working currently at Decathlon Canada, in Montreal QC.

More from Medium

Rush to Retire NPM for RushJS

Rush logo

Analyze and Optimize Webpack Bundles Size and Contents

From Apollo to Urql — Part 2

TypeScript and ML languages