3 kyu
Hard Sudoku Solver
1,008 of 1,057Marx314
Loading description...
Algorithms
Games
Puzzles
Game Solvers
This comment has been reported as {{ abuseKindText }}.
Show
This comment has been hidden. You can view it now .
This comment can not be viewed.
- |
- Reply
- Edit
- View Solution
- Expand 1 Reply Expand {{ comments?.length }} replies
- Collapse
- Spoiler
- Remove
- Remove comment & replies
- Report
{{ fetchSolutionsError }}
-
-
Your rendered github-flavored markdown will appear here.
-
Label this discussion...
-
No Label
Keep the comment unlabeled if none of the below applies.
-
Issue
Use the issue label when reporting problems with the kata.
Be sure to explain the problem clearly and include the steps to reproduce. -
Suggestion
Use the suggestion label if you have feedback on how this kata can be improved.
-
Question
Use the question label if you have questions and/or need help solving the kata.
Don't forget to mention the language you're using, and mark as having spoiler if you include your solution.
-
No Label
- Cancel
Commenting is not allowed on this discussion
You cannot view this solution
There is no solution to show
Please sign in or sign up to leave a comment.
It was very difficult for me. I even gave up CodeWars for a year because I couldn't solve this problem in 2023. I don't like my solution because it's clumsy. But it worked! I'm glad I was able to solve this!
A year is a little extreme, but glad to see you did it!
This was a very challenging and fun kata! It required a lot of thought about which data structure and which algorithm to use to minimize the number of computations. In the end it was worth it and I managed to pass it marginally.
good for you man, im still timing out from using the backtracking approach :(
EDIT: I'm sorry, i used some code on github for the solution. Before anyone says anything, I probably shouldn't have done that, however I have spent some time reading the code, and I can fully understand it now. I think the point of codewars is to learn, but sometimes give up if it is too difficult. And for the reason why I did that, well, it's late now, so I got frustrated and just copy pasted some code off the internet.
A correctly composed Sudoku must have a unique solution !
well, this one is insane
timing out from backtrack :(
js plz
How many assertions per test? In my 100 random tests I've got 255 assertions passed but still timing out.
Its 5 per test.
Very interest Kata :) Thank you luckily i found the right method. my algorithm solved everything in 6 seconds, only on one Sudoku from your set it was required to take 1 step back. also my algorithm solved in 2 seconds "the most difficult sudoku in the world" by taking 14 steps back. I'm glad that my program coped with it!
why is backtracking alorithm not efficient enough?? wat isnt it supposed to be the solution here
It depends what exactly you mean by "backtracking algorithm", but there's "hard" in the title for a reason.
My solution does not use backtracking at all.
This comment has been hidden.
Even with a print statement at the top of your method it's impossible to debug time outs on this platform. My solution is lightning fast on my box, but of course submitting it here sends it into an infinite loop tailspin without access to the damn test suite.
Read this: https://docs.codewars.com/training/troubleshooting/#no-print
In Python:
print(expression, flush=True)This helps - thank you. But it just confirms all of the tests pass but the harness times out.
I have tried everything I could, but it always times out. I think they are just too strict on time limit in this kata.
I've tested 2 solutions and it work so I guess the code you made is a bit sub-optimal or run in loop.
This comment has been hidden.
It could be that your solution is missing an edge case, which makes it go into an infinite loop. You could test this by adding output lines (
print()orconsole.log()etc.) in each function/loop, then you should be able to see where/if there is some infinite loop.This comment has been hidden.
I'm consistently getting to 267 assertions in 100 random tests. This seems a bit surprising, since the randomness should introduce some variability in terms of how many I complete in time?
I tried putting time.sleep(0.05) into my solve() function - which should introduce enough delay over time, to make me complete a smaller number random tests. But it has no impact at all, either I get time-out straight away with no test results shown, or I get to 267. There were couple instances where I got 266 instead, but other than that it always seems to be 267.
Any thoughts? I understand that 267 might simply show how fast (or rather slow) my code is, I'm just surprised by the consistency, especially when time.sleep() gets thrown in the mix.
Hi,
Not an issue, a question. ;)
yeah, it's a bit surprising, but when it comes to deal with time out stuff, you can sometime expect then unexpectable, unfortunately... (I've already seen such a kind of behaviour myself, in the same situation)
To get you started, there are 100 random tests, with 5 assertion each, so your code seems to be 2 times slower than needed.
Good luck with increasing the speed, you're not so far away ;)
Closing.
Hi! Thanks for posting this kata.
What are the rules for determining a valid sudoko? From reading the article, it could be that each digit from 1 to 9 should appear once in each of the 9 3x3 subgrids - or maybe each row and column should also contain each digit exactly 1 time, as suggested ny the sentence "For example, the same single integer may not appear twice in the same row, column, or any of the nine 3×3 subregions of the 9×9 playing board"? Maybe there are other constraints (why else starting the sentence with 'For example'?)
Please consider including the rules in the kata description.
Hi. Great Kata, thanks ! Do we need to use numpy or is it not necessary ?
"The solution only need to give one valid solution" - which one? For example, problem case from "Fixed tests":
[[0, 8, 0, 0, 5, 0, 0, 2, 0], [6, 0, 0, 0, 0, 7, 0, 0, 5], [0, 0, 0, 2, 0, 9, 0, 0, 0], [0, 1, 7, 0, 0, 0, 9, 0, 0], [5, 0, 0, 0, 0, 0, 0, 0, 3], [0, 0, 9, 0, 0, 0, 8, 6, 0], [0, 0, 0, 8, 0, 3, 0, 0, 0], [9, 0, 0, 6, 0, 0, 0, 0, 2], [0, 5, 0, 0, 1, 0, 0, 3, 0]]
My solutions:
[[3, 8, 1, 4, 5, 6, 7, 2, 9], [6, 9, 2, 1, 8, 7, 3, 4, 5], [7, 4, 5, 2, 3, 9, 6, 1, 8], [2, 1, 7, 3, 6, 8, 9, 5, 4], [5, 6, 8, 7, 9, 4, 2, 7, 3], [4, 3, 9, 5, 2, 1, 8, 6, 1], [1, 2, 4, 8, 7, 3, 5, 9, 6], [9, 7, 3, 6, 4, 5, 1, 8, 2], [8, 5, 6, 9, 1, 2, 4, 3, 7]]
[[7, 8, 3, 4, 5, 6, 1, 2, 9], [6, 9, 2, 1, 8, 7, 3, 4, 5], [1, 4, 5, 2, 3, 9, 6, 7, 8], [8, 1, 7, 3, 6, 2, 9, 5, 4], [5, 6, 4, 7, 9, 8, 2, 1, 3], [3, 2, 9, 5, 4, 1, 8, 6, 7], [4, 7, 6, 8, 2, 3, 5, 9, 1], [9, 3, 1, 6, 7, 5, 4, 8, 2], [2, 5, 8, 9, 1, 4, 7, 3, 6]]
Each solution seems work, 487 tests passed with strategy "return first calculated solution". Ironically, all tests "Now testing multiple solution sudoku!" were passed but fails on fixed and random tests. How to decide which one should be returned to pass?
Your solution 1 isn't valid, see the middle row:
[5, 6, 8, 7, 9, 4, 2, 7, 3],there are 2 7s and no 1Yes, thats my fault, didn't notice at all :( Thank you for notice this, I think I should put some full-validation tests for my calculated solutions
How to check how many tests were passed before Time Out?
print to the console. If you're using python, use
print(..., flush=True)Passed: 304 Failed: 0 Exit Code: 1
Am I close?
100 random tests and 5 assertions per test. I let you do the maths.
Thanks buddy.
Tried lots of 'evil' task and everything going well on home computer with time less than 100 ms... but when tried to Attempt it's steady giving time out?
me too... i have no idea.
The examiner appears to keep cash between tests I fail at tables that my code resolves well
Test case are run sequentially therefore if the code produced include a global variable, you want to make sure to re-initialize each global variable at the beginning of the solve method.
I hope this clue help you.
Nice kata! But, I still need to optimize my code to avoid time out.
This comment has been hidden.
no idea since the code is unreadable... (see this)
but when I see you talking about working "without function definition", I wonder about global variables you forgot to clear from one call to the other, when you converted your code to a function (btw: global vars are evil... (unless you perfectly know what you're doing))
This comment has been hidden.
I don't understand what differences there are between your "with and without" function, in there. Only thing I can get from this now is that you have 2 different definitions of the
sudoku(puzzle)function so:oh first one was a code for no guess sudoku and the second one includes a little bit of search/guess. i improved the first one and edited my original question . the photo i attached show the not function execution...
Have enjoyed working on this! Thanks. Unfortunately my solution - a backtracking algorithm - is too slow. It gets through approx. 120 tests. Could you indicate how many tests are there in total?
Got up to 140 passes in the available time. Still not enough!
there are 100 random tests, but you see 5 assertions for each of them. So you need to reach 500 successful assertions just for the random tests. Meaning you need to change a bit your approach (the way you store your data and use them)
Python version updated with random tests.
I implemented backtracking and the given case solves fast. Are the newly added random tests OK? Can you post a couple for testing?
Ruby translation
Approved
My solution passes all tests but the last one of the multi-solution. It just says
Incorrect solution: False should equal True.When I try to do a print or sys.stdout.write to see what the board is, nothing is logged for it, so I assume you are supressing the log for the last solution? But, I get a log for the other solutions.
It's weird that my solution passes all multi-solutions except for the last one. Does the last one check all multi solutions? Or does it just check if valid?
Well, I got it using
sys.stderr.write. My solution has one zero in it. I don't know why, so I'll look at fixing my solution.This comment has been hidden.
This comment has been hidden.
I got the following test error message: ✘ You're solution shound only contains int: False should equal True Could anyone explain what happend? It can be easily checked that the solution is a valid one(if my understanding about this game is right.) The problem is [[0, 8, 0, 0, 0, 9, 7, 4, 3], [0, 5, 0, 0, 0, 8, 0, 1, 0], [0, 1, 0, 0, 0, 0, 0, 0, 0], [8, 0, 0, 0, 0, 5, 0, 0, 0], [0, 0, 0, 8, 0, 4, 0, 0, 0], [0, 0, 0, 3, 0, 0, 0, 0, 6], [0, 0, 0, 0, 0, 0, 0, 7, 0], [0, 3, 0, 5, 0, 0, 0, 8, 0], [9, 7, 2, 4, 0, 0, 0, 5, 0]]
The solution I get was: [[2, 8, 6, 1, 5, 9, 7, 4, 3], [3, 5, 4, 7, 6, 8, 9, 1, 2], [7, 1, 9, 2, 4, 3, 5, 6, 8], [8, 9, 3, 6, 1, 5, 4, 2, 7], [6, 2, 7, 8, 9, 4, 1, 3, 5], [1, 4, 5, 3, 2, 7, 8, 9, 6], [5, 6, 8, 9, 3, 1, 2, 7, 4], [4, 3, 1, 5, 7, 2, 6, 8, 9], [9, 7, 2, 4, 8, 6, 3, 5, 1]] ✘ You're solution shound only contains int: False should equal True
I'm doing the following line in the assertions:
now I don't know why you're solution isn't completly iterable but I may assume something wrong? Tell me if you find something please!
Thanks
Thank you for your information. Now I know the reason. I used numpy, so the dtype in my answer is 'numpy.int64' rather than 'int'. After I converted dtype to int, I pass the test. It seems this issue only occurs for multiple solution sudoku. Why do you check data type for multiple solution sudoku?
How have do you converted it to normal int? I'm trying to do
[[int(j) for j in result[i]] for i in range(9)]or with map() to convert from numpy to a list of ints and it's slowing down too much Edited : i've used arr.tolist() but it's still too slow ;_; guess my solution is not good enoughI justed used my solution for the "easy" sudoku. I rigged it up so it can search for multiple solutions, (in a list of solutions), but it wasn't clear to me from how the problem is stated if you are looking for that.
Hi!
Thanks for the comment, I'll change the problem description to be more explicit. I don't expect you to give every valid solution, I just expect you can give me one of the solution.
Hi Marx314,
Thanks for your reply. I thought finding all the solutions to a problem like this would be an interesting and challenging twist. I considered using a backtracking approach like n-queens, although I ended up doing something I find less confusing. But I learned the 8-queens problem had 13 distinct solutions, (not counting ones generated by symmetry). I thought that was cool.
Thanks for the kata!
Harry
Hi,
Thanks for taking the time to ask, maybe the solution given contains a string of codewars changed their version of python. I've added an assertion to make sure that solution only contains int Test.assert_equals(only_int, True, "You're solution shound only contains int")
I never thought I could do this! But after several sessions of struggle, I've done it! Thanks for the kata! :-)
"Run Suite' writes: [[7, 0, 5, 6, 2, 0, 8, 0, 0], [0, 2, 0, 8, 0, 9, 0, 7, 5], [3, 0, 8, 7, 4, 5, 0, 2, 1], [5, 3, 0, 2, 0, 6, 0, 1, 0], [0, 0, 2, 0, 0, 0, 5, 0, 0], [0, 7, 0, 5, 0, 4, 0, 6, 2], [2, 5, 0, 0, 6, 7, 0, 8, 4], [0, 8, 0, 4, 5, 2, 0, 9, 0], [0, 0, 7, 0, 0, 0, 2, 5, 0]] should equal [[7, 1, 5, 6, 2, 3, 8, 4, 9], [6, 2, 4, 8, 1, 9, 3, 7, 5], [3, 9, 8, 7, 4, 5, 6, 2, 1], [5, 3, 9, 2, 7, 6, 4, 1, 8], [4, 6, 2, 1, 9, 8, 5, 3, 7], [8, 7, 1, 5, 3, 4, 9, 6, 2], [2, 5, 3, 9, 6, 7, 1, 8, 4], [1, 8, 6, 4, 5, 2, 7, 9, 3], [9, 4, 7, 3, 8, 1, 2, 5, 6]]
but if i enter the first matrix into the program at home, it returns the second matrix, correctly. so it looks like the testing mechanism bug to me because why program which solved 20 sudokus including this one should just do nothing with input out of the sudden... am i wrong?
UPDATE: i beg pardon, the testing mechanism is right. now my problem is:
solve(problem ); solve(problem2) does not return the same mixed result as solve(problem2); solve(problem )
in both cases the solve function properly finishes the first board and do nothing with the second. that's kinda weird to me and i have a feeling i got smarter once i find out that. if anyone have a basic idea of why that's suppose to happen, i will gladly read the comments
does your function clean all your defined variable? beside that I don't see why this shouldn't work.
This comment has been hidden.
This comment has been hidden.
A sudoku game should have only one solution. In case it have more solution the function should be expected to raise an error like IndexError("Puzzle answer is not unique.").
Whoof, this one is really tough! I've just spent a few hours on it, and still all my solutions are way too slow.
Don't you want to provide some hint on practical algorithms to solve it?
I've give some hint in the description for possible algorithm to add now.
An alternative path would be to transform the puzzle into an Exact Cover problem and use Knuth's Algorithm X to quickly find a solution. A pretty understandable writeup can be found here.
In pre-set tests, the following construction is used:
Test.expect(solve(problem) == solution, "You won")that has two problems:
1.
You wonis printed if the solution is NOT correct.2. The expected and received solutions are not printed.
Please consider using
Test.assert_equals(solve(problem), solution, "Incorrect solution")instead.Hi, I've changed the pre-test and is testing the change to make sure it's working as expected.
I will also try to find a reference of an algorithme but basicly at some point you need some kind of mixe between deterministic and brute force.
Thanks!
This looks like a really, really good kata. Sad I was still unable to solve it, but I'll definitely give it more try. :) Thanks for recommendations.