3
$\begingroup$

I am making a computer game sudoku.
I have a simple algorithm(more like a rule) : check rows and columns before placing a number.
But solving like that sometimes get me stuck and I want to avoid correction algorithm unless there is no choice.
here is a case :
Fill any diagonal matrices with random numbers 0-9 :
enter image description here
Now pick one matrix and by the rule fill the numbers randomly :
enter image description here
But this step has a problem as shown in picture.
How to overcome that problem ?

P.S : I need a solved sudoku in order to turn it into a question.

$\endgroup$
  • 2
    $\begingroup$ If you fill randomly you are going to have to make corrections. Period. (Not that this is always a bad way to do it... there is definitely an upper bound to how long this strategy will take, with the time to solve often being far under that - not bad for such a naive approach). How do you fix that? Remove randomness. Use an algorithm. Etc. $\endgroup$ – Brevan Ellefsen Dec 8 '16 at 18:23
  • $\begingroup$ @BrevanEllefsen at certain level there is supposed to be randomness to produce a new solved sudoku! (naive? lol I want to derive one instead of just looking up the internet, wheres the fun in that?) $\endgroup$ – Mukul Kumar Dec 8 '16 at 18:25
  • $\begingroup$ Then I fail to understand your question... You are generating a sudoku puzzle from scratch then? In that case I really do think that correction algorithms are your best bet. There are other ways to do it though... I don't have time to look up the algorithms and share, but hopefully a combination of other users and Google will suffice. $\endgroup$ – Brevan Ellefsen Dec 8 '16 at 18:27
  • $\begingroup$ @BrevanEllefsen you are saying that I am asking which I already denied ? $\endgroup$ – Mukul Kumar Dec 8 '16 at 18:29
  • 1
    $\begingroup$ Like Brevan said, not every starting set of numbers will produce a possible sudoku. Even worse is that many possible puzzles will have more than one solution. 17 numbers AT least are required to produce a unique solution. This doesn't guarantee a unique or solvable solution though. $\endgroup$ – Kaynex Dec 8 '16 at 18:29
3
$\begingroup$

Not a strong answer, but probably worth writing everything. Any sudoku with less than 17 numbers does not have a unique solution. So, randomly guessing 16 numbers will likely have at least one solution, and could be found by lots of trial and error. Computers could make this easier.

Mind you, even with 16 numbers, no solution is guaranteed, but there are multiple "paths" to check.

A sudoku with 17 or more numbers MAY have a unique solution, or MAY not have a solution. It also MAY have multiple solutions. If you want to be sure you have multiple paths to take, don't work up to 17.

$\endgroup$
  • $\begingroup$ Got it Thanks That's gonna help a lot $\endgroup$ – Mukul Kumar Dec 8 '16 at 19:00
  • $\begingroup$ How about if I fill 16 random numbers on an empty sudoku and then by using permutations I fill one value in one box at a time then when I hit the dead-end, I just permute the previous values and try again? $\endgroup$ – Mukul Kumar Dec 9 '16 at 14:18
  • $\begingroup$ @Mukul Kumar I don't really know how much trial and error it might take, but that seems like a good strategy. $\endgroup$ – Kaynex Dec 9 '16 at 14:23
  • $\begingroup$ I can minimize the time by placing the 1st 16 numbers in such a way that some empty values have only one answer. $\endgroup$ – Mukul Kumar Dec 9 '16 at 14:26
2
$\begingroup$

It seems like you are trying to construct any valid sudoku from scratch to then use for your game. If you are not willing to use a backtracking guess and check method, here's one algorithm (of many possible) that always produces a valid sudoku:

Given any 3x3 square with nine distinct elements, a 9x9 Sudoku can be constructed in exactly the way you started.

Let $L_{1}$ = \begin{array}{|c|c|c|} \hline a & b & c \\ \hline d & e & f \\ \hline g & h & i \\ \hline \end{array}

then $L_{2}$ = \begin{array}{|c|c|c|} \hline i & g & h \\ \hline c & a & b \\ \hline f & d & e \\ \hline \end{array}

and $L_{3}$ = \begin{array}{|c|c|c|} \hline e & f & d \\ \hline h & i & g \\ \hline b & c & a \\ \hline \end{array}

Note that $L_{2}$ is a diagonal shift of $L_{1}$ where the rows are shifted down once (with the bottom row wrapping around to the top) and the columns are shifted right once (with the rightmost row wrapping around to the left). The same shift on $L_{2}$ is used to produce $L_{3}$.

For a given element $l$ in $L_{i}$, let $P_{i}(l) = \big( Row_{i}(l), Col_{i}(l) \big)$.

As a result of the construction of the subsquares, $i \not= j \implies Row_{i}(l) \not=Row_{j}(l) \wedge Col_{i}(l) \not=Col_{j}(l)$

Now, make any 3x3 Latin Square out of the subsquares $L_{1}, L_{2},$ and $L_{3}$ and you're done.

The result will be very regular. You can permute the result without affecting its validity in a few ways.

  • any set of three adjacent rows or columns (1-3), (4-6), (7-9) can be swapped with another set of three adjacent rows or columns.
  • any pair of rows or pair of columns both inside of the above mentioned sets can be swapped.
  • any pair of elements can be swapped across the whole sudoku (turning all a to b and all b to a)

J. Hammer and D. Hoffman, Factor pair latin squares, Australas. J. Combin., 69(1) (2017), 41-57

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.