Shikaku - hrátky s obdélníčky

28. 1. 2022 0:00 Jiří Raška

Shikaku je jedna z japonských logických her, kterou publikoval časopis Nikoli. Jako obvykle se jedná o deskovou hru, kterou je možné hrát na čtvercové nebo obdélníkové desce.

Úkolem je rozdělit desku na obdélníky, které jí plně pokrývají a vzájemně se nepřekrývají. Každý obdélník je určen jednou pozicí na desce s číslem udávajícím jeho plochu ve čtvercích. V zadání úlohy je tedy na desce tolik čísel, kolik je požadovaných obdélníků. Součet čísel pak představuje plochu celé desky.

Například zadání by mohlo vypadat následovně:

 ---------------
|   |   |   | 4 |
 ---------------
|   | 8 |   |   |
 ---------------
|   |   | 4 |   |
 ---------------
|   |   |   |   |
 ---------------

Pokusil jsem se tedy napsat řešení pro takovou hru. Nejdříve pomocí backtracking a následně také Constraint Programming. Třeba příjdete na nějaké jiné řešení.

Zdroj testovacích dat

Protože budu zkoušet dva postupy, vytvořil jsem si nejdříve jeden společný zdroj testovacích dat. Je to jedna třída DataSource v samostatném modulu. Ta obsahuje několik zadání hry a metody, jak s nimi jednoduše pracovat.

Jednodušší bude asi ukázka, jak s tím zdrojem testovacích vzorků pracuji:

In [1]:

						import numpy as np
from ShikakuSource import DataSource

source = DataSource()
					

Počet vzorků zadání hry ve zdroji:

In [2]:

						print(len(source))
					

Rozměry hrací desky pro jedem vzorek s pořadovým číslem 1:

In [3]:

						print(source.shape(1))
					

(4, 4)

Zadání pro jeden vzorek ve formě pole (pořadové číslo 1):

In [4]:

						print(source.board(1))
					

[[0 0 0 4]
 [0 8 0 0]
 [0 0 4 0]
 [0 0 0 0]]

Zdrojová data vzorku s pořadovým číslem 1, jedná se o souřadnice na desce a hodnotu políčka:

In [5]:

						print(source.data(1))
					

[((0, 3), 4), ((1, 1), 8), ((2, 2), 4)]

Řešení s pomocí backtracking

Nejdříve se pokusím na to jít tak, jak by asi každý očekával. Prostě budu zkoušet kombinace obdélníků, dokud nenajdu přijatelné řešení.

Přípravné práce

Bude asi dobré si připravit nějaké nástroje pro práci s obdélníky. Proto jsem si vytvořil jednu třídu Rectangle a nějaké pomocné funkce pro práci s nimi.

In [6]:

						class Rectangle:

    def __init__(self, corner, shape, board_shape):
        if not all((0 <= corner[i] < board_shape[0] and 0 < shape[i] <= board_shape[i] for i in (0, 1))):
            raise ValueError('coordinates are invalid')
        if not all((0 <= corner[i] + shape[i] <= board_shape[i] for i in (0, 1))):
            raise ValueError('coordinates are invalid')
        self.corner, self.shape, self.board_shape = corner, shape, board_shape

    def __iter__(self):
        yield self.corner
        yield self.shape

    def __eq__(self, other):
        return isinstance(other, type(self)) and tuple(self) == tuple(other)

    def __ne__(self, other):
        return not (self == other)

    def __lt__(self, other):
        return tuple(self) < tuple(other)

    def __repr__(self):
        return type(self).__name__ + repr(tuple(self))

    def inside(self, position):
        return all((self.corner[i] <= position[i] < self.corner[i] + self.shape[i] for i in (0, 1)))

    def slice(self):
        return tuple((slice(self.corner[i], self.corner[i] + self.shape[i]) for i in (0, 1)))

    def board(self):
        b = np.zeros(self.board_shape, dtype=int)
        b[slice()] = 1
        return b
					

Nejdříve funkce pro výpočet rozměrů obdélníků tak, aby měly požadovanou plochu.

Parametrem je kromě plochy obdélníka také velikost hrací desky, neb nechci řešit obdélníky, které by se mně na desku vůbec nevešly.

