How to generate 5x5 sudoku puzzle?

Question

I have written algorithm to generate 5x5 sudoku puzzles. Here is how it works. On my 5x5 sudoku there are only two contraints. There can be only item of one kind in every row and column.

1. Generate random position(0,4)

2. If position is filled go back to 1.

3. Generate random number(1,5)

4. If there is already this number in row or column go back to 3.

5. Fill position with number

6. If there are free places left go back to 1.

7. Delete random numbers.

There are two main problems.

1. This algorithm generate deadlocks so I check for tries and if there are more than 10 tries to fill position I reset EVERYTHING and try again.

2. It is too slow. Since I am desiging my sudoku for mobile devices I need to optimize it. It takes up to five seconds on my nexus 5 and up to two minutes on old samsung galaxy trend.

Answer 1

You can replace steps 1-6 by starting with a known valid filled grid, and then applying transformations to it that keep the constraints intact.

For example, you can start off with this grid, which is easy to generate by setting grid[i][j] to ((i + j) % 5) + 1:

1 2 3 4 5
2 3 4 5 1
3 4 5 1 2
4 5 1 2 3
5 1 2 3 4

Then, if you swap two rows, you will still have a valid grid, e.g. swapping rows 1 and 3:

1 2 3 4 5
4 5 1 2 3 <
3 4 5 1 2
2 3 4 5 1 <
5 1 2 3 4

You can also swap two columns and still end up with a valid grid, e.g swapping columns 2 and 4:

1 2 5 4 3
4 5 3 2 1
3 4 2 1 5
2 3 1 5 4
5 1 4 3 2
    ^   ^

So just start of with the regular grid, then inside a loop just generate pairs of random rows and pairs of random columns, and swap them. You can also swap digits, (e.g. changing all the 5s to 3s and vice versa). You will always end up with a valid result.

Then you can move on to step 7.

However, step 7 is more complicated than it seems, because you need your puzzles to be solveable. In other words at each point it should be possible for the player to logically deduce the value of at least one cell without guessing.

So you need to write a function that computes a list of the valid values for an empty cell, using the constraints (you just need a list of all values that aren't present in the same row or column). When removing the numbers in step 7, inside a loop:

• choose a random cell
• calculate the valid possible values for that cell based on the other non-empty cells in the grid
• if there is only one possible value (the value in the cell) then you can remove it

Another way that the value of a cell could be deduced is if it is the only cell in its row or column where that value is possible. To verify this you need to compute a list of valid values (values that aren't present in other non-empty cells in the same row or column) for each cell in the row or column that the cell is in, and even if the cell contains more than one possible value, if it is the only cell in its row that contains that value in its list, or the only cell in its column, then the value can be determined and so you can remove it.

You can repeat this until you have removed a desired number of cells. Because each cell that you removed was able to be deduced at the time it was removed (because it was the only possible value for the cell once the cell was empty) then the player should be able to solve the puzzle by adding the values back in the opposite order to which they were removed.

If this isn't producing "interesting" enough puzzles, then you can take the "cheat" approach, which is to have a database of existing hand-created puzzles, then choose one and scramble it by randomly swapping rows and columns, or swapping digits. This might have some copyright issues as "derivative works", but that's not a programming concern.