How to generate Sudoku boards with unique solutions

Question

How do you generate a Sudoku board with a unique solution? What I thought was to initialize a random board and then remove some numbers. But my question is how do I maintain the uniqueness of a solution?

Cussedness

Write an algorithm that solves a sudoku no matter how many clues it has and by that i mean even if it has 0 clues. That algorithm will help you in many tasks you will need afterwards. The most basic thing it will do is giving you a variaty of solved sudokus that you will be able to use to create the unsolvables with the help of a different function which will remove clues and another which will find the number of solutions each time you remove a clue. – Oxfordshire

I have generated the 81 numbers representing one of the possible solutions to a sudoku with no hidden numbers. See below: ``` 1 2 3 4 5 6 7 8 9 4 5 6 7 8 9 1 2 3 7 8 9 1 2 3 4 5 6 2 3 4 5 6 7 8 9 1 5 6 7 8 9 1 2 3 4 8 9 1 2 3 4 5 6 7 3 4 5 6 7 8 9 1 2 6 7 8 9 1 2 3 4 5 9 1 2 3 4 5 6 7 8 ``` – Wendel

Then I fixed the result of the computation in a ``cache'' in a kind of memoization and I generated a shuffled array of 9 numbers and used it to swap the 81 numbers with the corresponding ones in that shuffled array. Example: Shuffled array: 9 6 1 2 5 4 7 8 3 >> Index: 1 2 3 4 5 6 7 8 9 >>new 81 array: ``` 9 6 1 2 5 4 7 8 3 2 5 4 7 8 3 9 6 1 ... ``` – Wendel

Answer 1

Easy:

1. Find all solutions with an efficient backtracking algorithm.
2. If there is just one solution, you are done. Otherwise if you have more than one solution, find a position at which most of the solutions differ. Add the number at this position.
3. Go to 1.

I doubt you can find a solution that would be much faster than this.

Celinecelinka

I think you are right, but how to grade level for the borad generated in this way, it seems no parameter to control the difficut. – Tolu

Well, that's a different question, much more difficult. What is sure is that he more numbers you add, the easier. – Celinecelinka

No need to find all solutions, it's enough to search for a second one. – Davidson

Answer 2

Here is the way my own SuDoKu program does it:

---

1. Start with a complete, valid board (filled with 81 numbers).

2. Make a list of all 81 cell positions and shuffle it randomly.

3. As long as the list is not empty, take the next position from the list and remove the number from the related cell.

4. Test uniqueness using a fast backtracking solver. My solver is - in theory - able to count all solutions, but for testing uniqueness, it will stop immediately when it finds more than one solution.

5. If the current board has still just one solution, goto step 3) and repeat.

6. If the current board has more than one solution, undo the last removal (step 3), and continue step 3 with the next position from the list

7. Stop when you have tested all 81 positions.

---

This gives you not only unique boards, but boards where you cannot remove any more numbers without destroying the uniqueness of the solution.

Of course, this is only the second half of the algorithm. The first half is to find a complete valid board first (randomly filled!) It works very similar, but "in the other direction":

---

1. Start with an empty board.

2. Add a random number at one of the free cells (the cell is chosen randomly, and the number is chosen randomly from the list of numbers valid for this cell according to the SuDoKu rules).

3. Use the backtracking solver to check if the current board has at least one valid solution. If not, undo step 2 and repeat with another number and cell. Note that this step might produce full valid boards on its own, but those are in no way random.

4. Repeat until the board is completely filled with numbers.

Tillford

I'm a bit perplexed by (3) Use the solver to check if the current board has at least one valid solution. If you've only added one character to an empty board (in step 2) and then test your solver on in (in step 3), you're essentially solving an empty board. I don't think my solver is that good, and more importantly if it could solve an empty board then the problem of getting a valid solution would already be solved and I could skip to step 4! – Guadiana

@The111: solving an empty board is easy, you can do this even without a computer. But I am looking for a randomly filled board, that's why I don't just stop after step 3. – Tillford

What's the purpose of 3rd point in second algorithm? Is it possible to generate a valid board which does not have any solutions? – Cucumber

@Luke: take an arbitrary Sudoku with exactly one solution. Lets assume the upper left corner is free, and if you just apply the rules (in short: each row, column and 3x3 square shall contain the numbers 1-9), you find out directly that it is allowed to place 1,3,5 and 7 into the upper left corner. But only "1" is allowed in the final solution, so if you place 3,5 or 7, the backtracking solver will show that these three numbers will not lead to the valid final solution. – Tillford

Your logic is unclear. At the "second" phase (which is actually processed "first") you place numbers on the board and "use the backtracking solver to check if the current board has at least one valid solution". After some numbers (17-40) this gives you a unique solution, and the step 4 from now on is a waste of time. Moreover, the backtracking solver is already filled entire board and let you note at which configuration you have minimal state with unique solution. So you don't need the phase of throwing out numbers from the complete board. – Drain

