I would create a data-structure consisting of
- a partly filled square
- the list of numbers you need to place
Then you could use a recursive algorithm like the following:
- select an element from the number-list (*)
- select an empty position
- place the element at the position
- check, if the square is still consistent (all completely filled lines sum up to 175)
- if yes, repeat the step with the new square and the reduced number-list
- if no, restore the previous state (of number-list and square) and try with the next number and/or position
If the number-list is empty in step 1, you have found a solution.
Once you have your basic algorithm, you can optimize. E.g. your selection-algorithms and your consistency-checks.
That's when the real fun starts :-) (because you can add "intelligence" instead of pure "brute-force")
Hope this helps! Rata
(*) a basic selection-algorithm could be going from first to last.
| [reply] |
What I would do:
- If no open squares remain, you're done.
- If there's an open square that is the only open square in its row or column, goto 3. Else, goto 4.
- Pick an open square that is the only open square in its row or column. Calculate what the value should be. If the value is invalid (used already, greater than 20, less than 1, or different for the row and columns), return (from recursion, or overall -- in the latter case, it's unsolvable). If it's valid, fill in. Goto 1.
- Find a row or a column with the least number of open squares (but one that still has open squares). Pick one of its open squares. For each unused value 1 .. 20 try filling it in in the open square. Recurse.
| [reply] |