//file Sudoku006.cpp
//authors aou
//date 2006.02.24
#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
*/
// source: http://www.sudoku.com/
int problem1[PSIZE][PSIZE]=
{
{0,6,0, 1,0,4, 0,5,0},
{0,0,8, 3,0,5, 6,0,0},
{2,0,0, 0,0,0, 0,0,1},
{8,0,0, 4,0,7, 0,0,6},
{0,0,6, 0,0,0, 3,0,0},
{7,0,0, 9,0,1, 0,0,4},
{5,0,0, 0,0,0, 0,0,2},
{0,0,7, 2,0,6, 9,0,0},
{0,4,0, 5,0,8, 0,7,0}
};
int solution1[PSIZE][PSIZE]=
{
{9,6,3, 1,7,4, 2,5,8},
{1,7,8, 3,2,5, 6,4,9},
{2,5,4, 6,8,9, 7,3,1},
{8,2,1, 4,3,7, 5,9,6},
{4,9,6, 8,5,2, 3,1,7},
{7,3,5, 9,6,1, 8,2,4},
{5,8,9, 7,1,3, 4,6,2},
{3,1,7, 2,4,6, 9,8,5},
{6,4,2, 5,9,8, 1,7,3}
};
class CSudoku
{
private:
int a[PSIZE][PSIZE];
bool checkDupes(int wa[]);//duplicate and range
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(problem1);
puzzle1.display();
cout << endl;
puzzle2.display();
cout << endl;
CSudoku puzzle3(solution1);
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[])
/*
check the range and the following
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[]
display wa[]
call checkDupes(wa)
if necessary violations++
display violations
for each colums
move column elements into array wa[]
display wa[]
call checkDupes(wa)
if necessary violations++
display violations
//for each subregion
for r=0 to 6 step 3
for c=0 to 6 step 3
move subregion given by r and c elements into array wa[]
display wa[]
call checkDupes(wa)
if necessary violations++
display 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";
}
}
|