fork(2) download
copy 
  1. // http://u...content-available-to-author-only...e.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=691
  2. // Kaushik Acharya
  3. #include <iostream>
  4. #include <fstream>
  5. #include <vector>
  6. #include <cassert>
  7.  
  8. const bool READ_FROM_FILE = false;
  9.  
  10. //We are considering a column for each queen
  11. template<typename T>
  12. class Queen
  13. {
  14. public:
  15.     Queen()
  16.         : relValidPos_(0)
  17.     {
  18.     }
  19. public:
  20.     T currentPos()
  21.     {
  22.         assert((relValidPos_ < vecValidPos_.size()) && "can't provide a valid position");
  23.         return vecValidPos_[relValidPos_];
  24.     }
  25.     void addValidPos(T pos)
  26.     {
  27.         vecValidPos_.push_back(pos);
  28.     }
  29.     void moveToNextPos()
  30.     {
  31.         //Note: If this queen is currently at last valid position, then this call will move it to an invalid position.
  32.         //So its necessary to check the validity of this queen's position before using it.
  33.         ++relValidPos_;
  34.     }
  35.     bool isCurrentPosValid()
  36.     {
  37.         return (relValidPos_ < vecValidPos_.size());
  38.     }
  39.     void clearAllPos()
  40.     {
  41.         //This is called when we want to backtrack to a queen at higher level.
  42.         vecValidPos_.clear();
  43.         relValidPos_ = 0;
  44.     }
  45.     bool empty()
  46.     {
  47.         return vecValidPos_.empty();
  48.     }
  49. private:
  50.     std::vector<T> vecValidPos_; //This stores all valid positions for the queen in current state of the game
  51.     T relValidPos_; //This indicates the relative index of the queen in the valid positions in vecValidPos_
  52. };
  53.  
  54. template<typename T>
  55. class Chess
  56. {
  57. public:
  58. 	Chess(T size=8)
  59. 		: size_(size)
  60. 	{
  61. 		vecOrderQueen.reserve(size_);
  62.         vecQueen_.reserve(size_);
  63.         for (T q_i = 0; q_i != size_; ++q_i)
  64.         {
  65.             Queen<T> queen;
  66.             vecQueen_.push_back(queen);
  67.         }
  68.  
  69. /*
  70. 		vecQueenPosVec_.reserve(size_);
  71. 		vecQueenRelPos_.reserve(size_);
  72.  
  73. 		for (T q_i = 0; q_i != size_; ++q_i)
  74. 		{
  75. 			vecQueenPosVec_.push_back(std::vector<T>());
  76. 			vecQueenRelPos_.push_back(size_); //initialize with invalid relative position
  77. 		}
  78. */
  79. 	}
  80. public:
  81. 	void assign_initial_queen(T row, T col)
  82. 	{
  83. 		vecOrderQueen.push_back(col);
  84. 		//now assign the rest of the queens
  85. 		for (T q_i = 0; q_i != size_; ++q_i)
  86. 		{
  87. 			if (q_i != col)
  88. 			{
  89. 				vecOrderQueen.push_back(q_i);
  90. 			}
  91. 			else
  92. 			{
  93.                 vecQueen_[q_i].addValidPos(row);
  94.                 /*
  95. 				vecQueenPosVec_[q_i].push_back(col);
  96. 				vecQueenRelPos_[q_i] = 0;
  97.                 */
  98. 			}
  99. 		}
  100. 	}
  101.  
  102. 	void compute_arrangements();
  103. 	void print_header();
  104.     void print_arrangements();
  105. private:
  106.     void populate_valid_positions_for_next_queen(T queen_index_in_queen_list);
  107. private:
  108. 	T size_; //chess square is size_*size_
  109.     std::vector<Queen<T> > vecQueen_;
  110.     std::vector<std::vector<T> > vecArrangement_;
  111.     // Next one stores queen in a different order than above.
  112.     std::vector<T> vecOrderQueen; //First one is the initial queen. Rest of the queens are traversed sequentially in backtracking
  113. };
  114.  
  115. template<typename T>
  116. void Chess<T>::compute_arrangements()
  117. {
  118.     T relPos = 0;
  119.  
  120.     while (true)
  121.     {
  122.         T queen_index = vecOrderQueen[relPos];
  123.         bool flag_backtrack = false;
  124.  
  125.         if (vecQueen_[queen_index].isCurrentPosValid())
  126.         {
  127.             if (relPos == (size_-1))
  128.             {
  129.                 // current level is the last level in the hierarchy
  130.                 // collect this arrangement
  131.                 std::vector<T> arrangement;
  132.                 arrangement.reserve(size_);
  133.                 for (typename std::vector<Queen<T> >::iterator it = vecQueen_.begin(); it != vecQueen_.end(); ++it)
  134.                 {
  135.                     arrangement.push_back((*it).currentPos());
  136.                 }
  137.                 vecArrangement_.push_back(arrangement);
  138.  
  139.                 vecQueen_[queen_index].moveToNextPos();
  140.             }
  141.             else
  142.             {
  143.                 populate_valid_positions_for_next_queen(++relPos);
  144.             }
  145.         }
  146.         else
  147.         {
  148.             // backtrack to higher level
  149.             flag_backtrack = true;
  150.         }
  151.  
  152.         if (flag_backtrack)
  153.         {
  154.             vecQueen_[queen_index].clearAllPos();
  155.             if (relPos == 0)
  156.             {
  157.                 break;
  158.             }
  159.             --relPos;
  160.  
  161.             T prev_queen_index = vecOrderQueen[relPos];
  162.             vecQueen_[prev_queen_index].moveToNextPos();
  163.         }
  164.     }
  165. }
  166.  
  167. template<typename T>
  168. void Chess<T>::print_header()
  169. {
  170. 	std::cout << "SOLN       COLUMN" << std::endl;
  171. 	std::cout << " #     ";
  172. 	for (T q_i = 0; q_i != size_; ++q_i)
  173. 	{
  174. 		std::cout << " " << (q_i+1);
  175. 	}
  176. 	std::cout << std::endl;
  177. }
  178.  
  179. template<typename T>
  180. void Chess<T>::print_arrangements()
  181. {
  182. 	std::cout << std::endl;
  183.     for (T arrangement_i = 0; arrangement_i != vecArrangement_.size(); ++arrangement_i)
  184.     {
  185.         std::cout << " " << (arrangement_i+1) << "     ";
  186.         for (T q_i = 0; q_i != size_; ++q_i)
  187.         {
  188.             std::cout << " " << vecArrangement_[arrangement_i][q_i]+1;
  189.         }
  190.         std::cout << std::endl;
  191.     }
  192. }
  193.  
  194. template<typename T>
  195. void Chess<T>::populate_valid_positions_for_next_queen(T queen_index_in_queen_list)
  196. {
  197.     T queen_index = vecOrderQueen[queen_index_in_queen_list];
  198.     assert(vecQueen_[queen_index].empty() && "valid position list for the current queen row is expected to be empty");
  199.     // we will check validity for each row in the column belonging to this queen
  200.     for (T pos = 0; pos != size_; ++pos)
  201.     {
  202.         bool valid_pos_flag = true;
  203.         // check one by one the queens at higher level
  204.         for (T q_i = 0; q_i != queen_index_in_queen_list; ++q_i)
  205.         {
  206.             T other_queen_index = vecOrderQueen[q_i];
  207.             T other_queen_pos = vecQueen_[other_queen_index].currentPos();
  208.  
  209.             if (pos == other_queen_pos)
  210.             {
  211.                 valid_pos_flag = false;
  212.                 break;
  213.             }
  214.             T diff_in_col = 0;
  215.             if (other_queen_index < queen_index)
  216.             {
  217.                 diff_in_col = queen_index - other_queen_index;
  218.             }
  219.             else
  220.             {
  221.                 diff_in_col = other_queen_index - queen_index;
  222.             }
  223.  
  224.             T diff_in_row = 0;
  225.             if (pos < other_queen_pos)
  226.             {
  227.                 diff_in_row = other_queen_pos - pos;
  228.             }
  229.             else
  230.             {
  231.                 diff_in_row = pos - other_queen_pos;
  232.             }
  233.  
  234.             if (diff_in_row == diff_in_col)
  235.             {
  236.                 valid_pos_flag = false;
  237.                 break;
  238.             }
  239.         }
  240.  
  241.         if (valid_pos_flag)
  242.         {
  243.             vecQueen_[queen_index].addValidPos(pos);
  244.         }
  245.     }
  246. }
  247.  
  248. int main(int argc, char* argv[])
  249. {
  250. 	unsigned int nDataSet;
  251.     std::ifstream pFile;
  252.  
  253.     if (READ_FROM_FILE)
  254.     {
  255.         pFile.open("D:/cpp_practise/online_judge/uva/750_8_Queens_Chess_Problem_input.txt",std::ios::in);
  256.         assert(pFile.is_open() && "input file not opened");
  257.     }
  258.     if (READ_FROM_FILE)
  259.     {
  260.         pFile >> nDataSet;
  261.     }
  262.     else
  263.     {
  264.         std::cin >> nDataSet;
  265.     }
  266.  
  267. 	for (unsigned int dataset_i = 0; dataset_i != nDataSet; ++dataset_i)
  268. 	{
  269. 		Chess<unsigned int> chess(8);
  270. 		unsigned int initial_queen_row, initial_queen_col;
  271.         if (READ_FROM_FILE)
  272.         {
  273. 		    pFile >> initial_queen_row >> initial_queen_col;
  274.         }
  275.         else
  276.         {
  277.             std::cin >> initial_queen_row >> initial_queen_col;
  278.         }
  279. 		// convert to zero-indexed
  280. 		--initial_queen_row;
  281. 		--initial_queen_col;
  282.  
  283. 		chess.assign_initial_queen(initial_queen_row,initial_queen_col);
  284. 		chess.compute_arrangements();
  285.  
  286.         if (dataset_i > 0)
  287.         {
  288.             std::cout << std::endl;
  289.         }
  290. 		chess.print_header();
  291. 		chess.print_arrangements();
  292. 	}
  293.  
  294.     if (READ_FROM_FILE)
  295.     {
  296.         pFile.close();
  297.     }
  298. 	return 0;
  299. }
  300.  
  301. /*
  302. Test cases:
  303. http://o...content-available-to-author-only...a.es/board/viewtopic.php?p=27847#p27847
  304. http://o...content-available-to-author-only...a.es/board/viewtopic.php?p=39105#p39105
  305. */
