Page 2 of 3

Posted: Wed Feb 15, 2006 9:05 pm
by 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.
samiron wrote: 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 :)

Any other approach to solve this problem

Posted: Thu Feb 16, 2006 11:55 am
by 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?

Posted: Sun Feb 19, 2006 12:38 pm
by yukisama
samiron wrote: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 :oops: ).

Hi

Posted: Tue Feb 28, 2006 10:39 am
by tmdrbs6584
Hi logic
Bye logic

1

Posted: Tue Feb 28, 2006 10:39 am
by tmdrbs6584
Hi logic
Bye logic

2

Posted: Tue Feb 28, 2006 10:39 am
by tmdrbs6584
Hi logic
Bye logic

3

Posted: Tue Feb 28, 2006 10:39 am
by tmdrbs6584
Hi logic
Bye logic

Posted: Fri Mar 31, 2006 2:48 pm
by lonelyone
any test cases, please

Posted: Sun Apr 09, 2006 4:57 pm
by lonelyone
Or please someone could send your code to me for debugging
Would anyone help me.

My code was a mess, may scared everybody :oops: .
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.

Posted: Tue Aug 01, 2006 6:46 am
by smilitude
hi logic, bye logic? :D
what kindof joke is that?

Posted: Wed May 16, 2007 11:14 pm
by 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.

Posted: Wed May 16, 2007 11:47 pm
by 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 :)

Posted: Thu May 17, 2007 12:23 am
by 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.

Posted: Thu May 17, 2007 12:33 am
by 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 :)

Posted: Thu May 17, 2007 12:41 am
by 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.