Bit Manuplation

layout: post
title:  "Bit Manupulation"
date:  2016-04-01 19:24:56
categories: algorithm

Using bit manupulation to solve the Eight-Queen & Sudoku Problems. Sometime it seems that using bit manupulation can make the problem easy to be interpretated.

Sodoku Problem

 class Solution {
    public: bool dfs(vector < int > &empty_sells, \\
vector < vector < char > >&board, int start, int * col, int * row, int* grid) {
        if (start == empty_sells.size()) return true;
        int r = empty_sells[start] / 9;
        int c = empty_sells[start] % 9;
        int cur_val = col[c] | row[r] | grid[(r / 3) * 3 + c / 3];
        for (int j = 1; j <= 9; j++) {
            if ((cur_val | (1 << (j - 1))) ^ cur_val) {
                col[c]|= (1 << (j - 1));
                row[r] |= (1 << (j - 1));
                grid[(r / 3) * 3 + c / 3] |= (1 << (j - 1));
                board[r][c] = '0' + j;
                if (dfs(empty_sells, board, start + 1, col, row, grid)) {
                    return true;
                }
                board[r][c] = '.';
                col[c]^= (1 << (j - 1));
                row[r] ^= (1 << (j - 1));
                grid[(r / 3) * 3 + c / 3] ^= (1 << (j - 1));
            }
        }
        return false;
    }
    void solveSudoku(vector < vector < char > >&board) {
        int col[9], row[9], grid[9];
        memset(col, 0, sizeof(col));
        memset(row, 0, sizeof(row));
        memset(grid, 0, sizeof(grid));
        vector < int > empty_sells;
        for (int j = 0; j < board.size(); j++) {
             for (int k = 0; k < board[0].size(); k++) {
                 if (board[j][k] != '.') {
                     row[j] |= (1 << (board[j][k] - '0' - 1));
                     col[k] |= (1 << (board[j][k] - '0' - 1));
                     grid[(j / 3) * 3 + k / 3] |= (1 << (board[j][k] - '0' - 1));
                 } else {
                     empty_sells.push_back(j * 9 + k);
                 }
             }
         }
         dfs(empty_sells, board, 0, col, row, grid);
     }
 };

Eight Queens

01 void search(int n, vector<string> &matrix, int cur, int col, int left, int right) {
02         if (cur == n) {
03             ans.push_back(matrix);
04             return;
05         }
06         for (int j = 0; j < n; j ++) {
07             if (((col >> j) % 2) || ((left >> (cur + j)) % 2) || ((right >> (cur + n - 1 - j)) % 2)) continue;
08             matrix[cur][j] = 'Q';
09             search(n, matrix, cur + 1, col | (1 << j), left | (1 << (cur + j)), right | (1 << (cur + n - 1 - j)));
10             matrix[cur][j] = '.';
11         }
12     }
13     vector<vector<string> > solveNQueens(int n) {
14         col = left = right = 0;
15         vector<string> matrix;
16         string str = "";
17         for (int j = 0; j < n; j ++) str += ".";
18         for (int i = 0; i < n; i ++) {
19             matrix.push_back(str);
20         }
21         search(n, matrix, 0, 0, 0, 0);
22         return ans;
23     }

Leave a Reply

Your email address will not be published. Required fields are marked *