In [7]:

						def dimensions_for_area(area, board_shape):
    for i in range(1, area + 1):
        if area % i == 0:
            rows, cols = i, area // i
            if rows <= board_shape[0] and cols <= board_shape[0]:
                yield rows, cols

print(list(dimensions_for_area(8, (4, 4))))
					

[(2, 4), (4, 2)]

Úkolem další funkce bude najít všechny přijatelné obdélníky pro konkrétní pozici na desce tak, aby obdélníky měly požadované rozměry a na desku se vešly.

Parametry funkce jsou:

pozice na desce, vůči které se obdélníky vztahují (každý obdélník musí tuto ozici obsahovat)
požadované rozměry obdélníku
velikost hrací desky

Výsledkem je generátor takových obdélníků.

In [8]:

						def rectangles_for_position(position, shape, board_shape):
    for i in (a for a in range(max(position[0] - (shape[0] - 1), 0), position[0] + 1) if a + shape[0] <= board_shape[0]):
        for j in (b for b in range(max(position[1] - (shape[1] - 1), 0), position[1] + 1) if b + shape[1] <= board_shape[1]):
            yield Rectangle((i, j), shape, board_shape)

print(list(rectangles_for_position((2, 2), (1, 4), (4, 4))))
print(list(rectangles_for_position((2, 2), (4, 1), (4, 4))))
					

[Rectangle((2, 0), (1, 4))]
[Rectangle((0, 2), (4, 1))]

Spojením dvou výše uvedených funkci jsem nyní schopen napsat funkci, která mně vrátí všechny přijatelné obdélníky pro pozici s uvedením požadované plochy

Parametry funkce:

pozice na desce, vůči které se obdélníky vztahují
požadovaná plocha obdélníku
velikost hrací desky

Výsledkem je opět generátor obdélníků, které vyhovují požadavkům.

In [9]:

						def all_for_position(position, area, board_shape):
    for shape in dimensions_for_area(area, board_shape):
        for rect in rectangles_for_position(position, shape, board_shape):
            yield rect

print(list(all_for_position((2, 2), 4, (4, 4))))
					

[Rectangle((2, 0), (1, 4)), Rectangle((1, 1), (2, 2)), Rectangle((1, 2), (2, 2)), Rectangle((2, 1), (2, 2)), Rectangle((2, 2), (2, 2)), Rectangle((0, 2), (4, 1))]

Poslední funkcí z této části bude funkce, která mně ze všech obdélníků přijatelných pro jednu pozici vybere pouze ty obdélníky, které neobsahují pozice jiných obdélníků (to je to pravidlo, že pozice s číslem může ležet pouze v jednom obdélníku).

Parametry funkce:

pozice na desce, vůči které se obdélníky vztahují
požadovaná plocha obdélníku
zdrojová data pro jedno zadání hry
velikost hrací desky

Výsledkem je generátor takových obdélníků.

In [10]:

						def possible_for_position(position, area, data, board_shape):
    for rect in all_for_position(position, area, board_shape):
        if all((not rect.inside(p) for p, v in data if p != position)):
            yield rect

print(list(possible_for_position((2, 2), 4, source.data(1), (4, 4))))
					

[Rectangle((2, 0), (1, 4)), Rectangle((1, 2), (2, 2)), Rectangle((2, 1), (2, 2)), Rectangle((2, 2), (2, 2)), Rectangle((0, 2), (4, 1))]

Řešení

A nyní již vlastní řešení pomocí backtrack.

Pro vyhodnocení, zda se mně obdélníky překrývají, budu používat numpy pole.

Budu postupně procházet všechna zadání. Pro každé zadání pak:

nejdříve vytisknu zadání
vytvořím si prázdnou desku
pro každou pozici zadání vytvořím seznam všech přijatelných obdélniků
spustím funkci solve(), která:

postupně prochází všechny přijatelné obdélníky pro pozici
obdélník promitne na desku
pokud na desce není konflik, pokračuje rekurzivně na další pozici

v případě, že jsem nějaké řešení našel, tak jej vytisknu

Výsledek uvidíte po spuštění:

