Sudoku Solver in 100 lines of code

Discussion in 'Game Programming' started by madlex, Jun 6, 2008.

  1. madlex

    madlex New Member

    Joined:
    Jun 6, 2008
    Messages:
    12
    Likes Received:
    3
    Trophy Points:
    0
    Occupation:
    Technical Project Manager
    Location:
    Bucharest,RO
    Hello

    This is my first post on go4expert, and I hope it's done with the right foot :).

    The beggining



    Although there are many solutions to solve sodoku on the Internet, after a discussion with some friends who work in the field, I inferred that there are two types of solutions specific to the sodoku game: the strategic ones, based on logical/human-style steps, and those that generate solutions based on a pattern.
    The most easy to implement are those based on generation, and here two separate typical ways of implementation: greedy and backtracking.

    So I decided to post a very simple solution, based on a primary implementation of a backtracking which is easy to understand, easy to implement and,the most interesting fact, has very few lines of code.

    Advantages and disadvantages



    The advantages of this implementation consists in the fact that, against the strategic methods, which are much faster than the generating algorithms, are rather difficult to implement, most often partial implementations rezulting in bugs for complex sudoku grids, the backtracking solution can be implemented in very few lines of code and can be characterized by both reliable and time efficient.

    Even if sudoku is regarded as having only one solution, there are many cases in which sudoku grids have more solutions, either because the grid generating algorithms are defective or because this simple fact (the unique solution) is ignored by the application's provider. Considering this, human-style methods, although very fast, do not face very well sudoku grids with multiple solutions, and in this case, some of them rely on guessing technics or even forms of backtracking, against a simple backtracking that can find all solutions for sudoku grids with no problem at all.

    However, the human-style methods can display the logical steps used, and they can show hints, which is very useful for customer applications who joins a sudoku player. This is one of the main drawbacks of this implementation, and all others of the same kind.

    About the complexity of certain grids



    Certain sites or applications offers a note of the complexity of certain sudoku grids. These degrees of complexity are valid only for human-style methods and should not be taken into consideration for backtracking algorithms. The complexity of a grid in case of backtracking should be determined by analysing the backtracking algorithm and lead to the worst-case-scenario.For example, for the algorithm below, the worst-case-scenario is a sudoku grid that has as posible candidates for the first cells big numbers like 9,8,7 and so on, increasing the backtracking's solving time. This can be easily overtaken by generating a random distribution between posible candidates on a speciefied cell. However, for simplicity, this is not done in the code below.

    Differences between backtracking and greedy



    May it be said, backtracking based solutions should not be considered simple generators, or brute-forcing algorithms, because this is the main difference between backtracking and greedy. Backtracking algorithms are looking for solutions using a well-known preset pattern, trying to optimize as much as posibile the search tree, against greedy who generates sudoku grids until it finds a valid solution. Backtracking is considered to be a quick-solver in opposition to the greedy, which is considered a purely brute-force algorithm.

    The code



    Code below is not fully optimized to remain as clear and eloquent as possible, being more useful than a beginner an experienced programmer. The main goal for this code, is to present a simple implementation, but without forgeting the speed and reliability that it should have.

    The average time that takes for solving most of the grids is about 4-5 ms on a Athlon64 3000+@1800Mhz and about 2-4 ms on a Intel Core2Duo@2Ghz.

    Code explanations



    The solver is incapsulated within the class CSudokuSolver, and it has only two accesible functions Solve and GetSolution. The Solve function will initialize internal data by calling the Init function and it will run the core solving procedure by calling BTDo. The GetSolution function is intended to be called after Solve function, and will copy the solved grid into a bidim array. In case no solution is found or Solve wasn't called before, GetSolution will return FALSE, and it will leave the array intact.
    As you can see, the code is intended to be as lite and easy as posible.

    Note: any include statement was omited.



    Definition of solver's class:
    18 lines of code
    Code:
    typedef BYTE SUDOKUTBL[9][9];
    class CSudokuSolver
    {
    public:
        CSudokuSolver(void);
    protected:
        SUDOKUTBL m_tblSudoku;            //    Current sudoku table
        BYTE m_tblColDigits[9][9];           //    Table of digits used per column
        BYTE m_tblRowDigits[9][9];         //    Table of digits used per row
        BYTE m_tblSqrDigits[9][9];          //    Table of digits used per square
        BYTE m_bSolved;
        //    Core solver
        VOID Init(const SUDOKUTBL&);
        VOID BTDo(BYTE iRow,BYTE iCol);
    public:
        //	The "public" actions
        VOID Solve(const SUDOKUTBL & tblSudoku);
        BOOL GetSolution(SUDOKUTBL & tblSudoku);	//	will return false if no solution was found
    };
    
    The implementation :
    88 lines of code
    Code:
    CSudokuSolver::CSudokuSolver(void)
    : m_bSolved(FALSE)
    {}
    
    //    Useful macros (names are self-explanatory)
    #define IsDigitOnRow(iRow,iDigit) (m_tblColDigits[iRow][iDigit-1] != 0)
    #define IsDigitOnCol(iCol,iDigit) (m_tblRowDigits[iCol][iDigit-1] != 0)
    #define IsDigitOnSqr(iSqr,iDigit) (m_tblSqrDigits[iSqr][iDigit-1] != 0)
    #define SetDigitOnRow(iRow,iDigit,bSet) m_tblColDigits[iRow][iDigit-1] = bSet
    #define SetDigitOnCol(iCol,iDigit,bSet) m_tblRowDigits[iCol][iDigit-1] = bSet
    #define SetDigitOnSqr(iSqr,iDigit,bSet) m_tblSqrDigits[iSqr][iDigit-1] = bSet
    #define SqrFromPos(iRow,iCol) BYTE((iRow)/3)*3 + BYTE((iCol)/3)
    #define AssignDigit(iRow,iCol,iDigit){                      \
            SetDigitOnRow(iRow,iDigit,TRUE);                  \
            SetDigitOnCol(iCol,iDigit,TRUE);                     \
            SetDigitOnSqr(SqrFromPos(iRow,iCol),iDigit,TRUE);   \
            m_tblSudoku[iRow][iCol] = iDigit;}
    #define UnassignDigit(iRow,iCol,iDigit){		  \
            SetDigitOnRow(iRow,iDigit,FALSE);                \
            SetDigitOnCol(iCol,iDigit,FALSE);                   \
            SetDigitOnSqr(SqrFromPos(iRow,iCol),iDigit,FALSE);  \
            m_tblSudoku[iRow][iCol] = 0;}
    #define IsDigitAssigned(iRow,iCol,iDigit)		   \
            (								   \
                IsDigitOnRow(iRow,iDigit) ||			   \
                IsDigitOnCol(iCol,iDigit) ||			   \
                IsDigitOnSqr(SqrFromPos(iRow,iCol),iDigit) \
            )
    VOID CSudokuSolver::Init(const SUDOKUTBL& tbl)
    {
        //    Reset mappings
    	m_bSolved = FALSE;
        ZeroMemory(&m_tblColDigits,sizeof m_tblColDigits);
        ZeroMemory(&m_tblRowDigits,sizeof m_tblRowDigits);
        ZeroMemory(&m_tblSqrDigits,sizeof m_tblSqrDigits);
    
            for(BYTE i = 0; i < 9; i++ )
            for(BYTE j = 0; j < 9; j++ )
            {
                //    Lock "template" digits
                if( tbl[i][j] != 0 )
                {  AssignDigit(i,j,tbl[i][j]);}
    
                //    Copy sudoky table
                m_tblSudoku[i][j] = tbl[i][j];
            }
    }
    VOID CSudokuSolver::BTDo(BYTE iRow,BYTE iCol)
    {
        BYTE iDigit;
        if( iRow == 9 )
    	{	m_bSolved = TRUE;/*TODO:print solution here*/	return;	}
    
        //    Digit is in the "template" table
         if( m_tblSudoku[iRow][iCol] != 0 )
         {
            //    Call next step
            if( iCol == 8 )
                    BTDo( iRow+1,0);
            else    BTDo( iRow,iCol+1);
            return VOID();
         }
        //    Generate digits
        for( iDigit = 1; iDigit < 10; iDigit ++ )
        {
            if( IsDigitAssigned(iRow,iCol,iDigit) == FALSE )
            {
                AssignDigit(iRow,iCol,iDigit);
                    //    Call next step
                    if( iCol == 8 )
                            BTDo( iRow+1,0);
                    else    BTDo( iRow,iCol+1);
                UnassignDigit(iRow,iCol,iDigit);
            }
        }
    }
    VOID CSudokuSolver::Solve(const SUDOKUTBL & tbl)
    {
        Init(tbl);    //    initialize
        BTDo(0,0);    //    solve
    }
    BOOL CSudokuSolver::GetSolution(SUDOKUTBL & tbl)
    {
    	if( m_bSolved )
    	{
    		memcpy(&tbl,m_tblSudoku,sizeof SUDOKUTBL);
    		return TRUE;
    	}	return FALSE;
    }
    Cheers
     
  2. shabbir

    shabbir Administrator Staff Member

    Joined:
    Jul 12, 2004
    Messages:
    15,375
    Likes Received:
    388
    Trophy Points:
    83
    Really nice one.
     
  3. shabbir

    shabbir Administrator Staff Member

    Joined:
    Jul 12, 2004
    Messages:
    15,375
    Likes Received:
    388
    Trophy Points:
    83
  4. debleena_doll2002

    debleena_doll2002 New Member

    Joined:
    Feb 5, 2008
    Messages:
    119
    Likes Received:
    0
    Trophy Points:
    0
    Excellent Article!!!
     
  5. madlex

    madlex New Member

    Joined:
    Jun 6, 2008
    Messages:
    12
    Likes Received:
    3
    Trophy Points:
    0
    Occupation:
    Technical Project Manager
    Location:
    Bucharest,RO
    Thank you for your appreciation.

    Here's the code for the iterative version of the solver:

    Code:
    BOOL CSudokuSolver::Solve(SUDOKUTBL & tbl)
    {
    	Reset();
    	Init(tbl);	//	initialize
    
    	BYTE iDigit,
    		 idx,
    		 arrDigitStack[81],
    		 arrAssignedStack[81];
    
    	ZeroMemory(&arrDigitStack	,sizeof arrDigitStack);
    	ZeroMemory(&arrAssignedStack,sizeof arrAssignedStack);
    
    	idx		= 0;
    	BYTE bFall(0);
    
    	while( idx < m_cTblIdx )
    	{
    		if( m_lpfnDebug )
    			m_lpfnDebug(&m_tblSudoku,m_arrTblIdx[idx].iRow,m_arrTblIdx[idx].iCol);
    
    		if( arrDigitStack[idx] )
    		{	
    			//	Unassign previous assigned digit
    			if( arrAssignedStack[idx] )
    			{
    				UnassignDigit(
    					m_arrTblIdx[idx].iRow,
    					m_arrTblIdx[idx].iCol,
    					arrDigitStack[idx]);
    
    				arrAssignedStack[idx]	= 0;
    			}
    
    			//	No more digits to assign - fallback
    			if( arrDigitStack[idx] == 9 )
    				goto fallback;
    		}
    
    		//	Try assigning a digit
    		for( iDigit = arrDigitStack[idx]+1; iDigit < 10 ; iDigit ++ )
    		{
    			if( IsDigitAssigned(
    					m_arrTblIdx[idx].iRow,
    					m_arrTblIdx[idx].iCol,
    					iDigit) )
    				continue;
    
    			AssignDigit(
    				m_arrTblIdx[idx].iRow,
    				m_arrTblIdx[idx].iCol,
    				iDigit);
    
    			arrDigitStack	[idx]	= iDigit;	//	assigned
    			arrAssignedStack[idx]	= 1;
    	
    			//	Advance
    			goto nextdigit;
    		}
    
    fallback:
    		//	Reset stack
    		arrAssignedStack[idx] = 0;
    		arrDigitStack[idx]	  = 0;
    
    		//	Fallback
    		if( !idx )
    			return FALSE;//	no solution
    		idx  --;
    		continue;
    nextdigit:
    		//	Climb
    		idx  ++;
    	}
    
    	if( m_lpfnSolution )
    		m_lpfnSolution( &m_tblSudoku );
    	m_bSolved = TRUE;
    	return TRUE;
    }
    It improves the speed of the implementation. Cheers.
     
    firdaus_lazim likes this.
  6. madlex

    madlex New Member

    Joined:
    Jun 6, 2008
    Messages:
    12
    Likes Received:
    3
    Trophy Points:
    0
    Occupation:
    Technical Project Manager
    Location:
    Bucharest,RO
    Application

    And here is a MFC application that implements both the iterative and recursive solving algorithm.

    Cheers
     

    Attached Files:

  7. shabbir

    shabbir Administrator Staff Member

    Joined:
    Jul 12, 2004
    Messages:
    15,375
    Likes Received:
    388
    Trophy Points:
    83
  8. ydeveloper66

    ydeveloper66 New Member

    Joined:
    Jul 6, 2010
    Messages:
    2
    Likes Received:
    0
    Trophy Points:
    0
    Home Page:
    http://www.ydeveloper.com/java-ecommerce.html
    Hello,

    Great post! Thanks for sharing whole code. I will try to implement it. Hope it will work.
     
  9. umairaraza100

    umairaraza100 Banned

    Joined:
    Jul 29, 2011
    Messages:
    5
    Likes Received:
    0
    Trophy Points:
    0
    Home Page:
    http://www.earnmoney.pk/
    wow very nice work thanks for sharing with us in this forum
     
  10. hitesh123

    hitesh123 Banned

    Joined:
    Oct 20, 2011
    Messages:
    11
    Likes Received:
    0
    Trophy Points:
    0
    Occupation:
    seo executive
    Location:
    delhi
    you have done great job........nice
     
  11. parker1234

    parker1234 Banned

    Joined:
    Jan 20, 2012
    Messages:
    18
    Likes Received:
    0
    Trophy Points:
    0
    Hey that s very good nice effort....keep updating such useful information
     
  12. kellys

    kellys Banned

    Joined:
    Jun 14, 2012
    Messages:
    13
    Likes Received:
    0
    Trophy Points:
    0
    Home Page:
    http://www.phuketvillaservices.com/en/phuket-villas
    thanks for the share.. will give it a try
     

Share This Page

  1. This site uses cookies to help personalise content, tailor your experience and to keep you logged in if you register.
    By continuing to use this site, you are consenting to our use of cookies.
    Dismiss Notice