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

rushel
Learning poster
Posts: 67
Joined: Sat Jan 22, 2005 5:57 am

10957 - So Doku Checker

Post by rushel » Sat Oct 29, 2005 11:37 pm

Can anybody gives me hints on this problem.
A backtracking with some pruning will do or is it more of mathmatical problem.

LIBe
New poster
Posts: 6
Joined: Sat Oct 29, 2005 11:56 pm

Post by LIBe » Sun Oct 30, 2005 12:05 am

I solved it by BackTracking...

To find how many solution in inputs, it maybe works O(|blanks|^9)

Jan
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Location: Dhaka, Bangladesh
Contact:

Post by Jan » Sun Oct 30, 2005 8:26 am

At first, list the possible numbers for every position in the matrix. Then try all by recursion. Whenever you get 2 solutions you dont have to look further.

Hope it helps.
Ami ekhono shopno dekhi...
HomePage

misof
A great helper
Posts: 430
Joined: Wed Jun 09, 2004 1:31 pm

Post by misof » Sun Oct 30, 2005 8:41 am

LIBe wrote:To find how many solution in inputs, it maybe works O(|blanks|^9)
This is quite obviously false. In fact, finding the exact count of sudoku boards was quite a difficult problem and solving it took the mathematical community quite a while. As far as I know, there's still no known closed form formula for the general case (N^2 by N^2 boards).

E.g., see http://www.shef.ac.uk/%7Epm1afj/sudoku/

LIBe
New poster
Posts: 6
Joined: Sat Oct 29, 2005 11:56 pm

Post by LIBe » Sun Oct 30, 2005 3:51 pm

misof wrote:
LIBe wrote:To find how many solution in inputs, it maybe works O(|blanks|^9)
This is quite obviously false. In fact, finding the exact count of sudoku boards was quite a difficult problem and solving it took the mathematical community quite a while. As far as I know, there's still no known closed form formula for the general case (N^2 by N^2 boards).

E.g., see http://www.shef.ac.uk/%7Epm1afj/sudoku/
Ah, it's my fault :oops: you're right

Bj
New poster
Posts: 24
Joined: Mon Oct 17, 2005 1:39 am
Location: Sweden

Post by Bj » Mon Oct 31, 2005 6:35 am

I have a love-hate relationship with these problems. On one hand I have already written several so doku solvers. On the other hand I am very well aware there are some very special cases that will completely screw up my runtime, if it weren't for the constraints. God forbid someone will create a problem where you actually have to return a specific solution to the so doku puzzle, such as the one that requires the deepest recursion. ;)

User avatar
danielrocha
New poster
Posts: 44
Joined: Sun Apr 27, 2003 3:17 am
Location: Rio Grande do Norte - Brazil
Contact:

Post by danielrocha » Mon Oct 31, 2005 4:12 pm

While we're on the Sudoku topic, has any of you tried to solve the problem 3285 ( http://acmicpc-live-archive.uva.es/nuev ... php?p=3285 )? It a simple "count-how-many-different-solutions" Sudoku problem, but I can't develop an fast enough algorithm :(

Can anyone who's already solved this problem help me? Any special solving techniques? Some great backtrack prunning?
Daniel
UFRN HDD-1
Brasil

txandi
New poster
Posts: 25
Joined: Sun Feb 29, 2004 2:06 am

Post by txandi » Mon Oct 31, 2005 8:18 pm

I've also been trying the same icpc problem, and I only get TLE (lots of TLE's :cry: ). If sb find a fast algorithm please email me at txandi@gmail.com.

What I'm doing now is:
1) Fill all "sure" blanks (the ones that can only be filled with a number)
2) Sort the blanks I have to fill. The first one will be the one with less possible digits to be filled (for example, if in a column there are only two blanks, these ones will be the first ones in the list). The next one will be the one with less possible digits, assuming the previous blanks were filled... an so on...
3) Backtracking. For each blank, fill it with all the possible digits an continue. To know the possible digits of each row/column/group, i have boolean arrays that I actualize in each iteration.

