← Complete problem index

PROJECT EULER · #0628

Open Chess Positions

Statement only · SolvedOriginal problem ↗

A position in chess is an (orientated) arrangement of chess pieces placed on a chessboard of given size. In the following, we consider all positions in which n pawns are placed on a n×n board in such a way, that there is a single pawn in every row and every column.

We call such a position an open position, if a rook, starting at the (empty) lower left corner and using only moves towards the right or upwards, can reach the upper right corner without moving onto any field occupied by a pawn.

Let f(n) be the number of open positions for a n×n chessboard.
For example, f(3)=2, illustrated by the two open positions for a 3×3 chessboard below.

Open position 1Open position 2

You are also given f(5)=70.

Find f(108) modulo 1008691207.

Write-up coming later

The complete problem is available here. An approach, code, and answer will be added later.