Couples at a Square Table
Combinatorics · 29th PMO Qualifying Stage
Four married couples sit together around a square table. The table has eight seats, with two seats per side. Let $N$ be the number of possible seating arrangements such that no one sits on the same side as their spouse. What are the first three digits (from the left) of $N$? (Note that two arrangements are considered identical if one is a $90^\circ$, $180^\circ$, or $270^\circ$ rotation of the other.)