I think this algorithm works fast: I'm the first on the 10957's ranklist with something a little simpler than this.

Bj
New poster
Posts: 24
Joined: Mon Oct 17, 2005 1:39 am
Location: Sweden

Post by Bj » Tue Nov 01, 2005 10:43 pm

Here are some test cases if anyone's interested. At first I posted these because I didn't know why my program failed. Now I do. :)



0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0

0 0 3 0 2 0 6 0 0
9 0 0 3 0 5 0 0 1
0 0 1 8 0 6 4 0 0
0 0 8 1 0 2 9 0 0
7 0 0 0 0 0 0 0 8
0 0 6 7 0 8 2 0 0
0 0 2 6 0 9 5 0 0
8 0 0 2 0 3 0 0 9
0 0 5 0 1 0 3 0 0

2 0 0 0 8 0 3 0 0
0 6 0 0 7 0 0 8 4
0 3 0 5 0 0 2 0 9
0 0 0 1 0 5 4 0 8
0 0 0 0 0 0 0 0 0
4 0 2 7 0 6 0 0 0
3 0 1 0 0 7 0 4 0
7 2 0 0 4 0 0 6 0
0 0 4 0 1 0 0 0 3

0 0 0 0 0 0 9 0 7
0 0 0 4 2 0 1 8 0
0 0 0 7 0 5 0 2 6
1 0 0 9 0 4 0 0 0
0 5 0 0 0 0 0 4 0
0 0 0 5 0 7 0 0 9
9 2 0 1 0 8 0 0 0
0 3 4 0 5 9 0 0 0
5 0 7 0 0 0 0 0 0

0 3 0 0 5 0 0 4 0
0 0 8 0 1 0 5 0 0
4 6 0 0 0 0 0 1 2
0 7 0 5 0 2 0 8 0
0 0 0 6 0 3 0 0 0
0 4 0 1 0 9 0 3 0
2 5 0 0 0 0 0 9 8
0 0 1 0 2 0 6 0 0
0 8 0 0 6 0 0 2 0

0 2 0 8 1 0 7 4 0
7 0 0 0 0 3 1 0 0
0 9 0 0 0 2 8 0 5
0 0 9 0 4 0 0 8 7
4 0 0 2 0 8 0 0 3
1 6 0 0 3 0 2 0 0
3 0 2 7 0 0 0 6 0
0 0 5 6 0 0 0 0 8
0 7 6 0 5 1 0 9 0

1 0 0 9 2 0 0 0 0
5 2 4 0 1 0 0 0 0
0 0 0 0 0 0 0 7 0
0 5 0 0 0 8 1 0 2
0 0 0 0 0 0 0 0 0
4 0 2 7 0 0 0 9 0
0 6 0 0 0 0 0 0 0
0 0 0 0 3 0 9 4 5
0 0 0 0 7 1 0 0 6

0 4 3 0 8 0 2 5 0
6 0 0 0 0 0 0 0 0
0 0 0 0 0 1 0 9 4
9 0 0 0 0 4 0 7 0
0 0 0 6 0 8 0 0 0
0 1 0 2 0 0 0 0 3
8 2 0 5 0 0 0 0 0
0 0 0 0 0 0 0 0 5
0 3 4 0 9 0 7 1 0

4 8 0 0 0 6 9 0 2
0 0 2 0 0 8 0 0 1
9 0 0 3 7 0 0 6 0
8 4 0 0 1 0 2 0 0
0 0 3 7 0 4 1 0 0
0 0 1 0 6 0 0 4 9
0 2 0 0 8 5 0 0 7
7 0 0 9 0 0 6 0 0
6 0 9 2 0 0 0 1 8

0 0 0 9 0 0 0 0 2
0 5 0 1 2 3 4 0 0
0 3 0 0 0 0 1 6 0
9 0 8 0 0 0 0 0 0
0 7 0 0 0 0 0 9 0
0 0 0 0 0 0 2 0 5
0 9 1 0 0 0 0 5 0
0 0 7 4 3 9 0 2 0
4 0 0 0 0 7 0 0 0

