#include <iostream>
#include <fstream>
#include "intset.h"
#define DEBUG

using namespace std;

typedef SetOfSmallInts Puzzle [9] [9];
typedef SetOfSmallInts* PuzzleSection [9];

/****************************************************************
*                      copyPuzzle                              *
****************************************************************
* Copy puzzle p into pp.  For example, if p is a puzzle, then  *
*    Puzzle q;                                                 *
*    copyPuzzle(q, p);                                         *
* stores a copy of puzzle p into q.                            *
****************************************************************/

void copyPuzzle(Puzzle pp, Puzzle p)
{
  int i, j;
  for(i = 0; i < 9; i++)
  {
    for(j = 0; j < 9; j++)
    {
      pp[i][j] = p[i][j];
    }
  }
}

/****************************************************************
*                      getRow                                  *
****************************************************************
* Store the i-th row of puzzle p into puzzle section R.        *
* The rows are numbered from 0 to 8.                           *
*                                                              *
* After doing this, the k-th set in row i is *(R[k]).          *
* Do not omit *(...). The cells in the row are numbered        *
* 0,1,...,8.                                                   *
****************************************************************/

void getRow(PuzzleSection R, Puzzle p, int i)
{
  int j;
  for(j = 0; j < 9; j++)
  {
    R[j] = &(p[i][j]);
  }
}

/****************************************************************
*                      getColumn                               *
****************************************************************
* Store the j-th column of puzzle p into puzzle section R.     *
* The columns are numbered from 0 to 8.                        *
*                                                              *
* After doing this, the k-th set in column j is                *
* *(R[i]).  Do not omit *(...).  The cells in the              *
* column are numbered 0,1,...,8.                               *
****************************************************************/

void getColumn(PuzzleSection R, Puzzle p, int j)
{
  int i;
  for(i = 0; i < 9; i++)
  {
    R[i] = &(p[i][j]);
  }
}

/****************************************************************
*                      getSquare                               *
****************************************************************
* Store the k-th square of puzzle p into puzzle section R.     *
* The squares are numbered as follows.                         *
*           0 1 2                                              *
*           3 4 5                                              *
*           6 7 8                                              *
* For example, square 4 is the middle square in the puzzle.    *
*                                                              *
* After doing getSquare, the i-th set in the square is *(R[i]).*
* Do not omit *(...). The cells in the square are numbered     *
* 0,1,...,8, in the same pattern shown above for the squares   *
* themselves.  For example *(R[3]) is the first position in    *
* the second row of the square.                                *
****************************************************************/

void getSquare(PuzzleSection R, Puzzle p, int k)
{
  int i;
  for(i = 0; i < 9; i++)
  {
    R[i] = &(p[k - k%3 + i/3][3*(k%3) + i%3]);
  }
}

/****************************************************************
*                      readPuzzle                              *
****************************************************************
* readPuzzle reads a puzzle in from standard input.            *
*  Then it stores the puzzle into p                             *
****************************************************************/
void readPuzzle(Puzzle p)
{
   char temp = '0';
   ifstream inputFile;
   int rowCount = 0;
   int colCount = 0;

   inputFile.open("puzzle1.txt");

   while(inputFile >> temp){
      if(temp != '-')
         p[rowCount][colCount] = singletonSet((temp-'0'));

      if(temp == '-')
         p[rowCount][colCount] = singletonSet(0);

         colCount++;
         if(colCount == 9){
            rowCount++;
            colCount = 0;
         }
   }
}

/*void readPuzzle(Puzzle p)
{
     char n;
     SetOfSmallInts set = rangeSet(1,9);
     for(int i =0; i<9; i++)
     {
             for(int j=0; j < 9; j++)
             {
                     cin >> n;
                     if(n == '-') p[i][j]=set;
                     else p[i][j] = singletonSet(n-'0');
             }
     }
}*/


