0

Hi,
I am writing a sudoku solver program that uses recursion to solve all the empty cells.
However, I have no idea why my function did not do anything.
I read in my puzzle as double char array and convert it to double int array.

My output is :
900020750
600050040
020400010
208000000
070509060
000000401
010005080
090070004
082040006

where all the 0s are the empty cells

//
#include "puzzle.h"
#include <iostream>
#include <stdlib.h>
using namespace std;

Puzzle::Puzzle(const char grid[][9])
{ /*
  for(int i = 0; i < 9; i++)
  {
    for(int j = 0; j < 9; j++)
    {
      //cout << "row"<< i << " column" << j << " "<< grid[i][j] << endl;
      if(grid[i][j] == '*')
        puzzle[i][j] = 0;
      else
        puzzle[i][j] = grid[i][j] - '0';

//cout << "puzzle row" << i << " column" << j << " " << puzzle[i][j] << endl;
    }
  }*/
  for(int i = 0; i < 9; i++)
    for(int j = 0; j < 9; j++)
      puzzle[i][j] = 0;

  puzzle[0][0] = 9;
  puzzle[0][4] = 2;
  puzzle[0][6] = 7;
  puzzle[0][7] = 5;

  puzzle[1][0] = 6;
  puzzle[1][4] = 5;
  puzzle[1][7] = 4;

  puzzle[2][1] = 2;
  puzzle[2][3] = 4;
  puzzle[2][7] = 1;

  puzzle[3][0] = 2;
  puzzle[3][2] = 8;

  puzzle[4][1] = 7;
  puzzle[4][3] = 5;
  puzzle[4][5] = 9;
  puzzle[4][7] = 6;

  puzzle[5][6] = 4;
  puzzle[5][8] = 1;

  puzzle[6][1] = 1;
  puzzle[6][5] = 5;
  puzzle[6][7] = 8;

  puzzle[7][1] = 9;
  puzzle[7][4] = 7;
  puzzle[7][8] = 4;

  puzzle[8][1] = 8;
  puzzle[8][2] = 2;
  puzzle[8][4] = 4;
  puzzle[8][8] = 6;


}

bool Puzzle::isRowValid(int row, int num)
{
  for(int col = 0; col < 9; col++)
  {
    if(puzzle[row][col] == num)
      return false;
  }
  return true;
}

bool Puzzle::isColValid(int col, int num)
{
  for(int row = 0; row < 9; row++)
  {
    if(puzzle[row][col] == num)
      return false;
  }
  return true;
}

bool Puzzle::isBoxValid(int row, int col, int value)
{
  row = (row/3)*3;
  col = (col/3)*3;

  for(int i = 0; i < 3; i++)
  {
    for(int j = 0; j < 3; j++)
    {
      if(puzzle[row+i][col+j] == value)
        return false;
    }
  }
return true;
}

void Puzzle::next(int row, int col)
{
  if(col < 8)
    solve(row,col+1);
  else
    solve(row+1,0);
}

void Puzzle::solve(int row, int col)
{
  // exit when row is > 8
  if(row > 8)
      return;

  // check if cell needs to be solve
  if(puzzle[row][col] != 0)
    next(row, col);
  else
  {
    // find a valid number for current cell
    for(int num = 1; num <= 9; num++)
    {
      if(isRowValid(row,num) && isColValid(col,num) && isBoxValid(row,col,num))
      {
        //cout << "check2" << endl;
        puzzle[row][col] = num;
        //cout << "puzzle row" << row << " column" << col << " " << num << endl;
        next(row,col);
      }
    }

    // valid number not found, return to caller
    puzzle[row][col] = 0;
  }

}

void Puzzle::display()
{
  for(int row = 0; row < 9; row++)
  {
    for(int col = 0; col < 9; col++)
      cout << puzzle[row][col];

    cout << endl;
  }
}
1
Contributor
0
Replies
14
Views
Have something to contribute to this discussion? Please be thoughtful, detailed and courteous, and be sure to adhere to our posting rules.