0 0 1 9 0 0 0 0 3
9 0 0 7 0 0 1 6 0
0 3 0 0 0 5 0 0 7
0 5 0 0 0 0 0 0 9

0 0 4 3 0 2 6 0 0
2 0 0 0 0 0 0 7 0
6 0 0 1 0 0 0 3 0
0 4 2 0 0 7 0 0 6
5 0 0 0 0 6 8 0 0

0 0 0 1 2 5 4 0 0
0 0 8 4 0 0 0 0 0
4 2 0 8 0 0 0 0 0
0 3 0 0 0 0 0 9 5
0 6 0 9 0 2 0 1 0
5 1 0 0 0 0 0 6 0
0 0 0 0 0 3 0 4 9
0 0 0 0 0 7 2 0 0
0 0 1 2 9 8 0 0 0

0 6 2 3 4 0 7 5 0
1 0 0 0 0 5 6 0 0
5 7 0 0 0 0 0 4 0
0 0 0 0 9 4 8 0 0
4 0 0 0 0 0 0 0 6
0 0 5 8 3 0 0 0 0
0 3 0 0 0 0 0 9 1
0 0 6 4 0 0 0 0 7
0 5 9 0 8 3 2 6 0

3 0 0 0 0 0 0 0 0
0 0 5 0 0 9 0 0 0
2 0 0 5 0 4 0 0 0
0 2 0 0 0 0 7 0 0
1 6 0 0 0 0 0 5 8
7 0 4 3 1 0 6 0 0
0 0 0 8 9 0 1 0 0
0 0 0 0 6 7 0 8 0
0 0 0 0 0 5 4 3 7

6 3 0 0 0 0 0 0 0
0 0 0 5 0 0 0 0 8
0 0 5 6 7 4 0 0 0
0 0 0 0 2 0 0 0 0
0 0 3 4 0 1 0 2 0
0 0 0 0 0 0 3 4 5
0 0 0 0 0 7 0 0 4
0 8 0 3 0 0 9 0 2
9 4 7 1 0 0 0 8 0

0 0 0 0 2 0 0 4 0
0 0 8 0 3 5 0 0 0
0 0 0 0 7 0 6 0 2
0 3 1 0 4 6 9 7 0
2 0 0 0 0 0 0 0 0
0 0 0 5 0 1 2 0 3
0 4 9 0 0 0 7 3 0
0 0 0 0 0 0 0 1 0
8 0 0 0 0 4 0 0 0

3 6 1 0 2 5 9 0 0
0 8 0 9 6 0 0 1 0
4 0 0 0 0 0 0 5 7
0 0 8 0 0 0 4 7 1
0 0 0 6 0 3 0 0 0
2 5 9 0 0 0 8 0 0
7 4 0 0 0 0 0 0 5
0 2 0 0 1 8 0 6 0
0 0 5 4 7 0 3 2 9

0 5 0 8 0 7 0 2 0
6 0 0 0 1 0 0 9 0
7 0 2 5 4 0 0 0 6
0 7 0 0 2 0 3 0 1
5 0 4 0 0 0 9 0 8
1 0 3 0 8 0 0 7 0
9 0 0 0 7 6 2 0 5
0 6 0 0 9 0 0 0 3
0 8 0 1 0 3 0 4 0

0 8 0 0 0 5 0 0 0
0 0 0 0 0 3 4 5 7
0 0 0 0 7 0 8 0 9
0 6 0 4 0 0 9 0 3
0 0 7 0 1 0 5 0 0
4 0 8 0 0 7 0 2 0
9 0 1 0 2 0 0 0 0
8 4 2 3 0 0 0 0 0
0 0 0 1 0 0 0 8 0

0 0 3 5 0 2 9 0 0
0 0 0 0 4 0 0 0 0
1 0 6 0 0 0 3 0 5
9 0 0 2 5 1 0 0 8
0 7 0 4 0 8 0 3 0
8 0 0 7 6 3 0 0 1
3 0 8 0 0 0 1 0 4
0 0 0 0 2 0 0 0 0
0 0 5 1 0 4 8 0 0

