Sudoku

/***

Sudoku

Given a partially filled 9×9 2D array ‘grid[9][9]‘, the goal is to assign digits (from 1 to 9) to the empty cells so that every row, column, and subgrid of size 3×3 contains exactly one instance of the digits from 1 to 9.

Backtracking Algorithm

Like all other Backtracking problems, we can solve Sudoku by one by one assigning numbers to empty cells. Before assigning a number, we check whether it is safe to assign. We basically check that the same number is not present in current row, current column and current 3X3 subgrid. After checking for safety, we assign the number, and recursively check whether this assignment leads to a solution or not. If the assignment doesn’t lead to a solution, then we try next number for current empty cell. And if none of number (1 to 9) lead to solution, we return false.

***/

#include<iostream>

using namespace std;

class Sudoku {

public:

       Sudoku(int (*m)[9]);

       ~Sudoku(){ };

       bool fill_Sudoku();

       void print();

private:

       int sudo[9][9];

       // index by number, fill[i][j], j is the row array which fill by the column.

       int fill[10][9];

       bool isSafe(int, int, int);

       bool isSuccess(int*, int*);

};

Sudoku :: Sudoku (int (*m)[9]) {

       //initial sudo[][] and fill[][]

       for(int i = 1; i<10; i++) {

              for(int j = 0; j<9; j++)

                     fill[i][j] = -1;

       }

       for(int i = 0; i<9; i++) {

              for(int j = 0; j<9; j++) {

                     sudo[i][j] = m[i][j];

                     if(sudo[i][j] != 0) {

                           fill[sudo[i][j]][i] = j;

                     }

              }

       }

}

bool Sudoku :: isSafe(int num, int row, int col) {

       if(fill[num][row] != -1) return false;

       for(int i = 0; i<9; i++) {

              if(fill[num][i] == col) return false;

       }

       int r = row / 3;

       int c = col / 3;

       for(int i = r*3; i<r*3+3; i++) {

              for(int j = c*3; j<c*3+3; j++) {

                     if(sudo[i][j] == num) return false;

              }

       }

       return true;

}

bool Sudoku :: isSuccess(int *row, int *col) {

       for(int i = 0; i<9; i++) {

              for(int j = 0; j<9; j++) {

                     if(sudo[i][j] == 0) {

                           *row = i;

                           *col = j;

                           return false;

                     }

              }

       }

       return true;

}

bool Sudoku :: fill_Sudoku() {

       int row, col;

       if(isSuccess(&row, &col)) {

              return true;

       }

       for(int i = 1; i<=9; i++) {

              if(isSafe(i, row, col)) {

                     sudo[row][col] = i;

                     fill[i][row] = col;

                     if(fill_Sudoku()) return true;

                    

                     sudo[row][col] = 0;

                     fill[i][row] = -1;

              }            

       }

       return false;

}

void Sudoku::print() {

       for (int i = 0; i<9; i++)

       {

              for (int j = 0; j<9; j++)

              {

                     cout<<sudo[i][j]<<” “;

              }

              cout<<endl;

       }

}

int main()

{

       // 0 means unassigned cells

       int grid[9][9] = {

       {3, 0, 6, 5, 0, 8, 4, 0, 0},

       {5, 2, 0, 0, 0, 0, 0, 0, 0},

       {0, 8, 7, 0, 0, 0, 0, 3, 1},

       {0, 0, 3, 0, 1, 0, 0, 8, 0},

       {9, 0, 0, 8, 6, 3, 0, 0, 5},

       {0, 5, 0, 0, 9, 0, 6, 0, 0},

       {1, 3, 0, 0, 0, 0, 2, 5, 0},

       {0, 0, 0, 0, 0, 0, 0, 7, 4},

       {0, 0, 5, 2, 0, 6, 3, 0, 0}};

      

       Sudoku sd(grid);

       sd.fill_Sudoku();

       sd.print();

       return 0;

}

Backtracking Algorithm

