slidingpuzzle package

A package for solving sliding tile puzzles.

Examples

>>> from slidingpuzzle import *
>>> b = new_board(3, 3)
>>> print_board(b)
1 2 3
4 5 6
7 8
>>> print_board(shuffle(b))
1 6 7
4   8
5 3 2
>>> search(b, "greedy", heuristic=manhattan_distance)
solution=[3, 2, 8, 3, 6, 7, 3, 6, 7, 1, 4, 7, 2, 5, 7, 4, 1, 2, 5, 8]
solution_len=20, generated=829, expanded=518, unvisited=312, visited=313

Subpackages

• slidingpuzzle.nn package

Submodules

slidingpuzzle.algorithms module

Search algorithms

class Algorithm(value)

All supported algorithms.

A_STAR = 'a*'

BEAM = 'beam'

BFS = 'bfs'

DFS = 'dfs'

GREEDY = 'greedy'

IDA_STAR = 'ida*'

IDDFS = 'iddfs'

a_star(board: ndarray[Any, dtype[_ScalarType_co]], **kwargs) → SearchResult

A* heuristic search algorithm. Supports weights, depth bounds, and f-bounds. The distance of a search state from the goal is computed as:

\[f(n) = g(n) + w \cdot h(n)\]

or equivalently f(n) = len(state.history) + weight * heuristic(state.board) Here, g(n) is the cost of the solution so far, w is the weight, and h(n) is the heuristic evaluation. When no heuristic is used, A* becomes breadth-first search. When weight != 1 or an inadmissable heuristic is used, A* may return a suboptimal solution.

Parameters:

• board – The board

• depth_bound (int) – A limit to search depth. Default is \(\infty\).

• f_bound (float) – A limit on state cost. Default is \(\infty\).

• detect_dupes (bool) – Duplicate detection (i.e. track visited states). Default is True.

• heuristic – A function that maps boards to an estimated cost-to-go. Default is slidingpuzzle.heuristics.linear_conflict_distance().

• weight (float) – A constant multiplier on heuristic evaluation

Returns:

A slidingpuzzle.state.SearchResult with a solution and statistics

beam(board: ndarray[Any, dtype[_ScalarType_co]], **kwargs) → SearchResult

Beam search is a variant of breadth-first search that sorts its children greedily using a heuristic function and then drops child states to match the beam width. This search is incomplete, meaning it may miss a solution although it exists. It is useful for limiting memory usage in large search spaces.

Parameters:

• board – The board

• depth_bound (int) – A limit to search depth. Default is \(\infty\).

• f_bound (float) – A limit on state cost. Default is \(\infty\).

• detect_dupes (bool) – Duplicate detection (i.e. track visited states). Default is True.

• heuristic – A function that maps boards to an estimated cost-to-go. Default is slidingpuzzle.heuristics.linear_conflict_distance().

• width (int) – The beam width. Default is 4.

Returns:

A slidingpuzzle.state.SearchResult with a solution and statistics

bfs(board: ndarray[Any, dtype[_ScalarType_co]], **kwargs) → SearchResult

Breadth-first search

Parameters:

• board – The board

• depth_bound (int) – A limit to search depth. Default is \(\infty\).

• detect_dupes (bool) – Duplicate detection (i.e. track visited states). Default is True.

Returns:

A slidingpuzzle.state.SearchResult with a solution and statistics

compare(h: int = 3, w: int = 3, num_iters: int = 32, alga: ~slidingpuzzle.algorithms.Algorithm | str = Algorithm.A_STAR, algb: ~slidingpuzzle.algorithms.Algorithm | str = Algorithm.A_STAR, ha: ~typing.Callable[[~numpy.ndarray[~typing.Any, ~numpy.dtype[~numpy._typing._array_like._ScalarType_co]]], int | float] = <function linear_conflict_distance>, hb: ~typing.Callable[[~numpy.ndarray[~typing.Any, ~numpy.dtype[~numpy._typing._array_like._ScalarType_co]]], int | float] = <function linear_conflict_distance>, kwargsa: dict | None = None, kwargsb: dict | None = None, **kwargs) → tuple[float, float]

Runs search on num_iters random boards, trying both alga(board, ha) and algb(board, hb) on each board. Returns the average number of states generated for both.

Parameters:

• h – Height of the board

• w – Width of the board