0 0 0 0 0 0 0 0 0
0 0 9 8 0 5 1 0 0
0 5 1 9 0 7 4 2 0
2 9 0 4 0 1 0 6 5
0 0 0 0 0 0 0 0 0
1 4 0 5 0 8 0 9 3
0 2 6 7 0 9 5 8 0
0 0 5 1 0 3 6 0 0
0 0 0 0 0 0 0 0 0

0 2 0 0 3 0 0 9 0
0 0 0 9 0 7 0 0 0
9 0 0 2 0 8 0 0 5
0 0 4 8 0 6 5 0 0
6 0 7 0 0 0 2 0 8
0 0 3 1 0 2 9 0 0
8 0 0 6 0 5 0 0 7
0 0 0 3 0 9 0 0 0
0 3 0 0 2 0 0 5 0

0 0 5 0 0 0 0 0 6
0 7 0 0 0 9 0 2 0
0 0 0 5 0 0 1 0 7
8 0 4 1 5 0 0 0 0
0 0 0 8 0 3 0 0 0
0 0 0 0 9 2 8 0 5
9 0 7 0 0 6 0 0 0
0 3 0 4 0 0 0 1 0
2 0 0 0 0 0 6 0 0

0 4 0 0 0 0 0 5 0
0 0 1 9 4 3 6 0 0
0 0 9 0 0 0 3 0 0
6 0 0 0 5 0 0 0 2
1 0 3 0 0 0 5 0 6
8 0 0 0 2 0 0 0 7
0 0 5 0 0 0 2 0 0
0 0 2 4 3 6 7 0 0
0 3 0 0 0 0 0 4 0

0 0 4 0 0 0 0 0 0
0 0 0 0 3 0 0 0 2
3 9 0 7 0 0 0 8 0
4 0 0 0 0 9 0 0 1
2 0 9 8 0 1 3 0 7
6 0 0 2 0 0 0 0 8
0 1 0 0 0 8 0 5 3
9 0 0 0 4 0 0 0 0
0 0 0 0 0 0 8 0 0

3 6 0 0 2 0 0 8 9
0 0 0 3 6 1 0 0 0
0 0 0 0 0 0 0 0 0
8 0 3 0 0 0 6 0 2
4 0 0 6 0 3 0 0 7
6 0 7 0 0 0 1 0 8
0 0 0 0 0 0 0 0 0
0 0 0 4 1 8 0 0 0
9 7 0 0 3 0 0 1 4

5 0 0 4 0 0 0 6 0
0 0 9 0 0 0 8 0 0
6 4 0 0 2 0 0 0 0
0 0 0 0 0 1 0 0 8
2 0 8 0 0 0 5 0 1
7 0 0 5 0 0 0 0 0
0 0 0 0 9 0 0 8 4
0 0 3 0 0 0 6 0 0
0 6 0 0 0 3 0 0 2

0 0 7 2 5 6 4 0 0
4 0 0 0 0 0 0 0 5
0 1 0 0 3 0 0 6 0
0 0 0 5 0 8 0 0 0
0 0 8 0 6 0 2 0 0
0 0 0 1 0 7 0 0 0
0 3 0 0 7 0 0 9 0
2 0 0 0 0 0 0 0 4
0 0 6 3 1 2 7 0 0

0 0 0 0 0 0 0 0 0
0 7 9 0 5 0 1 8 0
8 0 0 0 0 0 0 0 7
0 0 7 3 0 6 8 0 0
4 5 0 7 0 8 0 9 6
0 0 3 5 0 2 7 0 0
7 0 0 0 0 0 0 0 5
0 1 6 0 3 0 4 2 0
0 0 0 0 0 0 0 0 0

0 3 0 0 0 0 0 8 0
0 0 9 0 0 0 5 0 0
0 0 7 5 0 9 2 0 0
7 0 0 1 0 5 0 0 8
0 2 0 0 9 0 0 3 0
9 0 0 4 0 2 0 0 1
0 0 4 2 0 7 1 0 0
0 0 2 0 0 0 8 0 0
0 7 0 0 0 0 0 9 0