Success #stdin #stdout 0s 3444KB
comments (?)
stdin
copy 
4

1 2
6 7
7 8
8 8
stdout
copy 
SOLN       COLUMN
 #      1 2 3 4 5 6 7 8

 1      3 1 7 5 8 2 4 6
 2      4 1 5 8 2 7 3 6
 3      4 1 5 8 6 3 7 2
 4      5 1 4 6 8 2 7 3
 5      5 1 8 4 2 7 3 6
 6      5 1 8 6 3 7 2 4
 7      6 1 5 2 8 3 7 4
 8      7 1 3 8 6 4 2 5

SOLN       COLUMN
 #      1 2 3 4 5 6 7 8

 1      1 7 5 8 2 4 6 3
 2      2 5 7 1 3 8 6 4
 3      2 5 7 4 1 8 6 3
 4      2 7 5 8 1 4 6 3
 5      4 2 7 5 1 8 6 3
 6      4 7 1 8 5 2 6 3
 7      4 8 1 5 7 2 6 3
 8      5 2 4 7 3 8 6 1
 9      5 3 1 7 2 8 6 4
 10      5 3 8 4 7 1 6 2
 11      5 7 1 4 2 8 6 3
 12      5 7 4 1 3 8 6 2
 13      5 8 4 1 7 2 6 3
 14      7 3 8 2 5 1 6 4

SOLN       COLUMN
 #      1 2 3 4 5 6 7 8

 1      4 2 5 8 6 1 3 7
 2      4 2 8 6 1 3 5 7
 3      4 6 1 5 2 8 3 7
 4      5 2 4 6 8 3 1 7
 5      5 3 1 6 8 2 4 7
 6      5 8 4 1 3 6 2 7
 7      6 3 1 8 5 2 4 7
 8      6 3 5 8 1 4 2 7

SOLN       COLUMN
 #      1 2 3 4 5 6 7 8

 1      4 7 5 2 6 1 3 8
 2      5 7 2 6 3 1 4 8
 3      6 3 5 7 1 4 2 8
 4      6 4 7 1 3 5 2 8
https://ideone.com/a5GpMX
language:
C++ (gcc 8.3)
created:
10 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!