@Stan: "this gives you a unique solution, and the step 4 from now on is a waste of time." - The test for uniqueness would mean to let the solver run until it finds a second solution (or not), which requires additional running time in each step. The above description, however, can stop the solver whenever it finds a first solution. Letting the solver backtrack then to find a second solution would lead to precisely the same additional search steps which are required in the approach above (the only difference is the cell order is taken randomly). – Tillford

... and if you have still doubts, feel free to implement this by yourself, maybe with both approaches, and compare the running times. – Tillford

I do have my own implementation, which is why I found the suggested approach overcomplicated. We could update the "adding numbers" phase in steps 3 and 4 like this: Use the backtracking solver to check if the current board has at least one valid solution and let it find second one (if any). If no solutions found, undo step 2 and repeat with another number and cell. 4. Continue in case of multiple solutions and stop if the solver found exactly 1 solution. And the phase of "removing numbers" is not needed. It has many overheads in 2,3,5,6, besides searching, so 2 phases idea looks inefficient. – Drain

I'm confused when you say your algorithm will stop immediately when it finds more than one solution. Do you mean when it will stop when it finds the first solution? But in later steps you talk about what happens when the puzzle has more than one solution. – Fakery

@CalicoSkies: when the algorithm starts, there are 81 numbers at the board, and when the first numbers are removed, the initial placing of these numbers are still the one and only unique solution. But by removing more and more numbers, there will be the point reached where more than one solution will be possible. So the solver will then find at least 2 solutions. At this point, the last removal will be undone and another number will be removed instead. – Tillford

I have implemented this solution (with my own back-tracker) and it works very well. However, there are a few possible improvements when testing uniqueness : 1. If the cell to be removed has only 1 valid option according to the rules, there is no need to use the Solver. 2. When applying the Solver, one should prevent the removed cell from taking the same value as before. Indeed, by doing so, we reduce the number of solutions by 1 and we can now abort at the first solution (instead of the second). – Inhumane

Answer 3

You can cheat. Start with an existing Sudoku board that can be solved then fiddle with it.

You can swap any row of three 3x3 blocks with any other row. You can swap any column of three 3x3 blocks with another column. Within each block row or block column you can swap single rows and single columns. Finally you can permute the numbers so there are different numbers in the filled positions as long as the permutation is consistent across the whole board.

None of these changes will make a solvable board unsolvable.

Strychnine

but how about uniqueness? how do u choose the blank cells to keep the solution unique? – Handal

@kvphxga: You start with a partial board with a unique solution. None of the allowed swaps affect the uniqueness of the solution. – Strychnine

Isn't this a horrible solution? If you use one single complete Sudoku board and swap rows and columns, will the solver notice similarities (feel samey) between puzzles? You end up only using an incredibly small number of unique solutions and I fear at some point it wont feel random to the solver. It may be worth the effort to do better than this. – Zygoma

You swap individual lines within rows/columns and also reassign numbers to positions. If you want, you can have, say, ten different starting grids and pick one at random. – Strychnine

By the way, this falls under Combinatorics - there are a lot more Full Solutions than "essentially different solutions" (wikipedia). With this, you can take 1 configuration and make multiple puzzles with it, but as @Zygoma mentioned, this most likely will lead to puzzles that feel, and play similar. – Asmodeus

And here's a clean way to permute numbers: Don't start with numbers, start with letters. Then when you're done, pick numbers randomly to replace each letter. – Kiethkiev