• num_iters – Number of iterations to compute average nodes generated

• alga – Search algorithm paired with ha

• algb – Search algorithm paired with hb

• ha – First heuristic function to evaluate

• hb – Second heuristic function to evaluate

• kwargsa – Keyword args for only alga

• kwargsb – Keyword args for only algb

• kwargs – Keyword args for both algorithms

Returns:

A tuple containing (avg. generated A, avg. generated B)

dfs(board: ndarray[Any, dtype[_ScalarType_co]], **kwargs) → SearchResult

Depth-first search

Parameters:

• board – The board

• depth_bound (int) – A limit to search depth. Default is \(\infty\).

• detect_dupes (bool) – Duplicate detection (i.e. track visited states). Default is True.

Returns:

A slidingpuzzle.state.SearchResult with a solution and statistics

evaluate(h: int = 3, w: int = 3, heuristic: ~typing.Callable[[~numpy.ndarray[~typing.Any, ~numpy.dtype[~numpy._typing._array_like._ScalarType_co]]], int | float] = <function linear_conflict_distance>, alg: ~slidingpuzzle.algorithms.Algorithm | str = Algorithm.A_STAR, num_iters: int = 64, **kwargs) → float

Runs search on num_iters random boards. Returns the average number of nodes generated.

Parameters:

• h – Height of the board

• w – Width of the board

• heuristic – Heuristic function to evaluate

• alg – Search algorithm to evaluate

• num_iters – Number of iterations to average

• kwargs – Additional args for algorithm

Returns:

The average number of states generated

get_next_states(state: State) → list[State]

Creates a list of next viable states, given the current state.

greedy(board: ndarray[Any, dtype[_ScalarType_co]], **kwargs) → SearchResult

Greedy best-first search. This search orders all known states using the provided heuristic and greedily chooses the state closest to the goal.

Parameters:

• board – The board

• depth_bound (int) – A limit to search depth. Default is \(\infty\).

• f_bound (float) – A limit on state cost. Default is \(\infty\).

• detect_dupes (bool) – Duplicate detection (i.e. track visited states). Default is True.

• heuristic – A function that maps boards to an estimated cost-to-go. Default is slidingpuzzle.heuristics.linear_conflict_distance().

Returns:

A slidingpuzzle.state.SearchResult with a solution and statistics

ida_star(board: ndarray[Any, dtype[_ScalarType_co]], **kwargs) → SearchResult

Iterative deepening A*. A depth-first search that uses an f-bound instead of depth to limit search. The next bound is set to the minimum increase in f-bound observed during the current iteration. See a_star().

Parameters:

• board – The board

• depth_bound (int) – A limit to search depth. Default is \(\infty\). This is an optional bound used in addition to the default f-bound.

• detect_dupes (bool) – Duplicate detection (i.e. track visited states). Default is True.

• heuristic – A function that maps boards to an estimated cost-to-go. Default is slidingpuzzle.heuristics.linear_conflict_distance().

• weight (float) – A constant multiplier on heuristic evaluation. Default is 1.

Returns:

A slidingpuzzle.state.SearchResult with a solution and statistics

iddfs(board: ndarray[Any, dtype[_ScalarType_co]], **kwargs) → SearchResult

Iterative deepening depth first search. Similar to dfs(), except that the depth bound is incrementally increased until a solution is found.

Parameters:

• board – The board

• depth_bound (int) – The initial bound. Default is slidingpuzzle.heuristics.linear_conflict_distance().

• detect_dupes (bool) – Duplicate detection (i.e. track visited states). Default is True.

Returns:

A slidingpuzzle.state.SearchResult with a solution and statistics

search(board: ndarray[Any, dtype[_ScalarType_co]], alg: Algorithm | str = Algorithm.A_STAR, **kwargs) → SearchResult

Searches for a set of moves that take the provided board state to the solved state.

Requested alg may be one of Algorithm (or str name).

See slidingpuzzle.heuristics for heuristic functions or provide your own.

If a heuristic is provided with “bfs”, “dfs”, or “iddfs”, it is only used to sort the locally generated nodes on each expansion, but not the entire open list. You may also provide a “bound” via the kwargs described below to limit the search depth.

If “greedy” or “a*” is used, the entire open list is sorted. The “greedy” algorithm sorts only on the heuristic, while “a*” uses heuristic + length of the solution. Default heuristics are listed in the table below.

