2
$\begingroup$

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?

Improve this question
$\endgroup$
6
  • $\begingroup$ This questions seems more apt for something like PPCG or SO, as it's more an algorithmic question rather than a puzzle $\endgroup$
    – Wen1now
    Commented Dec 14, 2017 at 7:24
  • $\begingroup$ Can I move the question? $\endgroup$
    – qwerty_uiop
    Commented Dec 14, 2017 at 7:33
  • 4
    $\begingroup$ If you're looking for practicality, then brute force really is the way to go. It's only a 3x3 grid containing digits 1-9, and you'll be able to easily detect invalid configurations and prune really early into each configuration. Brute force is definitely the most feasible answer for a problem of this scope. $\endgroup$
    – votbear
    Commented Dec 14, 2017 at 7:33
  • $\begingroup$ @qwerty_uiop meta.stackexchange.com/questions/64068/… <- read that, I think it has the protocols for cross-site stuff $\endgroup$
    – Wen1now
    Commented Dec 14, 2017 at 7:35
  • $\begingroup$ @VotBear But I want to generalize it such that the algorithm is scalable for any grid dimension $\endgroup$
    – qwerty_uiop
    Commented Dec 14, 2017 at 7:35

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.