In [11]:

						for sample in range(len(source)):
    print(source.board(sample))
    print('.' * 40)

    board = np.zeros(source.shape(sample), dtype=int)

    possible_rectangles = []
    for pos, val in source.data(sample):
        possible_rectangles.append(list(possible_for_position(pos, val, source.data(sample), source.shape(sample))))

    def solve(index=0):
        if index >= len(possible_rectangles):
            return True, []
        for rec in possible_rectangles[index]:
            board[rec.slice()] += 1
            if (board <= 1).all():
                ok, result = solve(index + 1)
                if ok:
                    result.insert(0, rec)
                    return True, result
            board[rec.slice()] -= 1
        else:
            return False, None

    ok, result = solve()
    if ok:
        b = np.zeros(source.shape(sample), dtype=int)
        for val, rec in enumerate(result):
            b[rec.slice()] += 1
        if (b == 1).all():
            b = np.zeros(source.shape(sample), dtype=object)
            for val, rec in enumerate(result):
                b[rec.slice()] = chr(ord('A') + val)
            print(b)
        else:
            print("SOLUTION IS NOT VALID")

        print()
        print('=' * 40)
        print()
					

[[0 2]
 [2 0]]
........................................
[['A' 'A']
 ['B' 'B']]

========================================

[[0 0 0 4]
 [0 8 0 0]
 [0 0 4 0]
 [0 0 0 0]]
........................................
[['B' 'B' 'A' 'A']
 ['B' 'B' 'A' 'A']
 ['B' 'B' 'C' 'C']
 ['B' 'B' 'C' 'C']]

========================================

[[2 0 0 0 0]
 [0 0 2 0 4]
 [0 0 3 2 0]
 [0 4 0 2 0]
 [4 0 0 2 0]]
........................................
[['A' 'A' 'B' 'C' 'C']
 ['H' 'F' 'B' 'C' 'C']
 ['H' 'F' 'D' 'E' 'E']
 ['H' 'F' 'D' 'G' 'G']
 ['H' 'F' 'D' 'I' 'I']]

========================================

[[0 0 2 0 0]
 [5 2 0 0 0]
 [0 3 2 0 0]
 [0 0 0 3 4]
 [0 0 2 0 2]]
........................................
[['B' 'C' 'A' 'A' 'G']
 ['B' 'C' 'E' 'F' 'G']
 ['B' 'D' 'E' 'F' 'G']
 ['B' 'D' 'H' 'F' 'G']
 ['B' 'D' 'H' 'I' 'I']]

========================================

[[0 0 0 0 0 0 6]
 [2 0 0 3 0 0 0]
 [0 3 0 0 0 6 0]
 [0 0 0 0 0 3 0]
 [3 6 0 0 0 3 0]
 [0 5 0 0 0 2 0]
 [2 0 0 0 3 2 0]]
........................................
[['B' 'A' 'A' 'A' 'A' 'A' 'A']
 ['B' 'C' 'C' 'C' 'E' 'E' 'E']
 ['G' 'D' 'D' 'D' 'E' 'E' 'E']
 ['G' 'H' 'H' 'H' 'F' 'F' 'F']
 ['G' 'H' 'H' 'H' 'I' 'I' 'I']
 ['J' 'J' 'J' 'J' 'J' 'K' 'K']
 ['L' 'L' 'M' 'M' 'M' 'N' 'N']]

========================================

[[0 0 3 0 2 0 0]
 [0 0 5 0 0 0 0]
 [0 3 0 0 0 0 0]
 [0 2 0 4 4 0 4]
 [0 0 2 0 0 0 2]
 [2 2 2 0 0 6 0]
 [0 2 0 0 2 2 0]]
........................................
[['A' 'A' 'A' 'B' 'B' 'N' 'H']
 ['C' 'C' 'C' 'C' 'C' 'N' 'H']
 ['D' 'D' 'D' 'F' 'G' 'N' 'H']
 ['E' 'E' 'I' 'F' 'G' 'N' 'H']
 ['K' 'L' 'I' 'F' 'G' 'N' 'J']
 ['K' 'L' 'M' 'F' 'G' 'N' 'J']
 ['O' 'O' 'M' 'P' 'P' 'Q' 'Q']]

========================================

[[ 0  0  0  4  0  0  2  0  0  0]
 [ 3  0  0  2  0  0  6  0  4  0]
 [ 0  4  0  0  0  0  0  0  4  8]
 [ 0  0  4  0 15  0  0  0  0  0]
 [ 2  0  0  0  0  0  0  2  0  0]
 [ 0  0  0  0  0  0  0  0  0  0]
 [ 4  0 12  0  0  0  0  0  0  0]
 [ 0  0  0  0  0  0  0  0  3  0]
 [ 0  2  0  0  5  0  0  4  2  0]
 [ 0  0  2  0  0  0  6  0  0  0]]