@Zygoma - By swapping rows, columns, blocks, and changing the digits, one solution can be drawn 609,499,054,080 ways. (That's 6⁸ × 9!) I wouldn't notice. – Kiethkiev

@Kiethkiev Just because there's billions of permutations doesn't mean the solve path will be unique each time. If you were to actually play enough sudokus like this back to back, you would pick up on the inherent logical patterns/properties within. Perhaps if you only played once a week, it would be less noticeable. But the optimal solve path is always going to be nearly identical when written out step by step. – Zygoma

@Zygoma I would assume the blanked-out numbers would be different every time, which would change the path to a solution each time. One solution to a Sudoku is going to be pretty similar to the next one anyway. – Kiethkiev

Answer 4

Unless P = NP, there is no polynomial-time algorithm for generating general Sudoku problems with exactly one solution.

In his master's thesis, Takayuki Yato defined The Another Solution Problem (ASP), where the goal is, given a problem and some solution, to find a different solution to that problem or to show that none exists. Yato then defined ASP-completeness, problems for which it is difficult to find another solution, and showed that Sudoku is ASP-complete. Since he also proves that ASP-completeness implies NP-hardness, this means that if you allow for arbitrary-sized Sudoku boards, there is no polynomial-time algorithm to check if the puzzle you've generated has a unique solution (unless P = NP).

Sorry to spoil your hopes for a fast algorithm!

Gehenna

To be fair, you can generate a few hundred unique puzzles a second using the technique in the selected answer. – Heid

Well, in this case i would like to see that. Because If you try to generate diabolical sudoku, it is sometimes really long to test all possible possibilities. For easy sudoku with a lot of initial filled digits, I agree. – Neath

My hopes for fast Zebra puzzle generator almost vanished until I read the beginning of this paper (thank you!) carefully. In solver you need to find a solution (hence the name solver), while in generator you need to generate puzzle -- you don't need to actually solve it (the fact that most approaches uses solver as part of generator is another story). I am not saying your first statement is false, I am saying it is not proven in that paper. – Shawn

@Heid permuting puzzles with validity-preserving-transformations does not give "fundamentally different" puzzles. – Tenaculum

@starball Hmm, maybe we were looking at different answers? I was referring to Tomas's answer, which doesn't talk about permuting puzzles. – Heid

Answer 5

This way you can generate any possible sudoku board as well as any other nxn sudoku board

as for how efficient this algorithm is , it took 3.6 secs to generate a million boards in java & 3.5 sec in golang

1. Find any filled board of sudoku. (use trivial ones will not affect final result)

int[][] board = new int[][] {
                {1,2,3,  4,5,6,  7,8,9},
                {4,5,6,  7,8,9,  1,2,3},
                {7,8,9,  1,2,3,  4,5,6},

                {2,3,1,  5,6,4,  8,9,7},
                {5,6,4,  8,9,7,  2,3,1},
                {8,9,7,  2,3,1,  5,6,4},

                {3,1,2,  6,4,5,  9,7,8},
                {6,4,5,  9,7,8,  3,1,2},
                {9,7,8,  3,1,2,  6,4,5}
        };

2. for each number from 1 to 9 (say num), (i.e 1, 2, 3, 5, 6, 7, 8, 9) take a random number from range [1 to 9], traverse the board, swap num with your random number.

void shuffleNumbers() {
        for (int i = 0; i < 9; i++) {
            int ranNum = random.nextInt(9);
            swapNumbers(i, ranNum);
        }
    }

private void swapNumbers(int n1, int n2) {
    for (int y = 0; y<9; y++) {
        for (int x = 0; x<9; x++) {
            if (board[x][y] == n1) {
                board[x][y] = n2;
            } else if (board[x][y] == n2) {
                board[x][y] = n1;
            }
        }
    }
}

3. Now shuffle rows. Take the first group of 3 rows , shuffle them , and do it for all rows. (in 9 X 9 sudoku), do it for second group and as well as third.

void shuffleRows() {
        int blockNumber;

        for (int i = 0; i < 9; i++) {
            int ranNum = random.nextInt(3);
            blockNumber = i / 3;
            swapRows(i, blockNumber * 3 + ranNum);
        }
    }

void swapRows(int r1, int r2) {
        int[] row = board[r1];
        board[r1] = board[r2];
        board[r2] = row;
    }

4. Swap columns, again take block of 3 columns , shuffle them, and do it for all 3 blocks

void shuffleCols() {
        int blockNumber;

        for (int i = 0; i < 9; i++) {
            int ranNum = random.nextInt(3);
            blockNumber = i / 3;
            swapCols(i, blockNumber * 3 + ranNum);
        }
    }
void swapCols(int c1, int c2) {
        int colVal;
        for (int i = 0; i < 9; i++){
            colVal = board[i][c1];
            board[i][c1] = board[i][c2];
            board[i][c2] = colVal;
        }
    }

5. swap the row blocks itself (ie 3X9 blocks)

void shuffle3X3Rows() {

        for (int i = 0; i < 3; i++) {
            int ranNum = random.nextInt(3);
            swap3X3Rows(i, ranNum);
        }
    }

void swap3X3Rows(int r1, int r2) {
        for (int i = 0; i < 3; i++) {
            swapRows(r1 * 3 + i, r2 * 3 + i);
        }
    }

6. do the same for columns, swap blockwise

void shuffle3X3Cols() {

        for (int i = 0; i < 3; i++) {
            int ranNum = random.nextInt(3);
            swap3X3Cols(i, ranNum);
        }
    }
private void swap3X3Cols(int c1, int c2) {
        for (int i = 0; i < 3; i++) {
            swapCols(c1 * 3 + i, c2 * 3 + i);
        }
    }

Now you are done, your board should be a valid sudoku board

To generate a board with hidden values, this can be done using backtracking sudoku algorithm with it try to remove one element from the board until you have a board that is solvable, remove until it will become unsolvable even if you remove only one more element.

if you want to categorised final generated board by difficulty, just count how many numbers are left in board while removing element one by one. The less the number harder it will be to solve

least possible hints in sudoku can be 17, but all possible sudoku board not necessarily reducible to 17 hint sudoku

Epsom

After having solved hundreds of Sudoku puzzles by hand, I must say that the number of starting numbers has little to do with the difficulty of solving a puzzle. The difficulty comes from the complexity of the algorithms needed to solve the puzzle. Some algorithms are easy to implement by eye when just glancing at a puzzle while other algorithms require placing notes in cells to keep track of more complicated patterns. So when judging difficulty, it must be taken into account how easy it is for a human to solve the puzzle, not how much effort it might be for a computer. – Gossipry

Answer 6

The solution is divide in to 2 parts:
A. Generating the number pattern 600 billion
B. Generating the masking pattern ~ 7e23 combinations

A ) For Number pattern the fastest way which can generate unique combinations with NO time spent on backtracing or testing