2 0 0 1 7 0 6 0 3
0 5 0 0 0 0 1 0 0
0 0 0 0 0 6 0 7 9
0 0 0 0 4 0 7 0 0
0 0 0 8 0 1 0 0 0
0 0 9 0 5 0 0 0 0
3 1 0 4 0 0 0 0 0
0 0 5 0 0 0 0 6 0
9 0 6 0 3 7 0 0 2

0 0 0 0 0 0 0 8 0
8 0 0 7 0 1 0 4 0
0 4 0 0 2 0 0 3 0
3 7 4 0 0 0 9 0 0
0 0 0 0 3 0 0 0 0
0 0 5 0 0 0 3 2 1
0 1 0 0 6 0 0 5 0
0 5 0 8 0 2 0 0 6
0 8 0 0 0 0 0 0 0

0 0 0 0 0 0 0 8 5
0 0 0 2 1 0 0 0 9
9 6 0 0 8 0 1 0 0
5 0 0 8 0 0 0 1 6
0 0 0 0 0 0 0 0 0
8 9 0 0 0 6 0 0 7
0 0 9 0 7 0 0 5 2
3 0 0 0 5 4 0 0 0
4 8 0 0 0 0 0 0 0

6 0 8 0 7 0 5 0 2
0 5 0 6 0 8 0 7 0
0 0 2 0 0 0 3 0 0
5 0 0 0 9 0 0 0 6
0 4 0 3 0 2 0 5 0
8 0 0 0 5 0 0 0 3
0 0 5 0 0 0 2 0 0
0 1 0 7 0 4 0 9 0
4 0 9 0 6 0 7 0 1

0 5 0 0 1 0 0 4 0
1 0 7 0 0 0 6 0 2
0 0 0 9 0 5 0 0 0
2 0 8 0 3 0 5 0 1
0 4 0 0 7 0 0 2 0
9 0 1 0 8 0 4 0 6
0 0 0 4 0 1 0 0 0
3 0 4 0 0 0 7 0 9
0 2 0 0 6 0 0 1 0

0 5 3 0 0 0 7 9 0
0 0 9 7 5 3 4 0 0
1 0 0 0 0 0 0 0 2
0 9 0 0 8 0 0 1 0
0 0 0 9 0 7 0 0 0

0 8 0 0 3 0 0 7 0
5 0 0 0 0 0 0 0 3
0 0 7 6 4 1 2 0 0
0 6 1 0 0 0 9 4 0

0 0 6 0 8 0 3 0 0
0 4 9 0 7 0 2 5 0
0 0 0 4 0 5 0 0 0
6 0 0 3 1 7 0 0 4
0 0 7 0 0 0 8 0 0
1 0 0 8 2 6 0 0 9
0 0 0 7 0 2 0 0 0
0 7 5 0 4 0 1 9 0
0 0 3 0 9 0 6 0 0

0 0 5 0 8 0 7 0 0
7 0 0 2 0 4 0 0 5
3 2 0 0 0 0 0 8 4
0 6 0 1 0 5 0 4 0
0 0 8 0 0 0 5 0 0
0 7 0 8 0 3 0 1 0
4 5 0 0 0 0 0 9 1
6 0 0 5 0 8 0 0 7
0 0 3 0 1 0 6 0 0

0 0 0 9 0 0 8 0 0
1 2 8 0 0 6 4 0 0
0 7 0 8 0 0 0 6 0
8 0 0 4 3 0 0 0 7
5 0 0 0 0 0 0 0 9
6 0 0 0 7 9 0 0 8
0 9 0 0 0 4 0 1 0
0 0 3 6 0 0 2 8 4
0 0 1 0 0 7 0 0 0

