{"id":26729,"date":"2017-12-22T20:31:35","date_gmt":"2017-12-22T15:01:35","guid":{"rendered":"https:\/\/www.wikitechy.com\/technology\/?p=26729"},"modified":"2017-12-22T20:31:35","modified_gmt":"2017-12-22T15:01:35","slug":"branch-bound-n-queen-problem","status":"publish","type":"post","link":"https:\/\/www.wikitechy.com\/technology\/branch-bound-n-queen-problem\/","title":{"rendered":"Branch and Bound | Set 5 (N Queen Problem)"},"content":{"rendered":"

The\u00a0N queens puzzle<\/strong>\u00a0is the problem of placing N\u00a0chess<\/a>\u00a0queens<\/a>\u00a0on an N\u00d7N chessboard so that no two queens threaten each other. Thus, a solution requires that no two queens share the same row, column, or diagonal.<\/p>\n

For example, below is one of the solution for famous 8 Queen problem.\"Branch<\/p>\n

Backtracking Algorithm for N-Queen is already discussed here<\/a>. In backtracking solution we backtrack when we hit a dead end. In Branch and Bound solution, after building a partial solution, we figure out that there is no point going any deeper as we are going to hit a dead end<\/strong>.<\/em><\/p>\n

Let\u2019s begin by describing backtracking solution. \u201cThe idea is to place queens one by one in different columns, starting from the leftmost column. When we place a queen in a column, we check for clashes with already placed queens. In the current column, if we find a row for which there is no clash, we mark this row and column as part of the solution. If we do not find such a row due to clashes, then we backtrack and return false.<\/p>\n

\"Branch<\/p>\n

    \n
  1. For the 1st Queen, there are total 8 possibilities as we can place 1st Queen in any row of first column. Let\u2019s place Queen 1 on row 3.<\/li>\n
  2. After placing 1st Queen, there are 7 possibilities left for the 2nd Queen. But wait, we don\u2019t really have 7 possibilities. We cannot place Queen 2 on rows 2, 3 or 4 as those cells are under attack from Queen 1. So, Queen 2 has only 8 \u2013 3 = 5 valid positions left.<\/li>\n
  3. After picking a position for Queen 2, Queen 3 has even fewer options as most of the cells in its column are under attack from the first 2 Queens.<\/li>\n<\/ol>\n[ad type=”banner”]\n

    We need to figure out an efficient way of keeping track of which cells are under attack. In previous solution we kept an 8\u00ad-by\u00ad-8 Boolean matrix and update it each time we placed a queen, but that required linear time to update as we need to check for safe cells.<\/p>\n

    Basically, we have to ensure 4 things:
    \n1. No two queens share a column.
    \n2. No two queens share a row.
    \n3. No two queens share a top-right to left-bottom diagonal.
    \n4. No two queens share a top-left to bottom-right diagonal.<\/p>\n

    Number 1 is automatic because of the way we store the solution. For number 2, 3 and 4, we can perform updates in O(1) time. The idea is to keep three Boolean arrays that tell us which rows and which diagonals are occupied<\/strong>.<\/p>\n

    Lets do some pre-processing first. Let\u2019s create two N x N matrix one for \/ diagonal and other one for \\ diagonal. Let\u2019s call them slashCode and backslashCode respectively. The trick is to fill them in such a way that two queens sharing a same \/\u00addiagonal will have the same value in matrix slashCode, and if they share same \\\u00addiagonal, they will have the same value in backslashCode matrix.<\/p>\n

    For an N x N matrix, fill slashCode and backslashCode matrix using below formula \u2013<\/p>\n

    slashCode\t\t\t

    \n\t\t\t\t\t\t\t<\/div>\n\t\t\t\t\t
    \n\t\t\t\t\t\t\t<\/div>\n\t\t = row + col
    \nbackslashCode\t\t\t
    \n\t\t\t\t\t\t\t<\/div>\n\t\t\t\t\t
    \n\t\t\t\t\t\t\t<\/div>\n\t\t = row \u2013 col + (N-1)<\/p>\n

    Using above formula will result in below matrices<\/p>\n

    \"Branch<\/p>\n

    The \u2018N \u2013 1\u2019 in the backslash code is there to ensure that the codes are never negative because we will be using the codes as indices in an array.<\/p>\n[ad type=”banner”]\n

    Now before we place queen i on row j, we first check whether row j is used (use an array to store row info). Then we check whether slash code ( j + i ) or backslash code ( j \u2013 i + 7 ) are used (keep two arrays that will tell us which diagonals are occupied). If yes, then we have to try a different location for queen i. If not, then we mark the row and the two diagonals as used and recurse on queen i + 1. After the recursive call returns and before we try another position for queen i, we need to reset the row, slash code and backslash code as unused again, like in the code from the previous notes.<\/p>\n

    Below is C++ implementation of above idea \u2013<\/p>\n

    <\/div> 
    \/* C++ program to solve N Queen Problem using Branch   and Bound *\/#include<stdio.h>#include<string.h>#define N 8 \/* A utility function to print solution *\/void printSolution(int board[N][N]){    for (int i = 0; i < N; i++)    {        for (int j = 0; j < N; j++)            printf("%2d ", board[i][j]);        printf("\\n");    }} \/* A Optimized function to check if a queen canbe placed on board[row][col] *\/bool isSafe(int row, int col, int slashCode[N][N],            int backslashCode[N][N], bool rowLookup[],            bool slashCodeLookup[], bool backslashCodeLookup[] ){    if (slashCodeLookup[slashCode[row][col]] ||        backslashCodeLookup[backslashCode[row][col]] ||        rowLookup[row])    return false;     return true;} \/* A recursive utility function to solve N Queen problem *\/bool solveNQueensUtil(int board[N][N], int col,    int slashCode[N][N], int backslashCode[N][N], bool rowLookup[N],    bool slashCodeLookup[], bool backslashCodeLookup[] ){    \/* base case: If all queens are placed    then return true *\/    if (col >= N)        return true;     \/* Consider this column and try placing       this queen in all rows one by one *\/    for (int i = 0; i < N; i++)    {        \/* Check if queen can be placed on           board[i][col] *\/        if ( isSafe(i, col, slashCode, backslashCode, rowLookup,                    slashCodeLookup, backslashCodeLookup) )        {            \/* Place this queen in board[i][col] *\/            board[i][col] = 1;            rowLookup[i] = true;            slashCodeLookup[slashCode[i][col]] = true;            backslashCodeLookup[backslashCode[i][col]] = true;             \/* recur to place rest of the queens *\/            if ( solveNQueensUtil(board, col + 1, slashCode, backslashCode,                    rowLookup, slashCodeLookup, backslashCodeLookup) )                return true;             \/* If placing queen in board[i][col]            doesn't lead to a solution, then backtrack *\/             \/* Remove queen from board[i][col] *\/            board[i][col] = 0;            rowLookup[i] = false;            slashCodeLookup[slashCode[i][col]] = false;            backslashCodeLookup[backslashCode[i][col]] = false;        }    }     \/* If queen can not be place in any row in        this colum col then return false *\/    return false;} \/* This function solves the N Queen problem usingBranch and Bound. It mainly uses solveNQueensUtil() tosolve the problem. It returns false if queenscannot be placed, otherwise return true andprints placement of queens in the form of 1s.Please note that there may be more than onesolutions, this function prints one of thefeasible solutions.*\/bool solveNQueens(){    int board[N][N];    memset(board, 0, sizeof board);     \/\/ helper matrices    int slashCode[N][N];    int backslashCode[N][N];     \/\/ arrays to tell us which rows are occupied    bool rowLookup[N] = {false};     \/\/keep two arrays to tell us which diagonals are occupied    bool slashCodeLookup[2*N - 1] = {false};    bool backslashCodeLookup[2*N - 1] = {false};     \/\/ initalize helper matrices    for (int r = 0; r < N; r++)        for (int c = 0; c < N; c++)            slashCode[r]1 = r + c,            backslashCode[r]1 = r - c + 7;     if (solveNQueensUtil(board, 0, slashCode, backslashCode,      rowLookup, slashCodeLookup, backslashCodeLookup) == false )    {        printf("Solution does not exist");        return false;    }     \/\/ solution found    printSolution(board);    return true;} \/\/ driver program to test above functionint main(){    solveNQueens();     return 0;}<\/code><\/pre> <\/div>\n
     <\/p>\n
    Output :<\/p>\n
     1  0  0  0  0  0  0  0 \r\n 0  0  0  0  0  0  1  0 \r\n 0  0  0  0  1  0  0  0 \r\n 0  0  0  0  0  0  0  1 \r\n 0  1  0  0  0  0  0  0 \r\n 0  0  0  1  0  0  0  0 \r\n 0  0  0  0  0  1  0  0 \r\n 0  0  1  0  0  0  0  0<\/pre>\n[ad type=”banner”]\n","protected":false},"excerpt":{"rendered":"
    Branch and Bound (N Queen Problem)-Branch and Bound The N queens puzzle is the problem of placing N chess queens on an N\u00d7N chessboard so.<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[69969,79474,83676],"tags":[79757,79756,79752,74484,79754,79753,79755,79751,79762,79758,74494,79750,79763,79759,79760,79761],"class_list":["post-26729","post","type-post","status-publish","format-standard","hentry","category-algorithm","category-branch-and-bound","category-n-queen-problem","tag-4-queen-problem-using-backtracking-in-c","tag-4-queen-problem-using-backtracking-ppt","tag-4-queens-problem-state-space-tree","tag-4-queens-problem-using-backtracking-algorithm","tag-5-queens-problem","tag-5-queens-solution","tag-8-queens-problem-in-design-and-analysis-of-algorithm","tag-backtracking-and-branch-and-bound-algorithms","tag-complexity-of-graph-coloring-using-backtracking","tag-n-queen-problem-algorithm-using-backtracking","tag-n-queen-problem-in-c","tag-n-queen-problem-time-complexity","tag-space-complexity-of-n-queen-problem","tag-time-complexity-of-backtracking-algorithms","tag-time-complexity-of-graph-coloring-problem","tag-time-complexity-of-sum-of-subsets-problem-using-backtracking"],"_links":{"self":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts\/26729","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/comments?post=26729"}],"version-history":[{"count":0,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts\/26729\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/media?parent=26729"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/categories?post=26729"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/tags?post=26729"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}