107. The Man Machine

Codeforces

IDCF10269107

Time5000ms

Memory256MB

Difficulty—

English · Original

Formal · Original

The Man Machine You played against a Man Machine in chess, and because it is a superhuman being, you lost every game. Now, you're trying to practice chess so that you can beat the Man Machine. To practice, you want to figure out how many different ways there are to place $N$ queens on an $N$ by $N$ chessboard, such that no two queens attack each other (queens can attack any number of spaces directly diagonal, left, right, up, or down). This is called the $N$-queens problem, and is a standard computer science problem involving recursion and backtracking. Your task is to implement this solution on chessboards where $N$ can be up to 9. The only line of input contains a single positive integer $N$: the size of the chessboard. Output a single positive integer $c$: the number of ways to place $N$ queens on the chessboard, such that no two queens attack each other. If your program consists only of a lookup table with the correct values, your submission will be judged as incorrect and you may be disqualified from the contest. ## Input The only line of input contains a single positive integer $N$: the size of the chessboard. ## Output Output a single positive integer $c$: the number of ways to place $N$ queens on the chessboard, such that no two queens attack each other. [samples] ## Note If your program consists only of a lookup table with the correct values, your submission will be judged as incorrect and you may be disqualified from the contest.

**Definitions** Let $ N \in \mathbb{Z}^+ $ with $ 1 \leq N \leq 9 $ be the size of the chessboard. Let $ Q = \{ (r_i, c_i) \mid i \in \{1, \dots, N\} \} $ be a set of queen positions, where $ r_i, c_i \in \{1, \dots, N\} $ denote the row and column of the $ i $-th queen. **Constraints** 1. Each queen occupies a unique row: $ r_i \neq r_j $ for all $ i \neq j $. 2. Each queen occupies a unique column: $ c_i \neq c_j $ for all $ i \neq j $. 3. No two queens share a diagonal: $ |r_i - r_j| \neq |c_i - c_j| $ for all $ i \neq j $. **Objective** Compute the number of valid configurations $ c $ satisfying all constraints above.

API Response (JSON)

{
  "problem": {
    "name": "107. The Man Machine",
    "description": {
      "content": "The Man Machine You played against a Man Machine in chess, and because it is a superhuman being, you lost every game. Now, you're trying to practice chess so that you can beat the Man Machine. To pr",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 5000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF10269107"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "The Man Machine\n\nYou played against a Man Machine in chess, and because it is a superhuman being, you lost every game. Now, you're trying to practice chess so that you can beat the Man Machine.\n\nTo pr...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ N \\in \\mathbb{Z}^+ $ with $ 1 \\leq N \\leq 9 $ be the size of the chessboard.  \nLet $ Q = \\{ (r_i, c_i) \\mid i \\in \\{1, \\dots, N\\} \\} $ be a set of queen positions, where $ r_i,...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments