Trying to make a sudoku puzzle generator

Before I start, I know that there are tons of Sudoku puzzle generators for MATLAB out there but none of them do what I would like. I am trying to create a Sudoku generator that will take a 9x9 array of zeros and replace the first row with a randomly generated array of the numbers 1-9. To do this, I am using the randperm function as follows:

numb=zeros(9,9);
numb(1,:)=randperm(9,9);

this part works fine. Where I am having issues is generating all following lines. As of right now, I am using a a different for loop for each row with nested for loops inside for each column. An example of the code I am using for the second row of the array is as follows:

for r=2;
    for c=1;
        numb(r,c)=randi(9);
        for i=1:3;
            while numb(r,c) == numb(r-1,i);
                numb(r,c)=randi(9);
            end
        end
    end

      for c=2;
          numb(r,c)=randi(9);
          for i=1:3;
              while numb(r,c) == numb(r-1,i) || numb(r,c) == numb(r,c-1);
                  numb(r,c)=randi(9);
              end
          end
      end

      for c=3;
          numb(r,c)=randi(9);
          for i=1:3;
              while numb(r,c) == numb(r-1,i) || numb(r,c) == numb(r,c-1) || numb(r,c) == numb(r,c-2);
                  numb(r,c)=randi(9);
              end
          end
      end

      for c=4;
          numb(r,c)=randi(9);
          for i=4:6;
              for j=1:(c-1);
                  while numb(r,c) == numb(r-1,i) || numb(r,c) == numb(r,c-j);
                      numb(r,c)=randi(9);
                  end
              end
          end
      end

      for c=5;
          numb(r,c)=randi(9);
          for i=4:6;
              for j=1:(c-1);
                  while numb(r,c) == numb(r-1,i) || numb(r,c) == numb(r,c-j);
                      numb(r,c)=randi(9);
                  end
              end
          end
      end

      for c=6;
          numb(r,c)=randi(9);
          for i=4:6;
              for j=1:(c-1);
                  while numb(r,c) == numb(r-1,i) || numb(r,c) == numb(r,c-j);
                      numb(r,c)=randi(9);
                  end
              end
          end
      end

      for c=7;
          numb(r,c)=randi(9);
          for i=4:6;
              for j=1:(c-1);
                  while numb(r,c) == numb(r-1,i) || numb(r,c) == numb(r,c-j);
                      numb(r,c)=randi(9);
                  end
              end
          end
      end

      for c=8;
          numb(r,c)=randi(9);
          for i=4:6;
              for j=1:(c-1);
                  while numb(r,c) == numb(r-1,i) || numb(r,c) == numb(r,c-j);
                      numb(r,c)=randi(9);
                  end
              end
          end
      end

      for c=9;
          numb(r,c)=randi(9);
          for i=4:6;
              for j=1:(c-1);
                  while numb(r,c) == numb(r-1,i) || numb(r,c) == numb(r,c-j);
                      numb(r,c)=randi(9);
                  end
              end
          end
      end
  end

Can anyone tell me why the code as I have it written will work most of the time but not all the time to check and make sure there are no repeats in the second row, each column, and each 3x3 box? also, if anyone has any tips on how to extend this for loop or a better one to encorporate remaining rows, I'd love your input.

Answer 1

[Greg Dionne]

I like your randperm() idea. You can use it to do the scrambling without any for-loops at all.

You may safely transform a valid Suduko grid into another via:

