Logic game, 9 square cards and one large area

Question

I'm not sure if this is the right place, maybe some other batch exchange, tell me what I will send somewhere else.

Here is my problem, I found an old game in my friends place, it should be a mind game: 9 small square cards, and you should put them so that they all fit together, here is a photo:

After several hours before the game, I gathered that there was no real easy way to end the game, and so I went programmatically.

It's hard for me here, although I could just use some random functions, a big loop and get it. But there is something like (4 * 9) ^ 9 solutions, so it is not so simple.

, , : , , , , , , .

: , 8 , 9 , , , , ?

require 'json'

class Array
    def rotate n
        a =dup
        n.times do a << a.shift end
        a
    end
end


@grid = [[{"type"=>"p", "head" => 1},{"type"=>"c", "head" => 1},{"type"=>"a", "head" => 2},{"type"=>"o", "head" => 2}],
[{"type"=>"o", "head" => 1},{"type"=>"a", "head" => 2},{"type"=>"c", "head" => 2},{"type"=>"p", "head" => 1}],
[{"type"=>"c", "head" => 1},{"type"=>"p", "head" => 2},{"type"=>"o", "head" => 2},{"type"=>"a", "head" => 1}],
[{"type"=>"p", "head" => 1},{"type"=>"c", "head" => 2},{"type"=>"o", "head" => 2},{"type"=>"a", "head" => 1}],
[{"type"=>"p", "head" => 2},{"type"=>"c", "head" => 2},{"type"=>"a", "head" => 1},{"type"=>"c", "head" => 1}],
[{"type"=>"a", "head" => 1},{"type"=>"p", "head" => 2},{"type"=>"o", "head" => 2},{"type"=>"p", "head" => 1}],
[{"type"=>"a", "head" => 1},{"type"=>"o", "head" => 1},{"type"=>"a", "head" => 2},{"type"=>"c", "head" => 2}],
[{"type"=>"o", "head" => 1},{"type"=>"a", "head" => 2},{"type"=>"c", "head" => 2},{"type"=>"p", "head" => 1}],
[{"type"=>"p", "head" => 1},{"type"=>"c", "head" => 2},{"type"=>"o", "head" => 2},{"type"=>"a", "head" => 1}]]
@new_grid = [nil, nil, nil,nil, nil, nil,nil, nil, nil]
@used = [false, false, false,false, false, false,false, false, false]

def check_validity(card, position, orientation)
    # since I'm adding from top left to bottom, I only need to check top and left           
    try_card = @grid[card].rotate orientation     
    valid = true
    # top
    if (@new_grid[position-3])
        if (try_card[0]["type"] != @new_grid[position-3][2]["type"] || try_card[0]["head"] == @new_grid[position-3][2]["head"])
            valid = false
        end
    end
    # left
    if (@new_grid[position-1] && (position % 3) != 0)
        if (try_card[3]["type"] != @new_grid[position-1][1]["type"] || try_card[3]["head"] == @new_grid[position-1][1]["head"])
            valid = false       
        end
    end
    return valid
end


def solve_puzzle(position)
    (0..8).each do |card|
        unless (@used[card])
            (0..3).each do |orientation|
                if (check_validity(card, position, orientation))
                    @used[card] = true
                    @new_grid[position] = @grid[card].rotate orientation
                                        if position == 7 
                                            puts @new_grid.to_json                                      
                                        end
                    if (position < 8)
                        solve_puzzle(position + 1)
                    else
                        puts "I WON"
                        puts @new_grid.to_json
                    end
                    @new_grid[position] = nil
                    @used[card] = false
                end
            end
        end
    end
end


solve_puzzle(0)

Answer 1

. , , , . , :)

:

    void generate(int whichPos) //whichPos is from 1 to 9
    {
       for (int card = 1; card <= 9; card++)
       {
          if (used[card]) continue;

          for (int orientation = 0; orientation < 4; orientation++)
          {
              if (orientation does match other cards from 1 to whichPos - 1 in the grid)
              { 
                  used[card] = true;
                  saveInGrid();
                  generate(whichPos + 1);
                  used[card] = false;
              }       
          }  
        }
    }

    generate(1);