/****************************************************************
*                      printPuzzle                             *
****************************************************************
* printPuzzle prints Puzzle p out in standard output. If the   *
* set is a singleton set it will write a number in that set.   *
* If it is not singleton, it will write '-'. If it is empty,   *
* it will write 0.                                             *
****************************************************************/
void printPuzzle(Puzzle p)
{
   int k;
   for(int i=0; i < 9; i++)
   {
      for(int j=0; j < 9; j++)
      {
           k= onlyMember(p[i][j]);
           if (j == 3 || j == 6) cout << " ";
           if (k == 0) cout << "-";
           else cout << k;
       }
       if (i==2 || i == 5) cout << "\n";
       cout <<"\n";
   }
}
/****************************************************************
*                      showPuzzle                               *
****************************************************************
*  showPuzzle prints Puzzle p out in a suitable debugging form. *
*  It will print all members of each set. If the set has a      *
*  singleton set or multiple numbers it will print that.        *
*  If the set is empty it will just write zero.                 *
*                                                               *
****************************************************************/

void showPuzzle(Puzzle p)
{
   SetOfSmallInts s;
   int smallInt = 0;

   for(int i = 0; i < 9; i++)
   {
      for(int j = 0; j < 9; j++)
       {
         s=p[i][j];
         for(int k=0; k < 9; k++)
          {
            smallInt=smallest(s);
            if(smallInt==0 && k!=0)
            {
               cout << " ";
            }
            else cout << smallInt;
            s = remove(smallInt, s);
            if (k==9) cout << " ";
          }
       }
      cout << '\n';
     }
}


int returnSquare(int row, int col)
{
   if(row < 3){
      if(col < 3)
         return 0;
      if(col > 5)
         return 2;
      return 1;
   }

   if(row > 5){
      if(col < 3)
         return 6;
      if(col > 5)
         return 8;
      return 7;
   }

   if(col < 3)
      return 3;
   if(col > 5)
      return 5;
   return 4;
}

/****************************************************************
*                      debugPuzzle                             *
****************************************************************
*  showPuzzle prints Puzzle p out in a suitable debugging form. *
*  It will print all members of each set. If the set has a      *
*  singleton set or multiple numbers it will print that.        *
*  If the set is empty it will just write zero.                 *
*                                                               *
****************************************************************/

/*void debugPuzzle(Puzzle p)
{
   SetOfSmallInts tempSet[9];
   PuzzleSection section;
  
   for(int i = 0; i < 9; i++)
   {
      for(int j = 0; j < 9; j++)
      {
         if(member(0,p[i][j]))
         {
            p[i][j] = rangeSet(1,9);
         }
      }
   }

   for(int i = 0; i < 9; i++)
   {
      for(int j = 0; j < 9; j++)
      {
         if(size(p[i][j]) > 1)
         {
            getRow(section , p, i);
            for(int z = 0; z < 9; z++)
            {
               tempSet[z] = *section[z];
            }
            for(int k = 0; k<9; k++)
            {
               if(size(tempSet[k]) == 1)
               p[i][j] = setDifference(p[i][j], tempSet[k]);                  
            }
         }

      if(size(p[i][j]) > 1)
      {
         getColumn(section , p, j);
           for(int z = 0; z < 9; z++)
           {
              tempSet[z] = *section[z];
           }
           for(int k = 0; k<9; k++)
           {
              if(size(tempSet[k]) == 1)
              p[i][j] = setDifference(p[i][j], tempSet[k]);
           }
      }
      if(size(p[i][j]) > 1)
      {
         getSquare(section , p, returnSquare(i,j));
         for(int z = 0; z < 9; z++){
         tempSet[z] = *section[z];
      }
      for(int k = 0; k<9; k++)
      {
         if(size(tempSet[k]) == 1)
         p[i][j] = setDifference(p[i][j], tempSet[k]);
      }
     }
    }
   }
}*/