1. permuting the symbols '1'-'9'.
2. permuting any three rows/columns within the same band (e.g. X([4 5 6],:) = X([6 5 4],:)
3. permuting any three rows/columns of bands (e.g. X([1:3 4:6 7:9],:) = X([7:9 1:3 4:6],:)
4. transposition (e.g. X = X')

Have fun!

[Morgan Clendennin]

Hi Greg,

I like the idea that I would be able to do it without having to use any for loops and I like that you broke down the steps of how the code would work but how would the code check to make sure that the steps above have worked and there are no repeats in any of the rows, columns and 3x3 boxes without some sort of loop? I'm assuming I would use a while loop but I was wondering if there was maybe a problem with the syntax of my while loop that was making it so that I would be able to get a full array of numbers but there would be repeats where there shouldn't be.

[Morgan Clendennin]

Also I am confused as to what you mean by transposition at the end of your process steps

[Greg Dionne]

Something like this (you'll want MATLAB version R2016b or later):

    function X = sudoku
    % start with a legal position
    ir = 0:8;
    ic = reshape(ir,3,3)';
    X = 1 + mod(ir+ic(:), 9); 

    % step 1
    p = randperm(9,9);

    % step 2,3 (rows)
    r = randperm(3,3) + 3*(randperm(3,3)-1)';

    % step 2,3 (cols)
    c = randperm(3,3) + 3*(randperm(3,3)-1)';

    % Permute away!
    X = p(X);
    X = X(r,:);
    X = X(:,c);

    % Step 4 (Transpose at random)
    if randi(2)==1
        X = X';
    end

Hope this helps.

[Morgan Clendennin]

I'm still a little confused. Am I still making a 9x9 array of zeros like I did for the example I sent? also, I'm getting an error with your method on the third line. Because ir is a 3x3 array and ic is a 9x1 array, the dimensions don't match up and so it won't compute X

[Greg Dionne]

R2016b introduced implicit scalar expansion. But since you have a previous version of MATLAB, you can use bsxfun instead.

    function X = sudoku
    % start with a legal position
    ir = 0:8;
    ic = reshape(ir,3,3)';
    X = 1 + mod(bsxfun(@plus,ir,ic(:)),9);

    % step 1
    p = randperm(9,9);

    % step 2,3 (rows)
    r = bsxfun(@plus,randperm(3,3),3*(randperm(3,3)-1)');

    % step 2,3 (cols)
    c = bsxfun(@plus,randperm(3,3),3*(randperm(3,3)-1)');

    % Permute away!
    X = p(X);
    X = X(r,:);
    X = X(:,c);

    % Step 4 (Transpose at random)
    if randi(2)==1
        X = X';
    end

[Morgan Clendennin]

Thanks Greg! That works perfectly for me! My only question is why we go on to steps 1 2 and 3 for the rows and columns if the start with a legal position works for setting a place for each number such that there are no repeats unless to make sure that the puzzle is truly randomized. Also, what did you mean when you mentioned the transposition of the X matrix?

[Greg Dionne]

The idea here is that you want to avoid all the for-loops, backtracking and indexing.

By starting with a very simple board, you can reach all other valid Sudoku boards just by performing those permutations, except for those that also need transpositions. (See Enumerating Sudoku Solutions).

[Morgan Clendennin]

The only other issue that I am having at this point is where I am writing a function that will take the output of the Sudoku function and based on whether I specify that I am playing a easy, medium, hard or expert level game, will determine how many numbers to remove from the board and then randomly remove them. My problem is that I did what you did and said

function numbers=SudokuGame
perform specified stuff here
end

The problem is now that when in my other function I say

function easygame
numbers=SudokuGame
to_be_removed=25;
perform steps for removal...
end

the easygame function blows up saying that there is no numbers array for it to perform the random removal steps on. Any understanding of why this would happen?

[Greg Dionne]

I find it helpful to step through with the debugger to see what is going on. If you see an error message, Google it! Chances are good someone else may have run into the same issue you did.

Good luck with your program!

Answer 2

[Yeshwanth Devara]

I am assuming that you are looking to create a sudoku generator but don't want to use any of the existing ones.

It is possible that you are receiving the issue because the loops for the elements in row 2 columns 7 to 9, you are verifying the columns 4 to 6?

I changed the code to columns 7 to 9 and it seems to work fine.

     for c=7;
        numb(r,c)=randi(9);
        for i=7:9;
            for j=1:(c-1);
                while numb(r,c) == numb(r-1,i) || numb(r,c) == numb(r,c-j);
                numb(r,c)=randi(9);
                end
            end
        end
    end
    for c=8;
        numb(r,c)=randi(9);
        for i=7:9;
            for j=1:(c-1);
                while numb(r,c) == numb(r-1,i) || numb(r,c) == numb(r,c-j);
                numb(r,c)=randi(9);
                end
            end
        end
    end
    for c=9;
        numb(r,c)=randi(9);
        for i=7:9;
            for j=1:(c-1);
                while numb(r,c) == numb(r-1,i) || numb(r,c) == numb(r,c-j);
                numb(r,c)=randi(9);
            end
            end
        end
    end

It would be good to know if you would like to create a sudoku generator that is functionally different from others.

[Morgan Clendennin]

Hi Yeshwanth,

Thank you for getting back to me regarding my question. I want a Sudoku generator that is functionally the same as other Sudoku generators available out there but I don't like how they are coded up as I am trying to code mine up similar to there's and the ones I am trying to do it based off of are too confusing to follow. I tried your fix for my code and it still does not work. The code as I understand I have written it is supposed to check each of the preceeding rows values as well as the columns next to it to make sure that no rows, columns or 3x3 box has any repeating values. I am not getting this result at all. Maybe you can point out where I may have more mistakes?

Thanks,

Morgan

Answer 3

[Image Analyst]

Have you taken a look at the Sudoku code in Cleve's Laboratory?

(Cleve Moler is the founder of The Mathworks).

There are lots of other fun things in his laboratory in addition to that.