CODEWITHSUNDEEP
javaperformance
user1181445
user1181445

Reputation:

Efficiency between lists and methods

I was thinking of making a Sudoku solver, I have 2 questions:

1) What would be faster?

A) Go through all the empty spots, have a list of numbers (1-9) remove them if it is in same line, or same category, then if it is length 1, add the only one remaining. Repeat this while needed.

B) Go through all the numbers, then check all the spots to see if they can have that number. Repeat this while needed.

2) What is the most efficient List for housing a list under 9 in length?

Thanks,

Legend

Upvotes: 1

Views: 84

Answers (2)

Rhiya
Rhiya

Reputation: 271

I think B works! You can use a backtracking algorithm to check the empty spot with any of the 1-9 numbers(in order). Fill the spot with first available choice(1-9) and move ahead. If at any point you are unable to insert a number into a slot then backtrack to the previous slot and try a different number. This might be helpful :

http://edwinchan.wordpress.com/2006/01/08/sudoku-solver-in-c-using-backtracking/

Upvotes: 1

Joop Eggen
Joop Eggen

Reputation: 109557

Answer 2) Not a list but a set would make sense. In this case BitSet.

Case 1) There are 27 rules in a 9x9 sudoku.

Case 1A) Every spot participates in 3 rules.

Case 1B) Every number is 9 times repeated; appears in 3 rules.

Answer 1) 1A and 1B should theoretical not be different, but 1A seems to make an algorithm & data structure easier.

Upvotes: 1

Related Questions