Sudoku Solver

[emilyj127]

I have created code to generate a sudoku game. I am just stuck on the solver. I have started but not sure what to do next.The board i am trying to solve looks like this and is in a text file.
0 0 0 0 0 0 0 0 0
0 0 0 0 0 3 0 8 5
0 0 1 0 2 0 0 0 0
0 0 0 5 0 7 0 0 0
0 0 4 0 0 0 1 0 0
0 9 0 0 0 0 0 0 0
5 0 0 0 0 0 0 7 3
0 0 2 0 1 0 0 0 0
0 0 0 0 4 0 0 0 9
The zeros will be replaced with empty spaces The solver is the last program. Help is much greatly appreciated!

#include <fstream>
#include <iostream>
#include <cctype>
#include <iomanip>
#include <cstdlib>
using namespace std;

void readFile(int board[9][9]);
void options(int board[9][9]);
void chooseOption(int board[9][9], char coordinate[], int &num);
void display(int [9][9]);
void editNumber(int board[9][9], char coordinate[], int &num);
void saveFile(int board[9][9]);
void getCoordinate( char coordinate[]);
bool isPossible(int board[9][9], char coordinate[], int &num);
void showPossibleValues(char coordinates[], int board[9][9]);
void solveSudoku(int board[9][9], int &num, char coordinate[]);


/**********************************************************************
 * readFile- prompt user for filename and check if good
 ***********************************************************************/
void readFile(int board[9][9])
{
   ifstream input;
   char fileName[256];
   cout << "Where is your board located? ";
   cin >> fileName;

   input.open(fileName);
   if (input.fail())
   {
      cout << "Invalid file!\n";
      return;
   }

   for (int i = 0; i < 9; i++)
   {
      for (int j = 0; j < 9; j++)
         input >> board[i][j];

   }
   input.close();
   return;

}

/**********************************************************************
 * options- will display options 
 ***********************************************************************/
void options(int board[9][9])
{
   cout << "Options:\n"
        << "   ?  Show these instructions\n"
        << "   D  Display the board\n"
        << "   E  Edit one square\n"
        << "   S  Show the possible values for a square\n"
        << "   Q  Save and Quit\n"
        << "   C  Solve\n\n";

   return;
}

/**********************************************************************
 * chooseOption- will allow user to pick option by entering a letter
 ***********************************************************************/
void chooseOption(int board[9][9], char coordinate[], int &num)
{
   char option;
   cout << "> ";
   cin >> option;
   option = toupper(option);

   switch (option)
   {
      case '?':
         options(board);
         cout << "\n";
         break;
      case 'D':
         display(board);
         break;
      case 'E':
         editNumber(board,coordinate, num);
         break;
      case 'S':
         showPossibleValues(coordinate, board);
         break;
      case 'Q':
         saveFile(board);
         return;
      case 'C':
         solveSudoku(board, num, coordinate);
         break;
      default:
      {
         cout << "ERROR: Invalid command\n";
         options(board);
      }
   }

   chooseOption(board, coordinate, num);

   return;
}

/**********************************************************************
 * display- will the display the board from file
 ***********************************************************************/
void display(int board[9][9])
{
   int j;
   int i;
   cout << "   A B C D E F G H I\n";
   for (i = 0; i < 9; i++)
   {

      if ((i == 3) || (i == 6))
      {
         cout << "   -----+-----+-----\n";
      }

      cout << i + 1 << "  ";

      for (j = 0; j < 9; j++)
      {
         if ((board[i][j] == 0))
            cout << ' ';

         else if (board[i][j] > 0)
            cout << abs(board[i][j]);
         else
            cout << abs(board[i][j]);


         if ((j == 2) || (j == 5))
            cout << "|";
         else if (j == 8)
            cout << '\n';
         else
            cout << ' ';
      }

   }

   cout << endl;

   return;
}

/**********************************************************************
 * editNumber- allow the user to change numbers
 ***********************************************************************/