Of the provided algorithms, only beam search is incomplete. This means it may miss the goal, even thought the board is solvable.

The algorithms support some additional kwargs that can be used to customize their behavior. See the docs for individual algorithms.

Parameters:

• board – The initial board state to search.

• alg – The algorithm to use for search. Use print(ALGORITHMS) to see available.

• kwargs – Algorithm arguments as described above.

Returns:

Returns a slidingpuzzle.state.SearchResult containing a list of moves to solve the puzzle from the initial state along with some search statistics.

slidingpuzzle.board module

A collection of functions for working with sliding tile puzzle boards.

board_generator(h: int, w: int, start: int = 0, stop: int | None = None) → Iterator[ndarray[Any, dtype[_ScalarType_co]]]

Returns a generator that yields all solvable boards in lexicographical order.

Parameters:

• h – Height of board

• w – Width of board

• start – Index of board to start with

• stop – The board index to stop at, or None if we should run until completion. The board at stop is not included, similar to range().

Yields:

A board permutation

count_inversions(board: ndarray[Any, dtype[_ScalarType_co]]) → int

From each tile, count the number of tiles that are out of place after this tile. Returns the sum of all counts. See is_solvable().

Parameters:

board – The puzzle board.

Returns:

The count of inversions.

find_blank(board: ndarray[Any, dtype[_ScalarType_co]] | tuple[tuple[int, ...], ...]) → tuple[int, int]

Locate the blank tile’s (y, x)-coord. Equivalent to find_tile(board, BLANK).

Parameters:

board – The puzzle board.

Returns:

The (y, x)-coord of the blank tile.

find_tile(board: ndarray[Any, dtype[_ScalarType_co]] | tuple[tuple[int, ...], ...], tile: int) → tuple[int, int]

Given a tile number, find the (y, x)-coord on the board.

Parameters:

• board – The puzzle board.

• move – The

Raises:

ValueError – If the tile is not on the board.

Returns:

The tile position.

flatten_board(board: ndarray[Any, dtype[_ScalarType_co]] | tuple[tuple[int, ...], ...]) → list[int]

Flattens a board to a list. Useful for quickly compressing the board state. Can be reconstructed using board_from_iter().

Parameters:

board – The board to flatten

Returns:

A flat sequence of ints representing the board.

freeze_board(board: ndarray[Any, dtype[_ScalarType_co]]) → tuple[tuple[int, ...], ...]

Obtain a frozen copy of the board that is hashable.

Parameters:

board – The board to freeze.

Returns:

A frozen copy of the board.

from_cols(*cols: Iterable[int], dtype: dtype[Any] | None | type[Any] | _SupportsDType[dtype[Any]] | str | tuple[Any, int] | tuple[Any, SupportsIndex | Sequence[SupportsIndex]] | list[Any] | _DTypeDict | tuple[Any, Any] = None) → ndarray[Any, dtype[_ScalarType_co]]

Constructs a new board from a provided iterable of columns. Internally uses from_rows().

from_iter(h: int, w: int, iterable: Iterable[int], row_major: bool = True) → ndarray[Any, dtype[_ScalarType_co]]

Given an iterable of ints, will construct a board of size h x w in row-major order. The number of values should equal \(h \cdot w\) and all values must be provided. (Any partial extra row will be discarded.)

Parameters:

• h – Height of the board to construct

• w – Width of the board to construct

• iter – Iterable of values to construct board from

• row_major – If False, will assume values are provided in column-major order.

Raises:

• TypeError – If a non-int value is found in a row.

• ValueError – If rows have unequal length or tiles are duplicated, missing, or have unexpected gaps.

Returns:

The constructed board.

from_rows(*rows: Iterable[int], dtype: dtype[Any] | None | type[Any] | _SupportsDType[dtype[Any]] | str | tuple[Any, int] | tuple[Any, SupportsIndex | Sequence[SupportsIndex]] | list[Any] | _DTypeDict | tuple[Any, Any] = None) → ndarray[Any, dtype[_ScalarType_co]]

Constructs a new board from a provided iterable of rows. May throw a ValueError if rows are unequal in size or duplicate values are found.

Parameters:

• rows – One or more rows that constitute a board. Each row should contain ints.

