# Project Euler #96: Su Doku

# Project Euler #96: Su Doku

kitchent + 1 comment Could not pass all test cases in Python yet. Here are my techniques so far:

- Fill in cells with only one possible candidate
- Fill in the only occurrence of a particular candidate within a row, column or block
- Find preemptive set to reduce candidates for guessing
- Guess recursively and backtrack when it's contradicting

I tried with certain input such as:

`100920000 524010000 000000070 050008102 000000000 402700090 060000000 000030945 000071006`

and it takes forever. I would appreciate if someone could shed a light on me.

**EDIT**: After modifying the preemptive set method to include sets of elements, more progress can be made from deductive reasoning. Also, in each recursion level, employ every deductive techniques could reduce the guessing space significantly.The only test cases bothering me are #8 and #9. When the candidate list is not sorted by length, #9 could pass with some luck (guessed the right candidate early in the recursion), but I tend to still sort the list for more stable performance (guessing from out of is better than guessing from out of ).

**EDIT 2**: Finally passed all test cases. Two more techniques added are X-wing and block-column/row interaction. Some references which could be useful:oddRishav + 0 comments Hey, you can use the same concept which you use in Pen-Paper Sudoku like Checking the predicted no. in the same row, column, and then in the grid. Doing it recursively.

aa1992HackerRank Admin + 0 comments Finally solved it

jeekobu + 0 comments Funnest one in awhile!

Theare are number of comments about a recursive approach. I used an approach with no recursion or backtracking. If there's a way to see times in the new Hackerrank format, I don't see it, but all my local tests run in a fraction of a second.

I only needed two techniques: Cuts within a single row/column/block (e.g. if 1, 4, and 5 are only possible in 3 cells, the other 6 cells must be 2,3,6,7,8,9), and interactions between blocks and rows/columns. The techniques are applied until no further changes occur (seeing if each is necessary takes more time than just applying them).

I used bitmasks to represent possible values in a row (for example), which allows for high parallelism as well. E.g. once a cut is identified, applying it to the entire row is a &= operation.

IAmHacker1 + 0 comments which logic used for this prog

Kohua + 0 comments import java.io.

*; import java.util.*; import java.text.*; import java.math.*; import java.util.regex.*;public class Solution {

`public static void main(String[] args) { int[][] multi = new int[9][]; multi[0] = new int[9]; multi[1] = new int[9]; multi[2] = new int[9]; multi[3] = new int[9]; multi[4] = new int[9]; multi[5] = new int[9]; multi[6] = new int[9]; multi[7] = new int[9]; multi[8] = new int[9]; Scanner sc=new Scanner(System.in); for(int i=0;i<9;i++){ for(int j=0;j<9;j++){ multi[i][j] = sc.nextInt();} } for(int i=0;i<9;i++){ for(int j=0;j<9;j++){ if(multi[i][j]==0){multi[i][j]=9;} } } for(int i=0;i<multi.length;i++){ for(int j=0;j<multi[i].length;j++){ System.out.print(multi[i][j]); } System.out.println(); }/* Enter your code here. Read input from STDIN. Print output to STDOUT. Your class should be named Solution. */`

} } why is it showing runtime error...it's working fine in eclipse...please help me find the error in my code?

Megamind007 + 1 comment what concepts should i learn in order to solve these type of problems. I am not from CS and i have never come across questions like these

Kevinagin + 0 comments A good concept to know for this problem is backtracking. And a good warm-up problem for Sudoku is N-Queens.

ridsMan + 2 comments Does every test case have a unique solution? And could you kindly provide some other test case in addition to test case 0 and the one given here?

nonanon + 0 comments You can find examples of sudoku puzzles on the internet. For example, http://www.sudokuessentials.com/support-files/sudoku-easy-1.pdf gives an "easy" sudoku and its solution. I don't know if this particular example is more or less complex than required by the challenge, but my code solved it.

Crafter_Artisan + 0 comments Yeah, there's a sentence in the problem description that suggests that there could be test cases that have multiple solutions. But my code assumes a single unique solution for every test case and it worked.

varun786 + 1 comment tried recurcive soln in O(logc) yet tle

varun786 + 1 comment # include

# include

# include

# include

# include

using namespace std;

long long int count(long long int b,long long int c) { if(c==1) return b; long long int a; a=count(b,c/2); a=(a*a)%1000000000000; if((c&1)==1) a=(a*b)%1000000000000; return a; }

int main() { int t; cin>>t; while(t--) { long long int a,b,c,d,ans=1; cin>>a>>b>>c>>d;

`ans=count(b,c); ans=((ans*a)%1000000000000+d)%1000000000000; printf("%.12lld\n",ans); } return 0;`

}

varun786 + 0 comments Can anyone sort out my problem .I am not getting any idea why it is tle as at most log(10^9)=9*3.4=close to 33

Sort 28 Discussions, By:

Please Login in order to post a comment