Nested loops break out unexpectedly

Question

Hi guys,

I'm trying to create a sudoku game, for those that do not know what it is. You have a 9x9 box that needs to be filled with numbers from 1-9, every number must be unique in its row and column, and also in the 3x3 box it is found. I ended up doing loads of looping within a 2 dimensional array.

But at some point it just stops, with no exceptions whatsoever, just breaks out and nothing happens, and it's not always at the same position, but always goes past half way.

I was expecting a stack overflow exception at least.

Here's my code:

public class Engine
{
    public int[,] Create()
    {
        int[,] outer = new int[9, 9];


        for (int i = 0; i < 9; i++)
        {
            for (int j = 0; j < 9; j++)
            {
                 outer[i, j] = GetRandom(GetUsed(outer, i, j));
            }
        }

        return outer;

    }

    List<int> GetUsed(int[,] arr, int x, int y)
    {
        List<int> usedNums = new List<int>();
        for (int i = 0; i < 9; i++)
        {
            if (arr[x, i] != 0 && i != y)
            {
                if(!usedNums.Contains(arr[x, i]))
                    usedNums.Add(arr[x, i]);
            }
        }

        for (int i = 0; i < 9; i++)
        {
            if (arr[i, y] != 0 && i != x)
            {
                if (!usedNums.Contains(arr[i, y]))
                    usedNums.Add(arr[i, y]);
            }
        }

        int x2 = 9 - (x + 1);
        int y2 = 9 - (y + 1);

        if (x2 <= 3)
            x2 = 2;
        else if (x2 > 3 && x2 <= 6)
            x2 = 5;
        else x2 = 8;

        if (y2 <= 3)
            y2 = 2;
        else if (y2 > 3 && y2 <= 6)
            y2 = 5;
        else y2 = 8;

        for (int i = x2 - 2; i < x2; i++)
        {
            for (int j = y2 - 2; j < y2; j++)
            {
                if (arr[i, j] != 0 && i != x && j != y)
                {
                    if (!usedNums.Contains(arr[i, j]))
                        usedNums.Add(arr[i, j]);
                }
            }
        }

        return usedNums;
    }

    int GetRandom(List<int> numbers)
    {
        Random r;
        int newNum;
        do
        {
            r = new Random();
            newNum = r.Next(1, 10);
        } while (numbers.Contains(newNum));

        return newNum;
    }

}

Answer 1

It's not breaking out, it's getting stuck in an infinite loop.

If I'm reading this right, it looks like you're trying to create a Sudoku board to play on. Trouble is, it's not as simple as you think. As far as I can see, you're just going through it filling it with random unused values; the trouble is, not every such configuration is going to be valid - most of the time your random entries will eventually put you into an unsolvable board configuration.

Then, when you try to select a random value for some square, the inner GetRandom function will just loop infinitely trying to pick a number (since getUsed will already have all of 1 - 9, the do..while will never exit).

Easy way to see this for yourself: add this at the top of your GetRandom function:

if (Enumerable.Range(1, 9).All(i => numbers.Contains(i)))
    Console.WriteLine("PROBLEM!");

Now, if numbers has all of 1 to 9, it'll tell you. (And then still proceed to get stuck in an infinite loop, but that's your problem now ;))

Also, just as a sidenote, it's not good practice to keep making new Random() objects like that; better to just have a single instance of Random, initialize it in your constructor and then keep using Random.Next. At the very least, have Random r = new Random() at the top of the function, and then just have r.Next inside the loop.

Ok, here's a really simple example of getting into an unsolvable position, just in the first two rows:

123|456|789
456|123|X

There's no valid number left to put in the position marked X - see how that happened?
Filling the grid with random unused numbers isn't the same as filling it with "answers" - think of it this way, if you took a regular sudoku game and tried to solve it by just putting any random number that satisfied the rules in each blank square - you'd get stuck pretty soon, right? That's exactly what's happening to your program.

I'd suggest you try writing a sudoku solver first, that takes a valid initial board configuration and tries to solve it - then you can move on to trying to make boards yourself.

Answer 2

What would happen if in GetRandom, your numbers list was full of 1-10 already?

I think your program is freezing in the GetRandom method because you are telling it to loop infinitely until it finds a number between 1 and 10 that isn't in the list.

You should be telling it to look for 0 to 9, assuming 0 is "empty", and allowing it to leave if it gets a 0 because only 1-9 matter on the board. The 0 will be in the list by default it seems, so just ignore it.

do
{
   r = new Random();
   newNum = r.Next(0, 9);
} while (numbers.Contains(newNum) && newNum != 0);

Give that a shot and see if it works!

Answer 3

I tweaked the GetRandom for performance

static int GetRandom(List<int> usedNums)
{
    List<int> missingNums = new List<int>();
    for (int i = 1; i <= 10; i++)
    {
        if (!usedNums.Contains(i))
            missingNums.Add(i);
    }

    Random r = new Random();
    int rMissingNumIndex = r.Next(0, missingNums.Count - 1);

    return missingNums[rMissingNumIndex];
}

and got an exception because usedNums was passed with 10 elements, which means there can be no solution. Try using this method instead and you'll see the the problem.