........................................
[['C' 'A' 'A' 'A' 'A' 'B' 'B' 'F' 'F' 'I']
 ['C' 'G' 'G' 'D' 'E' 'E' 'E' 'F' 'F' 'I']
 ['C' 'G' 'G' 'D' 'E' 'E' 'E' 'H' 'H' 'I']
 ['J' 'J' 'J' 'J' 'K' 'K' 'K' 'H' 'H' 'I']
 ['L' 'O' 'O' 'O' 'K' 'K' 'K' 'M' 'M' 'I']
 ['L' 'O' 'O' 'O' 'K' 'K' 'K' 'S' 'P' 'I']
 ['N' 'O' 'O' 'O' 'K' 'K' 'K' 'S' 'P' 'I']
 ['N' 'O' 'O' 'O' 'K' 'K' 'K' 'S' 'P' 'I']
 ['N' 'Q' 'R' 'R' 'R' 'R' 'R' 'S' 'T' 'T']
 ['N' 'Q' 'U' 'U' 'V' 'V' 'V' 'V' 'V' 'V']]

========================================

[[ 0  0  4  0  0  0  2  6  0  0]
 [ 0  0  0  0  0  5  0  0  0  0]
 [ 0  0  2  0  3  0  3  0  0  0]
 [ 0  0  0  0  0  0  0  2  4  0]
 [ 9  0  0  0  0  0  0  0  0  0]
 [ 0  0  0 12  0  0  0  0  9  0]
 [ 0  4  0  0  0  0  0  0  0  3]
 [ 0  0  0 12  0  0  0  0  0  0]
 [ 0  2  0  0  0  0  4  0  4  0]
 [ 0  0  0  7  0  0  0  0  3  0]]
........................................
[['J' 'A' 'A' 'A' 'A' 'B' 'B' 'C' 'C' 'C']
 ['J' 'D' 'D' 'D' 'D' 'D' 'G' 'C' 'C' 'C']
 ['J' 'E' 'E' 'F' 'F' 'F' 'G' 'H' 'I' 'I']
 ['J' 'M' 'K' 'K' 'K' 'K' 'G' 'H' 'I' 'I']
 ['J' 'M' 'K' 'K' 'K' 'K' 'L' 'L' 'L' 'N']
 ['J' 'M' 'K' 'K' 'K' 'K' 'L' 'L' 'L' 'N']
 ['J' 'M' 'O' 'O' 'O' 'O' 'L' 'L' 'L' 'N']
 ['J' 'P' 'O' 'O' 'O' 'O' 'Q' 'Q' 'R' 'R']
 ['J' 'P' 'O' 'O' 'O' 'O' 'Q' 'Q' 'R' 'R']
 ['S' 'S' 'S' 'S' 'S' 'S' 'S' 'T' 'T' 'T']]

========================================

Řešení s využitím OR-Tools

Jako základ celého řešení je vytvoření modelu hry s využitím připravených nástrojů z knihovny OR-Tools.

In [12]:

						from ortools.sat.python import cp_model
					

Tímto modelem je třída, která je potomkem třídy CpSolverSolutionCallback.

Vlastní nastavení modelu se děje v metodě __init__.

