Statistics

Problem Statement for "SixteenQueens"

Problem Statement

You have a 50 times 50 chessboard. Both rows and columns of the chessboard are numbered from 0 to 49, inclusive.

A queen is a chess piece that attacks all cells that are in the same row, in the same column, or on the same diagonal. In this problem we will be using at most sixteen queens.

Some queens are already placed on the board. You are given their coordinates in the int[]s row and col. More precisely, for each valid i there is a queen on the cell (row[i], col[i]). These queens are placed in such a way that no two of them attack each other.

You want to place add additional queens onto the chessboard in such a way that in the final configuration no two queens will attack each other. Find any one valid solution.

Return a int[] with the coordinates of the added queens. More precisely, if you want to place queens onto the cells (r0, c0), (r1, c1), and so on, return the int[] { r0, c0, r1, c1, ... }.

Definition

Class:
SixteenQueens
Method:
addQueens
Parameters:
int[], int[], int
Returns:
int[]
Method signature:
int[] addQueens(int[] row, int[] col, int add)
(be sure your method is public)

Notes

  • For the given constraints a solution always exists. Any valid solution will be accepted.

Constraints

  • row will have between 0 and 16 elements, inclusive.
  • Each element of row will be between 0 and 49, inclusive.
  • col will have the same number of elements as row.
  • Each element of col will be between 0 and 49, inclusive.
  • The queens described by row and col stand on distinct cells and they do not attack each other.
  • add will be between 0 and 16, inclusive.
  • The number of elements in row plus the value of add will be at most 16.

