Sudoku Solver C++ help checking minigrids

Ms_Kyls

Hi everyone.. I am fairly new to C++.. I have studied it a little but not hugely so my code is not the best but it works for most of my solver. HOWEVER I am stuck on solving the minigrids...

Below is my current code (NOTE I am quite aware my function checkMini is completely wrong.. I just dont know how to fix it..)

#include <iostream>
#include <string>
#include <fstream>
#define NROWS 9 // Number of rows.
#define NCOLS 9 // Number of columns.
using namespace std;

void printMenu();
int loadFile(char data[NROWS][NCOLS]);
int displayFile(char data[NROWS][NCOLS]);
int checkCols(char data[NROWS][NCOLS]);
int checkRows(char data[NROWS][NCOLS]);
int checkMini(char data[NROWS][NCOLS]);

int main()
{

char choice = '*';
while (choice != 'Q')

{
char data[9][9];
printMenu();
cin >> choice;
switch (toupper(choice))
{
case 'L' : loadFile(data);
break;
case 'D' : displayFile(data);
break;
case 'R' : checkRows (data);
break;
case 'C' : checkCols (data);
break;
case 'M' : checkMini (data);
break;
case 'Q' : return 0;
default : cout << "Invalid option " << endl; cin.ignore(100,'\n');
}

}

return 0;

system("pause");
}

