10957 - So Doku Checker

[Solaris]

When I said, "Normal backtracking is enough to get AC." I meant I have got AC by using backtracking (in good time).

So I dont see any reason of your being afraid about the time complexity. As I said, the only thing you have to worry about is to cancel the illegal moves in an efficient way.

i think to find the case of "impossible" & "unique" the total tree will be generate. Isn't then a huge time required to compute???

I dont think so, whenever u put a number in one cell you are actually making a number of moves illegal for other cells. Which means that you dont have to go for all possible combinations and a big part of the search tree will be invalid.

And unfortunately I am not good enough to know any other better/easier method to solve this problem.

Best Wishes

[mrahman]

Solaris wrote

"Normal backtracking is enough to get AC."
I dont think so, whenever u put a number in one cell you are actually making a number of moves illegal for other cells. Which means that you dont have to go for all possible combinations and a big part of the search tree will be invalid.

Yes solaris is right. I also know only Backtrack solution. Is there any other approach to solve this problem?

[yukisama]

Sorry for late solaris
thanks for your advice.
But i am facing some problems>>>>
firstly, i am afraid about the time complexity in using backtracking.
2nd ly implementating backtracking is seems to be hard to me..
i think to find the case of "impossible" & "unique" the total tree will be generate. Isn't then a huge time required to compute???

pls keep posting about the problem
thanks...

the time required is acceptable if u can follow Solaris's advice.

consider the first 3 rows of a sudoku:

Code: Select all

123 456 789
456 abc 123
789 def 456

possible canadiates for the empty cells:
a,b,c : {7,8,9}
d,e,f : {1,2,3}

try all canadiates? obviously TLE could be resulted because there are too many invalid combinations (eg. a=b=c=7 d=e=f=1 is invalid) to compute

however after assigning a canadiate to a cell , the canadiates of other cells change as well:

if a = 7
canadiates of b,c : {8,9}

then lots of combinations could be elminated

hope my little advice could help u

btw, my ACed program used about 3s to do this question (for me is acceptable ).

[tmdrbs6584]

Hi logic
Bye logic

[tmdrbs6584]

Hi logic
Bye logic

[tmdrbs6584]

Hi logic
Bye logic

[tmdrbs6584]

Hi logic
Bye logic

[lonelyone]

any test cases, please

[lonelyone]

Or please someone could send your code to me for debugging
Would anyone help me.

My code was a mess, may scared everybody .
So I don't wanna post my code on the eboard.

If you could debug for me, I could send my code to you.
Thanks everyone.

[smilitude]

hi logic, bye logic?
what kindof joke is that?

[Darko]

I am trying to figure out what a "corner case" might be. I am getting the same output for that set above. What I do is - read the board, if I find an inconsistency, I declare it illegal. If it is legal, try to solve it. I am not quite sure what I might be missing (I solved 989 and 3285 using the same solver).

Any hints?

[EDIT] I removed a single line in my code and got AC. For the benefit of others - if reading a number makes a board unsolvable, it is not necessarily illegal, it is illegal only if that number is already in that row/column/square. I guess that is how illegal was defined in the problem statement, I should've read it more carefully.

[little joey]

At the time I made the testset, I could not think of any 'corner cases', so all cases are generated at random. There may be completely filled or completely empty boards in the input, but I can't see why they would be special. The obvious question is: Are you sure your output format is correct?

PM your code, if you're really desperate, but I'm sure you can solve it yourself

[Darko]

Here's an n=2 board that might qualify as a "corner case":

4 3 0 0
0 0 0 1
0 0 0 0
2 0 0 0

It is impossible to solve, because you can't put anything in the first column of the second row, which can be determined while reading the board in. But it is not illegal by the definition in the problem statement (and my WA code would say it is). So, it would break most of the generic solvers, I would think.

[little joey]

Hmm. I don't see it as a corner case. It's 'Impossible' by the definition of the problem statement (it's not illegal, but has no solution). Unless, of course, you would define 'corner case' as: not solvable by most generic solvers

[Darko]

Alright - here's the definition of a "corner case": Any case that breaks Darko's solution. :)

My problem was that I equaled "inconsistency" with "illegality".

I guess I learned that impossibility cannot easily be determined from the initial state. For some reason I was convinced that it would be the case.