CODEWITHSUNDEEP
c++recursion
Hofbr
Hofbr

Reputation: 1010

Solving a Sudoku Puzzle Recursively

I'm trying to solve a Sudoku Puzzle recursively, Yet the puzzle seems to get into a recursive loop continuously in instances where a row contains duplicate values > 1.

Any input where there is a duplicate in a box, row, column get suck in infinite loops, rather than my recursive method solvePuzzle failing.

Examples of failed input are...

Same Box

input = "011"

 0 1 1|0 0 0|0 0 0
 0 0 0|0 0 0|0 0 0
 0 0 0|0 0 0|0 0 0
------+-----+------
 0 0 0|0 0 0|0 0 0
 0 0 0|0 0 0|0 0 0
 0 0 0|0 0 0|0 0 0
------+-----+------
 0 0 0|0 0 0|0 0 0
 0 0 0|0 0 0|0 0 0
 0 0 0|0 0 0|0 0 0

Same Row

input = "0100001"

 0 1 0|0 0 0|1 0 0
 0 0 0|0 0 0|0 0 0
 0 0 0|0 0 0|0 0 0
------+-----+------
 0 0 0|0 0 0|0 0 0
 0 0 0|0 0 0|0 0 0
 0 0 0|0 0 0|0 0 0
------+-----+------
 0 0 0|0 0 0|0 0 0
 0 0 0|0 0 0|0 0 0
 0 0 0|0 0 0|0 0 0

Same Column

input = "01000000000000000000000000001"

 0 1 0|0 0 0|0 0 0
 0 0 0|0 0 0|0 0 0
 0 0 0|0 0 0|0 0 0
------+-----+------
 0 1 0|0 0 0|0 0 0
 0 0 0|0 0 0|0 0 0
 0 0 0|0 0 0|0 0 0
------+-----+------
 0 0 0|0 0 0|0 0 0
 0 0 0|0 0 0|0 0 0
 0 0 0|0 0 0|0 0 0

It otherwise successfully solves other instances. Looking through the debugger, it seems that the stack never progresses beyond row 1. I'm lost to figure out where in my logic I've gone wrong to make it stuck.

The Recursive method is below, I'll include my declarations and implementation for reference at the bottom.

Solve Puzzles

bool Puzzle::solvePuzzle(int row, int col) {
   int next_row = nextRow(row, col);
   int next_col = nextCol(col);

   if (row == 9) {
      return true;
   }

   if (m_board[row][col].isFixed()) {
      return solvePuzzle(next_row, next_col);
   }

   for (int val = 1; val <= 9; val++) {

      if (set(row, col, val) && solvePuzzle(next_row, next_col)) {
         return true;
      }
      else {
         m_board[row][col].setValue(0);
      }
   }
   return false;
}

Declarations

#pragma once
#include <iostream>


class Puzzle
{
private:
   class Square {
      int m_value;
      bool m_is_fixed;

   public:
      // CONSTRUCTOR
      Square() { m_value = 0; m_is_fixed = false; };

      Square(int value) { m_value = value; m_is_fixed = (value > 0) ? true : false; };

      // DESTRUCTOR
      ~Square() { m_value = 0; m_is_fixed = false; };

      // ACCESSORS
      int getValue() const { return (m_value > 0) ? m_value : -1; };

      int getTrueValue() const { return m_value; }

      // MUTATORS
      void setValue(int value) { m_value = value; };

      void setFixedFlag(bool flag) { m_is_fixed = flag; };

      // INQUIRIES
      bool isFixed() const { return m_is_fixed; };

   };

private:
   static const int m_row_size = 9;
   static const int m_col_size = 9;
   Square m_board [m_row_size][m_col_size];
   int m_num_variable_entries = 0;

public:
   // CONSTRUCTOR
   Puzzle() { setSquares(); };

   // DESTRUCTOR
   ~Puzzle() {};

   // ACCESSORS
   int size() const { return m_num_variable_entries; };

   int numEmpty();

   void display(std::ostream& out) const;

   int get(int const row, int const col) const { return m_board[row][col].getValue(); };

   // MUTATORS
   bool set(int const row, int const col, int const value);

   // FACILITATORS
   void input(std::istream& in);

   bool solvePuzzle(int row = 0, int col = 0);   

public:
   // FRIENDS
   friend std::ostream& operator<<(std::ostream& out, const Puzzle& puzzle);

   friend std::istream& operator>>(std::istream& in, Puzzle& puzzle);

private:
   // MUTATORS
   void setSquares();

   int convertCharToInt(char const c) { return int(c) - 48; };

   // FACILITATORS
   int nextRow(int const row, int const col) const { return (col == m_col_size - 1) ? row + 1 : row; };

   int nextCol(int const col) const { return (col + 1) % m_col_size; };

   // INQUIRIES
   bool isRowLegal(int const row, int const col, int const val) const;

   bool isColLegal(int const row, int const col, int const val) const;

   bool isBoxLegal(int const row, int const col, int const val) const;

   bool isLegal(int const row, int const col, int const val) const;

};

Implementation

#include <iostream>
#include "Puzzle.h"

// CONSTRUCTOR

