How to resolve the algorithm Pentomino tiling step by step in the Racket programming language
Published on 12 May 2024 09:40 PM
How to resolve the algorithm Pentomino tiling step by step in the Racket 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 Racket programming language
Source code in the racket programming language
#lang racket
(require racket/hash)
(module+ main (Pentomino-tiling))
(define n-rows 8)
(define n-cols 8)
(define blank '-)
(define (build-grid)
(for/fold ((grid (for*/hash ((r n-rows) (c n-cols)) (values (cons r c) #f)))) ((_ 4))
(hash-set grid (cons (random n-rows) (random n-cols)) blank)))
(define (make-shapes-map)
(hash 'F (F) 'I (I) 'L (L) 'N (N) 'P (P) 'T (T) 'U (U) 'V (V) 'W (W) 'X (X) 'Y (Y) 'Z (Z)))
(define (print-grid grid)
(for ((r n-rows) #:when (when (positive? r) (newline)) (c n-cols))
(write (hash-ref grid (cons r c))))
(newline))
(define (Pentomino-tiling (grid (build-grid)))
(define solution (solve 0 grid (make-shapes-map)))
(if solution (print-grid solution) (displayln "no solution")))
(define (solve p grid shapes (failed-shapes (hash)))
(define-values (r c) (quotient/remainder p n-cols))
(cond [(not grid) #f]
[(hash-empty? shapes) (and (hash-empty? failed-shapes) grid)]
[(hash-ref grid (cons r c) #f) (solve (add1 p) grid shapes failed-shapes)]
[else
(define s (car (hash-keys shapes)))
(define os (hash-ref shapes s))
(define shapes-s (hash-remove shapes s))
(define (try-place-orientation o)
(and (for/and ((dy.dx o))
(let ((y (+ r (car dy.dx))) (x (+ c (cdr dy.dx))))
(and (>= x 0) (>= y 0) (< x n-cols) (< y n-rows) (not (hash-ref grid (cons y x))))))
(for/fold ((grid (hash-set grid (cons r c) s))) ((dy.dx o))
(hash-set grid (cons (+ r (car dy.dx)) (+ c (cdr dy.dx))) s))))
(or (for*/first
((o os)
(solution (in-value (solve (add1 p)
(try-place-orientation o)
(hash-union shapes-s failed-shapes))))
#:when solution)
solution)
(solve p grid shapes-s (hash-set failed-shapes s os)))]))
(define (F) '(((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))))
(define (I) '(((0 . 1) (0 . 2) (0 . 3) (0 . 4))
((1 . 0) (2 . 0) (3 . 0) (4 . 0))))
(define (L) '(((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))))
(define (N) '(((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))))
(define (P) '(((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))))
(define (T) '(((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))))
(define (U) '(((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))))
(define (V) '(((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))))
(define (W) '(((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))))
(define (X) '(((1 . -1) (1 . 0) (1 . 1) (2 . 0))))
(define (Y) '(((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))))
(define (Z) '(((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))))
You may also check:How to resolve the algorithm Equilibrium index step by step in the Elena programming language
You may also check:How to resolve the algorithm Function definition step by step in the МК-61/52 programming language
You may also check:How to resolve the algorithm Word wrap step by step in the NetRexx programming language
You may also check:How to resolve the algorithm Hello world/Text step by step in the Fexl programming language
You may also check:How to resolve the algorithm Palindrome detection step by step in the Component Pascal programming language