Programming design for solving a puzzle [closed]

Question

It's difficult to tell what is being asked here. This question is ambiguous, vague, incomplete, overly broad, or rhetorical and cannot be reasonably answered in its current form. For help clarifying this question so that it can be reopened, visit the help center.

Closed 8 years ago.

Sorry if i posted this here wrong. But i sort of did not know which Stackoverflow channel should i post this and thought this is the best.

I am solving a KenKen Puzzle. It is very similar to sudoku and have some cages with a total sum and operator and we have to solve filling boxes using unique numbers.

To solve the puzzle, i would be having an input where i can get values for each cage, such as total value of the cage, operator to be used ad boxes involved.

As per my approach for solving the problem using backtracking:

1. I am parsing the input to create a class data structure for each cage.

2. Later i am creating an array of class objects for each cage.

3. Thereafter i would apply my algorithm using backtracking to solve this puzzle.

Before i start coding i just wanted to discuss with folks here, if they do think the programming approach is right or do i still need to make changes to the approach or if they would like to suggest me something to solve.

Answer 1

I think backtracking is the probably one of the best ways to solve this problem. Honestly I cannot figure out something better at the moment.

I don't know what exactly you are planning to do in your algorithm. But I suggest you should not only rely on the backtracking itself. I only read the article on wikipedia to know what KenKen is. But it seems as if it would be possible to improve the backtracking from beginning:

For backtracking you usually use a stack. So you probably have a stack with objects which tell you which number you put in which cage. Now you could give each of this stack objects a property which tells if your algorithm just chose this number from a bunch of possibilities or if your algorithm was forced to chose this number at this place because it had no other choice. So instead of such a stack:

(2,2) 5
(1,1) 4
(0,0) 1

Your stack would look like this:

(2,2) 5 CHOSEN
(1,1) 4 IMPLIED
(0,0) 1 CHOSEN

And then you have to backtrack only to the last "IMPLIED", because you cannot chose some other value here. Also, something would be IMPLIED if all other choices turned out to be wrong. I don't know how far this is possible in a KenKen. You should make sure, that a choice in the beginning cannot force your algorithm later to use IMPLIED although the number actually is not IMPLIED at this place.