// ACCESSORS
int Puzzle::numEmpty() {
   int num_empty = 0;
   for (int row = 0; row < m_row_size; row++) {
      for (int col = 0; col < m_col_size; col++) {
         if (m_board[row][col].getTrueValue() == 0) {
            num_empty++;
         }
      }
   }
   return num_empty;
}

void Puzzle::display(std::ostream& out) const {
   for (int row = 0; row < m_row_size; row++) {
      for (int col = 0; col < m_col_size; col++) {
         // cout col divider between blocks for given cols
         if (col == 3 || col == 6) {
            std::cout << "|";
         }
         else {
            std::cout << " ";
         }
         std::cout << m_board[row][col].getTrueValue();
      }
      // cout row divider between blocks for given rows
      if (row == 2 || row == 5) {
         std::cout << std::endl;
         const int front = 0;
         const int end = 18;
         for (int i = front; i < end + 1; i++) {
            if (i % 6 == 0 && i != front && i != end) {
               std::cout << "+";
            }
            else {
               std::cout << "-";
            }
         }
      }
      std::cout << std::endl;
   }
}

// MUTATORS
void Puzzle::setSquares() {
   m_num_variable_entries = 0;

   for (int row = 0; row < m_row_size; row++) {
      for (int col = 0; col < m_col_size; col++) {
         if (m_board[row][col].getTrueValue() == 0) {
            m_board[row][col].setFixedFlag(false);
         }
         else {
            ++m_num_variable_entries;
            m_board[row][col].setFixedFlag(true);
         }
      }
   }
}

bool Puzzle::set(int const row, int const col, int const val) {
   if (isLegal(row, col, val)) {
      m_board[row][col].setValue(val);
      return true;
   }
   else {
      return false;
   }
}

// FACILITATORS
void Puzzle::input(std::istream& in) {

   m_num_variable_entries = 0;
   char c;
   int row = 0;
   int col = 0;
   while (in >> c) {
      if (c >= '0' && c <= '9') {
         int num = convertCharToInt(c);
         m_board[row][col].setValue(num);
         if (c == '0') {
            m_board[row][col].setFixedFlag(false);
         }
         else {
            m_board[row][col].setFixedFlag(true);
            m_num_variable_entries++;
         }
         row = nextRow(row, col);
         col = nextCol(col);
      }
      if (row == 9) {
         break;
      }
   }
}

bool Puzzle::solvePuzzle(int row, int col) {
   int next_row = nextRow(row, col);
   int next_col = nextCol(col);

   if (row == 9) {
      return true;
   }

   if (m_board[row][col].isFixed()) {
      return solvePuzzle(next_row, next_col);
   }

   for (int val = 1; val <= 9; val++) {

      if (set(row, col, val) && solvePuzzle(next_row, next_col)) {
         return true;
      }
      else {
         m_board[row][col].setValue(0);
      }
   }
   return false;
}

// INQUIRIES
bool Puzzle::isRowLegal(int const row, int const col, int const val) const {
   // iterate through a row and skip the square we're confirming
   // check for existing equivalent value.
   for (int i = 0; i < m_col_size; i++) {
      if (i != col && m_board[row][i].getTrueValue() == val) {
         return false;
      }
   }
   return true;
}

bool Puzzle::isColLegal(int const row, int const col, int const val) const {
   // iterate through a col and skip the square we're confirming
   // check for existing equivalent value.
   for (int i = 0; i < m_row_size; i++) {
      if (i != row && m_board[i][col].getTrueValue() == val) {
         return false;
      }
   }
   return true;
}

bool Puzzle::isBoxLegal(int const row, int const col, int const val) const {
   int const row_corner = (row / 3) * 3;
   int const col_corner = (col / 3) * 3;

   for (int i = row_corner; i < (row_corner + 3); i++) {
      for (int j = col_corner; j < (col_corner + 3); j++) {
         if ((i != row || j != col) && m_board[i][j].getTrueValue() == val) {
            return false;
         }
      }
   }
   return true;
}

bool Puzzle::isLegal(int const row, int const col, int const val) const {
   return (isRowLegal(row, col, val) &&
           isColLegal(row, col, val) &&
           isBoxLegal(row, col, val));
}

// FRIENDS
std::ostream& operator<<(std::ostream& out, const Puzzle& puzzle) {
   puzzle.display(out);
   return out;
}

std::istream& operator>>(std::istream& in, Puzzle& puzzle) {
   puzzle.input(in);
   return in;
}

Upvotes: 2

Views: 196

Answers (1)

Hofbr
Hofbr

Reputation: 1010

As noted in the comments to my question by @n. m. and @Matt Clarke, the isLegal call only checks that a given input is not duplicated. There is not a check for duplicated entries already existing in the board.

So in my input method, I've added a check that still utilizes the logic of the isLegal method.

I also made my solvePuzzle method private, the method can be called as helper method once we've verified the puzzle is solvable.

bool Puzzle::isPuzzleLegal() const {
   for (int row = 0; row < m_row_size; row++) {
      for (int col = 0; col < m_col_size; col++) {
         if (m_board[row][col].isFixed()) {
            bool result = isLegal(row, col, m_board[row][col].getTrueValue());
            if (!result) {
               return false;
            }
         }
      }
   }
   return true;
}

Upvotes: 1

Related Questions