Answer 2

, , .

- -- , .

: , , {x1,..., x9}, x1, x2, x3 - , x4, x5, x6 - , x7, x8, x9 - .

D = {(p, r) | p - {p1, p2,..., p9}, r - {0, 90, 180, 270}}.

- x1,..., x9 D, , (.. ).

. :

• pi xj, pi ;
• xj (pi, r), xj;
• - , , ,
• - , , ;
• , backjumping, ( , , ).

- , . , , , .

, , .

!

Answer 3

, . 3 6, , .

: , :

# left
if (@new_grid[position-1] && (position % 3) != 0)
    if (try_card[3]["type"] != @new_grid[position-1][1]["type"] || try_card[3]["head"] == @new_grid[position-1][1]["head"])
        valid = false       
    end
end

2: , :

[{"type"=>"p", "head" => 2},{"type"=>"c", "head" => 2},{"type"=>"a", "head" => 1},{"type"=>"c", "head" => 2}],

, ,

[{"type"=>"p", "head" => 2},{"type"=>"c", "head" => 2},{"type"=>"a", "head" => 1},{"type"=>"c", "head" => 1}],

Answer 4

. , / / (, ).

- , , , . . , , . 3 6 9 . , :

0   1   2
3   4   5
6   7   8

, 4, 1, 3, 5, 7 , , . 4 3,5 2371 . 4, 1, 5, 2, 7, 8, 3, 0, 6, 1,2 813 , . , - , (0, 1, 3, 4, 2, 5, 6, 7, 8). , , .

Step[] Steps = {
    new Step() { Type = 0, Position = 4 },
    new Step() { Type = 1, Position = 1, MatchP1 = 4, MatchO1 = 0 },
    new Step() { Type = 1, Position = 5, MatchP1 = 4, MatchO1 = 1 },
    new Step() { Type = 2, Position = 2, MatchP1 = 5, MatchO1 = 0, MatchP2 = 1, MatchO2 = 1 },
    new Step() { Type = 1, Position = 7, MatchP1 = 4, MatchO1 = 2 },
    new Step() { Type = 2, Position = 8, MatchP1 = 7, MatchO1 = 1, MatchP2 = 5, MatchO2 = 2 },
    new Step() { Type = 1, Position = 3, MatchP1 = 4, MatchO1 = 3 },
    new Step() { Type = 2, Position = 0, MatchP1 = 1, MatchO1 = 3, MatchP2 = 3, MatchO2 = 0 },
    new Step() { Type = 2, Position = 6, MatchP1 = 3, MatchO1 = 2, MatchP2 = 7, MatchO2 = 3 },
};

, , , . 1 - , 2 - , 3 - /, 4 - . xor 0x10, , . , xor 2 0x10, , , xor 0x10, .

Card[] cards = {
    new Card(0x01, 0x03, 0x14, 0x12),
    new Card(0x02, 0x14, 0x13, 0x01),
    new Card(0x03, 0x11, 0x12, 0x04),

    new Card(0x01, 0x13, 0x12, 0x04),
    new Card(0x11, 0x13, 0x04, 0x03),
    new Card(0x04, 0x11, 0x12, 0x01),

    new Card(0x04, 0x02, 0x14, 0x13),
    new Card(0x02, 0x14, 0x13, 0x01),
//              new Card(0x01, 0x13, 0x12, 0x04) // no solution
    new Card(0x01, 0x11, 0x12, 0x04) // 4 solutions
};

, , , . NextType ( ) , :

public CardImageOrientation[][] Orientations { get; set; }

public struct CardImageOrientation
{
    public int CardIndex;
    public int TypePosition;
    public int NextType;
}

// Orientations[1] is an array of CardImageOrientation structs
// that tell me what cards contain a side with type 1, what position
// it is in, and what the next type clockwise is

:

public bool Method1Step(int stepIndex)
{
    StepCalls++;
    if (stepIndex > 8) // found a match
    {
        FindCount++;
        return !Exhaustive; // false return value will keep going if exhaustive flag is true
    }

    Step step = Steps[stepIndex];
    switch (step.Type)
    {
        case 0:
            // step 0 we just loop through all cards and try them in position 4 with orientation 0
            for (int i = 0; i < 9; i++)
            {
                PlaceCard(i, 4, 0);
                steppedUp = true;
                if (Method1Step(stepIndex + 1))
                    // found a solution, return true (will be false below for exhaustive)
                    return true;
                RemoveCard(4);
            }
            break;
        case 1:
        case 2:
            // step type 1 we simply try to match one edge with another, find card in position we are matching with
            Card card = Cards[CardIndices[step.MatchP1]];

            // to find the actual type in that position, we take the position we are looking for, subtract card orientation, add 4 and take the lowest two bits
            int type = card.Types[(step.MatchO1 - card.Orientation + 4) & 0x03];

            // find opposite orientation where we need to put the match in the empty spot
            int orientation2 = (step.MatchO1 + 2) & 0x03;

            // looking for type that is the opposite of the existing type
            int searchType = type ^ 0x10;
            for (int i = 0; i < Orientations[searchType].Length; i++)
            {
                // try one card value that matches
                CardImageOrientation cio = Orientations[searchType][i];

                // make sure it isn't in use
                if (Cards[cio.CardIndex].Position < 0)
                {
                    // check either we are step 1 or that second type matches as well
                    if (step.Type == 1 || (
                            step.Type == 2 && 
                            (Cards[CardIndices[step.MatchP2]].Types[(step.MatchO2 - Cards[CardIndices[step.MatchP2]].Orientation + 4) & 0x3] ^ cio.NextType) == 0x10)
                        ) {
                        // get new orientation for card
                        int newOrientation = (orientation2 - cio.TypePosition + 4) & 0x03;

                        PlaceCard(cio.CardIndex, step.Position, newOrientation);
                        if (Method1Step(stepIndex + 1))
                            // found solution and non-exhaustive so return true
                            return true;
                        RemoveCard(step.Position);
                    }
                }
            }
            break;
    }
    return false; // dead end or exhaustive search
}

: 4 9999 , 1 9999. , 3,465 1555 7,2 , .72 . 4,16 Method1Step().

Answer 5

, prolog , , . , , :

9 9!= 362880 ( )

4 → 4 ^ 9 = 262114

4 , , /= 4.

23 781 703 680 , : (

Answer 6

puzzle puzzle, Pentominoes Soduku.

X, . X Dancing Links.

, X ( Suduku ) , .

, , Getafix , Getafix .

X 9 , 9 4 , 324 , .

. 9 - , , . , , , , . , - 96 .

. , OP, :

• Getafix Head ()
• ()
• Asterix Feet ()
• Obelix Feet ()

• 9 (TopLeft, TopCentre,... MiddleCentre,... BottomRight)
• 9 (Piece1... Piece9)
• 96

contraint, , , , .

• : TopLeft, Piece1
• : TopLeftEast-Roman-Head, TopLeftSouth-Asterix-Feet
• : TopCentreWest-Getafix-Head, TopCentreWest-Getafix-Feet, TopCentreWest-Obelix-Head, TopCentreWest-Obelix-Feet, TopCentreWest-Asterix-Feet, TopCentreWest-Asterix-Head, TopCentreWest-Roman-Head
  ( , Roman-Feet TopCentreWest)
• : MiddleLeftNorth-Obelix-Head, MiddleLeftNorth-Obelix-Feet, MiddleLeftNorth-Getafix-Head, MiddleLeftNorth-Getafix-Feet, MiddleLeftNorth-Roman-Head, MiddleLeftNorth-Roman-Feet, MiddleLeftNorth-Asterix-Feet
  ( Asterix-Head MiddleLeftNorth)

TopLeft...

• : TopLeft, Piece1
• : TopLeftEast-Getafix-Head, TopLeftSouth-Roman-Head.

• ...

• : TopLeft, Piece1

• : TopLeftEast-Obelix-Feet, TopLeftSouth-Getafix-Head

• ...

• : TopLeft, Piece1

• : TopLeftEast-Asterix-Feet, TopLeftSouth-ObelixFeet
• ...

4 8 , 4 8 ( 32 , 36 ).

36 / 8 ( 288 ).

, , !