Step 1. Choose an already exiting matrix, I chose the below one as it can be made easily by human without any help from a computing device or solver:

First row is numbers in ascending order
Second row is also in ascending order but start from 4 & roll around
Third row is also in ascending order but start from 7 & roll around
Row 4,5,6: Replace the three cell column with the top right column - 2 5 8 and roll within the 3x3 cell for last column
Row 7,8,9: Replace the three cell column with the top right column - 3 6 9 and roll within the 3x3 cell for last column

1 2 3 4 5 6 7 8 9
4 5 6 7 8 9 1 2 3
7 8 9 1 2 3 4 5 6
2 3 1 5 6 4 8 9 7
5 6 4 8 9 7 2 3 1
8 9 7 2 3 1 5 6 4
3 1 2 6 4 5 9 7 8
6 4 5 9 7 8 3 1 2
9 7 8 3 1 2 6 4 5

Step 2. Shuffle the the digits and replace in all other cells
Step 3. Randomly rearrange columns 1,2 and 3 within themselves
Step 4. Randomly rearrange columns 4,5 and 6 within themselves
Step 5. Randomly rearrange columns 7,8 and 9 within themselves
Step 6. Randomly rearrange rows 1,2 and 3 within themselves
Step 7. Randomly rearrange rows 4,5 and 6 within themselves
Step 8. Randomly rearrange rows 7,8 and 9 within themselves
Step 9. Randomly rearrange in 3 column groups of size 9x3
Step 10. Randomly rearrange in 3 row groups of size 3x9

voila...

5 8 3 1 6 4 9 7 2
7 2 9 3 5 8 1 4 6
1 4 6 2 7 9 3 8 5
8 5 2 6 9 1 4 3 7
3 1 7 4 2 5 8 6 9
6 9 4 8 3 7 2 5 1
4 6 5 9 1 3 7 2 8
2 3 1 7 8 6 5 9 4
9 7 8 5 4 2 6 1 3

B ) For Masking Pattern we need to have a solver algorithm. As we already have a quite unique number grid (which is also solved!) this gives us faster performance for using solver

Step 1: Start with selecting 15 random locations out of the 81.
Step 2: Check with solver whether it has unique solution
Step 3: If solution not unique select additional location. iterate Steps 2 and 3 until unique solution found

This should give you the very unique and fast Sudoku board.

Eisenstein

It took some thought but I think that I have it now. Step 2 means e.g. change all the 1's for 5's and 2's for 1's. Steps 3-8 mean that you can rearrange rows and columns so long as they stay in the same squares. Steps 9 & 10 mean rearrange rows and columns of squares. Did I get it right? – Ailurophobe

This algorithm only creates very specific kinds of puzzles. As you can see the numbers (5, 8, 3) appear in rows 1, 2 and 3 always as a group. Same goes for all other 3-groups. For a general purpose sudoku generator this algorithm is unfortunately not useful. – Humoral

Answer 7

SWIFT 5 version

The simply way, here my code:

First, create the function into [[Int]] array

func getNumberSudoku() -> [[Int]] {
    // Original number
    let originalNum = [1,2,3,4,5,6,7,8,9]

    // Create line 1 to 9 and shuffle from original
    let line1 = originalNum.shuffled()
    let line2 = line1.shift(withDistance: 3)
    let line3 = line2.shift(withDistance: 3)
    let line4 = line3.shift(withDistance: 1)
    let line5 = line4.shift(withDistance: 3)
    let line6 = line5.shift(withDistance: 3)
    let line7 = line6.shift(withDistance: 1)
    let line8 = line7.shift(withDistance: 3)
    let line9 = line8.shift(withDistance: 3)

    // Final array
    let renewRow = [line1,line2,line3,line4,line5,line6,line7,line8,line9]

    // Pre-shuffle for column
    let colSh1 = [0,1,2].shuffled()
    let colSh2 = [3,4,5].shuffled()
    let colSh3 = [6,7,8].shuffled()
    let rowSh1 = [0,1,2].shuffled()
    let rowSh2 = [3,4,5].shuffled()
    let rowSh3 = [6,7,8].shuffled()

    // Create the let and var
    let colResult = colSh1 + colSh2 + colSh3
    let rowResult = rowSh1 + rowSh2 + rowSh3
    var preCol: [Int] = []
    var finalCol: [[Int]] = []
    var prerow: [Int] = []
    var finalRow: [[Int]] = []

    // Shuffle the columns
    for x in 0...8 {
        preCol.removeAll()
        for i in 0...8 {
            preCol.append(renewRow[x][colResult[i]])
        }
        finalCol.append(preCol)
    }

    // Shuffle the rows
    for x in 0...8 {
        prerow.removeAll()
        for i in 0...8 {
            prerow.append(finalCol[x][rowResult[i]])
        }
        finalRow.append(prerow)
    }

    // Final, create the array into the [[Int]].
    return finalRow
}

