In chess it is possible to place eight queens on the board so that no one queen can be taken by any other. Write a program that will determine all such possible arrangements for eight queens given the initial position of one of the queens.
Input
The first line of the input contains the number of datasets, and it's followed by a blank line. Each dataset contains a pair of positive integers separated by a single space that describes the initial position of one of the 8 queens
Output
Output for each dataset will consist of a one-line-per-solution representation.
Each solution will be sequentially numbered 1...N. Each solution will consist of 8 numbers. Each of the 8 numbers will be the ROW coordinate for that solution. The column coordinate will be indicated by the order in which the 8 numbers are printed. That is, the rst number represents the ROW in which the queen is positioned in column 1; the second number represents the ROW in which the queen is positioned in column 2, and so on
Sample Input
1 1 1
Sample Output
SOLN COLUMN # 1 2 3 4 5 6 7 8 1 1 5 8 6 3 7 2 4 2 1 6 8 3 7 4 2 5 3 1 7 4 6 8 2 5 3 4 1 7 5 8 2 4 6 3
The full description of the problem can be found here.
#include <iostream>
#include <algorithm>
#include <vector>
#include <cmath>
class Chess
{
const int row_size, col_size;
const int row_queen, col_queen;
std::vector<std::vector<int> > sol;
// queens_row_num[i] == on which row the queen is placed on col i
int queens_row_num[8 + 1], idx_queens_row_num;
bool queen_is_in_attack_pos(const int &row, const int &col)
{
for ( int j = 1; j <= col_size; ++j )
{
if ( queens_row_num[j] )
{
if ( std::abs(queens_row_num[j] - row) ==
std::abs(j - col) ||
queens_row_num[j] == row || j == col )
return true;
}
}
return false;
}
bool eight_queens_are_in_place()
{
for ( int j = 1; j <= col_size; ++j )
{
if ( !queens_row_num[j] )
return false;
}
return true;
}
void store_cur_sol()
{
std::vector<int> v;
for ( int j = 1; j <= col_size; ++j )
{
v.push_back(queens_row_num[j]);
}
sol.push_back(v);
}
void go_through_board(int col)
{
if ( eight_queens_are_in_place() )
{
store_cur_sol();
return;
}
for ( int j = col + 1; j <= col_size; ++j )
{
if ( queens_row_num[j] )
continue;
for ( int i = 1; i <= row_size; ++i )
{
if ( !queen_is_in_attack_pos(i, j) )
{
queens_row_num[j] = i;
go_through_board(j);
queens_row_num[j] = 0;
}
}
}
}
public:
Chess(const int &r, const int &c) : row_queen(r), col_queen(c),
row_size(8), col_size(8)
{}
void find_solutions()
{
// go through the column so as to get the solution
// in sorted order
std::fill(queens_row_num, queens_row_num + col_size + 1, 0);
queens_row_num[col_queen] = row_queen;
go_through_board(0);
}
void print_solutions()
{
std::cout << "SOLN COLUMN" << std::endl;
std::cout << " # 1 2 3 4 5 6 7 8" << std::endl;
std::cout << std::endl;
for ( int i = 1; i <= (int)sol.size(); ++i )
{
std::cout << (i < 10 ? " " : "") << i << " ";
for ( int k = 0; k < col_size; ++k )
{
std::cout << " " << sol[i - 1][k];
}
std::cout << std::endl;
}
}
};
int main()
{
int T;
std::cin >> T;
for ( int t = 1; t <= T; ++t )
{
int r, c;
std::cin >> r >> c;
Chess chess = Chess(r, c);
chess.find_solutions();
chess.print_solutions();
if ( t < T )
std::cout << std::endl;
}
return 0;
}
What are the possible way to improve:
- on quality-wise
- to make it more readable so that someone can understand 6 months down the road
- to make it more C++-like