How to create a 5x5 sudoku puzzle?
I wrote an algorithm for creating 5x5 Sudoku puzzles. This is how it works. There are only two contraindications in my 5x5 Sudoku. There can be only one item per row and column.
-
Create a random position (0.4)
-
If the position is full, go back to 1.
-
Generate random number (1.5)
-
If that number is already in a row or column, go back to 3.
-
Fill position with a digit
-
If there are empty seats, go back to 1.
-
Remove random numbers.
There are two main problems.
-
This algorithm generates deadlocks, so I check tries, and if there are more than 10 attempts to fill the position I reset EVERYTHING and try again.
-
It's too slow. Since I am going to Sudoku for mobile, I need to optimize it. It will take up to five seconds on my 5 link and up to two minutes on the old galactic trend.
source to share
You can replace steps 1-6 by starting with a known valid filled mesh and then applying transformations to it that keep the constraints intact.
For example, you can start with this grid, which can be easily generated 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 lines you still have a valid grid, eg. replacing lines 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 have a valid grid, like 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 with a regular grid, then inside the loop, just create pairs of random rows and pairs of random columns and replace them. You can also swap numbers (for example, change all 5s to 3s and vice versa). You will always have a valid result.
Then you can go to step 7.
However, step 7 is harder than it sounds, because you need your puzzles to solve. In other words, at each point the player should be able to logically infer the value of at least one cell without guessing.
So, you need to write a function that computes a list of valid values for an empty cell using constraints (you just need a list of all values that are missing in one row or column). When removing numbers in step 7 inside the loop:
- select a random cell
- calculate the valid possible values for this cell based on other nonblank cells in the grid
- if there is only one possible value (value in the cell) you can remove it
Another way that the value of a cell can be displayed is that it is the only cell in its row or column where this value is possible. To verify this, you need to compute a list of valid values (values that are not present in other nonblank cells in the same row or column) for every 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 therefore you can delete it.
You can repeat this until you have removed the desired number of cells. Since each deleted cell could have been inferred at the time it was deleted (since this was the only possible value for the cell after the cell was empty), then the player must solve the puzzle by adding the values back in the opposite order in which they were deleted.
If that doesn't create enough "interesting" puzzles, then you can take the "cheat" approach, which is to have a database of existing hand-crafted puzzles, then pick one and scramble it randomly by swapping rows and columns, or swapping numbers. This may have some copyright issues as "derivative works", but this is not a programming problem.
source to share