/****************************************************************
*                      Tactic 1 Sec                            *
****************************************************************
*  showPuzzle prints Puzzle p out in a suitable debugging form. *
*  It will print all members of each set. If the set has a      *
*  singleton set or multiple numbers it will print that.        *
*  If the set is empty it will just write zero.                 *
*                                                               *
****************************************************************/
void tacticOneSec(Puzzle p)
{
   SetOfSmallInts tempSet[9];
   PuzzleSection section;
  
   for(int i = 0; i < 9; i++)
   {
      for(int j = 0; j < 9; j++)
      {
         if(member(0,p[i][j]))
         {
            p[i][j] = rangeSet(1,9);
         }
      }
   }

   for(int i = 0; i < 9; i++)
   {
      for(int j = 0; j < 9; j++)
      {
         if(size(p[i][j]) > 1)
         {
            getRow(section , p, i);
            for(int z = 0; z < 9; z++)
            {
               tempSet[z] = *section[z];
            }
            for(int k = 0; k<9; k++)
            {
               if(size(tempSet[k]) == 1)
               p[i][j] = setDifference(p[i][j], tempSet[k]);                
            }
         }

      if(size(p[i][j]) > 1)
      {
         getColumn(section , p, j);
           for(int z = 0; z < 9; z++)
           {
              tempSet[z] = *section[z];
           }
           for(int k = 0; k<9; k++)
           {
              if(size(tempSet[k]) == 1)
              p[i][j] = setDifference(p[i][j], tempSet[k]);
           }
      }
      if(size(p[i][j]) > 1)
      {
         getSquare(section , p, returnSquare(i,j));
         for(int z = 0; z < 9; z++){
         tempSet[z] = *section[z];
      }
      for(int k = 0; k<9; k++)
      {
         if(size(tempSet[k]) == 1)
         p[i][j] = setDifference(p[i][j], tempSet[k]);
      }
     }
    }
   }
}

/****************************************************************
*                      Tactic 1                                 *
****************************************************************
*  Tactic 1 will run through each row, column and square of     *
*  Puzzle p. Tatic 1 will return true if there was a change to  *
*  any of the rows, columns, or squares. If nothing was changed *
*  it will return false.                                        *
****************************************************************/
bool tacticOne(Puzzle p)
{      
       bool result = false;
       PuzzleSection scanSec;
       for(int i = 0; i < 9; i++)
       {
               getRow(scanSec,p,i);
               if(tacticOneSec(scanSec)) result = true;
       }
       for(int i = 0; i < 9; i++)
       {
               getColumn(scanSec,p,i);
               if(tacticOneSec(scanSec)) result = true;
       }
       for(int i = 0; i < 9; i++)
       {
               getSquare(scanSec,p,i);
               if(tacticOneSec(scanSec)) result = true;
       }
       return result;
}
/****************************************************************
*                      allSingle                               *
****************************************************************
*  allSingle will run though puzzle p to make sure all sets    *
*  are singleton sets. If they are allSingle will return true. *
*  If there is a nonsingleton set it will return false.        *
****************************************************************/

bool allSingle(Puzzle p)
{
     bool final = false;
     SetOfSmallInts tatOne;
     for( int i = 0; i < 9; i++)
     {
          for( int j = 0; i < 9; j++)
          {
               tatOne=p[i][j];
               if(isSingleton(tatOne)) final = true;
               else return false;
          }
     return final;
     }
}
/****************************************************************
*                      solver                                  *
****************************************************************
*  Solver will find the solution to the puzzle. Solver will run*
*  tactic 1 then do a debug print. If the solver will run      *
*  through tactic 1 until all sets are singleton sets.         *
****************************************************************/

bool solver(Puzzle p)
{
//    bool endResult = false;
//     while()
//     {
//       tacticOne(p);
//         # ifdef DEBUG
//         debugPuzzle(taticOne(p));
//         # endif
  //         if (allSingle == true)
   //        return endResult = true;
//       if(tacticOne==false)
}

int main()
{
    Puzzle p;
    readPuzzle(p);
    printPuzzle(p);
    cout << '\n';
    # ifdef DEBUG
    //debugPuzzle(p);
    # endif
    cout << '\n';
    showPuzzle(p);
    cout <<'\n';
    tacticOneSec(p);
  
}

1-- 489 --6
73- --- -4-
--- --1 295

--7 12- 6--
5-- 7-3 --8
--6 -95 7--

914 6-- ---
-2- --- -37
8-- 512 --4

#include "intset.h"