Then usage:

var finalArray = [[Int]]
finalArray = getNumberSudoku()

Moonshiner

Answer 8

It's not easy to give a generic solution. You need to know a few things to generate a specific kind of Sudoku... for example, you cannot build a Sudoku with more than nine empty 9-number groups (rows, 3x3 blocks or columns). Minimum given numbers (i.e. "clues") in a single-solution Sudoku is believed to be 17, but number positions for this Sudoku are very specific if I'm not wrong. The average number of clues for a Sudoku is about 26, and I'm not sure but if you quit numbers of a completed grid until having 26 and leave those in a symmetric way, you may have a valid Sudoku. On the other hand, you can just randomly quit numbers from completed grids and testing them with CHECKER or other tools until it comes up with an OK.

Baluchistan

The # of min clues is proven 2b 17 :) – Deflect

I'd like the add that the problem of the minimum number of pre-filled cells necessary to guarantee a unique solution has, since this discussion, been proven to be 17. (Of course, that does not mean that every board can be reducible to 17 cells: it simply means that there is no Sudoku board with 16 pre-filled cells that has a unique solution, and there is at least one board with 17 pre-filled cells that has a unique solution.) – Bergmans

Answer 9

Here is a way to make a classic sudoku puzzle (sudoku puzzle with one and only solution; pre-filled squares are symmetrical around the center square R5C5).

1) start with a complete grid (using group filling plus circular shift to get it easily)

2) remove number(s) from two symmetrical squares if the cleared squares can be inferred using the remaining clues.

3) repeat (2) until all the numbers are checked.

Using this method you can create a very easy sudoku puzzle with or without programming. You can also use this method to craft harder Sudoku puzzles. You may want to search "create classic sudoku" on YouTube to have a step by step example.

Saith

Answer 10

You can start with any valid (filled) puzzle and modify it to produce a completely different one (again, filled). Instead of permutating groups of numbers, you can swap single cells - there will be no similarity whatsoever between the seed puzzle and the resulting puzzle. I have written a simple program long ago in VB, you can find it here: https://www.charalampakis.com/blog/programming-vb-net/a-simple-algorithm-for-creating-sudoku-puzzles-using-visual-basic. It can be translated to any language easily.

Then, randomly and gradually remove cells and check if the puzzle is solvable and has a unique solution. You can also rate the puzzle in terms of difficulty depending on the rules needed for the solution. Continue until removing any known cell leads to an unsolvable puzzle.

HTH

Atwitter

Answer 11

I also think that you will have to explicitly check uniqueness. If you have less than 17 givens, a unique solution is very unlikely, though: None has yet been found, although it is not clear yet whether it might exist.)

But you can also use a SAT-solver, as opposed to writing an own backtracking algorithm. That way, you can to some extent regulate how difficult it will be to find a solution: If you restrict the inference rules that the SAT-solver uses, you can check whether you can solve the puzzle easily. Just google for "SAT solving sudoku".

Rattly

Answer 12

One way to generate sudoku faster.

1. find an exist sudoku.
2. exchange the value with a random group.
3. exchange the cell or the column or the row-grid or the column-grid.

You exchange the value will make the value different, if not exchange the rows or the column, the sudoku isn't changed in the essential.

You can flag the sudoku with 9 grids, the rows and column exchanged must do in the same grid. Like you can exchange row1-3, row4-6, row7-9, don't exchange row1-4 or row1-7. You can also exchange the row-grid(exchange row1~3 with the row4~6 or row7~9).

Solve the sudoku: record the empty with all the possible value, then check the value from 1 to 9. If one value is unique, remove it from the loop.

Upswing

Answer 13

You may need code like this:

#pz is a 9x9 numpy array
def PossibleValueAtPosition(pz:[], row:int, col:int):
    r=row//3*3
    c=col//3*3
    return {1,2,3,4,5,6,7,8,9}.difference(set(pz[r:r+3,c:c+3].flat)).difference(set(pz[row,:])).difference(set(pz[:,col]))

