如何解决Sudoku求解器C＃的堆栈溢出错误？与递归函数有关吗？

Question

我正在尝试制作数独求解器。每当我尝试运行它时，都会给我一个堆栈溢出错误（System.StackOverflowException：“引发了类型为System.StackOverflowException”的异常。）。我认为这可能与调用FindEmpy函数的solve函数过多有关？任何帮助是极大的赞赏！非常感谢！

using System;

namespace sudokusolver
{
    class Program
    {
        static public void PrintBoard(int[][] bo)
        {
            for (int i = 0; i < bo.Length; i++)
            {
                if (i % 3 == 0 && i != 0)
                {
                    Console.WriteLine("- - - - - - - - - - - - -");
                }
                for (int j = 0; j < bo[0].Length; j++)
                {
                    if (j % 3 == 0 && j != 0)
                    {
                        Console.Write(" | ");
                    }
                    if (j == 8)
                    {
                        Console.WriteLine(bo[i][j]);
                    }
                    else
                    {
                        Console.Write(bo[i][j] + " ");
                    }
                }
            }
        }

        static public (int,int) FindEmpty(int[][] bo)
        {
            for (int i = 0; i < bo.Length; i++) 
            {
                for (int j = 0; j < bo[0].Length; j++)
                {
                    if (bo[i][j] == 0)
                    { 
                        return (i, j);
                    }
                }
            }
            return (100, 100);
        }

        static public bool Solve(int[][] bo)
        {
            int x;
            int y;
            if (FindEmpty(bo) == (100, 100))
            {
                return true;
            }
            else
            {
                y = FindEmpty(bo).Item1;
                x = FindEmpty(bo).Item2;
            }

            for (int i = 0; i < 10; i++)
            {
                if (IsValid(bo, i, x, y) == true)
                {
                    bo[y][x] = i;
                    if (Solve(bo) == true)
                    {
                        return true;
                    }
                    else
                    {
                        bo[y][x] = 0;
                    }
                }
            }
            return false;
        }

        static public bool IsValid(int[][] bo, int num, int x, int y)
        {
            for (int i = 0; i < bo.Length; i++)
            {
                if (bo[y][i] == num && x != i)
                {
                    return false;
                }
            }
            for (int i = 0; i < bo[0].Length; i++)
            {
                if (bo[i][x] == num && y != i)
                {
                    return false;
                }
            }
            int boxx = x / 3;
            int boxy = y / 3;
            for (int i = boxy * 3; i < boxy * 3 + 3; i++)
            {
                for (int j = boxx * 3; j < boxx * 3 + 3; j++)
                {
                    if (bo[i][j] == num && i != y && j != x)
                    {
                        return false;
                    }
                }
            }
            return true;
        }

        static void Main(string[] args)
        {
            int[][] board = {
                new int[] {7,0,0,0,0,0,2,0,0},
                new int[] {4,0,2,0,0,0,0,0,3},
                new int[] {0,0,0,2,0,1,0,0,0},
                new int[] {3,0,0,1,8,0,0,9,7},
                new int[] {0,0,9,0,7,0,6,0,0},
                new int[] {6,5,0,0,3,2,0,0,1},
                new int[] {0,0,0,4,0,9,0,0,0},
                new int[] {5,0,0,0,0,0,1,0,6},
                new int[] {0,0,6,0,0,0,0,0,8}
            };

            PrintBoard(board);
            Solve(board);
            PrintBoard(board);
        }
    }
}

Answer 1

        static public bool Solve(int[][] bo)
        {
            int x;
            int y;
            if (FindEmpty(bo) == (100, 100))
            {
                return true;
            }
            else
            {
                y = FindEmpty(bo).Item1;
                x = FindEmpty(bo).Item2;
            }

-            for (int i = 0; i < 10; i++)
+            for (int i = 1; i < 10; i++)
            {
                if (IsValid(bo, i, x, y) == true)
                {
                    bo[y][x] = i;
                    if (Solve(bo) == true)
                    {
                        return true;
                    }
                    else
                    {
                        bo[y][x] = 0;
                    }
                }
            }
            return false;
        }

在某个时候，IsValid(bo, 0, x, y)返回true，因此您永远用另一个零替换零。