Problem solving techniques (Example problems) (Cont.)

Time for backtracking is now. In this post i will show you how to use backtracking solving a specific type of problems. To know about backtracking please revise previous posts.

Problem 10 (8 Queens problem)

 The eight queens puzzle is the problem of placing eight chess queens on an 8×8 chessboard so that no two queens attack each other. Thus, a solution requires that no two queens share the same row, column, or diagonal.

Solution

  

/**

 * rows: Each cell represents the col number that will contain a queen in this row

 * curRow: The current row to be filled

**/

int cnt = 0;
void place_8_queens(int rows[], int curRow) {
    if(curRow >= 8) {
        for(int i = 0; i < 8; i++) cout << rows[i] << " ";
        cout << endl;
        cnt++;
        return;
    }
  
    for(int i = 0; i < 8; i++) {
        bool valid = true;
        for(int j = 0; j < curRow; j++)
            if(rows[j] == i || (i == rows[j]+(curRow-j)) || (i == rows[j]-(curRow-j)))
                valid = false;
       
        if(valid) {
            rows[curRow] = i;
            place_8_queens(rows, curRow+1);
        }
    }
}

int main() {
    int rows[8];
  
    place_8_queens(rows, 0);
    cout << "There are " cnt << " valid placement." << endl;
}

Problem 11 (Tree Find)

In this problem given a tree whith the following definition:

struct node {
    int val;                    // Current node value
    vector<int> childs; // Contains the indices of the cilds nodes
};

vector<node> tree;   // Tree[0] is the tree root

and an element, find this element.

Solution

This solution is a DFS (Depth first search) where at each time visiting a node, check if it holds the element return true, else find it in its childs.

bool search_tree(node cur, int elem) {
    if(cur.val == elem) return true;
   
    for(int i = 0; i < cur.childs.size(); i++)  // Search all childs of current node
        if(search_tree(tree[cur.childs[i]]), elem) return true; // Found it, return true
       
    return false; // not found neither in this node nor in its child, then backtrack
}

int main() {
    search_tree(tree[0], -21);
}

Problem 12 (Sudoku)

Sudoku puzzles consists of a partially completed row-column grid of cells partitioned into N regions or zones each of size N cells, to be filled in using a prescribed set of N distinct symbols (typically the numbers {1, ..., N}), so that each row, column and region contains exactly one of each element of the set. The puzzle can be solved using a variety of algorithms. Here is the backtracking way to solve it:

#define N    3 // For learning purposes

bool check_row(int grid[][N], int row, int col, int a) {
    for(int i = 0; i < col; i++)
        if(grid[row][i] == a) return false;
      
    return true;
}

bool check_col(int grid[][N], int row, int col, int a) {
    for(int i = 0; i < row; i++)
        if(grid[i][col] == a) return false;
      
    return true;
}

void small_sudoku(int grid[][N], int i, int j) {
    vector<int> allowed_nums;
    int a;
   
    for(a = 1; a <= N; a++) {
        if(check_row(grid, i, j, a) && check_col(grid, i, j, a)) {
            grid[i][j] = a;
              
            if(j < N-1) small_sodoku(grid, i, j+1);
            else if(j == N-1 && i < N-1) small_sodoku(grid, i+1, 0);
            else {
                cout << "Found placement" << endl;
              
                for(int r = 0; r < N; r++) {
                    for(int c = 0; c < N; c++)
                        cout << grid[r][c] << " ";
                    cout << endl;
                }
            }
        }
    }
}

In the next post i will show you how to solve graph related problems.