How to resolve the algorithm Pentomino tiling step by step in the Julia programming language

Published on 22 June 2024 08:30 PM
#Julia

How to resolve the algorithm Pentomino tiling step by step in the Julia programming language

Table of Contents

Problem Statement

A pentomino is a polyomino that consists of 5 squares. There are 12 pentomino shapes, if you don't count rotations and reflections. Most pentominoes can form their own mirror image through rotation, but some of them have to be flipped over.

A Pentomino tiling is an example of an exact cover problem and can take on many forms. A traditional tiling presents an 8 by 8 grid, where 4 cells are left uncovered. The other cells are covered by the 12 pentomino shapes, without overlaps, with every shape only used once. The 4 uncovered cells should be chosen at random. Note that not all configurations are solvable.

Create an 8 by 8 tiling and print the result.

Let's start with the solution:

Step by Step solution about How to resolve the algorithm Pentomino tiling step by step in the Julia programming language

This code solves a puzzle called Pentomino, which consists of placing 12 pentominoes (shapes made of 5 squares connected by their sides) into an 8x8 grid without overlapping.

The code starts defining the size of the grid and the number of pentominoes to place. It also defines a list of letters representing each pentomino and a list of vectors representing the offsets of the squares in each pentomino relative to the first square.

The code then creates a dictionary that maps each letter to a list of vectors representing the offsets of the squares in each pentomino and a dictionary that keeps track of whether each pentomino has been placed.

The printgrid function is used to print the grid to the console.

The tryplaceorientation function is used to try to place a pentomino in a particular orientation at a particular position in the grid. It checks if the pentomino fits in the grid and if it doesn't overlap with any other pentominoes. If it does fit, it places the pentomino in the grid and returns true. Otherwise, it returns false.

The removeorientation function is used to remove a pentomino from the grid.

The solve function is a recursive function that tries to place all of the pentominoes in the grid. It starts at a particular position in the grid and tries to place a pentomino in each of its possible orientations. If it can place a pentomino, it marks it as placed and calls itself recursively to try to place the remaining pentominoes. If it can't place a pentomino, it removes the pentomino from the grid and tries the next orientation. If it can't place any pentominoes in the current position, it moves to the next position in the grid.

The placepentominoes function is the main function that calls the solve function to try to solve the puzzle. It first places four squares in the grid to ensure that there is at least one solution. It then calls the solve function to try to place the remaining pentominoes. If the solve function returns true, it prints the solution to the grid. Otherwise, it prints a message saying that no solution was found.

Source code in the julia programming language

using Random

struct GridPoint x::Int; y::Int end