void editNumber(int board[9][9],char coordinate[], int &num)
{
   int i = 0;
   int j = 0;

   getCoordinate(coordinate);



   for (char *p = coordinate; *p; p++)
   {

      if (isalpha(*p))
      {
         *p = toupper(*p);
         switch (*p)
         {
            case 'A':
               j = 0;
               break;

            case 'B':
               j = 1;
               break;

            case 'C':
               j = 2;
               break;

            case 'D':
               j = 3;
               break;

            case 'E':
               j = 4;
               break;

            case 'F':
               j = 5;
               break;

            case 'G':
               j = 6;
               break;

            case 'H':
               j = 7;
               break;

            case 'I':
               j = 8;
               break;

            default:
               cout << "ERROR: Square '" << coordinate << "' is invalid\n";
         }
      }

      if (isdigit(*p))
         i =  atoi(p) - 1;

   }

   if (board[i][j] > 0)
      cout << "ERROR: Square '" << coordinate << "' is filled\n";
   else
   {
      cout << "What is the value at '" << coordinate << "': ";
      cin >> num;


      if ((board[i][j] < 9) && (board[i][j] > 0) ||
          (isPossible(board, coordinate, num) == true))
         board[i][j] = - num;
      else
         cout << "ERROR: Value '" << num << "' in square '"
              << coordinate << "' is invalid\n";

   }

   cout << endl;

   return;
}

/**********************************************************************
 * saveFile- allow the user to save sudoku game and write it to a
 * different file
 **********************************************************************/
void saveFile(int board[9][9])
{
   ofstream output;
   char savedFile[256];
   cout << "What file would you like to write your board to: ";
   cin >> savedFile;
   output.open(savedFile);

   for (int i = 0; i < 9; i++)
   {
      for (int j = 0; j < 9; j++)
         output << board[i][j] << ' ';
   }

   cout << "Board written successfully\n";

   output.close();

   return;

}

/**********************************************************************
 * getCoordinate- prompt user for coordinates 
 ***********************************************************************/
void getCoordinate(char coordinate[])
{
   cout << "What are the coordinates of the square: ";
   cin.ignore();
   cin.getline(coordinate, 256);

   return;
}

/**********************************************************************
 * isPossible- compute possible values
 **********************************************************************/
bool isPossible(int board[9][9], char coordinate[], int &num)
{
   int i = coordinate[0];
   int j = coordinate[1];



   for (char *p = coordinate; *p; p++)
   {

      if (isalpha(*p))
      {
         *p = toupper(*p);
         switch (*p)
         {
            case 'A':
               j = 0;
               break;

            case 'B':
               j = 1;
               break;

            case 'C':
               j = 2;
               break;

            case 'D':
               j = 3;
               break;

            case 'E':
               j = 4;
               break;

            case 'F':
               j = 5;
               break;

            case 'G':
               j = 6;
               break;

            case 'H':
               j = 7;
               break;

            case 'I':
               j = 8;
               break;

         }
      }

      if (isdigit(*p))
         i =  atoi(p) - 1;
   }
   bool found = true;





   for (int r = 0; r < 9; r++)
   {
      if ((board[i][r] == num) ||
          (board[r][j] == num))
         found = false;
   }

   for ( int sc = 3 * (i / 3); sc < (3 * (i / 3) + 3); sc++)
   {
      for ( int sr = 3 * (j / 3); sr < (3 * (j / 3) + 3); sr++)
         if (board[sc][sr] == num)
            found = false;

   }



   return found;
}

[emilyj127]

here is the rest of the code

/**********************************************************************
 * showPossibleValues- display possible values for coordinate
 **********************************************************************/