Examples

  1. {3}

    {5}

    1

    Returns: {0, 0 }

    There is a queen at (3,5). We are asked to add one more queen. In the example output shown above we place it at (0,0).

  2. {0}

    {1}

    1

    Returns: {4, 7 }

    There is a queen at (0,1). This time we cannot place the second queen at (0,0) because the two queens would attack each other.

  3. {0}

    {1}

    3

    Returns: {4, 7, 15, 0, 49, 49 }

    Adding three queens.

  4. {14, 19}

    {3, 47}

    0

    Returns: { }

    The easiest inputs are those where you don't have to add any new queens.

  5. {}

    {}

    2

    Returns: {0, 0, 1, 2 }

    There can be zero queens on the board before you start adding the new ones.

  6. {}

    {}

    16

    Returns: {0, 0, 1, 2, 2, 4, 3, 1, 4, 3, 5, 8, 6, 10, 7, 12, 8, 14, 9, 5, 10, 7, 11, 18, 12, 6, 13, 21, 14, 9, 15, 24 }

  7. {1,2,3}

    {7,2,19}

    1

    Returns: {0, 1 }

    There are three queens already on the board: at (1,7), (2,2), and (3,19). Our solution proposes to put the fourth queen onto the cell (0,1). There are many other valid solutions, and any of those will be accepted as well.

  8. {}

    {}

    0

    Returns: { }

  9. {4,35,36,16,24,39,1,34,32,28,2,23}

    {27,29,21,32,25,2,6,0,22,15,35,45}

    4

    Returns: {0, 3, 3, 1, 5, 4, 6, 8 }

  10. {38,35,48,15,2,21,24,34,6,14,30,26}

    {21,36,12,46,8,6,32,16,41,44,47,38}

    4

    Returns: {0, 0, 1, 3, 3, 2, 4, 7 }

  11. {43,49,35,22,30,36,46,14,7,13,38,0}

    {18,15,16,34,19,49,33,38,40,24,35,10}

    4

    Returns: {1, 0, 2, 2, 3, 4, 4, 7 }

  12. {4,32,34}

    {17,39,30}

    13

    Returns: {0, 0, 1, 2, 2, 4, 3, 1, 5, 8, 6, 3, 7, 11, 8, 7, 9, 14, 10, 16, 11, 5, 12, 20, 13, 6 }

  13. {23,2,43,45,20,36,13,11,30,8,33,6,28,41}

    {48,38,30,40,1,15,22,11,12,6,25,17,0,7}

    2

    Returns: {0, 2, 1, 4 }

  14. {4,1,2,11,32,12,31,29,36,44,34,40,39,24}

    {23,16,8,47,31,49,33,36,0,4,21,2,15,7}

    2

    Returns: {0, 1, 3, 3 }

  15. {5}

    {19}

    15

    Returns: {0, 0, 1, 2, 2, 4, 3, 1, 4, 3, 6, 9, 7, 11, 8, 5, 9, 14, 10, 6, 11, 17, 12, 7, 13, 20, 14, 8, 15, 23 }

  16. {35,46}

    {19,34}

    14

    Returns: {0, 0, 1, 2, 2, 4, 3, 1, 4, 3, 5, 8, 6, 10, 7, 12, 8, 14, 9, 5, 10, 7, 11, 18, 12, 6, 13, 21 }

  17. {35,48,39,31,7}

    {37,17,36,21,26}

    11

    Returns: {0, 0, 1, 2, 2, 5, 3, 1, 4, 8, 5, 4, 6, 11, 8, 3, 9, 15, 10, 6, 11, 18 }

  18. {22,36,31,8,32,29,27,4,45,1,17,44,12,18}

    {19,48,38,4,7,1,36,18,31,37,40,44,43,2}

    2

    Returns: {0, 3, 2, 0 }

  19. {34,24,46,33,37,47,43,32,6}

    {30,4,6,45,38,23,13,19,5}

    7

    Returns: {0, 0, 1, 3, 2, 7, 3, 9, 4, 1, 5, 8, 7, 11 }

  20. {23,22,3,40,16,29,19,20,37,0,27,18,10,21}

    {3,37,25,17,13,42,28,43,30,1,29,6,27,31}

    2

    Returns: {1, 4, 2, 0 }

  21. {15,16,38,24,39,2,31,3,0,40,46,6,35,42}

    {32,20,43,38,29,11,26,14,39,23,7,5,6,31}

    2

    Returns: {1, 1, 4, 0 }

  22. {28,5,33,20,47,4,45,39,38,16,48,7,3,31,0,15}

    {38,25,32,27,12,8,31,5,14,45,19,35,18,44,37,40}

    0

    Returns: { }

  23. {6,4,37,15,8,25,7,18,40,41,42,32}

    {21,10,6,11,37,22,26,35,14,20,27,34}

    4

    Returns: {0, 0, 1, 2, 2, 5, 3, 1 }

  24. {33,27,28,43,46,1,6,49,47,11,26,30}

    {33,40,27,26,31,12,28,37,3,42,30,44}

    4

    Returns: {0, 1, 2, 0, 3, 5, 4, 7 }

  25. {14,40,34,20}

    {12,1,31,9}

    12

    Returns: {0, 0, 1, 2, 2, 4, 3, 6, 4, 3, 5, 10, 6, 13, 7, 11, 8, 14, 9, 5, 10, 18, 11, 20 }

  26. {49,4,47,19,41,42}

    {18,3,38,2,39,0}

    10

    Returns: {0, 1, 1, 4, 2, 6, 3, 8, 5, 5, 6, 12, 7, 9, 8, 15, 9, 17, 10, 7 }

  27. {22,35,23,28,2,19,42,26,27}

    {12,13,23,39,47,38,19,7,26}

    7

    Returns: {0, 1, 1, 3, 3, 0, 4, 2, 5, 8, 6, 10, 7, 14 }

  28. {48,16,46,17,3,25,49,23,5,40,28,4}

    {31,2,36,25,1,12,26,33,22,21,4,30}

    4

    Returns: {0, 0, 1, 5, 2, 3, 6, 8 }

  29. {4,13,27,0,38,34,21,2,41}

    {10,14,30,7,36,13,25,43,37}

    7

    Returns: {1, 0, 3, 3, 5, 15, 6, 11, 7, 1, 8, 5, 9, 2 }

  30. {20,22,6,38,33,0,3,48,12,17,40,19,45,16}

    {34,0,1,13,39,2,24,29,5,43,25,38,19,26}

    2

    Returns: {1, 4, 2, 6 }

  31. {6,24,11,8,14,27,45,37,41,16,4,7}

    {45,24,18,35,5,26,27,46,29,40,2,33}

    4

    Returns: {0, 1, 1, 3, 2, 6, 3, 0 }

  32. {39,36,26,47,38}

    {18,38,35,31,34}

    11

    Returns: {0, 0, 1, 2, 2, 5, 3, 1, 4, 8, 5, 4, 6, 11, 7, 13, 8, 3, 9, 6, 10, 17 }

  33. {14,9,39,41,19}

    {7,18,30,31,26}

    11

    Returns: {0, 0, 1, 2, 2, 4, 3, 1, 4, 3, 5, 8, 6, 10, 7, 12, 8, 14, 10, 5, 11, 19 }

  34. {38,0,31,46,21,35,24,39,9,25,49,6,42,30,20}

    {11,27,31,26,23,19,2,48,29,6,42,37,43,45,9}

    1

    Returns: {1, 0 }

  35. {16,26,7,42,15,9,23,36,34}

    {21,42,13,11,29,33,7,14,36}

    7

    Returns: {0, 0, 1, 2, 2, 5, 3, 1, 4, 8, 5, 4, 6, 15 }

  36. {40,34,2,24,11,38,46,12,3,20,16}

    {40,13,23,48,31,46,10,25,30,35,6}

    5

    Returns: {0, 1, 1, 3, 4, 2, 5, 0, 6, 5 }

  37. {42,17,24,16,41}

    {32,38,7,35,34}

    11

    Returns: {0, 0, 1, 2, 2, 4, 3, 1, 4, 3, 5, 8, 6, 10, 7, 12, 8, 14, 9, 5, 10, 17 }

  38. {18,38,44,20,2,39,49,48}

    {16,43,41,36,48,13,20,7}

    8

    Returns: {0, 0, 1, 2, 3, 5, 4, 3, 5, 1, 6, 9, 7, 11, 8, 14 }

  39. {43,33,34,26,31}

    {30,35,31,49,46}

    11

    Returns: {0, 0, 1, 2, 2, 5, 3, 1, 4, 8, 5, 4, 6, 11, 7, 3, 8, 14, 9, 16, 10, 18 }

  40. {37,49,29}

    {45,43,28}

    13

    Returns: {0, 0, 1, 2, 2, 4, 3, 1, 4, 7, 5, 9, 6, 3, 7, 12, 8, 14, 9, 16, 10, 5, 11, 20, 12, 8 }

  41. {38,31,45,32,47,39,49,43}

    {24,2,21,17,10,6,3,22}

    8

    Returns: {0, 0, 1, 4, 2, 1, 3, 5, 4, 8, 5, 11, 6, 7, 7, 12 }

  42. {35,48}

    {34,48}

    14

    Returns: {0, 1, 1, 3, 2, 0, 3, 6, 4, 8, 5, 2, 6, 11, 7, 13, 8, 15, 9, 4, 10, 18, 11, 5, 12, 21, 13, 9 }

  43. {2,14}

    {33,41}

    14

    Returns: {0, 0, 1, 2, 3, 1, 4, 3, 5, 7, 6, 9, 7, 4, 8, 12, 9, 5, 10, 15, 11, 6, 12, 18, 13, 20, 15, 8 }

  44. {10,19,22,20,6,24,0,17,16,15}

    {38,46,45,31,32,26,47,35,30,27}

    6

    Returns: {1, 0, 2, 2, 3, 4, 4, 1, 5, 3, 7, 10 }

  45. {22,9,3,10,2,19,7,11,18,0,14,4,8,24,6}

    {39,44,45,34,33,37,30,32,40,36,26,48,46,27,35}

    1

    Returns: {1, 0 }

  46. {8,4,5,24,19,3}

    {36,48,27,41,44,34}

    10

    Returns: {0, 0, 1, 2, 2, 4, 6, 1, 7, 3, 9, 6, 10, 8, 11, 5, 12, 11, 13, 16 }

  47. {27,33,34,43,49,46}

    {14,3,6,24,15,23}

    10

    Returns: {0, 0, 1, 2, 2, 4, 3, 1, 4, 7, 5, 9, 6, 11, 7, 13, 8, 5, 9, 16 }

  48. {31,25,47,45,37,30,26,27,32,46}

    {48,38,40,32,41,30,31,34,26,27}

    6

    Returns: {0, 1, 1, 3, 2, 0, 3, 2, 4, 7, 5, 11 }

  49. {37,46,32,47,42}

    {37,42,41,39,30}

    11

    Returns: {0, 1, 1, 3, 2, 0, 3, 2, 4, 7, 5, 9, 6, 11, 7, 13, 8, 5, 9, 16, 10, 18 }

  50. {10,12,4,7,0,17,22,21,19,24,8}

    {28,38,27,32,33,25,31,26,36,44,48}

    5

    Returns: {1, 0, 2, 2, 3, 4, 5, 1, 6, 3 }

  51. {5,4,15,9,12,7}

    {10,8,3,22,21,7}

    10

    Returns: {0, 1, 1, 4, 2, 0, 3, 5, 6, 13, 8, 2, 10, 6, 11, 17, 13, 12, 14, 9 }

  52. {16,14,9,3,6,22,18,15,5,11}

    {29,49,26,46,28,33,48,42,25,32}

    6

    Returns: {0, 0, 1, 2, 2, 4, 4, 1, 7, 3, 8, 6 }

  53. {31,44,32,39,38,27,40,48,41,36,43,30}

    {13,19,1,7,24,15,16,20,12,0,8,11}

    4

    Returns: {0, 2, 1, 4, 2, 6, 3, 3 }

  54. {32,29,26,48,37}

    {3,11,4,5,24}

    11

    Returns: {0, 0, 1, 2, 2, 6, 3, 1, 4, 7, 5, 10, 6, 8, 7, 13, 8, 15, 9, 17, 10, 9 }

  55. {32,39,48,33,36}

    {10,16,22,3,24}

    11

    Returns: {0, 0, 1, 2, 2, 4, 3, 1, 4, 7, 5, 9, 6, 11, 7, 6, 8, 14, 9, 17, 10, 5 }

  56. {17,14,19,4,6,3,12,21,1}

    {8,16,14,11,0,1,15,18,17}

    7

    Returns: {0, 5, 2, 6, 5, 4, 7, 3, 8, 9, 9, 2, 10, 10 }

  57. {24,13,22,7,18,12,14,20,5,17,16,15,1,21,0,6}

    {15,1,22,16,10,23,4,5,6,14,20,17,19,3,8,11}

    0

    Returns: { }

  58. {6,16,3,24,21}

    {40,48,34,44,42}

    11

    Returns: {0, 0, 1, 2, 2, 4, 4, 1, 5, 3, 7, 6, 8, 11, 9, 5, 10, 14, 11, 16, 12, 18 }

  59. {26,48,49,35,42,38,44}

    {4,16,8,21,11,13,24}

    9

    Returns: {0, 0, 1, 2, 2, 5, 3, 1, 4, 6, 5, 9, 6, 3, 7, 12, 8, 7 }

  60. {13,5,2,4}

    {23,21,3,8}

    12

    Returns: {0, 0, 1, 6, 3, 1, 6, 2, 7, 4, 8, 7, 9, 11, 10, 13, 11, 5, 12, 18, 14, 25, 15, 10 }

  61. {12,13}

    {5,17}

    14

    Returns: {0, 0, 1, 2, 2, 4, 3, 1, 4, 3, 5, 8, 6, 12, 7, 14, 8, 16, 9, 6, 10, 15, 11, 20, 14, 9, 15, 7 }

  62. {46,41,44,49,33,26,35,36}

    {22,13,2,11,6,9,1,23}

    8

    Returns: {0, 0, 1, 3, 2, 5, 3, 7, 4, 10, 5, 4, 6, 14, 7, 8 }

  63. {31,25,49,32,38,45}

    {44,42,39,33,40,26}

    10

    Returns: {0, 0, 1, 4, 2, 1, 3, 7, 4, 2, 5, 10, 6, 3, 7, 13, 8, 15, 9, 5 }

  64. {2,10,8}

    {19,6,10}

    13

    Returns: {0, 0, 1, 2, 3, 1, 4, 3, 5, 8, 6, 11, 7, 4, 9, 13, 11, 17, 12, 7, 13, 20, 14, 22, 15, 5 }

  65. {12,10,21,7,13,6,3,14,4,8,9,24,16,22,2}

    {43,31,39,40,37,26,33,49,44,36,28,34,30,48,27}

    1

    Returns: {0, 0 }

  66. {21,5,2,11,15}

    {30,39,31,46,47}

    11

    Returns: {0, 0, 1, 2, 3, 1, 4, 3, 6, 8, 7, 4, 8, 11, 9, 13, 10, 5, 12, 6, 13, 18 }

  67. {26,35,31,25,32,38,36}

    {0,17,12,4,3,15,19}

    9

    Returns: {0, 1, 1, 5, 2, 2, 3, 6, 4, 9, 5, 7, 6, 13, 7, 16, 8, 14 }

  68. {20,4}

    {1,20}

    14

    Returns: {0, 0, 1, 2, 2, 4, 3, 6, 5, 3, 6, 5, 7, 11, 8, 14, 9, 16, 10, 7, 11, 19, 12, 8, 13, 18, 14, 9 }

  69. {0 }

    {1 }

    15

    Returns: {1, 3, 2, 0, 3, 2, 4, 4, 5, 8, 6, 10, 7, 12, 8, 14, 9, 5, 10, 7, 11, 18, 12, 6, 13, 21, 14, 9, 15, 24 }

  70. { }

    { }

    2

    Returns: {0, 0, 1, 2 }

  71. {0 }

    {0 }

    10

    Returns: {1, 2, 2, 4, 3, 1, 4, 3, 5, 8, 6, 10, 7, 12, 8, 14, 9, 5, 10, 7 }

  72. {0, 1 }

    {0, 3 }

    14

    Returns: {2, 1, 3, 4, 4, 2, 5, 8, 6, 10, 7, 12, 8, 14, 9, 5, 10, 7, 11, 18, 12, 6, 13, 21, 14, 9, 15, 24 }

  73. {1 }

    {0 }

    1

    Returns: {0, 2 }

This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2024, TopCoder, Inc. All rights reserved.
This problem was used for: