10957 - So Doku Checker

rushel · 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 · 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 · 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.

misof · 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 · 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

you're right

Bj · 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.

danielrocha · 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?

txandi · 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

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

_.B._ · 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 · 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!

_.B._ · 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 · 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

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

Solaris · 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

samiron · 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...

OJ Board