Backtracking is a general algorithm for finding all (or some) solutions to some computational problem, that incrementally builds candidates to the solutions, and abandons each partial candidate c (“backtracks”) as soon as it determines that c cannot possibly be completed to a valid solution.

Backtracking can be applied only for problems which admit the concept of a “partial candidate solution” and a relatively quick test of whether it can possibly be completed to a valid solution. It is useless, for example, for locating a given value in an unordered table. When it is applicable, however, backtracking is often much faster than brute force enumeration of all complete candidates, since it can eliminate a large number of candidates with a single test.

Backtracking is an important tool for solving constraint satisfaction problems, such as crosswords, verbal arithmetic,Sudoku, and many other puzzles. It is often the most convenient (if not the most efficient) technique for parsing, for the knapsack problem and other combinatorial optimization problems. It is also the basis of the so-called logic programming languages such as Icon, Planner and Prolog. Backtracking is also utilized in the (diff) difference engine for the MediaWiki software.

Basic Problem:

Eight queens pluzzle

Sudoku

Knapsack

…..

Basic Idea:

Only compute the eligible candidates, thus if the candidates are not valid for the constraint, abandon it.

Method as if push_back(obj), recursive call, than pop_back()…

Diameter of Tree (in the form of parent pointer)

/***

Given a tree in the form of parent pointers of every node (for root assume parent pointer to be null), write code to find the diameter of tree.

IDEA: Space complexity O(1), time complexity(nlogn)

// mark non-leaf nodes

for each node do

  mark its direct parent node

end

// get max length

for each node do

  if node is marked then //non-leaf

    skip

  else // leaf

    visit all parent nodes until root and count the length

    keep the max length

  end

end

***/

#include<iostream>

using namespace std;

class node {

public:

       node(int);

       int data;

       bool visit;

       node *parent;

};

node :: node(int val) {

       data = val;

       visit = true;

       parent = nullptr;

}

int diameter_tree(node **n, int size) {

       int height = 0;

       // mark node to find leaf

       for(int i = 0; i<size; i++) {

       //Note: edge condition of parent

              if (n[i]->parent != nullptr)

                     n[i]->parent->visit = false;     

       }

       for(int i = 0; i<size; i++) {

              if(n[i]->visit) {

                     node *ptr = n[i];

                     int h = 0;

                     while(ptr != nullptr) {   

                           h++;

                           ptr = ptr->parent;  

                     }

                     if(h > height) height = h;

              }

       }     

       return height;      

}

void main() {

       node *n[7];

       for (int i = 0; i<7; i++)

              n[i] = new node(i+1);

       n[0]->parent = n[4];

       n[1]->parent = n[4];

       n[2]->parent = n[5];

       n[3]->parent = n[5];

       n[4]->parent = n[6];

       n[5]->parent = n[6];

       cout<<diameter_tree(n, 7)<<endl;

}

Longest Substring Without Repeat

#include <iostream>

#include <string>

using namespace std;

class LongSubstring {

public:

       LongSubstring();

       ~LongSubstring();

       int getLongestSubstring(string s);

       string out;

       int maxlength;

private:

       bool isMax(int a, int b);

       void map_to_hash(char, int);

       int get_hash_value(char);

       void update(int, int);

       int start;

       int hash[26];

};

bool LongSubstring::isMax(int a, int b){

       if(a > b) return true;

       return false;

}

LongSubstring::LongSubstring() {

       for(int i = 0; i < 26; i++)

       {

              hash[i] = -1;

       }

       maxlength = 1;

       start = 0;

}

LongSubstring::~LongSubstring(){

}

int LongSubstring::getLongestSubstring(string s) {

       // Start typing your C/C++ solution below

       // DO NOT write int main() function

       if(s.size() == 0)

              return 0;

      

       int temp = 0;

       map_to_hash(s[0], 0);

       for(int i = 1; i < s.size(); i++){

              if(get_hash_value(s[i]) < temp){

                     map_to_hash(s[i], i);          

              }

              else{

                     temp = get_hash_value(s[i]) + 1;

                     map_to_hash(s[i], i);              

              }            

              if (!isMax(maxlength,  i-temp+1)) update(i, temp);

       }

       out.assign(s,start,maxlength);

       return maxlength;

}