void showPossibleValues(char coordinate[], int board[9][9])
{
   int i = 0;
   int j = 0;

   getCoordinate(coordinate);

   for (char *p = coordinate; *p; p++)
   {

      if (isalpha(*p))
      {
         *p = toupper(*p);
         switch (*p)
         {
            case 'A':
               j = 0;
               break;

            case 'B':
               j = 1;
               break;

            case 'C':
               j = 2;
               break;

            case 'D':
               j = 3;
               break;

            case 'E':
               j = 4;
               break;

            case 'F':
               j = 5;
               break;

            case 'G':
               j = 6;
               break;

            case 'H':
               j = 7;
               break;

            case 'I':
               j = 8;
               break;

         }
      }

      if (isdigit(*p))
         i =  atoi(p) - 1;
   }

   if (board[i][j] > 0)
      cout << "ERROR: Square '" << coordinate << "' is read-only\n\n";



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

   int c;
   for (int r = 0; r < 9; r++)
   {
      for ( c = 0; c < 10; c++)
      {

         if (((board[i][r]) == (compArray[c])) ||
             ((board[r][j]) == (compArray[c])))
            compArray[c] = 0;


         for ( int sc = 3 * (i / 3); sc < (3 * (i / 3) + 3); sc++)
         {
            for ( int sr = 3 * (j / 3); sr < (3 * (j / 3) + 3); sr++)
               if (board[sc][sr] == compArray[c])
                  compArray[c] = 0;

         }

      }
   }

   int count = 0;

   cout << "The possible values for '" << coordinate << "' are: ";
   for ( c = 0; c < 10; c++)
   {
      if (compArray[c] != 0)
      {

         if (count != 0)
            cout << ", ";

         cout << compArray[c];
         count++;
      }
   }


   cout << "\n\n";
   return;
}

/**********************************************************************
 * solveSudoku- solve the board
 **********************************************************************/
void solveSudoku(int board[9][9], int &num, char coordinate[])
{

   for (int i = 0; i < 9; i++)
   {
      for (int j = 0; j < 9; j++)
      {

         if (board[i][j] == 0)
         {
            for (num = 1; num < 10; num++)
            {

               coordinate[0] = i;
               coordinate[1] = j;
               if (isPossible(board, coordinate, num) == true)
               {
                  board[i][j] = - num;

               }



            }



         }

      }
   }

}

/**********************************************************************
 * Main will execute the program by calling other functions 
 ***********************************************************************/
int main()
{
   int num;
   char coordinate[256];
   int board[9][9];
   readFile(board);
   options(board);
   display(board);
   chooseOption(board,coordinate, num);

   return 0;
}

[Mats]

The example game you have shown there has only 16 clues, but a minimum of 17 are required to make a unique grid (unique solution).

Good counting skills. I'm going to bed. lol

Anyway for a puzzle like this you want to use recursion. Top post here is good: http://stackoverflow.com/questions/16675248/sudoku-solving-algorithm-c

[emilyj127]

I am pretty sure there are 17.

[heebleworp]

By happy coincidence I'm working on the exact same thing :)

I don't know about using recursion (suppose it's possible) but you'll want functions that:
1) Check a cell's ("cell" meaning one of the board's 81 positions) row for a value.
2) Check a cell's column for a value.
3) Check a cell's 3x3 square for a value.

Then some others, I'm still here atm. Not stuck, just haven't gotten around to writing the necessary function(s), I'm either one function away from solving puzzles or still have others to write that I haven't thought of yet. Their logic is easy enough to describe if you want me to, though half the fun from programming something like this is figuring out the answer for yourself.

[heebleworp]

Finished writing a solver, if you want any hints on the logic part of the solver let me know.

Looking at the code you've posted one major change you should make imo is how you represent the sudoku. Currently you represent it as a 2D array of int, which makes sense and for puzzles which can be determined only by checking rows, columns and 3x3 squares may be optimal. However for puzzles where checking rows, columns and 3x3 squares is not sufficient life becomes much easier if you store the possible values as well. Here's a snippet of the code I ended up with:

const int SQUARESIZE = 9;

//Cell is a single position of the Sudoku, with (0,0) being the upperleft and (8,8) being the lowerright
//possible is initially true for all values since all values are intially possible. knownVal is zero if
//the value is unknown, 1-9 if the value is known.
struct Cell
{
    int knownVal;
    bool possible[SQUARESIZE];
    //something spoilery here though not necessary
};

//a Sudoku is a SQUARESIZE by SQUARESIZE grid of Cells
typedef Cell Sudoku[SQUARESIZE][SQUARESIZE];

You could use something similar.