Sudoku005
[ Home ] [ Up ]

//file    Sudoku005.cpp
//authors aou
//date    2006.02.22

#include <iostream>
using namespace std;

int const PSIZE = 9;

/*  Project 01, date assigned 2006.02.03, date due 2006.02.10

    Implement the following member function:
    
    int isValid(void);   
    
    test it on two puzzles, one good and one bad
*/
int bad[PSIZE][PSIZE]=
  {
    {1,2,3,4,5,6,7,8,0},
    {1,2,3,4,5,6,7,8,9},
    {9,8,7,6,5,4,3,2,1},
    {1,2,3,4,5,6,7,8,9},
    {1,2,3,4,5,6,7,8,9},
    {9,8,7,6,5,4,3,2,1},
    {1,2,3,4,5,6,7,8,9},
    {1,2,3,4,5,6,7,8,9},
    {0,8,7,6,5,4,3,2,1}
  };

int good[PSIZE][PSIZE]=
  {
    {0,0,0,4,5,6,7,8,0},
    {1,2,3,4,5,6,7,8,9},
    {9,0,7,6,5,4,3,2,1},
    {1,2,3,4,5,6,7,8,9},
    {1,2,3,4,5,6,7,8,9},
    {9,8,7,6,5,4,3,2,1},
    {1,2,3,4,5,6,7,8,9},
    {1,2,3,4,5,6,7,8,9},
    {0,8,7,6,5,4,3,2,1}
  };


class CSudoku
  {
  private:
    int a[PSIZE][PSIZE];
    bool checkDupes(int wa[]);
    void moveRowToArray(int r, int wa[]);
    void moveColToArray(int c, int wa[]);
    void moveRegionToArray(int r, int c, int wa[]);
  public:
    CSudoku(void);        //default constructor
    CSudoku(int d[PSIZE][PSIZE]); //custom constructor
    void display(void);
    int  isValid(void);   //Project 01 test it on two puzzles one good and one bad
    void createNew(void);
    bool checkSolution(void);
    bool isvalidMove(int r, int c, int n);
    bool solve(void);
  };


void test_CSudoku_isValid(void);


void main(void)
  {
  test_CSudoku_isValid();
  }


void test_CSudoku_isValid(void)
  {
  CSudoku puzzle1, puzzle2(good);
  puzzle1.display();
  cout << endl;
  puzzle2.display();
  cout << endl;

  CSudoku puzzle3(bad);
  puzzle3.display();
  cout << endl;

  int violations;
  violations = puzzle3.isValid();
  if (0 == violations)
    cout << "This is a good pouzzle\n";
  else
    cout << "This is NOT a good pouzzle violations ="
    << violations << endl;
  }


bool CSudoku::checkDupes(int wa[])
    /*
    Method1: Compare each value with every other value
    Method2: Sort and compare adjacent values
    method3: Search for missing values 1, 2, 3,... order
    Method4: Use an array of foundFlags
    Method5: If sum is not 45 then something wrong for sure, 
             if sum is 45 then there is no guarantee
    */
  {
  return true;
  }


void CSudoku::moveRowToArray(int r, int wa[])
    /*
    Move column c elements:
    wa[i] = a[r][i] for i=0 to 8
    */
  {
  }


void CSudoku::moveColToArray(int c, int wa[])
    /*
    Move row r elements:
    wa[i] = a[i][c] for i=0 to 8
    */
  {
  }


void CSudoku::moveRegionToArray(int r, int c, int wa[])
    /*
    Move region r,c elements:
    if r=0, c=0 => moving 00,01,02,
                          10,11,12
                          20,21,22
    ------------------------------ 
    for r=0, c=0
      wa[0]=a[r][c]
      wa[1]=a[r][c+1]
      wa[2]=a[r][c+2]
      wa[3]=a[r+1][c]
      wa[4]=a[r+1][c+1]
      wa[5]=a[r+1][c+2]
      wa[6]=a[r+2][c]
      wa[7]=a[r+2][c+1]
      wa[8]=a[r+2][c+2]

    ------------------------------ 
    for r=0, c=0
      iwa=0
      for ic=c to c+2
        wa[iwa++] = a[r][ic]

      for ic=c to c+2
        wa[iwa++] = a[r+1][ic]

      for ic=c to c+2
        wa[iwa++] = a[r+2][ic]

    ------------------------------ 
    for r=0, c=0
      iwa=0

      for ir=r to r+2 step 1
        for ic=c to c+2 step 1
          wa[iwa++] = a[ir][ic]


    ------------------------------ 
    for given r and c

    iwa=0

    for ir=r to r+2 step 1
      for ic=c to c+2 step 1
        wa[iwa++] = a[ir][ic]
    */
  {
  }


int CSudoku::isValid(void)
  {
  /*
  problem:
    returns the number of violations (27 max)
    nine rows, 9 columns, 9 subregions
  algorithm:
    violations = 0

    for each row 
      move row elements into array wa[]
      call checkDupes(wa)
      if necessary violations++ 

    for each colums
      move column elements into array wa[]
      call checkDupes(wa)
      if necessary violations++ 

    for each subregion
      move subregion elements into array wa[]
      call checkDupes(wa)
      if necessary violations++ 

    return violations

  */
  //supply the missing code
  return true;
  }


CSudoku::CSudoku(void)
  {
  for (int r=0; r<9; r++)
    for (int c=0; c<9; c++)
      a[r][c] = 0;
  }


CSudoku::CSudoku(int d[9][9])
  {
  for (int r=0; r<9; r++)
    for (int c=0; c<9; c++)
      a[r][c] = d[r][c];
  }


void CSudoku::display(void)
  {
  for (int r=0; r<9; r++)
    {
    for (int c=0; c<9; c++)
      {
      if (a[r][c]==0)
        cout << ' ';
      else
        cout << a[r][c];
      if (c==2 || c==5) 
        cout << '|';
      else
        cout << ' ';
      }

    cout << endl;
    if (r==2 || r==5)
      cout << "-----+-----+-----\n";
    }
  }