def SolvePuzzle(pz:[], n:int, Nof_solution:int):# init Nof_solution = 0
    if Nof_solution>1:
        return Nof_solution  # no need to further check
    if n>=81:
        Nof_solution+=1
        return Nof_solution
    (row,col) = divmod(n,9)
    if pz[row][col]>0:      # location filled, try next location
        Nof_solution = SolvePuzzle(pz, n+1, Nof_solution)
    else:
        l = PossibleValueAtPosition(pz, row,col)
        for v in l:         # if l = empty set, bypass all 
            pz[row][col] = v    # try to fill a possible value v  
            Nof_solution = SolvePuzzle(pz, n+1, Nof_solution)
            pz[row][col] = 0
    return Nof_solution     # resume the value, blacktrack

Rhyne

Answer 14

Quick and Dirty, but works:

import numpy as np
import math

N = 3

# rewrite of https://www.tutorialspoint.com/valid-sudoku-in-python
def isValidSudoku(M): 
    '''
    Check a sudoku matrix:
        A 9x9 sudoku matrix is valid iff every:
          row contains 1 - 9 and
          col contains 1 - 9 and
          3x3 contains 1 - 9
        0 is used for blank entry
    '''
    for i in range(9):
        row = {}
        col = {}
        block = {}
        row_cube = N * (i//N)
        col_cube = N * (i%N)
        for j in range(N*N):
            if M[i][j] != 0 and M[i][j] in row:
                return False
            row[M[i][j]] = 1
            if M[j][i] != 0 and M[j][i] in col:
                return False
            col[M[j][i]] = 1
            rc = row_cube + j//N
            cc = col_cube + j%N
            if M[rc][cc] in block and M[rc][cc] != 0:
                return False
            block[M[rc][cc]]=1
    return True
    
def generate_sudoku_puzzles(run_size, seed):  
    
    order = int(math.sqrt(run_size))
    count = 0
    valid = 0
    empty = []
    np.random.seed(seed) # for reproducible results
    
    for k in range(order):
        for l in range(order):

            A = np.fromfunction(lambda i, j: ((k*i + l+j) % (N*N)) + 1, (N*N, N*N), dtype=int)
            B = np.random.randint(2, size=(N*N, N*N))
            empty.append(np.count_nonzero(B))
            C = A*B
            count += 1

            if isValidSudoku(C):
                valid += 1
                last = C
#               print('C(',k,l,') is valid sudoku:')
#               print(C) # Uncomment for puzzle

    print('Tried', count, 'valid', valid, 'yield', round(valid/count, 3)*100, '%', 'Average Clues', round(sum(empty)/len(empty)))
    return(last)

posTest = np.array([(0, 7, 0, 0, 4, 0, 0, 6, 0), \
                    (3, 0, 0, 5, 0, 7, 0, 0, 2), \
                    (0, 0, 5, 0, 0, 0, 3, 0, 0), \
                    (0, 4, 0, 3, 0, 6, 0, 5, 0), \
                    (6, 0, 0, 0, 0, 0, 0, 0, 8), \
                    (0, 1, 0, 2, 0, 8, 0, 3, 0), \
                    (0, 0, 7, 0, 0, 0, 4, 0, 0), \
                    (1, 0, 0, 8, 0, 2, 0, 0, 9), \
                    (0, 6, 0, 0, 9, 0, 0, 1, 0), \
                    ])

negTest = np.array([(0, 7, 0, 0, 4, 0, 0, 6, 2), \
                    (3, 0, 0, 5, 0, 7, 0, 0, 2), \
                    (0, 0, 5, 0, 0, 0, 3, 0, 0), \
                    (0, 4, 0, 3, 0, 6, 0, 5, 0), \
                    (6, 0, 0, 0, 0, 0, 0, 0, 8), \
                    (0, 1, 0, 2, 0, 8, 0, 3, 0), \
                    (0, 0, 7, 0, 0, 0, 4, 0, 0), \
                    (1, 0, 0, 8, 0, 2, 0, 0, 9), \
                    (0, 6, 0, 0, 9, 0, 0, 1, 0), \
                    ])

print('Positive Quality Control Test:', isValidSudoku(posTest))
print('Negative Quality Control Test:', isValidSudoku(negTest))

print(generate_sudoku_puzzles(10000, 0))

Output:

Positive Quality Control Test: True
Negative Quality Control Test: False
Tried 10000 valid 31 yield 0.3 % Average Clues 40
[[0 0 2 3 0 0 0 7 8]
[7 8 9 1 2 0 0 0 0]
[5 0 0 0 9 0 0 3 0]
[0 0 0 6 7 8 0 0 2]
[0 2 0 0 0 0 7 8 9]
[8 0 0 2 3 0 0 0 0]
[0 0 0 0 0 2 3 0 5]
[0 5 6 0 8 9 1 2 0]
[0 3 0 5 0 0 0 9 0]]

Uncomment the two lines for puzzle source.

Larhondalari

Answer 15

Here is a SQL Server stored procedure to generate Sudoku puzzles. I still need to remove values from the completed grid.

  CREATE PROC dbo.sp_sudoku
  AS
  DROP TABLE IF EXISTS #cg

  ;
  WITH cg
    AS (          SELECT 1 AS g, 1 AS c, RAND() AS rnd
        UNION ALL SELECT 1 AS g, 2 AS c, RAND() AS rnd
        UNION ALL SELECT 1 AS g, 3 AS c, RAND() AS rnd
        UNION ALL SELECT 2 AS g, 1 AS c, RAND() AS rnd
        UNION ALL SELECT 2 AS g, 2 AS c, RAND() AS rnd
        UNION ALL SELECT 2 AS g, 3 AS c, RAND() AS rnd
        UNION ALL SELECT 3 AS g, 1 AS c, RAND() AS rnd
        UNION ALL SELECT 3 AS g, 2 AS c, RAND() AS rnd
        UNION ALL SELECT 3 AS g, 3 AS c, RAND() AS rnd)
     , cg_seq
    AS (SELECT g
             , c
             , row_number() over (partition by g
                                      order by rnd) AS n
          FROM cg)
  SELECT g
        , c + ((g - 1) * 3) AS c
        , n + ((g - 1) * 3) AS n
    INTO #cg
    FROM cg_seq

--SELECT *
--  FROM #cg
-- ORDER BY g, c

  DROP TABLE IF EXISTS #rg

  ;
  WITH rg
    AS (          SELECT 1 AS g, 1 AS r, RAND() AS rnd
        UNION ALL SELECT 1 AS g, 2 AS r, RAND() AS rnd
        UNION ALL SELECT 1 AS g, 3 AS r, RAND() AS rnd
        UNION ALL SELECT 2 AS g, 1 AS r, RAND() AS rnd
        UNION ALL SELECT 2 AS g, 2 AS r, RAND() AS rnd
        UNION ALL SELECT 2 AS g, 3 AS r, RAND() AS rnd
        UNION ALL SELECT 3 AS g, 1 AS r, RAND() AS rnd
        UNION ALL SELECT 3 AS g, 2 AS r, RAND() AS rnd
        UNION ALL SELECT 3 AS g, 3 AS r, RAND() AS rnd)
     , rg_seq
    AS (SELECT g
             , r 
             , row_number() over (partition by g
                                      order by rnd) AS n
          FROM rg)
  SELECT g
        , r + ((g - 1) * 3) AS r 
        , n + ((g - 1) * 3) AS n
    INTO #rg
    FROM rg_seq

--SELECT *
--  FROM #rg
-- ORDER BY g, r

  DROP TABLE IF EXISTS #r1

  ;
  WITH r1
    AS (          SELECT 1 AS r, 1 AS c, RAND() AS rnd
        UNION ALL SELECT 1 AS r, 2 AS c, RAND() AS rnd
        UNION ALL SELECT 1 AS r, 3 AS c, RAND() AS rnd
        UNION ALL SELECT 1 AS r, 4 AS c, RAND() AS rnd
        UNION ALL SELECT 1 AS r, 5 AS c, RAND() AS rnd
        UNION ALL SELECT 1 AS r, 6 AS c, RAND() AS rnd
        UNION ALL SELECT 1 AS r, 7 AS c, RAND() AS rnd
        UNION ALL SELECT 1 AS r, 8 AS c, RAND() AS rnd
        UNION ALL SELECT 1 AS r, 9 AS c, RAND() AS rnd)
     , r1_seq
    AS (SELECT r
             , c
             , row_number() over (order by rnd) AS n
          FROM r1)
  SELECT *
    INTO #r1
    FROM r1_seq

  DROP TABLE IF EXISTS #r_tot

  ;
  WITH r2
    AS (SELECT r + 1 AS r
             , CASE WHEN c > 6 THEN c - 6
                    ELSE            c + 3
               END AS c
             , n
          FROM #r1)
     , r3
    AS (SELECT r + 1 AS r
             , CASE WHEN c > 6 THEN c - 6
                    ELSE            c + 3
               END AS c
             , n
          FROM r2)
     , r4
    AS (SELECT r + 3 AS r
             , CASE WHEN c = 1 THEN c + 8
                    ELSE            c - 1
               END AS c
             , n
          FROM #r1)
     , r5
    AS (SELECT r + 1 AS r
             , CASE WHEN c > 6 THEN c - 6
                    ELSE            c + 3
               END AS c
             , n
          FROM r4)
     , r6
    AS (SELECT r + 1 AS r
             , CASE WHEN c > 6 THEN c - 6
                    ELSE            c + 3
               END AS c
             , n
          FROM r5)
     , r7
    AS (SELECT r + 6 AS r
             , CASE WHEN c = 1 THEN c + 7
                    WHEN c = 2 THEN c + 7
                    ELSE            c - 2
               END AS c
             , n
          FROM #r1)
     , r8
    AS (SELECT r + 1 AS r
             , CASE WHEN c > 6 THEN c - 6
                    ELSE            c + 3
               END AS c
             , n
          FROM r7)
     , r9
    AS (SELECT r + 1 AS r
             , CASE WHEN c > 6 THEN c - 6
                    ELSE            c + 3
               END AS c
             , n
          FROM r8)
     , r_tot
    AS (
            SELECT * FROM #r1
  UNION ALL SELECT * FROM r2
  UNION ALL SELECT * FROM r3
  UNION ALL SELECT * FROM r4
  UNION ALL SELECT * FROM r5
  UNION ALL SELECT * FROM r6
  UNION ALL SELECT * FROM r7
  UNION ALL SELECT * FROM r8
  UNION ALL SELECT * FROM r9
  )
    SELECT *
      INTO #r_tot
      FROM r_tot

  DROP TABLE IF EXISTS #r_tot2

  ;
  SELECT g.n AS r
       , r.c
       , r.n
    INTO #r_tot2
    FROM #r_tot r
       , #rg    g
   WHERE r.r = g.r

  DROP TABLE IF EXISTS #c_tot2

  ;
  SELECT r.r
       , g.n AS c
       , r.n
    INTO #c_tot2
    FROM #r_tot2 r
       , #cg    g
   WHERE r.c = g.c

  ;
  WITH c1 AS (SELECT r, n FROM #c_tot2 WHERE c = 1)
     , c2 AS (SELECT r, n FROM #c_tot2 WHERE c = 2)
     , c3 AS (SELECT r, n FROM #c_tot2 WHERE c = 3)
     , c4 AS (SELECT r, n FROM #c_tot2 WHERE c = 4)
     , c5 AS (SELECT r, n FROM #c_tot2 WHERE c = 5)
     , c6 AS (SELECT r, n FROM #c_tot2 WHERE c = 6)
     , c7 AS (SELECT r, n FROM #c_tot2 WHERE c = 7)
     , c8 AS (SELECT r, n FROM #c_tot2 WHERE c = 8)
     , c9 AS (SELECT r, n FROM #c_tot2 WHERE c = 9)
  SELECT c1.r
       , CAST(c1.n AS CHAR(2))
       + CAST(c2.n AS CHAR(2))
       + CAST(c3.n AS CHAR(2))
       + CAST(c4.n AS CHAR(2))
       + CAST(c5.n AS CHAR(2))
       + CAST(c6.n AS CHAR(2))
       + CAST(c7.n AS CHAR(2))
       + CAST(c8.n AS CHAR(2))
       + CAST(c9.n AS CHAR(2)) AS puzzle
    FROM c1, c2, c3, c4, c5, c6, c7, c8, c9 WHERE c1.r = c2.r AND c3.r = c2.r AND c4.r = c3.r AND c5.r = c4.r AND c6.r = c5.r AND c7.r = c6.r AND c8.r = c7.r AND c9.r = c8.r
  ORDER BY r
  
  

Epithet

Answer 16

build complete Sudoku

you can generate one place (like middle center one) with random 1-9 on complete blank matrix, look like this :

   ·  ·  ·   ·  ·  ·   ·  .  ·
   ·  .  ·   ·  .  .   .  ·  .
   .  ·  ·   .  ·  ·   ·  ·  .

   ·  .  ·   2  9  1   .  ·  .
   ·  .  ·   8  6  7   ·  ·  ·
   ·  ·  ·   3  5  4   ·  ·  ·

   ·  ·  .   ·  .  ·   .  ·  ·
   ·  ·  .   ·  ·  .   .  ·  .
   ·  .  ·   ·  ·  ·   ·  ·  ·

so you can use backtrace solve and make complete sudoku

random "dig hole" , after each "dig hole" you need verify this puzzle is one-solution

based on the complete sudoku , you can clear number of random position at it , that I'am call it "dig hole" , after each dig hole , you need to verify the puzzle and make sure is one-solution, until all dig hole done

how can verify a sudoku puzzle is one-solution ?

use dfs try to find many solution, if only one, that mean one-solution, else you can break and return

the "dig hold" count is your sudoku puzzle difficulty

in my project , four level difficulty : easy(40) / medium(45) / hard(50) / expert(56)

references

I'am write sudoku solver and generator lib with different languages, maybe you can refer to it：

• sudoku-nodejs
• sudoku-go
• sudoku-dart
• sudoku-flutter

Laminous