Как исправить ошибку переполнения стека в Sudoku solver c#? Имеет отношение к рекурсивной функции? - PullRequest
Новая
       58

Как исправить ошибку переполнения стека в Sudoku solver c#? Имеет отношение к рекурсивной функции?

0 голосов
/ 21 января 2020

Я пытаюсь сделать решатель судоку. Всякий раз, когда я пытаюсь его запустить, выдается ошибка переполнения стека:

System.StackOverflowException: «Исключение типа« System.StackOverflowException »было выдано. '

I Вы полагаете, что это, вероятно, связано с функцией решения, слишком часто вызывающей функцию FindEmpy?
Любая помощь очень ценится!
Большое спасибо! 

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);
        }
    }
}

1 Ответ

1 голос
/ 21 января 2020 

        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, поэтому вы заменяете ноль другим нулем навсегда.

...