Cross

[scriptman]

hey

i just took a quiz where i had no idea how to write this code for this type of problem

so i had this cross

--------
                  |    |   |
             -------------------
             |   |    |    |    |
             ---------------------
                 |    |    |
                 ---------

sry for the wierd shape..but is a cross.n we had to put numbers in it so that no two number are adjacent to it horiztonally, vertically, or diagonally

ex..

       3 5
     7 1 8 2
       4 6

any clue on how to write this code using backtracking..thanks

[twanvl]

Do you have to use every number from [1..8] exactly once? Otherwise a solution is trivial, any permutation of [1..8] is ok.
From now on I'll assume there are some more restrictions.

A naive solution could consist of the following:

• a representation of a partially filled in puzzle, you could use an array of length 8 for this (listing the numbers from left to right, top to bottom). You could use 0 for fields that are not yet filled in.
• a function "bool allowed(Puzzle p);" that checks whether p is a valid solution (no adjacent numbers that are the same, except 0 which represents an empty field), and no duplicates, whatever the constraints are...
• a function "void move(Puzzle& p);" that takes the first clear (0) field and sets it to, for example, 1.
• a function "void next(Puzzle& p);" that takes the last (nonzero) field and increments it. If it is already the maximum value, clear it (set it to zero) and repeat.
• the main function starts with an empty puzzle, and then:
  
  • calls: move(p), filling in one more field
  • calls: while (!allowed(p)) next(p), ending up in a valid (partial) solution.
  • repeat until puzzle is completely filled

The division into functions is quite arbitrary, you could all lump it into one big function if you like.

Note also that there are smarter ways to solve such puzzles, the best way is (probably) to for each cell have a list (stored as a set/bit field/whatever) of which values are still possible in that field. If there is only one possibility in a field then write that value there. Now repeatedly cross out that value in adjacent fields. If this stops before you find a solution, fall back to backtracking.

[wossname]

For a much larger grid you could use genetic algorithms. The benefit of this would be that the time required to solve would increase slowly for large changes in grid size. There might be less scope for backtracking though.