/****************************************************************
* Note: This file uses capabilities of treating integers     *
* as sequences of bits.  For example, integer 12 on a        *
* 32 bit machine is 00000000000000000000000000001100.        *
* The rightmost bit is the 1's column, the next bit the    *
* 2's column, etc.  The columns are numbered, from right to    *
* left, starting at 0.  A set is represented by putting a 1 in *
* column k if k is in the set, and a 0 if k is not in the set. *
* For example, set {2,5} is represented as integer        *
* 00000000000000000000000000100100.                *
*                                *
* Operations are as follows.                    *
*                                *
*   x & y    The bitwise "and" of x and y.  (The result has  *
*              a 1 in each column whether both x and y have a  *
*              1.)  This has the effect of intersecting sets.    *
*                                *
*  x | y       The bitwise "or" of x and y.  (Ther result has    *
*              a 1 in each column whether either x or y or    *
*        both have a 1.)  This has the effect of taking  *
*              the union of sets.                *
*                                *
*  ~x          The bitwise complement of x.  The result has a  *
*              1 in each column where x has a 0, and a 0 in     *
*              each column where x has a 1.            *
*                                *
*  x >> k      The result of shifting x to the right k bits.   *
*              (Normally, the leftmost bit is duplicated k     *
*              times.)                        *
*                                                              *
*  x << k      The result of shifting x to the left k bits.    *
*              Normally, the rightmost k bits become 0.    *
****************************************************************/

const SetOfSmallInts emptySet;

/***********************************************************
*                   makeSet                               *
***********************************************************
* Return the set represented by integers i.           *
***********************************************************/

SetOfSmallInts makeSet(int i)
{
  SetOfSmallInts s;
  s.ival = i;
  return s;
}

/***********************************************************
*                   singletonSet                          *
***********************************************************/

SetOfSmallInts singletonSet(int x)
{
  return makeSet(1 << x);
}

/***********************************************************
*                   rangeSet                              *
***********************************************************/

SetOfSmallInts rangeSet(int x, int y)
{
  if(x > y) return emptySet;
  else return makeSet(((1 << (y - x + 1)) - 1) << x);
}

/***********************************************************
*                   isEmpty                               *
***********************************************************/

bool isEmpty(SetOfSmallInts s)
{
  return s.ival == 0;
}

/***********************************************************
*                   isSingleton                           *
***********************************************************/

bool isSingleton(SetOfSmallInts s)
{
  return onlyMember(s) != 0;
}


/***********************************************************
*                   size                                  *
***********************************************************/

int size(SetOfSmallInts s)
{
  int n, r;

  n = 0;
  r = s.ival;
  while(r != 0) {
    if(r & 1) n++;
    r = r >> 1;
  }
  return n;
}

/***********************************************************
*                   member                                *
***********************************************************/

bool member(int x, SetOfSmallInts s)
{
  return ((1 << x) & s.ival) != 0;
}

/***********************************************************
*                   insert                                *
***********************************************************/

SetOfSmallInts insert(int x, SetOfSmallInts s)
{
  return makeSet(s.ival | (1 << x));
}

/***********************************************************
*                   remove                                *
***********************************************************/

SetOfSmallInts remove(int x, SetOfSmallInts s)
{
  return makeSet(s.ival & ~(1 << x));
}

/***********************************************************
*                   setDifference                         *
***********************************************************/

SetOfSmallInts setDifference(SetOfSmallInts s, SetOfSmallInts t)
{
  return makeSet(s.ival & ~t.ival);
}

/***********************************************************
*                   setUnion                              *
***********************************************************/

SetOfSmallInts setUnion(SetOfSmallInts s, SetOfSmallInts t)
{
  return makeSet(s.ival | t.ival);
}

/***********************************************************
*                   setIntersection                       *
***********************************************************/

SetOfSmallInts setIntersection(SetOfSmallInts s, SetOfSmallInts t)
{
  return makeSet(s.ival & t.ival);
}

/***********************************************************
*                   smallest                              *
***********************************************************/

int smallest(SetOfSmallInts s)
{
  int i,val;

  val = s.ival;
  if(val == 0) return 0;

  i = 0;
  if((val & 31) == 0) {val = val >> 5; i = 5;}
  if((val & 7) == 0)  {val = val >> 3; i += 3;}
  while((val & 1) == 0) {
    val = val >> 1;
    i++;
  }
  return i;
}