void LongSubstring::update(int cur, int oldpos){

       start = oldpos;

       maxlength = cur-oldpos+1;

}

void LongSubstring::map_to_hash(char ch, int pos){

       hash[ch – ‘a’] = pos;

}

int LongSubstring::get_hash_value(char ch) {

       return hash[ch – ‘a’];

}

void main() {

       string str;

       //char* ch;

       LongSubstring ls;

       str = “abcabcdbb”;

       //ch = &str[0];

       cout<<ls.out<<”      length: “<<ls.getLongestSubstring(str)<<endl;

}

Recover Binary Tree through it preorder and inorder traversal

/***

Given preorder and inorder traversal of a tree, construct the binary tree.

Example:

preorder = {7,10,4,3,1,2,8,11}

inorder = {4,10,3,1,7,11,8,2}

***/

#include<iostream>

using namespace std;

class node {

public:

       int data;

       node *left, *right;

       node(int val) {

              this->data = val;

              this->left = nullptr;

              this->right = nullptr;

       }

};

class binarytree {

public:

       binarytree(int *pre, int *in, int sz) {

              preorder = pre;

              inorder = in;

              size = sz;

       }

       node *getroot();

       void printBT();

private:

       node *constructBT(int &index, int begin, int end);

       int findindex(int val, int begin, int end);

       int *preorder;

       int *inorder;

       int size;

       node *root;  

};

int binarytree::findindex(int val, int begin, int end) {

       for(int i = begin; i<=end; i++) {

              if(inorder[i] == val) return i;

       }

       return -1;

}

node * binarytree::constructBT(int &index, int begin, int end) {    

       if(begin > end) {

              index–;

              return nullptr;

       }

       node *n = new node(preorder[index]);

       if(begin == end) return n;

       node *left, *right;

       int id = findindex(preorder[index], begin, end);

       index++;

       left = constructBT(index, begin, id-1);

       index++;

       right = constructBT(index, id+1, end);

       n->left = left;

       n->right = right;

       return n;    

}

node * binarytree::getroot(){

       int index = 0;

       root = constructBT(index, 0, size-1);

       return root;

}

void printBT(node *root) {

       if (root == nullptr) return;

      

       printBT(root->left);

       cout<<root->data<<” “;

       printBT(root->right);

}

void main() {

       int preorder[] = {7,10,4,3,1,2,8,11};

       int inorder[] = {4,10,3,1,7,11,8,2};

       int sz = sizeof(preorder) / sizeof(int);

       binarytree bt(preorder, inorder, sz);

       node *root = bt.getroot();

       node *p = root;

       printBT(p);

}

Recover Binary Tree through it preorder and inorder traversal

/***

Given preorder and inorder traversal of a tree, construct the binary tree.

Example:

preorder = {7,10,4,3,1,2,8,11}

inorder = {4,10,3,1,7,11,8,2}

***/

#include<iostream>

using namespace std;

classnode {

public:

       int data;

       node *left, *right;

       node(intval) {

              this->data = val;

              this->left = nullptr;

              this->right = nullptr;

       }

};

classbinarytree {

public:

       binarytree(int *pre, int *in, intsz) {

              preorder = pre;

              inorder = in;

              size = sz;

       }

       node *getroot();

       void printBT();

private:

       node *constructBT(int &index, int begin, int end);

       int findindex(int val, int begin, int end);

       int *preorder;

       int *inorder;

       int size;

       node *root;  

};

intbinarytree::findindex(intval, intbegin, intend) {

       for(int i = begin; i<=end; i++) {

              if(inorder[i] == val) return i;

       }

       return -1;

}

