Why is my sudoku solver in C# not working?

badcoder_94 0
Viewed 77

This is my first post so I apologize if I'm doing it wrong. I started coding a couple of months ago in python and I've now made my way over to C#. In an effort to learn backtracking I've attempted coding the sudoku solver. But, for the life of my, I cannot understand why my code is not working. Naturally, there are many solutions out there. I feel the best way for me to progress right now though is to understand what I'm missing in my personal code. So, if you have the time:

Why will my code not return me a solved sudoku board? I suspect the fault lies in the recursion.

The main program:

using System;

namespace Sudoku
{
    class Program
    {
        static void Main(string[] args)
        {          
            
            var sudokuTemplate = new SudokuTemplate();
            var sudoku = sudokuTemplate.CreateSudoku();
            Print.print(sudoku);
            Console.WriteLine();
            Print.print(driver(sudoku));
        }    

        static int[,] driver(int[,] board)
        {
            var check = new ErrorCheck();

            for (int i = 0; i < 9; i++)
            {
                for (int j = 0; j < 9; j++)
                {
                    if (board[i,j] == 0)
                    {   
                        for (int n = 1; n <= 9; n++)
                        {
                            if (check.legal(board, i, j, n))
                            {
                                board[i, j] = n;  
                                driver(board); 
                            }   
                            else
                            {
                                board[i, j] = 0;
                            }                         
                        } 
                        return board;                      
                    }                  
                }
            }
            return board;
        }
    }
}

The unsolved sudoku

    namespace Sudoku
{
    class SudokuTemplate
    {
        public int[,] CreateSudoku()
        {
            var array = new int[,] 
            {
                {5,3,0,0,7,0,0,0,0},  
                {6,0,0,1,9,5,0,0,0},  
                {0,9,8,0,0,0,0,6,0},  
                {8,0,0,0,6,0,0,0,3},  
                {4,0,0,8,0,3,0,0,1},  
                {7,0,0,0,2,0,0,0,6},  
                {0,6,0,0,0,0,2,8,0},  
                {0,0,0,4,1,9,0,0,5},  
                {0,0,0,0,8,0,0,7,9}  
            };
            return array;
        }
    }
}

Error checker sees if the number n is legal to place on the board:

namespace Sudoku
{
    public class ErrorCheck
    {
        public bool legal(int[,]array, int row, int col, int n)
        {   //check col & rw
            for (int i = 0; i < 9; i++)
            {
                if (array[row, i] == n)
                {
                    return false;
                }
                if (array[i, col] == n)
                {
                    return false;
                }
            }

            //check boxes
            int valRow = 0;
            if (row < 6 && row > 2)
            {
                valRow = 3;
            }
            else if (row < 9 && row > 5)
            {
                valRow = 6;
            }

            int valCol = 0;
            if (col < 6 && col > 2)
            {
                valCol = 3;
            }
            else if (col < 9 && col > 5)
            {
                valCol = 6;
            }
            
            for (int i = 0; i < 3; i++)
            {
                for (int j = 0; j < 3; j++)
                {
                    if (array[(j+valRow), (i+valCol)] == n)
                        {
                            return false;
                        }
                }
            }
            return true;
        }   
        
    }
}

And finally the print function:

    namespace Sudoku
{
    class Print
    {
        public static void print(int[,] array)
        {
            // prints sudoku
            for (int i = 0; i < 9; i++)
            {
                for (int j = 0; j < 9; j++) 
                {
                    Console.Write("{0} ", array[i, j]);
                    Console.Write("|");     
                }
                Console.WriteLine();
            }
            
        }
    }
}

Edit:

Code results in printing the original unsolved sudoku board twice. It seems to be working correctly initially, but somewhere along the line everything is just reset to the original unsolved board.

solver sudoku c#
2 Answers

there are three problems.

The first is in sgmoore's answer, the Sudoku isn't valid. Try to copy an existing sudoku from internet.

The second is in the ErrorCheck class:

if (array[(i+valCol), (j+valRow)] == n)

You have to invert the two indices of the matrix to obtain the right box.

if (array[(j+valRow), (i+valCol)] == n)

The third error is in the Program class: you put in a cell the first valid number. In Sudoku you have to put the ONLY valid number. So, in my opinion, for each cell you have to check all the nine numbers and save in a list all the possible values, after that if there is only one possible value, you put that. This method can be enough for a simple Sudoku, but if the complexity increase, you will have to use other advanced techniques, like Double Pairs or X-Wing.

Errors aside, I think your code is very clear and simple to read. The only change I would make is to rename "i" and "j" with "row" and "col" in the Program class.

Samuele Coassin0

Thank you for all the replies. As suggested by Astrid, I spent some more time in the debugger and fixed a bunch of logic errors. I had mixed up || with && for example (these mistakes are now edited out I think). Still, this was not enough to get the code to work. So, I moved the backtracking out of the for loop in the driver function. This because I imagined that the method might be doing its job and just to rewrite everything with 0 as it was emerging. After the change, it looked like this:

static int[,] driver(int[,] board)
        {
            var check = new ErrorCheck();

            for (int row = 0; row < 9; row++)
            {
                for (int col = 0; col < 9; col++)
                {
                    if (board[row, col] == 0)
                    {   
                        for (int n = 1; n <= 9; n++)
                        {
                            if (check.legal(board, row, col, n))
                            {
                                board[row, col] = n;  
                                driver(board); 
                            }             
                        }                         
                        board[row, col] = 0;  
                        return board; 
                    }                  
                }
            }   
            return board;
        }

Still, it did not work. I tried debugging by printing what was happening to console. Sometimes, nothing was printed at all. In the end I tried printing from within the method and BAM! It seems to have worked.

static int[,] driver(int[,] board)
        {
            var check = new ErrorCheck();

            for (int row = 0; row < 9; row++)
            {
                for (int col = 0; col < 9; col++)
                {
                    if (board[row, col] == 0)
                    {   
                        for (int n = 1; n <= 9; n++)
                        {
                            if (check.legal(board, row, col, n))
                            {
                                board[row, col] = n;  
                                driver(board); 
                            }             
                        }                         
                        board[row, col] = 0;   
                        return board; 
                    }                  
                }
            }   
            Print.print(board);
            return board;
        }

I have not implemented the fancy optimization as suggested by Samuele Coassin, but at least works. However, I have no idea why the Print.print() method didn't work from outside of the driver method. If anyone has a clue, feel free to respond. If not, thank you anyway for the interest you've shown.

badcoder_940
Related