Ad
  • Custom User Avatar

    @Erhu, proving that sudoku has multiple solution may be done in different ways and one of them is not that time-consuming.
    Think of what it means that there are several solutions in terms of the resulting elements positions & values.

  • Custom User Avatar

    AFAIU, if you have a sudoku with zero empty (zeroed) cells, which doesn't require to be solved, it should be marked as invalid.

  • Default User Avatar

    I seem to have a problem where the program asks me to mark a grid that seems valid as invalid, like this one:

    Input:
    [4, 8, 3, 5, 7, 1, 9, 2, 6]
    [2, 7, 9, 4, 8, 6, 3, 5, 1]
    [5, 1, 6, 9, 2, 3, 8, 7, 4]
    [1, 9, 4, 3, 6, 7, 5, 8, 2]
    [3, 6, 7, 2, 5, 8, 1, 4, 9]
    [8, 2, 5, 1, 9, 4, 7, 6, 3]
    [6, 5, 1, 7, 4, 9, 2, 3, 8]
    [9, 4, 2, 8, 3, 5, 6, 1, 7]
    [7, 3, 8, 6, 1, 2, 4, 9, 5]
    --------------------------
    [[4, 8, 3, 5, 7, 1, 9, 2, 6], [2, 7, 9, 4, 8, 6, 3, 5, 1], [5, 1, 6, 9, 2, 3, 8, 7, 4], [1, 9, 4, 3, 6, 7, 5, 8, 2], [3, 6, 7, 2, 5, 8, 1, 4, 9], [8, 2, 5, 1, 9, 4, 7, 6, 3], [6, 5, 1, 7, 4, 9, 2, 3, 8], [9, 4, 2, 8, 3, 5, 6, 1, 7], [7, 3, 8, 6, 1, 2, 4, 9, 5]]
    [[4, 8, 3, 5, 7, 1, 9, 2, 6], [2, 7, 9, 4, 8, 6, 3, 5, 1], [5, 1, 6, 9, 2, 3, 8, 7, 4], [1, 9, 4, 3, 6, 7, 5, 8, 2], [3, 6, 7, 2, 5, 8, 1, 4, 9], [8, 2, 5, 1, 9, 4, 7, 6, 3], [6, 5, 1, 7, 4, 9, 2, 3, 8], [9, 4, 2, 8, 3, 5, 6, 1, 7], [7, 3, 8, 6, 1, 2, 4, 9, 5]]
    there are 1 solutions
    

    I am sure this is simple oversight on my part, as many people have solved this in Python and I don't think that everyone has made a mistake but me. Still, I can't find a reason for why this grid should be invalid. If someone could enlighten me I would be very grateful as I have been working on my solution for a week and would love to finally submit it :).

  • Custom User Avatar

    @akar-0 Thanks for the advice, the difficulty is definitly in the back tracking, but like mentioned, the test results are inconsistent and it makes it hard to debug.

  • Custom User Avatar

    I run my solution 20 times. I got 4 timeouts, and remaining 16 runs had quite comsistent times of 5-8s. So yes, it seems that its possible to get a pessimistic case, but I think the ratio is not terrible, and i also think there is many better solutions than mine.

  • Custom User Avatar

    All katas have random tests (or should have). You give no proof that tests would be buggy. If you have not been able to solve this kata (I have not either) this cannot be considered a kata issue.

    Try to practica on easier ones, 2kyu katas are supposed to be hard coding challenge.

  • Custom User Avatar

    The tests are randomly generate, you just have to get lucky and not run into bugged one.

  • Custom User Avatar

    How did others, including me, solved it then?

  • Custom User Avatar

    It could have been a good test but proving sudoku has single solution requires backtracking, which make the job time out, mainly because of the 200 random tests.

  • Custom User Avatar

    your code passes that test ("single solution"). Either that's not the problem you're facing, or you should reset the trainer.

    Closing

  • Default User Avatar

    According to your tests, this grid is invalid:

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

    Edit: OK, scratch that, apparently the problem was caused by another grid, not this one. I updated my solution to deal with those scenarios. Is there a way to delete the previous solution if it turned out to be not 100% correct?

  • Custom User Avatar

    In the "single solutions" list, there is the following problem:

    Input
    [6, 0, 0, 0, 0, 0, 0, 0, 2]
    [0, 0, 3, 6, 0, 1, 7, 0, 0]
    [0, 7, 0, 0, 4, 0, 0, 1, 0]
    [0, 5, 0, 9, 0, 4, 0, 3, 0]
    [0, 0, 9, 0, 0, 0, 1, 0, 0]
    [0, 6, 0, 7, 0, 8, 0, 2, 0]
    [0, 3, 0, 0, 6, 0, 0, 5, 0]
    [0, 0, 5, 3, 0, 9, 4, 0, 0]
    [7, 0, 0, 0, 0, 0, 0, 0, 3]

    to which my program provides the following output:

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

    And yet... it says the solution is invalid. What is going on?

  • Custom User Avatar

    Hi Kacarott, I have corrected myself in the 2nd reply; sorry about the confusion.

    As mentioned in the 2nd comment in the question, "the minimum requirement for unique solution is 17 givens" is a bit misleading.
    17 is not a condition to have multiple solutions.

  • Custom User Avatar

    Also note that over 500 people have solved this in Python, so the chance that all 500 of them made the same error as the checker in order to pass is very unlikely. I am going to close this, but you can post more evidence if you are convinced there is a problem.

  • Custom User Avatar

    The two solutions you showed in the original post are not the same, they are different. Have a look at both of them where I've marked Xs.

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

    Therefore there is no unique solution.

  • Loading more items...