In [13]:

						class GameBoard(cp_model.CpSolverSolutionCallback):

    def __init__(self, data, board_shape):
        cp_model.CpSolverSolutionCallback.__init__(self)
        self.model = cp_model.CpModel()

        self.shape = board_shape
        self.rectangles = []
        intervals_x, intervals_y = [], []

        for i, ((x, y), val) in enumerate(data):
            x1, y1 = self.model.NewIntVar(0, x, f"X1:{i}"), self.model.NewIntVar(0, y, f"Y1:{i}")
            x2, y2 = self.model.NewIntVar(x, board_shape[0] - 1, f"X2:{i}"), self.model.NewIntVar(y, board_shape[1] - 1, f"Y2:{i}")
            self.rectangles.append((x1, y1, x2, y2))

            size_x = self.model.NewIntVar(1, board_shape[0], f"dimX:{i}")
            size_y = self.model.NewIntVar(1, board_shape[1], f"dimY:{i}")

            self.model.Add(x1 + size_x <= board_shape[0])
            self.model.Add(y1 + size_y <= board_shape[1])

            self.model.Add(x1 + size_x > x)
            self.model.Add(y1 + size_y > y)

            self.model.AddMultiplicationEquality(val, [size_x, size_y])

            intervals_x.append(self.model.NewIntervalVar(x1, size_x, x2 + 1, f"IX:{i}"))
            intervals_y.append(self.model.NewIntervalVar(y1, size_y, y2 + 1, f"IY:{i}"))

        self.model.AddNoOverlap2D(intervals_x, intervals_y)

    def OnSolutionCallback(self):
        a = np.zeros(self.shape, dtype=object)
        for i, (x1, y1, x2, y2) in enumerate(self.rectangles):
            x1, y1, x2, y2 = self.Value(x1), self.Value(y1), self.Value(x2), self.Value(y2)
            a[x1:x2+1, y1:y2+1] = chr(ord('A') + i)
        print(a)
        self.StopSearch()

    def solve(self):
        cp_model.CpSolver().SearchForAllSolutions(self.model, self)
					

Nastavení modelu

Parametry pro nastavení modelu jsou zdrojová data zadání hry a velikost hrací desky.

Při nastavení proměnných modelu a omezení budu postupně procházet zadání pro všechny obdélníky.

Proměnné pro obdélníky

V mém modelu bude každý obdélník představován levým-horním a pravým-dolním rohem (proměnné x1, y1, x2 a y2). Současně je u každé proměnné omezení hodnot tak, aby bylo zajištěno, že (x1, y1) <= (x, y) a (x2, y2) >= (x, y).

Dále mám vytvořené proměnné představující velikost strany obdélníku, size_x a size_y. Pro ně je nastaveno omezení, že nesmí přesáhnout velikost hrací desky.

Omezení pro obdélníky

Do modelu jsem doplnil omezení pro levý-horní roh a velikost strany obdélníku. Jejich součet nesmí přesáhnout hranice hrací desky.

A také je zde omezení, že součet levého-horního rohu a velikosti obdélníku musí zajistit zahrnutí referenční pozice obdélníku v zadání.

Posledním omezením, které se vztahuje k jednomu obdélníku, je požadavek na velikost jeho plochy jako součin velikosti jeho stran.

Intervaly obdélníků v osách

Abych mohl zajistit to, že se mně obdélníky nebudou překrývat, potřebuji vytvořit ještě jednu sadu proměnných. Jsou to tzv. intervaly a představují vztah mezi souřadnicemi obdélníku a velikostí jeho stran.

Všechny intervaly si přidám do dvou polí, protože v této podobě je budu potřebovat pro poslední omezení.

Omezení na překryv obdélníků

Poslední, co potřebuji zajistit je omezení, aby se mně dva obdélníky nepřekrývaly.

Toho můžu docílit pomocí metody AddNoOverlap2D, která jako parametry potřebuje právě pole intervalů v osách x a y.

Výkonné metody

Ve třídě GameBoard mám definovány ještě dvě metody:

Metoda OnSolutionCallback se zavolá, když solver najde nějaké řešení. V mém případě si vyzvednu rohy všech obdélníků, promítnu je do numpy pole a vytisknu.

Následně pak ještě vyvolám zastavení činnosti solveru. To proto, že mne bude zajímat pouze první nalezené řešení.

Metoda solve zajistí vyvolání vlastního solveru nad modelem. To je tedy ta výkonná část celého řešení.

A to je co se týká vytvoření modelu a jeho řešení vše potřebné. Následuje již pouze vyzkoušení, jak to celé funguje.

Vyzkoušení řešení hry

Projdu všechna zadání hry a spustím na ně řešení. No a pak se uvidí.

In [14]:

						for sample in range(len(source)):
    print(source.board(sample))
    print('.' * 40)

    board = GameBoard(source.data(sample), source.shape(sample))
    board.solve()

    print()
    print('=' * 40)
    print()
					

[[0 2]
 [2 0]]
........................................
[['B' 'A']
 ['B' 'A']]

========================================

[[0 0 0 4]
 [0 8 0 0]
 [0 0 4 0]
 [0 0 0 0]]