• dtype – An optional numpy dtype for the board. Will be inferred if not provided.

Raises:

• TypeError – If a non-int value is found in a row.

• ValueError – If rows have unequal length or tiles are duplicated, missing, or have unexpected gaps.

Returns:

The constructed board.

get_goal_tile(h: int, w: int, pos: tuple[int, int]) → int

Given a board width and (y, x)-coord, return the tile number that belongs at (y, x).

Parameters:

• h – Height of the board

• w – Width of the board

• pos – A (y, x)-position on the board.

Returns:

The tile number that belongs at (y, x).

get_goal_x(h: int, w: int, tile: int) → int

Given a board width and tile number, returns the goal column position of tile.

Parameters:

• h – Height of the board

• w – Width of the board

• tile – The tile number of interest

Returns:

The goal column (x-coord)

get_goal_y(h: int, w: int, tile: int) → int

Given a board width and tile number, returns the goal row position of tile.

Parameters:

• h – Height of the board

• w – Width of the board

• tile – The tile number of interest

Returns:

The goal row (y-coord)

get_goal_yx(h: int, w: int, tile: int) → tuple[int, int]

Given a board width and tile number, returns the goal (y, x) position of tile.

Parameters:

• h – Height of the board

• w – Width of the board

• tile – The tile number of interest

Returns:

A tuple (y, x) indicating the tile’s goal position.

get_next_moves(board: ndarray[Any, dtype[_ScalarType_co]] | tuple[tuple[int, ...], ...], blank_pos: tuple[int, int] | None = None) → list[tuple[int, int]]

Return a list of all possible moves.

Parameters:

• board – The current puzzle board.

• blank_pos – The position of the empty tile. If not provided, it will be located automatically.

Returns:

A list of (y, x)-coords that are tile positions capable of swapping with the blank tile.

is_solvable(board: ndarray[Any, dtype[_ScalarType_co]]) → bool

Determines if it is possible to solve this board.

Note

The algorithm counts inversions to determine solvability. The “standard” algorithm has been modified here to support non-square board sizes.

Parameters:

board – The puzzle board.

Returns:

True if the board is solvable, False otherwise.

Return type:

bool

is_solved(board: ndarray[Any, dtype[_ScalarType_co]]) → bool

Determine if a board is in the solved state.

Parameters:

board – The board

Returns:

True if the board is solved, otherwise False.

new_board(h: int, w: int, dtype: dtype[Any] | None | type[Any] | _SupportsDType[dtype[Any]] | str | tuple[Any, int] | tuple[Any, SupportsIndex | Sequence[SupportsIndex]] | list[Any] | _DTypeDict | tuple[Any, Any] = None) → ndarray[Any, dtype[_ScalarType_co]]

Create a new board in the default solved state.

Parameters:

• h – Height of the board.

• w – Width of the board.

• dtype – An optional numpy dtype for the board. Will be inferred if not provided.

Returns:

The new board.

print_board(board: ~numpy.ndarray[~typing.Any, ~numpy.dtype[~numpy._typing._array_like._ScalarType_co]] | tuple[tuple[int, ...], ...], file=<_io.TextIOWrapper name='<stdout>' mode='w' encoding='utf-8'>) → None

Convienance function for printing a formatted board.

Parameters:

• board – The board to print.

• file – The target output file. Defaults to stdout.

random_move(board: ndarray[Any, dtype[_ScalarType_co]], blank_pos: tuple[int, int] | None = None) → ndarray[Any, dtype[_ScalarType_co]]

Picks a random legal move and applies it to the board.

Parameters:

• board – The board

• blank_pos – The position of the blank. If not provided, will be found.

shuffle(board: ndarray[Any, dtype[_ScalarType_co]]) → ndarray[Any, dtype[_ScalarType_co]]

Shuffles a board (in place). Board is always solvable.

Parameters:

board – The board to shuffle.

Returns:

The shuffled board.

shuffle_lazy(board: ndarray[Any, dtype[_ScalarType_co]], num_moves: int | None = None, moves: list | None = None) → ndarray[Any, dtype[_ScalarType_co]]

Shuffles a board in place by making random legal moves from the solved state. No repeated states are allowed. It is possible that this method terminates after making fewer than num_moves if no new states can be reached. Generally you should prefer to use shuffle(), although there are certain scenarios where this method may be preferable, such as guaranteeing that a solution is no further than num_moves away.