node * binarytree::constructBT(int &index, intbegin, intend) {    

       if(begin > end) {

              index–;

              returnnullptr;

       }

       node *n = newnode(preorder[index]);

       if(begin == end) return n;

       node *left, *right;

       int id = findindex(preorder[index], begin, end);

       index++;

       left = constructBT(index, begin, id-1);

       index++;

       right = constructBT(index, id+1, end);

       n->left = left;

       n->right = right;

       return n;    

}

node * binarytree::getroot(){

       int index = 0;

       root = constructBT(index, 0, size-1);

       return root;

}

void printBT(node *root) {

       if (root == nullptr) return;

      

       printBT(root->left);

       cout<<root->data<<” “;

       printBT(root->right);

}

void main() {

       int preorder[] = {7,10,4,3,1,2,8,11};

       int inorder[] = {4,10,3,1,7,11,8,2};

       int sz = sizeof(preorder) / sizeof(int);

       binarytree bt(preorder, inorder, sz);

       node *root = bt.getroot();

       node *p = root;

       printBT(p);

}

Closest Pair of Points

/*** Divide & Conquer – Closest Pair of Points

We are given an array of n points in the plane, and the problem is to find out the closest pair of points in the array. This problem arises in a number of applications. For example, in air-traffic control, you may want to monitor planes that come too close together, since this may indicate a possible collision. Recall the following formula for distance between two points p and q.

       Euclidean Distance = sqrt((p1.x – p2.x)^2 + (p1.y – p2.y)^2);

***/

#include<iostream>

#include<cmath>

#include <vector>

#include<algorithm>

#include<utility>

#include<limits>

using namespace std;

struct point {

       int x;

       int y;

};

bool sX (point p1, point p2);

bool sY (point p1, point p2);

class closestPair {

public:

       closestPair(int (*a)[2], int n);

       ~closestPair(){ }

       void getClosestpair(int begin, int end);

       double minDist;

      

private:

       vector<point> points;

//     int minDist;

       pair<point, point> closest;

       double distance(point p1, point p2);

       void crossDist(int vline, int begin, int end);

};

closestPair::closestPair(int (*a)[2], int n) {

       point p;

       points.clear();

       for(int i = 0; i < n; i++) {

              p.x = a[i][0];

              p.y = a[i][1];

              points.push_back(p);

       }

       sort(points.begin(), points.end(), sX);

       minDist = INT_MAX;

}

void closestPair::getClosestpair(int begin, int end) {

       int mid;

       double dist;

       int vline;

       if(begin == end) return;

       if(begin == end + 1) {

              dist = distance(points[begin], points[end]);

              if(minDist > dist) {

                     minDist = dist;

                     closest = make_pair(points[begin], points[end]);

              }

       }

       mid = (begin + end) / 2;

       vline = points[mid].x;

       getClosestpair(begin, mid);

       getClosestpair(mid+1, end);

       crossDist(vline, begin, end);

}

bool sX (point p1, point p2) {

       return (p1.x < p2.x);

}

bool sY (point p1, point p2) {

       return (p1.y < p2.y);

}

double closestPair::distance(point p1, point p2) {

       return sqrt((p1.x – p2.x)*(p1.x – p2.x) + (p1.y – p2.y)*(p1.y – p2.y));

}

void closestPair::crossDist(int vline, int begin, int end) {

       int xd;

       double dist;

       vector<point> left, right;

       for(int i = begin; i <= end; i++) {

              xd = points[i].x – vline;

              if(xd > 0 && abs(xd) < minDist) {

                     right.push_back(points[i]);

              }

              if(xd <= 0 && abs(xd) < minDist) {

                     left.push_back(points[i]);

              }

       }

       sort(left.begin(), left.end(), sY);

       sort(right.begin(), right.end(), sY);

       for(int i = 0; i < left.size(); i++) {

              for(int j = 0; j < right.size(); j++) {

                     if(j > i+7) break;

                     dist = distance(left[i], right[j]);

                     if(dist < minDist) {

                           minDist = dist;

                           closest = make_pair(points[i], points[j]);

                     }

              }

       }            

}

