10957 - So Doku Checker

All about problems in Volume 109. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

Solaris
Learning poster
Posts: 99
Joined: Sun Apr 06, 2003 5:53 am
Location: Dhaka, Bangladesh
Contact:

Post by Solaris » Wed Feb 15, 2006 9:05 pm

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 :)
Where's the "Any" key?

mrahman
New poster
Posts: 25
Joined: Mon Oct 24, 2005 9:45 am
Location: Bangladesh
Contact:

Any other approach to solve this problem

Post by mrahman » Thu Feb 16, 2006 11:55 am

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?
Practice Makes a man perfect

yukisama
New poster
Posts: 2
Joined: Tue Feb 14, 2006 9:29 am

Post by yukisama » Sun Feb 19, 2006 12:38 pm

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: ).

User avatar
tmdrbs6584
Learning poster
Posts: 98
Joined: Sat Jan 21, 2006 12:45 pm
Location: Busan,Corea(Republic of)

Hi

Post by tmdrbs6584 » Tue Feb 28, 2006 10:39 am

Hi logic
Bye logic

User avatar
tmdrbs6584
Learning poster
Posts: 98
Joined: Sat Jan 21, 2006 12:45 pm
Location: Busan,Corea(Republic of)

1

Post by tmdrbs6584 » Tue Feb 28, 2006 10:39 am

Hi logic
Bye logic

User avatar
tmdrbs6584
Learning poster
Posts: 98
Joined: Sat Jan 21, 2006 12:45 pm
Location: Busan,Corea(Republic of)

2

Post by tmdrbs6584 » Tue Feb 28, 2006 10:39 am

Hi logic
Bye logic

User avatar
tmdrbs6584
Learning poster
Posts: 98
Joined: Sat Jan 21, 2006 12:45 pm
Location: Busan,Corea(Republic of)

3

Post by tmdrbs6584 » Tue Feb 28, 2006 10:39 am

Hi logic
Bye logic

lonelyone
Learning poster
Posts: 65
Joined: Sat Feb 19, 2005 6:53 pm

Post by lonelyone » Fri Mar 31, 2006 2:48 pm

any test cases, please

lonelyone
Learning poster
Posts: 65
Joined: Sat Feb 19, 2005 6:53 pm

Post by lonelyone » Sun Apr 09, 2006 4:57 pm

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.

User avatar
smilitude
Experienced poster
Posts: 137
Joined: Fri Jul 01, 2005 12:21 am

Post by smilitude » Tue Aug 01, 2006 6:46 am

hi logic, bye logic? :D
what kindof joke is that?
fahim
#include <smile.h>

Darko
Guru
Posts: 580
Joined: Fri Nov 11, 2005 9:34 am
Location: Calgary, Canada

Post by Darko » Wed May 16, 2007 11:14 pm

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.

User avatar
little joey
Guru
Posts: 1080
Joined: Thu Dec 19, 2002 7:37 pm

Post by little joey » Wed May 16, 2007 11:47 pm

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
Guru
Posts: 580
Joined: Fri Nov 11, 2005 9:34 am
Location: Calgary, Canada

Post by Darko » Thu May 17, 2007 12:23 am

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.

User avatar
little joey
Guru
Posts: 1080
Joined: Thu Dec 19, 2002 7:37 pm

Post by little joey » Thu May 17, 2007 12:33 am

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 :)
Last edited by little joey on Thu May 17, 2007 3:32 pm, edited 1 time in total.

Darko
Guru
Posts: 580
Joined: Fri Nov 11, 2005 9:34 am
Location: Calgary, Canada

Post by Darko » Thu May 17, 2007 12:41 am

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.

Post Reply

Return to “Volume 109 (10900-10999)”