Parameters:

• board – The board to shuffle.

• num_moves (int) – Number of random moves to make. If None, (h + w) * 2 will be used.

• moves – If a list is provided, the moves made will be appended.

Returns:

The same board for chaining convience.

solution_as_tiles(board: ndarray[Any, dtype[_ScalarType_co]], solution: Iterable[tuple[int, int]]) → list[int]

Converts a list of (y, x)-coords indicating moves into tile numbers, given a starting board configuration.

Parameters:

• board – The initial board we will apply moves to (does not alter board).

• solution – A list of move coordinates in (y, x) form.

Returns:

A list of ints, which indicate a sequence of tile numbers to move.

swap_tiles(board: ndarray[Any, dtype[_ScalarType_co]], tile1: tuple[int, int] | int, tile2: tuple[int, int] | int | None = None) → ndarray[Any, dtype[_ScalarType_co]]

Mutates the board by swapping a pair of tiles.

Parameters:

• board – The board to modify.

• tile1 – The first tile position or value.

• tile2 – The second tile position or value. If None, the blank will be located and used.

Returns:

The modified board.

visit(visited: set[tuple[tuple[int, ...], ...]], board: ndarray[Any, dtype[_ScalarType_co]]) → bool

Helper to check if this state already exists. Otherwise, record it. Returns True if we have already been here, False otherwise.

Parameters:

• visited – Set of boards already seen.

• board – The current board.

Returns:

True if we’ve been here before.

slidingpuzzle.heuristics module

This module provides heuristic functions used to evaluate board states.

Each function accepts a puzzle board as input, and returns a numeric value that indicates the estimated distance from the goal.

corner_tiles_distance(board: ndarray[Any, dtype[_ScalarType_co]], relaxed: bool = True) → int

If tiles that belong in corners are not there but the tiles adjacent are correct, additional reshuffling will need to occur. This function adds 2 moves for every correct adjacent tile next to an out-of-place corner.

Note

This heuristic will return 0 on boards smaller than 4x4, as the corner adjacent tiles are shared between some corners, resulting in over-counting.

Parameters:

• board – The board

• relaxed – If False, can be safely combined with linear_conflict_distance().

Returns:

The additional distance required to shuffle corners into position.

euclidean_distance(board: ndarray[Any, dtype[_ScalarType_co]]) → float

The distance between each tile and its destination, as measured in Euclidean space

\[\sum_{i}^{n} \sqrt{(\text{tile}_{i, x} - \text{goal}_{i, x})^2 + (\text{tile}_{i, y} - \text{goal}_{i, y})^2}\]

Parameters:

board – The board

Returns:

The sum of all tile distances from their goal positions

hamming_distance(board: ndarray[Any, dtype[_ScalarType_co]]) → int

The count of misplaced tiles.

\[\sum_{i}^{n} \text{tile}_i \oplus \text{goal}_i\]

Parameters:

board – The board

Returns:

The number of tiles out of their goal positions

has_col_conflict(board: ndarray[Any, dtype[_ScalarType_co]], y: int, x: int) → bool

See has_row_conflict(). This is identical, but swaps rows for columns.

has_conflict(board: ndarray[Any, dtype[_ScalarType_co]], y: int, x: int)

Combines has_row_conflict() and has_col_conflict() for convenience.

has_row_conflict(board: ndarray[Any, dtype[_ScalarType_co]], y: int, x: int) → bool

On row y, we check every tile for conflict with column x.

What defines a “conflict”? From the original paper:

Definition 6: Two tiles j and k are in a linear conflict if j and k are in the same line, the goal positions of j and k are both in that line, j is to the right of k, and the goal position of j is to the left of the goal position of k.

Equivalently:

1. j and k are on the same line

2. j and k both have goal positions in their current line

3. j is right of k

4. j has a goal left of k

Parameters:

• board – The board:

• y – The row of interest

• x – The column we will be checking for involvement in any conflicts

Returns:

True if column x is involved in any conflicts on row y

last_moves_distance(board: ndarray[Any, dtype[_ScalarType_co]], relaxed: bool = True) → int

