I'm trying to think of an algorithm that gives out all possible solutions to a japanese sums puzzle. It's not an a college assignment or anything, I'm giving puzzles to my cousin for fun, but want to be ready with all solutions in an easy way, and I got stuck at this interesting hurdle.
So Imagine a 3x3 grid. You're given the total sum of all rows and all columns. All numbers in the grid can be any number between 1 to 9, and numbers could repeat. For example, suppose you are supposed to find all possible grids which satisfy the following constraint:
(SR1,SR2,SR3,SC1,SC2,SC3) = (4,5,4,4,5,4) Let's define an array = (0,0,0,0,0,0), which denotes the current sum
I came up with a solution to this but I'm unable to figure out how would you program it. So one way to solve this, would be to assign 1 to every element at the beginning, and next time you add a number to any element, you update the above array. So right now the array would be (3,3,3,3,3,3).
So you need to go from (3,3,3,3,3,3) to (4,5,4,4,5,4), and there are multiple ways to arrive at the latter array from the former array, and hence multiple final grids. I'm only able to think of brute force ways of coming up with all solutions. Is there an elegant solution/algorithm to this?