1
\$\begingroup\$

This is my approach on creating a sudoku generator and solver with backtracking. Is right for sudoku generator to inherit from soduku solver? What is your general overview on the class structure, data members, variable names and data structure used.

Here is the code

#ifndef SUDOKUGEN_HH
#define SUDOKUGEN_HH
/******************************************************************
 * Name: SudokuGen.hh
 * Author: Samuel Oseh
 * Description: SudokuGen class method-function prototype
 * Purpose: This class generates a sudoku puzzle for a 9 x 9 array
 * ****************************************************************/

#include <vector>
#include <array>
#include "SudokuSolver.hh"

class SudokuGen : public SudokuSolver {
    public:
        SudokuGen();
        ~SudokuGen(){}
        bool generateBoard( const std::string &difficulty );
        std::array< std::array< int, 9 >, 9 > board{};
    private:
        std::vector< int > validChoices;

        // utility functions
        void setValidChoices();
        void shuffleChoices( std::vector< int > & );
        void setBoard( const std::string &difficulty );
};

#endif

#ifndef SUDOKUSOLVER_HH
#define SUDOKUSOLVER_HH
/******************************************************************
 * Name: SudokuSolver.hh
 * Author: Samuel Oseh
 * Description: SudokuSolver class method-function prototype
 * Purpose: This class solves a sudoku puzzle for a 9 x 9 array
 * ****************************************************************/

#include <array>

class SudokuSolver {
    public:
        SudokuSolver(){}
        SudokuSolver( const std::array< std::array< int, 9 >, 9 > &board );
        ~SudokuSolver(){}
        bool solve();
        void printBoard( std::array< std::array< int, 9 >, 9 > &board ) const;
    protected:
        std::array< std::array< int, 9 >, 9 > board;
        bool isRowValid( std::array< std::array< int, 9 >, 9 > &board, int, int, int );
        bool isColValid( std::array< std::array< int, 9 >, 9 > &board, int, int, int );
        bool isBlockValid( std::array< std::array< int, 9 >, 9 > &board, int, int, int );
        bool choiceIsValid( std::array< std::array< int, 9 >, 9 > &board, int, int, int );
        std::array< int , 2 > getNextEmpty( std::array< std::array< int, 9 >, 9 > &board );
};

#endif

/******************************************************************
 * Name: SudokuGen.cc
 * Author: Samuel Oseh
 * Description: SudokuGen class method-function definitions
 * Purpose: This class generates a sudoku puzzle for a 9 x 9 array
 * ****************************************************************/

#include <iostream>
#include <random>
#include "SudokuGen.hh"

SudokuGen::SudokuGen() {
    setValidChoices();
    shuffleChoices( validChoices );
}

void SudokuGen::setValidChoices() {
    for ( unsigned int counter = 1; counter <= 9; ++counter ) {
        validChoices.push_back( counter );
    }
}

void SudokuGen::shuffleChoices( std::vector< int > &choices ) {
    std::default_random_engine engine ( static_cast< unsigned int > ( time(0) ) );
    std::uniform_int_distribution< unsigned int > randomInt( 0, choices.size() - 1 );

    for ( size_t i = 0; i < choices.size(); ++i ) {
        int swapIndex = randomInt( engine );
        for ( ; swapIndex == i; ) {
            swapIndex = randomInt( engine );
        }
        // swap
        int temp = choices[ i ];
        choices[ i ] = choices[ swapIndex ];
        choices[ swapIndex ] = temp;
    }
}

bool SudokuGen::generateBoard( const std::string &difficulty ) {
    std::array< int , 2 > empty = getNextEmpty( board );
    if ( empty[ 0 ] == -1 && empty [ 1 ] == -1 ) {
        setBoard( difficulty );
        return true;
    }

    for ( unsigned int counter = 0; counter < validChoices.size(); ++counter ) {
        if ( choiceIsValid( this->board, empty[ 0 ], empty[ 1 ], validChoices[ counter ] ) ) {
            board[ empty[ 0 ] ][ empty[ 1 ] ] = validChoices[ counter ];

            if ( generateBoard( difficulty ) )
                return true;
        }
        board[ empty[ 0 ] ][ empty[ 1 ] ] = 0;
    }
    return false;
}

void SudokuGen::setBoard( const std::string &difficulty ) {
    std::default_random_engine engine ( static_cast< unsigned int > ( time(0) ) );
    std::uniform_int_distribution< unsigned int > randomInt( 0, 8 );
    int row = 0, col = 0;
    int counter = 0;
    int limit = 0;
    if ( difficulty == "Easy" ) 
        limit = 25;
    else if ( difficulty == "Medium" )
        limit = 35;
    else if ( difficulty == "Hard" )
        limit = 45;
    else if ( difficulty == "Legend" )
        limit = 55;
    else {
        throw std::invalid_argument( "Invalid argument" );
    }
    while( counter < limit ) {
        row = randomInt( engine );
        col = randomInt( engine );
        if ( board[ row ][ col ] != 0 ) {
            board[ row ][ col ] = 0;
            ++counter;
        }
    }
}