Immediately before the last move, one of the tiles adjacent to the blank tile must be in the corner. If not, we must make at least 2 more moves to shuffle. Similarly, for the next-to-last move, the tiles 1-removed from the adjacents must be beside the corner. This is similar to corner_tiles_distance(), but specifically targets the goal corner, which has slightly different constraints.

Parameters:

• board – The board

• relaxed – If False, can be safely combined with linear_conflict_distance(), corner_tiles_distance(), or manhattan_distance().

Returns:

2 if neither of the final tiles to move are in the final corner, else 0.

linear_conflict_distance(board: ndarray[Any, dtype[_ScalarType_co]], optimized: bool = True) → int

Starts with Manhattan distance, then for each row and column, the number of tiles “in conflict” are identified, and 2 * this number is added to the total distance. (It will take at least 2 additional moves to reshuffle the conflicting tiles into their correct positions.) This is an admissible improvement over manhattan_distance() (Hansson, Mayer, Young, 1985). The last_moves_distance() and corner_tiles_distance() are included (Korf and Taylor, 1996).

Parameters:

• board – The board

• optimized – If False, will not include manhattan_distance(), last_moves_distance() and corner_tiles_distance(). It will return only the base number of linear conflicts, which may be useful in the design of new heuristics.

Returns:

Estimated distance to goal.

manhattan_distance(board: ndarray[Any, dtype[_ScalarType_co]]) → int

The minimum number of moves needed to restore the board to the goal state, if tiles could be moved through each other.

\[\sum_{i}^{n} |\text{tile}_{i, x} - \text{goal}_{i, x}| + |\text{tile}_{i, y} - \text{goal}_{i, y}|\]

Parameters:

board – The board

Returns:

The sum of all tile distances from their goal positions

prepare_manhattan_table(h, w) → dict[tuple[int, int, int], int]

Used on first invocation of manhattan_distance() to cache the board distances.

random_distance(board: ndarray[Any, dtype[_ScalarType_co]]) → int

A random distance computed as a hash of the board state. Useful as a baseline.

\[hash(\text{board})\]

Parameters:

board – The board

Returns:

A random distance that is consistent for a given board state

relaxed_adjacency_distance(board: ndarray[Any, dtype[_ScalarType_co]]) → int

Repeatedly swap misplaced tiles into their goal positions, ignoring legal board distance and rules. We repeat this process until the board is solved. This heuristic is a slight improvement to Hamming distance.

Parameters:

board – The board

Returns:

The estimated distance to goal.

slidingpuzzle.state module

Provides some convience classes to track search state and results.

class SearchResult(board: ndarray[Any, dtype[_ScalarType_co]], generated: int, expanded: int, unvisited: Collection[State], visited: set[tuple[tuple[int, ...], ...]], solution: list[tuple[int, int]] | None)

A dataclass for returning a puzzle solution along with some information concerning how the search progressed. Useful for evaluating different heuristics.

Parameters:

• board – The original input board.

• generated – The number of states generated during search.

• expanded – The number of states evaluated during search.

• unvisited – The list of states that were never reached.

• visited – The set of boards evaluated.

• solution – The list of moves from initial position to solution.

Note

The unvisited and visited attributes are traditionally known as “open” and “closed” in search parlance. However, Python’s built-in function open would collide, so they have been renamed.

board: ndarray[Any, dtype[_ScalarType_co]]

expanded: int

generated: int

solution: list[tuple[int, int]] | None

unvisited: Collection[State]

visited: set[tuple[tuple[int, ...], ...]]

class State(board: ~numpy.ndarray[~typing.Any, ~numpy.dtype[~numpy._typing._array_like._ScalarType_co]], blank_pos: tuple[int, int], history: list[tuple[int, int]] = <factory>, f: int | float = 0, g: int = 0)

A dataclass for representing the state during search. Although the board is enough to fully capture the game state, it is convenient to track some additional information.

Parameters:

• board – The board state.

• blank_pos – The (y, x)-coord of the blank tile.

• history – A list of (y, x)-coords representing moves from the initial state to the current board state.

• f – The stored value of this node. Used by some search algorithms to order states. The value stored here has no meaning if not using a relevant search algorithm.

• g – For some search algorithms, this will hold the number of moves made to reach this state. Used to tie-break when f values are identical.

blank_pos: tuple[int, int]

board: ndarray[Any, dtype[_ScalarType_co]]

f: int | float = 0

g: int = 0

history: list[tuple[int, int]]