I posted a little about this in [post=12787]Sudoku Solving Program Using 'C'[/POST] so that people could take a look at the solve part of the algorithm if they wanted. I was mid-development and this wasn't the part that was actually to change much except for a removal tweak of a magic number here and there. Since then... I have now expanded and pretty much finished the entire class. Consider this the beta form of the class. There are some small tweaks with the read I may do for error correction but for the most part if you keep to the input I detail it won't crash on you. Its pretty resistant as is and you should really be constructing your own interface that accesses and fills the class rather than just work off the read. First I'll post the cpp's and h's for SudokuGrid and SudokuCell and then detail the use and input. Once again.. hopefully these code blocks format properly. If not a moderator may need to help fix them up since I don't have edit access. SudokuCell.h Code: #pragma once class SudokuCell { int value; // value of the cell char *Possibilities; // Set of characters that are Possibilities for this cell. int Num_Possiblities; // Total Number of Possibilities a cell can hold. char Solved; // Flag if Solved public: char Get_Char_Value(int); // for int.. return character corresponding to that value int Get_Value_Char(char); // for char.. return int corresponding to that value // Cell Determination Methods char Is_Solved(); // Determines if this cell is solved (solved flag set) char Is_Broken(); // Determines if this cell is broken (no possibilities); int Get_Possibility(char); // returns the nTH Possibility with n being sent int OnlyOnePossibility(); // Determines if there is only one possibility for this cell char Num_Possibilities(); // returns the current number of possibilities this cell can be char NotPossibility(int); // Determines if a number provided is not a possibility char IsPossibility(int); // Determines if a number provided is a possibility // Property Gets and Sets int Get_Value(); void Set_Value(int); char *Get_Possibilities(); void Set_Possibilities(char *); int Get_Num_Possibilities(); void Set_Num_Possibilities(int); char Get_Solved(); void Set_Solved(char); // Constructors SudokuCell(SudokuCell &); SudokuCell(int); SudokuCell(void); ~SudokuCell(void); }; SudokuCell.cpp Code: #include "StdAfx.h" #include ".\sudokucell.h" char SudokuCell::Get_Char_Value(int num) { char retval = (char)num + 48; if (num > 9) retval = 'A' + num - 10; return retval; } int SudokuCell::Get_Value_Char(char Num) { int retval = 0; if (Num >= '1' && Num <= '9') retval = Num - 48; else retval = Num - 55; return retval; } char SudokuCell::Is_Solved() { return Solved; } char SudokuCell::Is_Broken() { int x = 0, Broken = TRUE; while (x < Get_Num_Possibilities() && Broken == TRUE) { if (*(Possibilities + x) != '0') Broken = FALSE; x++; } return Broken; } int SudokuCell::Get_Possibility(char Num) { char Value = 0, Found = 0, x = 0; int retval = 0; while (x < Get_Num_Possibilities() && Found != Num) { if (*(Possibilities + x) != '0') { Value = *(Possibilities + x); retval = Get_Value_Char(Value); Found++; } x++; } return retval; } int SudokuCell::OnlyOnePossibility() { char x = 0, Poss = 0, tVal; int retval = 0; while (x < Get_Num_Possibilities() && Poss <= 1) { if (*(Possibilities + x) != '0') { tVal = *(Possibilities + x); Poss++; } x++; } if (Poss == 1) retval = Get_Value_Char(tVal); return retval; } char SudokuCell::Num_Possibilities() { char x, Num_Found = 0; for (x = 0; x < Get_Num_Possibilities(); x++) { if (*(Possibilities + x) != '0') Num_Found++; } return Num_Found; } char SudokuCell::NotPossibility(int Value) { char SomethingChanged = FALSE; if (*(Possibilities + (Value - 1)) != '0') { SomethingChanged = TRUE; *(Possibilities + (Value - 1)) = '0'; } return SomethingChanged; } char SudokuCell::IsPossibility(int Value) { char test = FALSE, blah = Get_Char_Value(Value); if (*(Possibilities + (Value - 1)) == blah) test = TRUE; return test; } int SudokuCell::Get_Value() { return value; } void SudokuCell::Set_Value(int tValue) { int nPoss = Get_Num_Possibilities(); // Get Number of possibilities this cell can have char *tPoss = new char[nPoss + 1]; // make enough space for all possibilities plus 0 delimiter char cValue, x; cValue = Get_Char_Value(tValue); if (cValue != '0') { for(x = 0; x < nPoss; x++) tPoss[x] = Get_Char_Value(0); // fill string with 0's tPoss[tValue - 1] = Get_Char_Value(tValue); // set value as only possibility } else { for(x = 0; x < nPoss; x++) tPoss[x] = Get_Char_Value(x + 1); // fill string with all possibilities } tPoss[x] = '\0'; // add null to end of string Set_Possibilities(tPoss); // Set the new possibilities string value = tValue; } char *SudokuCell::Get_Possibilities() { return Possibilities; } void SudokuCell::Set_Possibilities(char *tPoss) { if (Possibilities) delete Possibilities; Possibilities = tPoss; } int SudokuCell::Get_Num_Possibilities() { return Num_Possiblities; } void SudokuCell::Set_Num_Possibilities(int nPoss) { Num_Possiblities = nPoss; } char SudokuCell::Get_Solved() { return Solved; } void SudokuCell::Set_Solved(char tSolved) { Solved = tSolved; } SudokuCell::SudokuCell(SudokuCell &Temp_Cell) { } SudokuCell::SudokuCell(int Num_Possibilities) { Possibilities = NULL; Set_Num_Possibilities(Num_Possibilities); Solved = 0; Set_Value(0); } SudokuCell::SudokuCell(void) { Possibilities = NULL; Set_Num_Possibilities(9); Solved = 0; Set_Value(0); } SudokuCell::~SudokuCell(void) { if (Possibilities) delete Possibilities; } SudokuGrid.h Code: #pragma once #include "SudokuCell.h" #define FALSE 0 #define TRUE 1 #define UNSOLVED 0 #define SOLVED 1 #define BROKEN 2 #define GRID_SIZE 81 class SudokuGrid { SudokuCell Cell[GRID_SIZE]; SudokuCell *ptrCell; int CellBlock_Width; int CellBlock_Height; int Num_CellBlock_Width; int Num_CellBlock_Height; int GridSize; char Find_Row(char, char); char Find_Col(char, char); char Find_Cellblock(char, char); void Remove_Row_Possibilities(char, int, int); void Remove_Col_Possibilities(char, int, int); void Remove_CellBlock_Possibilities(char, int, int); void Remove_RowColBlock_Possibilities(int, int); char Solve_RowSingles(); char Solve_ColumnSingles(); char Solve_CellBlockSingles(); int Solve_GridSingles(); int Get_RowCol_Offset(char, char); int Get_CellBlock_Offset(char, int); char Remove_CellBlock_Row_Possibilities(char, char, int); char Remove_CellBlock_Col_Possibilities(char, char, int); char Remove_Row_Possibilities(char, char, int); char Remove_Col_Possibilities(char, char, int); char Remove_Row_CellBlock_Isolation_Possibilities(); char Remove_Col_CellBlock_Isolation_Possibilities(); char Remove_CellBlock_Row_Isolation_Possibilities(); char Remove_CellBlock_Col_Isolation_Possibilities(); char Selective_Solutioning(); SudokuCell *Get_ptrCell(int); void Set_ptrCell(int, SudokuCell *); SudokuCell *Get_Cell(int); void Set_Cell(int, SudokuCell *); int Get_Cell_Value(int, int); void Set_Cell_Value(int, int, int); char Is_Solved(); char Is_Broken(); char Get_RowNumber(int); char Get_ColNumber(int); public: int Get_GridSize(); void Set_GridSize(); int Get_CellBlock_Width(); void Set_CellBlock_Width(int); int Get_CellBlock_Height(); void Set_CellBlock_Height(int); int Get_Num_CellBlock_Width(); void Set_Num_CellBlock_Width(int); int Get_Num_CellBlock_Height(); void Set_Num_CellBlock_Height(int); int Get_RowWidth(); int Get_ColHeight(); void Skip_Whitespace(FILE *); char Read_Value(FILE *); void Skip_Line(FILE *); void Read_File(char *); void Write_File(char *); char Solve(); void Set_SudokuGrid(SudokuGrid *); SudokuGrid(SudokuGrid *); SudokuGrid(int, int, int, int); SudokuGrid(); ~SudokuGrid(); }; SudokuGrid.cpp Code: #include "StdAfx.h" #include ".\sudokugrid.h" #include <stdio.h> int SudokuGrid::Get_Cell_Value(int row, int col) { int Offset = Get_RowCol_Offset(row, col); return Cell[Offset].Get_Value(); // return ptrCell[Offset].Get_Value(); } void SudokuGrid::Set_Cell_Value(int row, int col, int tvalue) { int Offset = Get_RowCol_Offset(row, col); Cell[Offset].Set_Value(tvalue); // ptrCell[Offset].Set_Value(tvalue); } SudokuCell *SudokuGrid::Get_ptrCell(int x) { return &ptrCell[x]; } void SudokuGrid::Set_ptrCell(int x, SudokuCell *Temp_Cell) { char *tPoss; ptrCell[x].Set_Num_Possibilities(Temp_Cell -> Get_Num_Possibilities()); tPoss = new char[Temp_Cell -> Get_Num_Possibilities() + 1]; strcpy(tPoss, Temp_Cell -> Get_Possibilities()); ptrCell[x].Set_Value(Temp_Cell -> Get_Value()); ptrCell[x].Set_Possibilities(tPoss); ptrCell[x].Set_Solved(Temp_Cell -> Get_Solved()); } SudokuCell *SudokuGrid::Get_Cell(int x) { return &Cell[x]; } void SudokuGrid::Set_Cell(int x, SudokuCell *Temp_Cell) { char *tPoss; Cell[x].Set_Num_Possibilities(Temp_Cell -> Get_Num_Possibilities()); tPoss = new char[Cell[x].Get_Num_Possibilities() + 1]; strcpy (tPoss, Temp_Cell -> Get_Possibilities()); Cell[x].Set_Value(Temp_Cell -> Get_Value()); Cell[x].Set_Possibilities(tPoss); Cell[x].Set_Solved(Temp_Cell -> Get_Solved()); } // Find Row returns an overall row based on a CellBlock value 1-n and an Ordinal Value 1-n in that Cell Block by row. char SudokuGrid::Find_Row(char CellBlock, char Ordinal) { char Row; Row = (Ordinal - 1) / Get_CellBlock_Width() + (CellBlock - 1) / Get_Num_CellBlock_Width() * Get_CellBlock_Height(); return Row + 1; } char SudokuGrid::Find_Col(char CellBlock, char Ordinal) { char Col; Col = (Ordinal - 1) % Get_CellBlock_Width() + (CellBlock - 1) % Get_Num_CellBlock_Width() * Get_CellBlock_Width(); return Col + 1; } char SudokuGrid::Find_Cellblock(char Row, char Col) { char CellBlock; CellBlock = (Row - 1) / Get_CellBlock_Height() * Get_Num_CellBlock_Width() + (Col - 1) / Get_CellBlock_Width(); return CellBlock + 1; // Adjust for 1-n rather than 0-n } void SudokuGrid::Remove_Row_Possibilities(char GridRow, int SolvedCell, int tValue) { int CellOffset; for (int Col = 0; Col < Get_RowWidth(); Col++) { CellOffset = Get_RowCol_Offset(GridRow, Col + 1); if (CellOffset != SolvedCell) { Cell[CellOffset].NotPossibility(tValue); // ptrCell[CellOffset].NotPossibility(tValue); } } } void SudokuGrid::Remove_Col_Possibilities(char GridCol, int SolvedCell, int tValue) { int CellOffset; for (int Row = 0; Row < Get_ColHeight(); Row++) { CellOffset = Get_RowCol_Offset(Row + 1, GridCol); if (CellOffset != SolvedCell) { Cell[CellOffset].NotPossibility(tValue); // ptrCell[CellOffset].NotPossibility(tValue); } } } void SudokuGrid::Remove_CellBlock_Possibilities(char GridCellBlock, int SolvedCell, int tValue) { int CellOffset; for (int x = 0; x < Get_CellBlock_Width() * Get_CellBlock_Height(); x++) { CellOffset = Get_CellBlock_Offset(GridCellBlock, x + 1); if (CellOffset != SolvedCell) { Cell[CellOffset].NotPossibility(tValue); // ptrCell[CellOffset].NotPossibility(tValue); } } } void SudokuGrid::Remove_RowColBlock_Possibilities(int CellNum, int tValue) { char Row = Get_RowNumber(CellNum), Col = Get_ColNumber(CellNum), CellBlock; CellBlock = Find_Cellblock(Row, Col); // Actual rows and columns 1-n, Cellblock return 1-n Remove_Row_Possibilities(Row, CellNum, tValue); // Actual Rows and Columns 1-n Remove_Col_Possibilities(Col, CellNum, tValue); // Actual Rows and Columns 1-n Remove_CellBlock_Possibilities(CellBlock, CellNum, tValue); // Actual Rows and Columns 1-n, CellBlock 1-n } int SudokuGrid::Solve_GridSingles() { char Found = FALSE; char tPoss; int nCell; for (nCell = 0; nCell < Get_GridSize(); nCell++) { if (Cell[nCell].Is_Solved() == FALSE) { if (tPoss = Cell[nCell].OnlyOnePossibility()) { // Old Array Version Found = TRUE; Cell[nCell].Set_Solved(TRUE); Cell[nCell].Set_Value(tPoss); Remove_RowColBlock_Possibilities(nCell, Cell[nCell].Get_Value()); // New Ptr Version /* Found = TRUE; ptrCell[nCell].Set_Solved(TRUE); ptrCell[nCell].Set_Value(tPoss); Remove_RowColBlock_Possibilities(nCell, ptrCell[nCell].Get_Value());*/ } } } return Found; } char SudokuGrid::Is_Solved() { char UnsolvedCell = FALSE; int x = 0; while (x < Get_GridSize() && UnsolvedCell == FALSE) { if (Cell[x].Is_Solved() == FALSE) UnsolvedCell = TRUE; // if (Cell[x].Is_Solved() == FALSE) // UnsolvedCell = TRUE; x++; } return !UnsolvedCell; } char SudokuGrid::Is_Broken() { char BrokenCell = FALSE; int x = 0; while (x < Get_GridSize() && BrokenCell == FALSE) { if (Cell[x].Is_Broken() == TRUE) BrokenCell = TRUE; // if (ptrCell[x].Is_Broken() == TRUE) // BrokenCell = TRUE; x++; } return BrokenCell; } char SudokuGrid::Get_RowNumber(int CellNum) { return CellNum / Get_RowWidth() + 1; } char SudokuGrid::Get_ColNumber(int CellNum) { return CellNum % Get_ColHeight() + 1; } char SudokuGrid::Solve_RowSingles() { char SomethingSolved = FALSE; char NumFound, tVal; int Row, Num, Col, Offset = 0, tOffset; for (Row = 0; Row < Get_ColHeight(); Row++) { for(Num = 0; Num < Cell[0].Get_Num_Possibilities(); Num++) { Col = 0; NumFound = 0; while (Col < Get_RowWidth() && NumFound < 2) { Offset = Get_RowCol_Offset(Row + 1, Col + 1); if (Cell[Offset].Is_Solved() == FALSE) { if (Cell[Offset].IsPossibility(Num+1)) { tOffset = Offset; tVal = Num; NumFound++; } } else if (Cell[Offset].Get_Value() == Num + 1) NumFound = 2; Col++; } if (NumFound == 1) { if (Cell[tOffset].Get_Value() != tVal + 1) { Cell[tOffset].Set_Value(tVal + 1); // ptrCell[tOffset].Set_Value(tVal + 1); SomethingSolved = TRUE; } } } } return SomethingSolved; } char SudokuGrid::Solve_ColumnSingles() { char SomethingSolved = FALSE; char NumFound, tVal; int Row, Num, Col, Offset = 0, tOffset; for (Col = 0; Col < Get_RowWidth(); Col++) { for(Num = 0; Num < Cell[0].Get_Num_Possibilities(); Num++) { Row = 0; NumFound = 0; while (Row < Get_ColHeight() && NumFound < 2) { Offset = Get_RowCol_Offset(Row + 1, Col + 1); if (Cell[Offset].Is_Solved() == FALSE) { if (Cell[Offset].IsPossibility(Num+1)) { tOffset = Offset; tVal = Num; NumFound++; } } else if (Cell[Offset].Get_Value() == Num + 1) NumFound = 2; Row++; } if (NumFound == 1) { if (Cell[tOffset].Get_Value() != tVal + 1) { Cell[tOffset].Set_Value(tVal + 1); // ptrCell[tOffset].Set_Value(tVal + 1); SomethingSolved = TRUE; } } } } return SomethingSolved; } char SudokuGrid::Solve_CellBlockSingles() { char SomethingSolved = FALSE; char NumFound, tVal; int CellBlock, Num, z, Offset = 0, tOffset; for (CellBlock = 0; CellBlock < (Get_Num_CellBlock_Width() * Get_Num_CellBlock_Height()); CellBlock++) { for(Num = 0; Num < Cell[0].Get_Num_Possibilities(); Num++) { z = 0; NumFound = 0; while (z < (Get_CellBlock_Width() * Get_CellBlock_Height()) && NumFound < 2) { Offset = Get_CellBlock_Offset(CellBlock + 1, z + 1); if (Cell[Offset].Is_Solved() == FALSE) { if (Cell[Offset].IsPossibility(Num+1)) { tOffset = Offset; tVal = Num; NumFound++; } } else if (Cell[Offset].Get_Value() == Num + 1) NumFound = 2; z++; } if (NumFound == 1) { if (Cell[tOffset].Get_Value() != tVal + 1) { Cell[tOffset].Set_Value(tVal + 1); // ptrCell[tOffset].Set_Value(tVal + 1); SomethingSolved = TRUE; } } } } return SomethingSolved; } int SudokuGrid::Get_RowCol_Offset(char Row, char Col) { return (Row - 1) * Get_RowWidth() + (Col - 1); } int SudokuGrid::Get_CellBlock_Offset(char CellBlock, int Ordinal) { int CellBlockStartOffset, CellBlockOrdinalOffset; CellBlockStartOffset = ((CellBlock - 1) % Get_Num_CellBlock_Width() * Get_CellBlock_Width()) + (Get_RowWidth() * Get_CellBlock_Height() * ((CellBlock - 1) / Get_Num_CellBlock_Width())); CellBlockOrdinalOffset = (Ordinal - 1) / Get_CellBlock_Width() * Get_RowWidth() + (Ordinal - 1) % Get_CellBlock_Width(); return CellBlockStartOffset + CellBlockOrdinalOffset; } char SudokuGrid::Remove_CellBlock_Row_Possibilities(char Row, char CellBlock, int Value) { char SomethingChanged = FALSE, x, y, Ordinal, Offset; for (x = 0; x < Get_CellBlock_Height(); x++) { if ((Row - 1) % Get_CellBlock_Height() != x) { for (y = 0; y < Get_CellBlock_Width(); y++) { Ordinal = (x * Get_CellBlock_Width() + y) + 1; Offset = Get_CellBlock_Offset(CellBlock, Ordinal); SomethingChanged |= Cell[Offset].NotPossibility(Value); // SomethingChanged |= ptrCell[Offset].NotPossibility(Value); } } } return SomethingChanged; } char SudokuGrid::Remove_CellBlock_Col_Possibilities(char Col, char CellBlock, int Value) { char SomethingChanged = FALSE, x, y, Ordinal, Offset; for (x = 0; x < Get_CellBlock_Width(); x++) { if ((Col - 1) % Get_CellBlock_Width() != x) { for (y = 0; y < Get_CellBlock_Height(); y++) { Ordinal = (y * Get_CellBlock_Width() + x) + 1; Offset = Get_CellBlock_Offset(CellBlock, Ordinal); SomethingChanged |= Cell[Offset].NotPossibility(Value); // SomethingChanged |= ptrCell[Offset].NotPossibility(Value); } } } return SomethingChanged; } char SudokuGrid::Remove_Row_Possibilities(char Row, char CellBlock, int Value) { char SomethingChanged = FALSE, Col, Offset; for (Col = 0; Col < Get_RowWidth(); Col++) { if (Find_Cellblock(Row, Col + 1) != CellBlock) { Offset = Get_RowCol_Offset(Row, Col + 1); SomethingChanged |= Cell[Offset].NotPossibility(Value); // SomethingChanged |= ptrCell[Offset].NotPossibility(Value); } } return SomethingChanged; } char SudokuGrid::Remove_Col_Possibilities(char Col, char CellBlock, int Value) { char SomethingChanged = FALSE, Row, Offset; for (Row = 0; Row < Get_ColHeight(); Row++) { if (Find_Cellblock(Row + 1, Col) != CellBlock) { Offset = Get_RowCol_Offset(Row + 1, Col); SomethingChanged |= Cell[Offset].NotPossibility(Value); // SomethingChanged |= ptrCell[Offset].NotPossibility(Value); } } return SomethingChanged; } char SudokuGrid::Remove_Row_CellBlock_Isolation_Possibilities() { char SomethingSolved = FALSE; char Row, Num, Col, MultBlocks, Offset = 0, tVal; char CellBlock = 0; for (Row = 0; Row < Get_ColHeight(); Row++) { for(Num = 0; Num < Cell[0].Get_Num_Possibilities(); Num++) { Col = 0; MultBlocks = FALSE; CellBlock = 0; while (Col < Get_RowWidth() && MultBlocks == FALSE) { Offset = Get_RowCol_Offset(Row + 1, Col + 1); if (Cell[Offset].Is_Solved() == FALSE) { if (Cell[Offset].IsPossibility(Num+1)) { char tCB = Find_Cellblock(Row + 1, Col + 1); if (CellBlock == 0) CellBlock = tCB; else if (tCB != CellBlock) MultBlocks = TRUE; tVal = Num; } } else if (Cell[Offset].Get_Value() == Num + 1) MultBlocks = TRUE; Col++; } if (MultBlocks == FALSE) { if (Remove_CellBlock_Row_Possibilities(Row + 1, CellBlock, tVal + 1)) SomethingSolved = TRUE; } } } return SomethingSolved; } char SudokuGrid::Remove_Col_CellBlock_Isolation_Possibilities() { char SomethingSolved = FALSE; char Col, Num, Row, MultBlocks, Offset = 0, tVal; char CellBlock = 0; for (Col = 0; Col < Get_RowWidth(); Col++) { for(Num = 0; Num < Cell[0].Get_Num_Possibilities(); Num++) { Row = 0; MultBlocks = FALSE; CellBlock = 0; while (Row < Get_ColHeight() && MultBlocks == FALSE) { Offset = Get_RowCol_Offset(Row + 1, Col + 1); if (Cell[Offset].Is_Solved() == FALSE) { if (Cell[Offset].IsPossibility(Num+1)) { char tCB = Find_Cellblock(Row + 1, Col + 1); if (CellBlock == 0) CellBlock = tCB; else if (tCB != CellBlock) MultBlocks = TRUE; tVal = Num; } } else if (Cell[Offset].Get_Value() == Num + 1) MultBlocks = TRUE; Row++; } if (MultBlocks == FALSE) { if (Remove_CellBlock_Col_Possibilities(Col + 1, CellBlock, tVal + 1)) SomethingSolved = TRUE; } } } return SomethingSolved; } char SudokuGrid::Remove_CellBlock_Row_Isolation_Possibilities() { char SomethingChanged = FALSE; char CellBlock, Num, z, MultRows, Offset = 0, tVal = 0, Row = 0; for (CellBlock = 0; CellBlock < Get_Num_CellBlock_Width() * Get_Num_CellBlock_Height(); CellBlock++) { for(Num = 0; Num < Cell[0].Get_Num_Possibilities(); Num++) { z = 0; MultRows = FALSE; Row = 0; while (z < Get_CellBlock_Width() * Get_CellBlock_Height() && MultRows == FALSE) { Offset = Get_CellBlock_Offset(CellBlock + 1, z + 1); if (Cell[Offset].Is_Solved() == FALSE) { if (Cell[Offset].IsPossibility(Num+1)) { char tRow = Find_Row(CellBlock + 1, z + 1); if (Row == 0) { Row = tRow; tVal = Num; } else if (tRow != Row) MultRows = TRUE; } } else if (Cell[Offset].Get_Value() == Num + 1) MultRows = TRUE; z++; } if (MultRows == FALSE) { if (Remove_Row_Possibilities(Row, (char)(CellBlock + 1), tVal + 1)) SomethingChanged = TRUE; } } } return SomethingChanged; } char SudokuGrid::Remove_CellBlock_Col_Isolation_Possibilities() { char SomethingChanged = FALSE; char CellBlock, Num, z, MultCols, Offset = 0, tVal = 0, Col = 0; for (CellBlock = 0; CellBlock < Get_Num_CellBlock_Width() * Get_Num_CellBlock_Height(); CellBlock++) { for(Num = 0; Num < Cell[0].Get_Num_Possibilities(); Num++) { z = 0; MultCols = FALSE; Col = 0; while (z < Get_CellBlock_Width() * Get_CellBlock_Height() && MultCols == FALSE) { Offset = Get_CellBlock_Offset(CellBlock + 1, z + 1); if (Cell[Offset].Is_Solved() == FALSE) { if (Cell[Offset].IsPossibility(Num+1)) { char tCol = Find_Col(CellBlock + 1, z + 1); if (Col == 0) { Col = tCol; tVal = Num; } else if (tCol != Col) MultCols = TRUE; } } else if (Cell[Offset].Get_Value() == Num + 1) MultCols = TRUE; z++; } if (MultCols == FALSE) { if (Remove_Col_Possibilities(Col, (char)(CellBlock + 1), tVal + 1)) SomethingChanged = TRUE; } } } return SomethingChanged; } char SudokuGrid::Selective_Solutioning() { char retval = UNSOLVED; char CellFound = FALSE, SomethingChanged = FALSE; SudokuGrid *WorkGrid; SudokuCell *tCell; int x, y, tVal1, tPoss; x = 0; while (x < Get_GridSize() && retval != SOLVED && SomethingChanged == FALSE) { if (Cell[x].Is_Solved() == FALSE) { tPoss = Cell[x].Num_Possibilities(); y = 0; while (y < tPoss && retval != SOLVED) { WorkGrid = new SudokuGrid(this); tCell = WorkGrid -> Get_Cell(x); tVal1 = Cell[x].Get_Possibility(1); tCell -> Set_Value(tVal1); retval = WorkGrid -> Solve(); if (retval == BROKEN) { Cell[x].NotPossibility(tVal1); retval = UNSOLVED; } else if (retval == SOLVED) Set_SudokuGrid(WorkGrid); delete WorkGrid; y++; } if (retval == UNSOLVED) retval = BROKEN; } x++; } return retval; } char SudokuGrid::Solve() { char Something_Changed, Solved = FALSE, Broken = FALSE, retval = UNSOLVED; while(Solved == FALSE && Broken == FALSE && retval == UNSOLVED) { Something_Changed = FALSE; while(Solve_GridSingles()) {} Something_Changed |= Solve_RowSingles(); Something_Changed |= Solve_ColumnSingles(); Something_Changed |= Solve_CellBlockSingles(); Broken = Is_Broken(); Solved = Is_Solved(); if (Something_Changed == FALSE && Solved == FALSE && Broken == FALSE) { Something_Changed |= Remove_Row_CellBlock_Isolation_Possibilities(); Something_Changed |= Remove_Col_CellBlock_Isolation_Possibilities(); Something_Changed |= Remove_CellBlock_Row_Isolation_Possibilities(); Something_Changed |= Remove_CellBlock_Col_Isolation_Possibilities(); Broken = Is_Broken(); Solved = Is_Solved(); if (Something_Changed == FALSE && Solved == FALSE && Broken == FALSE) retval = Selective_Solutioning(); } } if (Solved) retval = SOLVED; if (Broken) retval = BROKEN; return retval; } int SudokuGrid::Get_GridSize() { if (GridSize == 0) Set_GridSize(); return GridSize; } void SudokuGrid::Set_GridSize() { GridSize = Get_CellBlock_Width() * Get_Num_CellBlock_Width() * Get_CellBlock_Height() * Get_Num_CellBlock_Height(); } int SudokuGrid::Get_CellBlock_Width() { return CellBlock_Width; } void SudokuGrid::Set_CellBlock_Width(int tWidth) { CellBlock_Width = tWidth; } int SudokuGrid::Get_CellBlock_Height() { return CellBlock_Height; } void SudokuGrid::Set_CellBlock_Height(int tHeight) { CellBlock_Height = tHeight; } int SudokuGrid::Get_Num_CellBlock_Width() { return Num_CellBlock_Width; } void SudokuGrid::Set_Num_CellBlock_Width(int tCellBlock_Width) { Num_CellBlock_Width = tCellBlock_Width; } int SudokuGrid::Get_Num_CellBlock_Height() { return Num_CellBlock_Height; } void SudokuGrid::Set_Num_CellBlock_Height(int tCellBlock_Height) { Num_CellBlock_Height = tCellBlock_Height; } int SudokuGrid::Get_RowWidth() { return Get_CellBlock_Width() * Get_Num_CellBlock_Width(); } int SudokuGrid::Get_ColHeight() { return Get_CellBlock_Height() * Get_Num_CellBlock_Height(); } void SudokuGrid::Skip_Whitespace(FILE *stream) { char *ptr = NULL; fscanf(stream, " "); ptr = stream -> _ptr; while (*ptr == ' ') { fscanf(stream, " "); ptr = stream -> _ptr; } } char SudokuGrid::Read_Value(FILE *stream) { char Value = 0, num = 0, Done = FALSE; char *ptr = NULL; Skip_Whitespace(stream); ptr = stream -> _ptr; while (*ptr != ' ' && !Done) { switch(*ptr) { case '-': fscanf(stream, "-"); Done = TRUE; Value = 0; break; case '|': fscanf(stream, "|"); Skip_Whitespace(stream); ptr = stream -> _ptr; break; case '\n': Done = TRUE; break; default: fscanf(stream, "%c", &num); ptr = stream -> _ptr; Value *= 10; Value += (num - 48); break; } } return Value; } void SudokuGrid::Skip_Line(FILE *stream) { char temp = 0; while(temp != '\n') fscanf(stream, "%c", &temp); } void SudokuGrid::Read_File(char *Filename) { FILE *stream; int Row, Col; char temp, num, num2 = 0; int total = 0; if((stream = fopen(Filename, "r" )) == NULL) printf( "The file was not opened\n" ); else printf( "The file was opened\n" ); for(Row = 0; Row < Get_RowWidth(); Row++) { if (Row % Get_CellBlock_Height() == 0 && Row != 0) { temp = 0; Skip_Line(stream); } for (Col = 0; Col < Get_ColHeight(); Col++) { num = Read_Value(stream); Cell[Get_RowCol_Offset(Row + 1, Col + 1)].Set_Value(num); // ptrCell[Get_RowCol_Offset(Row + 1, Col + 1)].Set_Value(num); } fscanf(stream, "\n"); } fclose(stream); } void SudokuGrid::Write_File(char *Filename) { FILE *stream; int Row, Col, tVal, Num_Dashes = 0; if((stream = fopen(Filename, "w" )) == NULL) printf( "The file was not opened\n" ); else printf( "The file was opened\n" ); for(Row = 0; Row < Get_ColHeight(); Row++) { if (Row % Get_CellBlock_Height() == 0 && Row != 0) { for (int x = 0; x < Num_Dashes; x++) fprintf(stream, "-"); fprintf(stream, "\n"); } Num_Dashes = 0; fprintf(stream, " "); Num_Dashes++; for (Col = 0; Col < Get_RowWidth(); Col++) { if (Col % Get_CellBlock_Width() == 0 && Col != 0) { fprintf(stream, "| "); Num_Dashes += 2; } tVal = Cell[Get_RowCol_Offset(Row + 1, Col + 1)].Get_Value(); // tVal = ptrCell[Get_RowCol_Offset(Row + 1, Col + 1)].Get_Value(); fprintf(stream, "%d ", tVal); Num_Dashes += 3; if (tVal < 10) fprintf(stream, " "); } fprintf(stream, "\n"); } fclose(stream); } void SudokuGrid::Set_SudokuGrid(SudokuGrid *Temp_Grid) { Set_CellBlock_Width(Temp_Grid -> Get_CellBlock_Width()); Set_CellBlock_Height(Temp_Grid -> Get_CellBlock_Height()); Set_Num_CellBlock_Width(Temp_Grid -> Get_Num_CellBlock_Width()); Set_Num_CellBlock_Height(Temp_Grid -> Get_Num_CellBlock_Height()); Set_GridSize(); for (int x = 0; x < Get_GridSize(); x++) { Set_Cell(x, Temp_Grid -> Get_Cell(x)); } /* ptrCell = new SudokuCell[Get_GridSize()]; for (int y = 0; y < Get_GridSize(); y++) { Set_ptrCell(y, Temp_Grid -> Get_ptrCell(y)); }*/ } SudokuGrid::SudokuGrid(SudokuGrid *Temp_Grid) { ptrCell = NULL; Set_SudokuGrid(Temp_Grid); } SudokuGrid::SudokuGrid(int cbWidth, int cbHeight, int num_cbWidth, int num_cbHeight) { Set_CellBlock_Width(cbWidth); Set_CellBlock_Height(cbHeight); Set_Num_CellBlock_Width(num_cbWidth); Set_Num_CellBlock_Height(num_cbHeight); Set_GridSize(); ptrCell = NULL; // ptrCell = new SudokuCell[Get_GridSize()]; for (int x = 0; x < Get_GridSize(); x++) { Cell[x].Set_Num_Possibilities(Get_CellBlock_Width() * Get_CellBlock_Height()); Cell[x].Set_Value(0); } } SudokuGrid::SudokuGrid() { Set_CellBlock_Width(3); Set_CellBlock_Height(3); Set_Num_CellBlock_Width(3); Set_Num_CellBlock_Height(3); ptrCell = NULL; } SudokuGrid::~SudokuGrid() { if (ptrCell) delete [] ptrCell; }
Ok.. usage. This class is not just designed for your typical 9x9 grid. Sudoku's come in many different variations. Examples(hopefully these come out readable): 2 x 2 Code: - 2 | 3 - 1 - | - 4 ----------- 3 - | - 2 - 1 | 4 - 3 x 3 Code: - - - | - 2 - | 9 - - 3 5 6 | - - - | 4 - - - 2 - | - - - | - 6 - ----------------------- 1 - - | 7 - - | - - - - - 2 | 9 3 1 | 8 - - - - - | - - 5 | - - 6 ----------------------- - 4 - | - - - | - 2 - - - 7 | - - - | 3 1 5 - - 8 | - 5 - | - - - 4x4 Code: - - - - | - - - - | - - - - | - - - - - - 2 14 | 12 13 - - | - - 9 10 | 5 4 - - - 15 1 - | - 5 9 - | - 12 8 - | - 10 14 - - 7 - 4 | 10 - 8 - | - 13 - 3 | 6 - 16 - ----------------------------------------------------- - 13 - 10 | 2 - 6 - | - 9 - 11 | 14 - 15 - - 5 11 - | - 8 4 - | - 15 13 - | - 1 3 - - - 16 8 | 5 12 - - | - - 1 2 | 13 11 - - - - - - | - - - 15 | 14 - - - | - - - - ----------------------------------------------------- - - - - | - - - 6 | 11 - - - | - - - - - - 10 9 | 14 1 - - | - - 12 4 | 15 6 - - - 3 6 - | - 11 16 - | - 2 5 - | - 9 8 - - 4 - 13 | 15 - 3 - | - 8 - 16 | 10 - 11 - ----------------------------------------------------- - 14 - 15 | 1 - 5 - | - 3 - 8 | 12 - 6 - - 2 9 - | - 3 15 - | - 10 16 - | - 7 13 - - - 3 12 | 13 14 - - | - - 11 7 | 2 5 - - - - - - | - - - - | - - - - | - - - - 6 x 6 Code: - - 1 | 2 - - - 2 - | - 3 - --------------- 2 - - | - - 4 3 - - | - - 5 --------------- - 6 - | - 5 - - - 3 | 6 - - 8 x 8 Code: 1 - 2 4 | - - - - - 3 7 - | - - - - ------------------- - - 5 - | 4 - 7 - - 4 - - | 5 - - - ------------------- - - - 6 | - - 3 - - 8 - 5 | - 7 - - ------------------- - - - - | - 5 2 - - - - - | 8 4 - 6 Where dashes in the grid are unknown values. and - lines and | are seperators that I use to make the grid readable. In general.. the input file for the class expects a sudoku in this format. Empty cells get '-''s, cellblocks are seperated horizontally by | and vertically by one line of dashes. As long as it sticks to that format.. it should read in whether it is any of the above grid sizes. Right now since I use a static array.. the allocation is still hardcoded to a specific length denoted by GRID_SIZE. I've been in the process of debugging the class.. and debugging arrays is a lot easier than debugging pointer to arrays visually... but i've included ptrCell which is a pointerized version of the array along with comments at each point it would be set. Once you transition it over its just ptrCell rather than Cell with no other changes. Until then.. to play around with the class simply create a variable of that type. The default contstructor is set for a 9x9 grid. To make a custom grid pass the contructor 4 values pertaining to the grid that you want. These are: 1) CellBlock_Width. This is the Width of a CellBlock. For 3x3 Grid its 3. For the 8x8 Grid above its 4. 1) CellBlock_Height. This is the Height of a CellBlock. For 3x3 Grid its 3. For the 8x8 Grid above its 2. 1) Num_CellBlock_Width. This is how many Cellblocks there are wide. For a 3x3 its 3. For the 8x8 Grid Above its 2. 1) Num_CellBlock_Height. This is how many Cellblocks there are high. For a 3x3 its 3. For the 8x8 Grid Above its 4. So a 3x3 grid is SudokuGrid *sGrid = new SudokuGrid(3,3,3,3); For the 8x8 grid above its SudokuGrid *sGrid = new SudokuGrid(4,2,2,4); For the 6x6 grid above its SudokuGrid *sGrid = new SudokuGrid(3,2,2,3); If you aren't using the pointer notation for finality yet force the GRID_SIZE define to the number of cells in the grid. Now your main code if solving the sudoku would be to read in the file.. which you need to make sure is formatted to the constraints of the grid you created... hit Solve, and then write the file back out to disk. Lastly free the grid. Compile and run. sGrid -> Read_File("input.sku"); sGrid -> Solve(); sGrid -> Write_File("output.sku"); delete sGrid. That's pretty much all there is to it. I've tested this on 2x2's, 3x3's, 8x8's(both directions), 12x12's and seems to be pretty smooth now.