/******************************************************************
 * Name: SudokuSolver.cc
 * Author: Samuel Oseh
 * Description: SudokuSolver class method-function definitions
 * Purpose: This class solves a sudoku puzzle for a 9 x 9 array
 * ****************************************************************/

#include <iostream>
#include "SudokuSolver.hh"

SudokuSolver::SudokuSolver ( const std::array< std::array< int, 9 >, 9 > &board  ) {
    this->board = board;
}

bool SudokuSolver::solve() {
    std::array< int , 2 > empty = getNextEmpty( board );
    if ( empty[ 0 ] == -1 && empty [ 1 ] == -1 ) {
        printBoard( board );
        return true;
    }

    for ( unsigned int guess = 1; guess < 10; ++guess ) {
        if ( choiceIsValid( board, empty[ 0 ], empty[ 1 ], guess ) ) {
            board[ empty[ 0 ] ][ empty[ 1 ] ] = guess ;

            if ( solve() )
                return true;
        }
        board[ empty[ 0 ] ][ empty[ 1 ] ] = 0;
    }
    return false;
}

std::array< int , 2 > SudokuSolver::getNextEmpty( std::array< std::array< int, 9 >, 9 > &board ) {
    for ( int row = 0; row < board.size(); ++row ) {
        for ( int col = 0; col < board.size(); ++col ) {
            if ( board[ row ][ col ] == 0 ) {
                std::array< int, 2 > empty { row, col };
                return empty;
            }
        }
    }
    std::array< int, 2 > empty { -1, -1 };
    return empty;
}

bool SudokuSolver::choiceIsValid( std::array< std::array< int, 9 >, 9 > &board, int row, int column, int guess ) {
    // row wise check
    bool result = isRowValid( board, row, column, guess );

    // columnwise check
    if ( result == true )
        result = isColValid( board, row, column, guess );

    // block check
    if ( result == true )
        result = isBlockValid( board, row, column, guess );

    return result;
} 
bool SudokuSolver::isRowValid( std::array< std::array< int, 9 >, 9 > &board, int row, int column, int guess ) {
    for ( unsigned int counter = 0; counter < board.size(); ++counter ) {
        if ( board[ counter ][ column ] == guess )
            return false;
    }
    return true;
}

bool SudokuSolver::isColValid( std::array< std::array< int, 9 >, 9 > &board, int row, int column, int guess ) {
    for ( unsigned int counter = 0; counter < board.size(); ++counter ) {
        if ( board[ row ][ counter ] == guess )
            return false;
    }
    return true;
}

bool SudokuSolver::isBlockValid( std::array< std::array< int, 9 >, 9 > &board,  int row, int column, int guess ) {
    int segmentX = 3 * ( row / 3 );
    int segmentY = 3 * ( column / 3 );

    for ( unsigned int i = segmentX; i < segmentX + 3; ++i ) {
        for ( unsigned int j = segmentY; j < segmentY + 3; ++j ) {
            if ( board[ i ][ j ] == guess )
                return false;
        }
    }
    return true;
}
void SudokuSolver::printBoard( std::array< std::array< int, 9 >, 9 > &board ) const {
     for ( unsigned int counter = 97; counter < 106; ++counter )
        std::cout << "       " << static_cast< char >( counter );
    std::cout << std::endl;
    for ( unsigned int row = 0; row < board.size(); ++row ) {
        std::cout << "  |-------|-------|-------|-------|-------|-------|-------|-------|-------|" << std::endl;
        std::cout << ( row + 1 ) << " ";
        for ( unsigned  int column = 0; column < board.size(); ++column ) {
            if ( board[ row ][ column ]  == 0 )
                std::cout << "|       ";  
            else
                std::cout << "|   " << board[ row ][ column ] << "   ";
        }
        std::cout << "|";
        std::cout << std::endl;
        std::cout << "  |       |       |       |       |       |       |       |       |       |" << std::endl;
    }
    std::cout << "  |-------|-------|-------|-------|-------|-------|-------|-------|-------|" << "\n\n";
}

#include <iostream>
#include "SudokuGen.hh"
#include "SudokuSolver.hh"

using namespace std;

int main() {
    SudokuGen soduku;
    soduku.generateBoard( "Legend" );
    sudoku.printBoard( sudoku.board );
    std::cout << "\n\nSOLVED===========================================\n\n";
    SudokuSolver sudokuSolver( sudoku.board );
    sudokuSolver.solve();
}
\$\endgroup\$
2
  • \$\begingroup\$ if you write "std::array<std::array<int, 9>, 9>" (no leading/trailing spaces inside "<>"'s) instead of "std::array< std::array< int, 9 >, 9 >" it makes your code a lot more readable, IMPO.. And why does the generator inherit from the solver??? As far as I can see they share no members. \$\endgroup\$
    – user9413641
    Commented Oct 6, 2020 at 16:16
  • \$\begingroup\$ They share some methods....They both check if a guess is valid and also get the next empty location \$\endgroup\$
    – theProgrammer
    Commented Oct 6, 2020 at 17:20

1 Answer 1

Reset to default
1
\$\begingroup\$

I don't think the generator should inherit from the solver. Rather, any methods that they both need could be moved into a third class that either 1) they both inherit from or 2) they both include as a member.

I would try to do #2.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.