void printMenu()
{
cout << "\n\tSudoku Checker " << endl << endl;
cout << "\t L\t Load file " << endl;
cout << "\t D\t Display " << endl;
cout << "\t C \t Check columns " << endl;
cout << "\t R \t Check rows " << endl;
cout << "\t M \t Check minigrids" << endl;
cout << "\t Q\t Quit " << endl;
cout << " Rows and columns are labelled from 0 to 8 " << endl;
cout << endl;
}
int loadFile(char data[NROWS][NCOLS])
{
ifstream infile;
string filename;
//float list = 0;
cout << "Enter file name " <<endl>> filename;
infile.open(filename.c_str());
if (infile.fail())
{
cout << "File not found " << endl;
return EXIT_FAILURE;
}
for(int i=0;i<9;i++)
for(int j=0;j<9>> data[i][j];
return EXIT_SUCCESS;
}

int displayFile(char data[NROWS][NCOLS])
{
for(int i=0;i<NROWS;i++)
{
for(int j=0;j<NCOLS;j++)
cout << data[i][j] << " ";
cout << endl;
}
}

// Return 0 if duplicate found in any column; otherwise return nonzero.
int checkCols(char data[NROWS][NCOLS])
{
// Checking each column in turn ...
for (int column=0; column<NCOLS; column++)
{
// Start from the top of the column and move downwards to the second-to-last cell ...
for (int row=0; row<(NROWS-1); row++)
{
const char thisCell = data[row][column];
// Compares this cell to every cell below it in the same column.
for (int checkRow=row+1; checkRow<NROWS; checkRow++)
{

if (thisCell == data[checkRow][column])
{
// Found a duplicate; return an error.
cout << "Column " << column << " is incorrect " << endl;
return 0;
}
}
}
}
// Got through all the columns without a match; return success.
// return 1;
cout << "All columns are correct " << endl;
}
int checkRows(char data[NROWS][NCOLS])
{
// Check each column in turn ...
for (int column=0; column<NCOLS; column++)
{
for (int row=0; row<(NROWS); row++)
{
const char thisCell = data[row][column];
// Compare this cell to each in the row.
for (int checkCol=column+1; checkCol<NCOLS; checkCol++)
{

if (thisCell == data[row][checkCol])
{
// Found a duplicate; return an error.
cout << "Row " << row << " is incorrect " << endl;
return 0;
//cout << "number of duplicates found " << count << endl;
}
}
}
}
// Got through all the rows without a match; return success.
cout << "All rows are correct " << endl;
}

int checkMini(char data[NROWS][NCOLS])
{
for (int column=0; column<NCOLS; column++)
{
for (int row=0; row<NROWS; row++)
{
const char thisCell = data[row][column];

for (int checkRow=row+1; checkRow<(NROWS/3); checkRow++)
{
for (int checkCol=column+1; checkCol<(NCOLS/3); checkCol++)
{
//compare this cell to the grid
cout << "this is row data " << row << " and this is column " << column << endl;
cout << "this is the duplicate value " << data[row][column] << endl;
row ++;
column++;
if (thisCell == data[checkRow][checkCol] )
//if (squares[3*(i/3)+j/3][val])
{
//if (squares[3*(row/3)]+[column/3]) //'val' is already present in this square
cout << "Minigrid starting at row " << row << " column " << column << " is incorrect " << endl;
return 1;
}
}
}
}
}
cout << "All minigrids are correct " << endl;
}

Thanking you in advance Smile

Ms_Kyls · Posted: Wed Mar 11, 2009 1:56 am Post subject:

oh and just wanted to say what I need to do... I need to check if there are duplicates in the mini grids and then it needs to say which column and row the duplicate is on...
I am reading the data from a char file Smile

Am I on the right track?????

brasshopper · Posted: Wed Jun 03, 2009 4:06 pm Post subject: minigrid

You must have solved this by now - but - when you start trying to program automatic solving routines, you'll need a routine that gets, as a argument, the address of some cell, and which returns a list of coordinates that are in the box.

So, let's say that you have a "ninelist" which contains 9 potential intersecting (or otherwise) coordinates. You can use the ninelist to hold the coordinates for a row, a column, or a box.

The ninelist would be 18 integers, which hold pairs of xy coordinates.

The starting coordinate for a box corner is the coordinate divided by 3, reduced to an integer, times three.

Or, 0,1,2 reduce to 0, then 3,4,5 reduce to 3, and 6,7,8 reduce to 6.

I understand that you have decided to program in C++ but I think that tis is a bad choice for development. I would strongly suggest a "safe" language, (one that uses typing or run time checking to insure that your pointers are valid and/or your data is valid). Once programmed and debugged, translate.

This loop, in Perl, would be

$x and $y are passed in to the routine
sub boxcoords_to_ninelist ($$$) {
my $x = shift;
my $y = shift;
my $ninelistref = shift;

return -1 if $x < 0 or $x > 8 or $y < 0 or $y > 8;

$basex = (int($x/3))*3;
$basey = (int($y/3))*3;

my $ninelistpointer = 0;

for my $tempx ($basex..($basex+2)) {
for my $tempy ($basey..($basey+2)) {
$ninelistref->[$ninelistpointer++] = $tempx;
$ninelistref->[$ninelistpointer++] = $tempy;
}
}
return 0;
}
The code is untested, the only part I'm not sure will be apparrent is the passing of the reference to the array - the parent would create n array with

my @nine;

and pass it with

boxcoords_to_ninelist(1,1,\@nine)

Where the \ in this context says "Please make a reference to this thing, in this case, array". A reference can be used in place of any scalar.

A normal use of an array element is done with $nine[0] etc. Multi dimensional arrays are done in two ways - one is to use a hash, where elements are looked up by value, and the other is to create an array of arrays. If you were going to make a 9 by 9 array that could be accessed by

$array[1][2]

It would be stored as an array of arrays. $array[1] means that you have a reverence to a slice which includes $array[1][0..8] but it can be assigned or assigned to.

So my thing passed down is a pointer to my array. My $ninelistref is a copy of that pointer. $ninelistref[0] is invalid because $ninelistref is discovered to be the wrong type at runtime. $ninelistref-> says to dereference the pointer and adding [0] to that as $ninelistref->[0] says that the dereference will be as an array and that we are looking for the first element of the array, element zero. This could also be coded as ${$ninelistref}[0]

This type is checked at runtime.

I like perl for prototyping to c++ because there are a suprising number of canned classes that let you do hashes and regular expressions and other things that work in Perl.

I believe that the output from 1,1,\@nine would be that nine should be set to

[0,0,0,1,0,2,1,0,1,1,1,2,2,0,2,1,2,2]

In Perl there are too many ways to do stuff - you could return a list of references to pairs, for example. You just have to pick one and go with it. Don't alter it unless you are fairly sure that it will be worthwhile.

You are much more likely to fix performance problems with algorithm fixes.

lkSudoku · Posted: Tue Jun 09, 2009 7:52 pm Post subject:

You have several problems in the checkMini function

Once you have chosen a grid cell, and you try to find duplicates in the mini grid of the cell, the set of cells which should be compared is not the same as the one in your function

You should find the exact mini grid that contains the cell (by dividing row/col with 3), go through all the values in that mini grid while skipping the checked cell, and see if you get the same value again (or if you want a more efficient algorithm, you could maintain an empty set, go through a mini grid cells, and add their value to the set while checking if not already in it)

What you do in the code is that given a cell, you go over cells which are not in the same mini grid (and in some cases, no cells at all) and check them for uniqueness, for instance if the row is above NROWS/3, you do not check any cell