int main()

{

       int a[][2] = {{2, 3}, {12, 30}, {40, 50}, {5, 1}, {12, 10}, {3, 4}};

       int n = sizeof(a) / sizeof(a[0]);

       closestPair cp(a, n);

       cp.getClosestpair(0, n-1);

       cout<< “min = “<< cp.minDist<<endl;

       return 0;

}

Longest palindrome substring

/***Compute the longest palindrome substring ***/

#include <iostream>

#include <string>

using namespace std;

bool isPalindrom(string str, int start, int end) {

       if (start == end || start > end) return true;

       while (start != end && start < end)

       {

              if (str[start] != str[end]) return false;

              else {

                     start += 1;

                     end -= 1;

              }

       }

       return true;

}

string chk_longPalindrom(string str, int start, int chklen) {

       string outstr;

       int st;

      

       while (chklen != 0)

       {

              st = start;

              for(unsigned int i = 0; i < str.size()-chklen+1; i++) {

                     if (isPalindrom(str, st, st+chklen-1))

                     {

                           outstr.assign(str.begin()+st, str.begin()+st+chklen);

                           return outstr;

                     }

                     st++;

              }

              chklen–;

       }

       return “”;

}

void main() {

       string str = “FourscoreandsevenyearsagoourfaathersbroughtforthonthiscontainentanewnationconceivedinzLibertyanddedicatedtothepropositionthatallmenarecreatedequalNowweareengagedinagreahtcivilwartestingwhetherthatnaptionoranynartionsoconceivedandsodedicatedcanlongendureWeareqmetonagreatbattlefiemldoftzhatwarWehavecometodedicpateaportionofthatfieldasafinalrestingplaceforthosewhoheregavetheirlivesthatthatnationmightliveItisaltogetherfangandproperthatweshoulddothisButinalargersensewecannotdedicatewecannotconsecratewecannothallowthisgroundThebravelmenlivinganddeadwhostruggledherehaveconsecrateditfaraboveourpoorponwertoaddordetractTgheworldadswfilllittlenotlenorlongrememberwhatwesayherebutitcanneverforgetwhattheydidhereItisforusthelivingrathertobededicatedheretotheulnfinishedworkwhichtheywhofoughtherehavethusfarsonoblyadvancedItisratherforustobeherededicatedtothegreattdafskremainingbeforeusthatfromthesehonoreddeadwetakeincreaseddevotiontothatcauseforwhichtheygavethelastpfullmeasureofdevotionthatweherehighlyresolvethatthesedeadshallnothavediedinvainthatthisnationunsderGodshallhaveanewbirthoffreedomandthatgovernmentofthepeoplebythepeopleforthepeopleshallnotperishfromtheearth”;

       string longsub = chk_longPalindrom(str, 0, str.size());

       cout<<“Long sub string is [ “<<longsub<<” ]”<<endl;

}

Compute Adjacent pair

/****

Integer V lies strictly between integers U and W if U < V < W or if U > V > W.

A non-empty zero-indexed array A consisting of N integers is given. A pair of indices (P, Q), where 0 ≤ P < Q < N, is said to have adjacent values if no value in the array lies strictly between values A[P] and A[Q].

For example, in array A such that:

A[0] = 0 A[1] = 3 A[2] = 3

A[3] = 7 A[4] = 5 A[5] = 3

A[6] = 11 A[7] = 1

the following pairs of indices have adjacent values:

(0, 7), (1, 2), (1, 4),

(1, 5), (1, 7), (2, 4),

(2, 5), (2, 7), (3, 4),

(3, 6), (4, 5), (5, 7).

For example, indices 4 and 5 have adjacent values because there is no value in array A that lies strictly between A[4] = 5 and A[5] = 3; the only such value could be the number 4, and it is not present in the array.

Write a function that returns number of adjacent values ****/