0 0 0 0 8 0 0 0 0
2 7 0 0 0 0 0 5 4
0 9 5 0 0 0 8 1 0
0 0 9 8 0 6 4 0 0
0 2 0 4 0 3 0 6 0
0 0 6 9 0 5 1 0 0
0 1 7 0 0 0 6 2 0
4 6 0 0 0 0 0 3 8
0 0 0 0 9 0 0 0 0

0 0 0 6 0 2 0 0 0
4 0 0 0 5 0 0 0 1
0 8 5 0 1 0 6 2 0
0 3 8 2 0 6 7 1 0
0 0 0 0 0 0 0 0 0
0 1 9 4 0 7 3 5 0
0 2 6 0 4 0 5 3 0
9 0 0 0 2 0 0 0 7
0 0 0 8 0 9 0 0 0

0 0 0 9 0 0 0 0 2
0 5 0 1 2 3 4 0 0
0 3 0 0 0 0 1 6 0
9 0 8 0 0 0 0 0 0
0 7 0 0 0 0 0 9 0
0 0 0 0 0 0 2 0 5
0 9 1 0 0 0 0 5 0
0 0 7 4 3 9 0 2 0
4 0 0 0 0 7 0 0 0

3 8 0 0 0 0 0 0 0
0 0 0 4 0 0 7 8 5
0 0 9 0 2 0 3 0 0
0 6 0 0 9 0 0 0 0
8 0 0 3 0 2 0 0 9
0 0 0 0 4 0 0 7 0
0 0 1 0 7 0 5 0 0
4 9 5 0 0 6 0 0 0
0 0 0 0 0 0 0 9 2

0 0 0 1 5 8 0 0 0
0 0 2 0 6 0 8 0 0
0 3 0 0 0 0 0 4 0
0 2 7 0 3 0 5 1 0
0 0 0 0 0 0 0 0 0
0 4 6 0 8 0 7 9 0
0 5 0 0 0 0 0 8 0
0 0 4 0 7 0 1 0 0
0 0 0 3 2 5 0 0 0

0 1 0 5 0 0 2 0 0
9 0 0 0 0 1 0 0 0
0 0 2 0 0 8 0 3 0
5 0 0 0 3 0 0 0 7
0 0 8 0 0 0 5 0 0
6 0 0 0 8 0 0 0 4
0 4 0 1 0 0 7 0 0
0 0 0 7 0 0 0 0 6
0 0 3 0 0 4 0 5 0

0 8 0 0 0 0 0 4 0
0 0 0 4 6 9 0 0 0
4 0 0 0 0 0 0 0 7
0 0 5 9 0 4 6 0 0
0 7 0 6 0 8 0 3 0
0 0 8 5 0 2 1 0 0
9 0 0 0 0 0 0 0 5
0 0 0 7 8 1 0 0 0
0 6 0 0 0 0 0 1 0

9 0 4 2 0 0 0 0 7
0 1 0 0 0 0 0 0 0
0 0 0 7 0 6 5 0 0
0 0 0 8 0 0 0 9 0
0 2 0 9 0 4 0 6 0
0 4 0 0 0 2 0 0 0
0 0 1 6 0 7 0 0 0
0 0 0 0 0 0 0 3 0
3 0 0 0 0 5 7 0 2

0 0 0 7 0 0 8 0 0
0 0 6 0 0 0 0 3 1
0 4 0 0 0 2 0 0 0
0 2 4 0 7 0 0 0 0
0 1 0 0 3 0 0 8 0
0 0 0 0 6 0 2 9 0
0 0 0 8 0 0 0 7 0
8 6 0 0 0 0 5 0 0
0 0 2 0 0 6 0 0 0

0 0 1 0 0 7 0 9 0
5 9 0 0 8 0 0 0 1
0 3 0 0 0 0 0 8 0
0 0 0 0 0 5 8 0 0
0 5 0 0 6 0 0 2 0
0 0 4 1 0 0 0 0 0
0 8 0 0 0 0 0 3 0
1 0 0 0 2 0 0 7 9
0 2 0 7 0 0 4 0 0

