## 10957 - So Doku Checker

Moderator: Board moderators

Solaris
Learning poster
Posts: 99
Joined: Sun Apr 06, 2003 5:53 am
Contact:
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
Contact:

### Any other approach to solve this problem

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
samiron wrote:Sorry for late solaris
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...

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

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
Learning poster
Posts: 98
Joined: Sat Jan 21, 2006 12:45 pm
Location: Busan,Corea(Republic of)

### Hi

Hi logic
Bye logic

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

### 1

Hi logic
Bye logic

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

### 2

Hi logic
Bye logic

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

### 3

Hi logic
Bye logic

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

lonelyone
Learning poster
Posts: 65
Joined: Sat Feb 19, 2005 6:53 pm
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
Experienced poster
Posts: 137
Joined: Fri Jul 01, 2005 12:21 am
hi logic, bye logic?
what kindof joke is that?
fahim
#include <smile.h>

Darko
Guru
Posts: 580
Joined: Fri Nov 11, 2005 9:34 am
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
Guru
Posts: 1080
Joined: Thu Dec 19, 2002 7:37 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
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
Guru
Posts: 1080
Joined: Thu Dec 19, 2002 7:37 pm
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