#include<iostream>

#include<map>

#include<vector>

#include<algorithm>

using namespace std;

class find_adjacent_pair

{

public:

       find_adjacent_pair();

       ~find_adjacent_pair();

       void print_adjacent_pairs(int*);

private:

       map<int, vector<int>> mymap;

       void map_input(int*);

       void add_new_entry(int, int);

       void compute_self_pair(vector<int>);

       void compute_neighbour_pair(vector<int>, vector<int>);

};

find_adjacent_pair::find_adjacent_pair()

{

       mymap.clear();

}

find_adjacent_pair::~find_adjacent_pair()

{

       mymap.clear();

}

void find_adjacent_pair::print_adjacent_pairs(int* in) {

       map<int, vector<int>>::iterator its;

       map<int, vector<int>>::iterator itd;

       map_input(in);

       //key in the map is already sorted

       its = mymap.begin();

       compute_self_pair(its->second);

       while(its != mymap.end()) {

              itd=its;

              its++;

              compute_self_pair(its->second);

              compute_neighbour_pair(itd->second, its->second);            

       }

}

void find_adjacent_pair::map_input(int* in) {

       int *ptr, val, pos; 

       map<int, vector<int>>::iterator it;

       ptr = in;

       pos = 0;

       while (ptr != NULL)

       {

              val = *ptr;

              it = mymap.find(val);

              if (it != mymap.end()) it->second.push_back(pos);

              else add_new_entry(val, pos);

              ptr++;

              pos++;

       }

}

void find_adjacent_pair::add_new_entry(int value, int pos) {

       vector<int> ps;

       ps.push_back(pos);

       mymap.insert(pair<int, vector<int>>(value, ps));

}

void find_adjacent_pair::compute_self_pair(vector<int> ps) {

      

       vector<int> :: iterator it;

       vector<int> :: iterator itv;

       int i = 0;

       for(itv = ps.begin(); i < ps.size()-1; itv++) {

              for(it = itv+1; it != ps.end(); it++)

                     cout << “(“<<*itv<<“, “<<*it<<“)  “;

              i++;

       }

}

void find_adjacent_pair::compute_neighbour_pair(vector<int> ps1, vector<int>ps2) {

       vector<int> :: iterator it1;

       vector<int> :: iterator it2;

       for(it1 = ps1.begin(); it1 != ps1.end(); it1++)

              for(it2 = ps2.begin(); it2 != ps2.end(); it2++)

                     cout<<“(“<<*it1<<“, “<<*it2<<“) “;

}

Traverse by Zig-Zag order

/***

zig-zag traversal of a binary tree.

***/

#include<iostream>

#include<stack>

#include<vector>

using namespace std;

struct node{

       int val;

       node *left, *right;

};

void zigzag(stack<node*> pre, vector<node*> *v, int flag) {

       if(pre.empty()) return;

       stack<node *> cur;

       while(!pre.empty()) {

              node *n = pre.top();

              pre.pop();

              v->push_back(n);

              if(flag%2 == 0) {

                     if(n->left != nullptr) cur.push(n->left);

                     if(n->right != nullptr) cur.push(n->right);

              } else {

                     if(n->right != nullptr) cur.push(n->right);

                     if(n->left != nullptr) cur.push(n->left);

              }

       }

       zigzag(cur, v, flag+1);

}

void main() {

       node n[7];

       for(int i = 0; i<7; i++) {

              n[i].val = i+1;

              n[i].left = nullptr;

              n[i].right = nullptr;

       }

       n[0].left = &n[1];

       n[0].right = &n[2];

       n[1].left = &n[3];

       n[1].right = &n[4];

       n[2].left = &n[5];

       n[2].right = &n[6];

       stack<node*> pre;

       pre.push(n);

       vector<node*> list;

       zigzag(pre, &list, 0);

       for(int i = 0; i < list.size(); i++)

              cout<<list[i]->val<<“->”;

       cout<<endl;

}