0 0 0 0 0 3 0 1 7
0 1 5 0 0 9 0 0 8
0 6 0 0 0 0 0 0 0
1 0 0 0 0 7 0 0 0
0 0 9 0 0 0 2 0 0
0 0 0 5 0 0 0 0 4
0 0 0 0 0 0 0 2 0
5 0 0 6 0 0 3 4 0
3 4 0 2 0 0 0 0 0

3 0 0 2 0 0 0 0 0
0 0 0 1 0 7 0 0 0
7 0 6 0 3 0 5 0 0
0 7 0 0 0 9 0 8 0
9 0 0 0 2 0 0 0 4
0 1 0 8 0 0 0 5 0
0 0 9 0 4 0 3 0 1
0 0 0 7 0 2 0 0 0
0 0 0 0 0 8 0 0 6

0 0 3 9 0 0 7 6 0
0 4 0 0 0 6 0 0 9
6 0 7 0 1 0 0 0 4
2 0 0 6 7 0 0 9 0
0 0 4 3 0 5 6 0 0
0 1 0 0 4 9 0 0 7
7 0 0 0 9 0 2 0 1
3 0 0 2 0 0 0 4 0
0 2 9 0 0 8 5 0 0

0 0 3 9 0 0 7 6 0
0 4 0 0 0 6 0 0 9
6 0 0 0 1 0 0 0 4
0 0 0 6 7 0 0 9 0
0 0 4 0 0 5 6 0 0
0 1 0 0 4 9 0 0 0
7 0 0 0 9 0 2 0 1
3 0 0 2 0 0 0 4 0
0 2 0 0 0 8 5 0 0

0 0 3 9 0 0 7 6 0
0 4 0 0 0 6 0 0 9
6 0 7 0 1 0 0 0 4
2 0 0 6 7 0 0 9 0
0 0 4 3 0 5 6 0 0
0 1 0 0 4 9 0 0 7
7 2 0 0 9 0 2 0 1
3 0 0 2 0 0 0 4 0
0 2 9 0 0 8 5 0 0

0 0 3 9 0 0 7 6 0
0 4 0 0 0 6 0 0 9
6 0 7 0 1 0 0 0 4
2 0 0 6 7 0 0 9 0
0 0 4 3 0 5 6 0 0
0 1 0 0 4 9 0 0 7
7 5 0 0 9 0 2 0 1
3 0 0 2 0 0 0 4 0
0 2 9 0 0 8 5 0 0

0 1 1 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0

0 1 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
0 0 1 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 1 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 1

0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
0 0 0 9 9 0 0 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0

0 9 0 0 0 0 0 0 0
0 9 0 0 0 0 0 0 0
0 9 0 0 0 0 0 0 0
0 9 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0

1 0 0 0 0 0 0 0 0
0 2 0 0 0 0 0 0 0
0 0 3 0 0 0 0 0 0
0 0 0 4 0 0 0 0 0
0 0 0 0 5 0 0 0 0
0 0 0 0 0 6 0 0 0
0 0 0 0 0 0 7 0 0
0 0 0 0 0 0 0 8 0
0 0 0 0 0 0 0 0 9

0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0

1 8 2 7 5 0 3 0 9
9 5 6 0 3 0 0 8 0
3 4 7 0 0 9 0 5 0
2 0 3 0 4 0 0 9 8
4 0 8 9 0 2 5 0 3
5 7 9 3 6 8 1 2 4
0 2 0 4 9 0 8 3 0
0 3 0 0 2 0 9 0 5
0 9 0 0 0 3 0 1 0

1 8 2 7 5 0 3 0 9
9 5 6 0 3 0 0 8 0
3 4 7 0 0 9 0 5 0
2 0 3 0 4 0 0 9 8
4 0 8 9 0 2 5 0 3
5 7 9 3 6 8 1 2 4
0 2 0 4 9 0 8 3 0
0 3 0 0 2 0 9 0 5
0 9 0 0 0 3 0 1 1