........................................
[['B' 'B' 'C' 'A']
 ['B' 'B' 'C' 'A']
 ['B' 'B' 'C' 'A']
 ['B' 'B' 'C' 'A']]

========================================

[[2 0 0 0 0]
 [0 0 2 0 4]
 [0 0 3 2 0]
 [0 4 0 2 0]
 [4 0 0 2 0]]
........................................
[['A' 'A' 'B' 'C' 'C']
 ['H' 'F' 'B' 'C' 'C']
 ['H' 'F' 'D' 'E' 'E']
 ['H' 'F' 'D' 'G' 'G']
 ['H' 'F' 'D' 'I' 'I']]

========================================

[[0 0 2 0 0]
 [5 2 0 0 0]
 [0 3 2 0 0]
 [0 0 0 3 4]
 [0 0 2 0 2]]
........................................
[['B' 'C' 'A' 'A' 'G']
 ['B' 'C' 'E' 'F' 'G']
 ['B' 'D' 'E' 'F' 'G']
 ['B' 'D' 'H' 'F' 'G']
 ['B' 'D' 'H' 'I' 'I']]

========================================

[[0 0 0 0 0 0 6]
 [2 0 0 3 0 0 0]
 [0 3 0 0 0 6 0]
 [0 0 0 0 0 3 0]
 [3 6 0 0 0 3 0]
 [0 5 0 0 0 2 0]
 [2 0 0 0 3 2 0]]
........................................
[['B' 'A' 'A' 'A' 'A' 'A' 'A']
 ['B' 'C' 'C' 'C' 'E' 'E' 'E']
 ['G' 'D' 'D' 'D' 'E' 'E' 'E']
 ['G' 'H' 'H' 'H' 'F' 'F' 'F']
 ['G' 'H' 'H' 'H' 'I' 'I' 'I']
 ['J' 'J' 'J' 'J' 'J' 'K' 'K']
 ['L' 'L' 'M' 'M' 'M' 'N' 'N']]

========================================

[[0 0 3 0 2 0 0]
 [0 0 5 0 0 0 0]
 [0 3 0 0 0 0 0]
 [0 2 0 4 4 0 4]
 [0 0 2 0 0 0 2]
 [2 2 2 0 0 6 0]
 [0 2 0 0 2 2 0]]
........................................
[['A' 'A' 'A' 'B' 'B' 'N' 'H']
 ['C' 'C' 'C' 'C' 'C' 'N' 'H']
 ['D' 'D' 'D' 'F' 'G' 'N' 'H']
 ['E' 'E' 'I' 'F' 'G' 'N' 'H']
 ['K' 'L' 'I' 'F' 'G' 'N' 'J']
 ['K' 'L' 'M' 'F' 'G' 'N' 'J']
 ['O' 'O' 'M' 'P' 'P' 'Q' 'Q']]

========================================

[[ 0  0  0  4  0  0  2  0  0  0]
 [ 3  0  0  2  0  0  6  0  4  0]
 [ 0  4  0  0  0  0  0  0  4  8]
 [ 0  0  4  0 15  0  0  0  0  0]
 [ 2  0  0  0  0  0  0  2  0  0]
 [ 0  0  0  0  0  0  0  0  0  0]
 [ 4  0 12  0  0  0  0  0  0  0]
 [ 0  0  0  0  0  0  0  0  3  0]
 [ 0  2  0  0  5  0  0  4  2  0]
 [ 0  0  2  0  0  0  6  0  0  0]]
........................................
[['C' 'A' 'A' 'A' 'A' 'B' 'B' 'F' 'F' 'I']
 ['C' 'G' 'G' 'D' 'E' 'E' 'E' 'F' 'F' 'I']
 ['C' 'G' 'G' 'D' 'E' 'E' 'E' 'H' 'H' 'I']
 ['J' 'J' 'J' 'J' 'K' 'K' 'K' 'H' 'H' 'I']
 ['L' 'O' 'O' 'O' 'K' 'K' 'K' 'M' 'M' 'I']
 ['L' 'O' 'O' 'O' 'K' 'K' 'K' 'S' 'P' 'I']
 ['N' 'O' 'O' 'O' 'K' 'K' 'K' 'S' 'P' 'I']
 ['N' 'O' 'O' 'O' 'K' 'K' 'K' 'S' 'P' 'I']
 ['N' 'Q' 'R' 'R' 'R' 'R' 'R' 'S' 'T' 'T']
 ['N' 'Q' 'U' 'U' 'V' 'V' 'V' 'V' 'V' 'V']]

