0

I made a program that:

  1. Generates (possibly wrong) sudoku solutions.
  2. Checks if a solution is correct
  3. If it is, prints it.
  4. If not, back to step 1.

It detects valid and invalid solutions correctly.
I never get errors.

But:

When telling the program to generate a new, random solution, until it finds a valid one, it just keeps running.

The way I generate the attempted 'solutions' is by making a list of 9 lists of 9 numbers each, each list being the numbers 1-9 mixed up, like so:

   SUDOKU_ATTEMPT = [[8, 9, 6, 3, 7, 4, 2, 5, 1],
                     [6, 3, 4, 8, 1, 9, 7, 2, 5],
                     [1, 2, 5, 6, 8, 4, 7, 3, 9],
                     [1, 2, 9, 4, 3, 7, 8, 5, 6],
                     [6, 4, 9, 2, 3, 1, 7, 8, 5],
                     [3, 1, 8, 2, 7, 4, 9, 5, 6],
                     [3, 7, 2, 8, 4, 9, 5, 6, 1],
                     [7, 2, 1, 6, 4, 5, 3, 8, 9],
                     [2, 7, 8, 9, 4, 5, 1, 3, 6]]

As you can see, rows will be correct.
But not (necessarily) columns, nor 3 x 3 boxes.

Posts I checked:

Please consider up voting. If you think this question can be improved, please suggest how.

  • Are you generating random 9x9 matrices whose each line has integers from 1 to 9, until one is a valid sudoku solution? – Right leg Dec 02 '16 at 01:20
  • I'm not sure what matrices is, but I think the answer to that is a yes. –  Dec 02 '16 at 01:21
  • You should take a look at what they are, it's like one of the most useful mathematical tools. Basically, it's a table, so a sudoku problem is naturally modeled as a matrix. If `m` is a list of lists, you access its elements by `m[i][j]`, which can be seen table-wise as "the element in the i-th row and j-th column". (EDIT: this comment was just to briefly explain what's a matrix). – Right leg Dec 02 '16 at 01:26
  • I access it just like you write. –  Dec 02 '16 at 01:27
  • For your problem: it's absolutely normal that the program runs without stopping. The chances that a random 9x9 matrix (with constraints though, but really weak) is a sudoku problem are so low. Imagine rolling a one-million-sided die until you get a 3... – Right leg Dec 02 '16 at 01:28
  • I hear you. I couldn't get it any faster.. But will it get there eventually, if I let it run, say, for a day? –  Dec 02 '16 at 01:30
  • 1
    Depending on your code, which is probably not optimized (no critics here) and of the probability a 9x9 matrix is a valid sudoku solution (which I computed three years ago and have forgotten but believe me it's low), it might take one hour, or several years. Especially if you don't record the prior generated matrices (which you cannot do, because you'd make a memory overflow). Anyway, relying only on the random is not the good solution here. – Right leg Dec 02 '16 at 01:36
  • 2
    Have a look at http://stackoverflow.com/questions/6924216/how-to-generate-sudoku-boards-with-unique-solutions/6925745#6925745 That gives you a number of options to try. – rossum Dec 02 '16 at 09:35
  • 1
    A simple and fast way to generate valid Sudoku's is to start out with a valid solution and then do some random permutations to it as described [here](http://stackoverflow.com/questions/15690254/how-to-generate-a-complete-sudoku-board-algorithm-error/15690565#15690565). – Ebbe M. Pedersen Jan 07 '17 at 22:27
  • Please consider up voting this. –  Jun 05 '17 at 02:00

2 Answers2

1

For the record, and from the discussion in comments:

You are basically generating random 9x9 matrices until one is a sudoku solution. The problem is that you use very weak constraints: integers from 1 to 9, and unique on each row.

The probability that you actually generate a valid solution is very low (it's a good math exercise to compute it!). Therefore, your code is likely to run seemingly forever, even though it logically terminates.

Relying on the randomness to this extent is not the right solution in this case.

Right leg
  • 16,080
  • 7
  • 48
  • 81
  • You can see my solution on my GitHub! Thanks for your help - and please consider up voting. –  Jun 05 '17 at 02:00
0

I had made a sudoku generator using python3. Here's the code along with a few of the rules so that it is easier to understand:

import numpy as np
import random

sudo_list = np.array(\
[[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], ])


def shuffle(m, n, t=False):
    global sudo_list
    if t:
        np.random.shuffle(np.transpose(sudo_list[:, m:n]))
    else:
        np.random.shuffle(sudo_list[m:n, :])


def sudokuGenerator():
    global sudo_list
    # Step 3: Shuffling Col 1-3
    for i in range(random.randint(5, 10)):
        shuffle(0, 3, True)
    # Step 4: Shuffling Col 4-6
    for i in range(random.randint(5, 10)):
        shuffle(3, 6, True)
    # Step 5: Shuffling Col 7-9
    for i in range(random.randint(5, 10)):
        shuffle(6, 9, True)
    # Step 6: Shuffling Row 1-3
    for i in range(random.randint(5, 10)):
        shuffle(0, 3)
    # Step 7: Shuffling Row 4-6
    for i in range(random.randint(5, 10)):
        shuffle(3, 6)
    # Step 8: Shuffling Row 7-9
    for i in range(random.randint(5, 10)):
        shuffle(6, 9)
    # Step 9: Shuffling rows in sets of 3
    rows = np.array_split(sudo_list, 3)
    for i in range(random.randint(5, 10)):
        random.shuffle(rows)
    sudo_list = np.vstack(rows)
    # Step 10: Shuffling columns in sets of 3
    col = np.array_split(sudo_list.T, 3)
    for i in range(random.randint(5, 10)):
        random.shuffle(col)
    sudo_list = np.vstack(col)

    return sudo_list

print(sudokuGenerator())
flamekiller
  • 1