1 2 3 8 4 5 9 7 6
0 8 0 9 6 2 1 4 3
6 9 4 7 3 1 2 8 5
0 7 0 0 8 0 0 3 0
0 4 0 0 2 0 0 6 0
0 5 0 0 1 0 0 9 0
0 1 9 4 0 3 6 0 8
4 6 0 1 0 8 3 0 9
0 3 0 2 9 6 7 1 4



User avatar
_.B._
Experienced poster
Posts: 160
Joined: Sat Feb 07, 2004 7:50 pm
Location: Venezuela
Contact:

Me answers.

Post by _.B._ » Wed Nov 02, 2005 7:15 am

Greetings!
I'm getting plenty of WAs for this problem.
This is my output for your input:

Code: Select all

Case 1: Ambiguous.
Case 2: Unique.
Case 3: Unique.
Case 4: Unique.
Case 5: Unique.
Case 6: Unique.
Case 7: Unique.
Case 8: Unique.
Case 9: Unique.
Case 10: Unique.
Case 11: Unique.
Case 12: Unique.
Case 13: Unique.
Case 14: Unique.
Case 15: Unique.
Case 16: Unique.
Case 17: Unique.
Case 18: Unique.
Case 19: Unique.
Case 20: Unique.
Case 21: Unique.
Case 22: Unique.
Case 23: Unique.
Case 24: Unique.
Case 25: Unique.
Case 26: Unique.
Case 27: Unique.
Case 28: Unique.
Case 29: Unique.
Case 30: Unique.
Case 31: Unique.
Case 32: Unique.
Case 33: Unique.
Case 34: Unique.
Case 35: Unique.
Case 36: Unique.
Case 37: Unique.
Case 38: Unique.
Case 39: Unique.
Case 40: Unique.
Case 41: Unique.
Case 42: Unique.
Case 43: Unique.
Case 44: Unique.
Case 45: Unique.
Case 46: Unique.
Case 47: Unique.
Case 48: Unique.
Case 49: Unique.
Case 50: Unique.
Case 51: Unique.
Case 52: Unique.
Case 53: Ambiguous.
Case 54: Illegal.
Case 55: Impossible.
Case 56: Illegal.
Case 57: Illegal.
Case 58: Illegal.
Case 59: Illegal.
Case 60: Illegal.
Case 61: Ambiguous.
Case 62: Ambiguous.
Case 63: Unique.
Case 64: Illegal.
Case 65: Unique.
What is it supposed to be?

Keep posting!
_.

tywok
New poster
Posts: 32
Joined: Sun Oct 30, 2005 2:22 am

Post by tywok » Wed Nov 02, 2005 9:52 am

My ACed program outputs the same, it should be then a corner case. Post the code if you dont find it! :wink:
Impossible is nothing

User avatar
_.B._
Experienced poster
Posts: 160
Joined: Sat Feb 07, 2004 7:50 pm
Location: Venezuela
Contact:

Oke.

Post by _.B._ » Thu Nov 03, 2005 5:37 am

Thanks Tywok!
I'll work a little bit more on it then.

Keep posting!
_.

samiron
New poster
Posts: 4
Joined: Tue Sep 14, 2004 6:33 am

10957 - So Doku Checker

Post by samiron » Sat Feb 11, 2006 7:24 am

i like the game so much. Even i can play the game well but i can't solve the given problem for lack of logic about this problem :oops:

So any one pls give some idea how to proceed with this problem?????

Helping this poor logic man you can get a great piece......... :(

Finally thanks for helping(take the thanks after help....)
i am rony(nick name).i am student of cse in kuet.

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

Post by Solaris » Sat Feb 11, 2006 8:35 am

Normal backtracking is enough to get AC. Just make sure:

1. Do not fill a cell with invalid numbers.
2. Whenever u get two valid combinations, dont go for further search (As the result has already become ambiguous)

Hope it helps :)
Where's the "Any" key?

samiron
New poster
Posts: 4
Joined: Tue Sep 14, 2004 6:33 am

Post by samiron » Wed Feb 15, 2006 1:55 pm

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...
i am rony(nick name).i am student of cse in kuet.

Post Reply

Return to “Volume 109 (10900-10999)”