const nrows, ncols, target = 8, 8, 12
const grid = fill('*', nrows, ncols)
const shapeletters = ['F', 'I', 'L', 'N', 'P', 'T', 'U', 'V', 'W', 'X', 'Y', 'Z']
const shapevec = [
    [(1,-1, 1,0, 1,1, 2,1), (0,1, 1,-1, 1,0, 2,0),
        (1,0 , 1,1, 1,2, 2,1), (1,0, 1,1, 2,-1, 2,0), (1,-2, 1,-1, 1,0, 2,-1),
        (0,1, 1,1, 1,2, 2,1), (1,-1, 1,0, 1,1, 2,-1), (1,-1, 1,0, 2,0, 2,1)],
    [(0,1, 0,2, 0,3, 0,4), (1,0, 2,0, 3,0, 4,0)],
    [(1,0, 1,1, 1,2, 1,3), (1,0, 2,0, 3,-1, 3,0),
        (0,1, 0,2, 0,3, 1,3), (0,1, 1,0, 2,0, 3,0), (0,1, 1,1, 2,1, 3,1),
        (0,1, 0,2, 0,3, 1,0), (1,0, 2,0, 3,0, 3,1), (1,-3, 1,-2, 1,-1, 1,0)],
    [(0,1, 1,-2, 1,-1, 1,0), (1,0, 1,1, 2,1, 3,1),
        (0,1, 0,2, 1,-1, 1,0), (1,0, 2,0, 2,1, 3,1), (0,1, 1,1, 1,2, 1,3),
        (1,0, 2,-1, 2,0, 3,-1), (0,1, 0,2, 1,2, 1,3), (1,-1, 1,0, 2,-1, 3,-1)],
    [(0,1, 1,0, 1,1, 2,1), (0,1, 0,2, 1,0, 1,1),
        (1,0, 1,1, 2,0, 2,1), (0,1, 1,-1, 1,0, 1,1), (0,1, 1,0, 1,1, 1,2),
        (1,-1, 1,0, 2,-1, 2,0), (0,1, 0,2, 1,1, 1,2), (0,1, 1,0, 1,1, 2,0)],
    [(0,1, 0,2, 1,1, 2,1), (1,-2, 1,-1, 1,0, 2,0),
        (1,0, 2,-1, 2,0, 2,1), (1,0, 1,1, 1,2, 2,0)],
    [(0,1, 0,2, 1,0, 1,2), (0,1, 1,1, 2,0, 2,1),
        (0,2, 1,0, 1,1, 1,2), (0,1, 1,0, 2,0, 2,1)],
    [(1,0, 2,0, 2,1, 2,2), (0,1, 0,2, 1,0, 2,0),
        (1,0, 2,-2, 2,-1, 2,0), (0,1, 0,2, 1,2, 2,2)],
    [(1,0, 1,1, 2,1, 2,2), (1,-1, 1,0, 2,-2, 2,-1),
        (0,1, 1,1, 1,2, 2,2), (0,1, 1,-1, 1,0, 2,-1)],
    [(1,-1, 1,0, 1,1, 2,0)],
    [(1,-2, 1,-1, 1,0, 1,1), (1,-1, 1,0, 2,0, 3,0),
        (0,1, 0,2, 0,3, 1,1), (1,0, 2,0, 2,1, 3,0), (0,1, 0,2, 0,3, 1,2),
        (1,0, 1,1, 2,0, 3,0), (1,-1, 1,0, 1,1, 1,2), (1,0, 2,-1, 2,0, 3,0)],
    [(0,1, 1,0, 2,-1, 2,0), (1,0, 1,1, 1,2, 2,2),
        (0,1, 1,1, 2,1, 2,2), (1,-2, 1,-1, 1,0, 2,-2)]]
const shapes = Dict{Char,Vector{Vector{GridPoint}}}()
const placed = Dict{Char,Bool}()

for (ltr, vec) in zip(shapeletters, shapevec)
    shapes[ltr] = [[GridPoint(v[i], v[i + 1]) for i in 1:2:7] for v in vec]
    placed[ltr] = false
end

printgrid(m, w, h) = for x in 1:w for y in 1:h print(m[x, y], " ") end; println() end

function tryplaceorientation(o, R, C, shapeindex)
    for p in o
        r, c = R + p.x, C + p.y
        if r < 1 || r > nrows || c < 1 || c > ncols || grid[r, c] != '*'
            return false
        end
    end
    grid[R, C] = shapeindex
    for p in o
        grid[R + p.x, C + p.y] = shapeindex
    end
    true
end

function removeorientation(o, r, c)
    grid[r, c] = '*'
    for p in o
        grid[r + p.x, c + p.y] = '*'
    end
end

function solve(pos, nplaced)
    if nplaced == target
        return true
    end
    row, col = divrem(pos, ncols) .+ 1
    if grid[row, col] != '*'
        return solve(pos + 1, nplaced)
    end
    for i in keys((shapes))
        if !placed[i]
            for orientation in shapes[i]
                if tryplaceorientation(orientation, row, col, i)
                    placed[i] = true
                    if solve(pos + 1, nplaced + 1)
                        return true
                    else
                        removeorientation(orientation, row, col)
                        placed[i] = false
                    end
                end
            end
        end
    end
    false
end

function placepentominoes()
    for p in zip(shuffle(collect(1:nrows))[1:4], shuffle(collect(1:ncols))[1:4])
        grid[p[1], p[2]] = ' '
    end
    if solve(0, 0)
        printgrid(grid, nrows, ncols)
    else
        println("No solution found.")
    end
end

placepentominoes()

You may also check:How to resolve the algorithm LZW compression step by step in the Nim programming language
You may also check:How to resolve the algorithm Camel case and snake case step by step in the Nim programming language
You may also check:How to resolve the algorithm Deal cards for FreeCell step by step in the R programming language
You may also check:How to resolve the algorithm Count the coins step by step in the REXX programming language
You may also check:How to resolve the algorithm Mayan numerals step by step in the Julia programming language