========================================

[[ 0  0  4  0  0  0  2  6  0  0]
 [ 0  0  0  0  0  5  0  0  0  0]
 [ 0  0  2  0  3  0  3  0  0  0]
 [ 0  0  0  0  0  0  0  2  4  0]
 [ 9  0  0  0  0  0  0  0  0  0]
 [ 0  0  0 12  0  0  0  0  9  0]
 [ 0  4  0  0  0  0  0  0  0  3]
 [ 0  0  0 12  0  0  0  0  0  0]
 [ 0  2  0  0  0  0  4  0  4  0]
 [ 0  0  0  7  0  0  0  0  3  0]]
........................................
[['J' 'A' 'A' 'A' 'A' 'B' 'B' 'C' 'C' 'C']
 ['J' 'D' 'D' 'D' 'D' 'D' 'G' 'C' 'C' 'C']
 ['J' 'E' 'E' 'F' 'F' 'F' 'G' 'H' 'I' 'I']
 ['J' 'M' 'K' 'K' 'K' 'K' 'G' 'H' 'I' 'I']
 ['J' 'M' 'K' 'K' 'K' 'K' 'L' 'L' 'L' 'N']
 ['J' 'M' 'K' 'K' 'K' 'K' 'L' 'L' 'L' 'N']
 ['J' 'M' 'O' 'O' 'O' 'O' 'L' 'L' 'L' 'N']
 ['J' 'P' 'O' 'O' 'O' 'O' 'Q' 'Q' 'R' 'R']
 ['J' 'P' 'O' 'O' 'O' 'O' 'Q' 'Q' 'R' 'R']
 ['S' 'S' 'S' 'S' 'S' 'S' 'S' 'T' 'T' 'T']]

========================================

A to je vše.

Přidejte svůj názor jako první

Zdroj testovacích dat

Řešení s pomocí backtracking

Přípravné práce

Řešení

Řešení s využitím OR-Tools

Nastavení modelu

Proměnné pro obdélníky

Omezení pro obdélníky

Intervaly obdélníků v osách

Omezení na překryv obdélníků

Výkonné metody

Vyzkoušení řešení hry

Sdílet

Jiří Raška

Nejčtenější články autora

Poslední názory

Shikaku - hrátky s obdélníčky

Zdroj testovacích dat

Řešení s pomocí backtracking

Přípravné práce

Řešení

Řešení s využitím OR-Tools

Nastavení modelu

Proměnné pro obdélníky

Omezení pro obdélníky

Intervaly obdélníků v osách

Omezení na překryv obdélníků

Výkonné metody

Vyzkoušení řešení hry

Sdílet

Žádné názory

Jiří Raška

Nejčtenější články autora

Poslední názory

Dále u nás najdete

Nechtěla u koní nosit tepláky, tak si založila vlastní značku oblečení

Zakladatelé Bohemia Interactive koupili Parlamentní listy

Dohodáři se zaměstnavatelům už nevyplatí. Je tu konec brigád?

O co jde v žalobách na kryptoburzy Binance a Coinbase?

Zvědavého záškodníka v datovce pomohla odhalit DIA

ABBYY FineReader rozdává licence zdarma!

AI rozevře nůžky mezi dobrými a špatnými vývojáři

Netflix s novými podmínkami může být v klidu. Kdo ho podrží?

Na starém penzijku jste za 10 let prodělali 20 %

Neuropatie je zákeřná, protože ji nemusíte cítit. Někdy končí úrazem

Škoda 706 RO: stroj pro pamětníky

Brněnští vypouštěči pneumatik SUV vzali útokem i elektromobil

Qerko pokusně umožňuje v restauracích platit bitcoinem

Svůj první webový prohlížeč speciálně pro firmy má Microsoft

Microsoft přidává do Windows konečně i užitečné Widgety

Firmy nevědomky podporují informační války mezi zaměstnanci

To není obezita, ale lipedém. Léčí se dietou, prádlem a liposukcí

Stát přispívá 50 000 korun na IT kurz

Transakce s kryptoměnami se budou hlásit daňovým úřadům

Novinky z Windows, které by vás neměly minout: Zálohování