/***********************************************************
*                   onlyMember                            *
***********************************************************/

int onlyMember(SetOfSmallInts s)
{
  int x;

  x = smallest(s);
  if(x != 0 && isEmpty(remove(x, s))) return x;
  else return 0;
}

/****************************************************************
*                     SetOfSmallInts                *
****************************************************************
* A value of type SetOfSmallInts is a set of the integers from *
* 1 to 9.  When you create a variable of type SetofSmallInts,  *
* it initially holds an empty set.                *
****************************************************************/

struct SetOfSmallInts
{
  int ival;

  SetOfSmallInts()
  {
    ival = 0;
  }
};

/****************************************************************
*                     emptySet                    *
****************************************************************
* emptySet is an empty set.                    *
****************************************************************/

extern const SetOfSmallInts emptySet;

/****************************************************************
*                     singletonSet                *
****************************************************************
* singletonSet(x) is the set {x}.                *
****************************************************************/

SetOfSmallInts singletonSet(int x);

/****************************************************************
*                     rangeSet                    *
****************************************************************
* rangeSet(x,y) is the set {x,x+1,...,y}.  For example,    *
* rangeSet(2,5) is the set {2,3,4,5}.                *
****************************************************************/

SetOfSmallInts rangeSet(int x, int y);

/****************************************************************
*                     size                    *
****************************************************************
* size(s) returns the number of members of set s.        *
****************************************************************/

int size(SetOfSmallInts s);

/****************************************************************
*                     isEmpty                    *
****************************************************************
* isEmpty(s) is true if s is an empty set.            *
****************************************************************/

bool isEmpty(SetOfSmallInts s);

/****************************************************************
*                     isSingleton                *
****************************************************************
* isSingletonSet(s) is true if s is a singleton set.  That is, *
* it is true if s has exactly one member.            *
****************************************************************/

bool isSingleton(SetOfSmallInts s);

/****************************************************************
*                     member                    *
****************************************************************
* member(x,s) is true if x is a member of s.            *
****************************************************************/

bool member(int x, SetOfSmallInts s);

/****************************************************************
*                     setDifference                *
****************************************************************
* setDifference(s,t) is the set of all numbers that are in s,  *
* but not in t.                        *
****************************************************************/

SetOfSmallInts setDifference(SetOfSmallInts s, SetOfSmallInts t);

/****************************************************************
*                     setUnion                    *
****************************************************************
* setUnion(s,t) is the set of all numbers that are in either s *
* or t (or both).                        *
****************************************************************/

SetOfSmallInts setUnion(SetOfSmallInts s, SetOfSmallInts t);

/****************************************************************
*                     setIntersection                *
****************************************************************
* setIntersection(s,t) is the set of all numbers that are in   *
* both s and t.                          *
****************************************************************/

SetOfSmallInts setIntersection(SetOfSmallInts s, SetOfSmallInts t);

/****************************************************************
*                     insert                    *
****************************************************************
* insert(x,s) returns the set that you get by adding x to      *
* set s.  So it is equivalent to setUnion(s, singletonSet(x)). *
****************************************************************/

SetOfSmallInts insert(int x, SetOfSmallInts s);

/****************************************************************
*                     remove                    *
****************************************************************
* remove(x,s) returns the set that you get by removing x from  *
* set s.  So it is equivalent to                 *
* setDifference(s, singletonSet(x)).                 *
****************************************************************/

SetOfSmallInts remove(int x, SetOfSmallInts s);

/****************************************************************
*                     smallest                    *
****************************************************************
* smallest(s) returns the smallest member of s.  If s is empty,*
* then smallest(s) returns 0.                    *
****************************************************************/

int smallest(SetOfSmallInts s);

/****************************************************************
*                     onlyMember                *
****************************************************************
* If s is a singleton set, then onlyMember(s) returns the      *
* member of s.  If s is not a singleton set, then              *
* onlyMember(s) returns 0.                        *
****************************************************************/

int onlyMember(SetOfSmallInts s);

void tacticOneSec(Puzzle p)

bool tacticOneSec(Puzzle p)

return true;
return false;
return 1;
return 0;