[SOLUTION] Ruby Quiz #33 Tiling Turmoil

[David Tran]

Here is my solution, it is kind of short ...

#--------------------------------------------------------------------
# Program : Solution for Ruby Quiz #33 Tiling Turmoil
# Author : David Tran
# Date : 2005-05-20
# Version : 1.0
#--------------------------------------------------------------------
def tile(a, n, m, s, x)
@Count +=3D 1 =20
h =3D m/2
new_s =3D [s, s+h, s+h*n, s+h*n+h]
new_x =3D [s+(h-1)*n+(h-1), s+(h-1)*n+h, s+h*n+h-1, s+h*n+h]=20
p =3D ((x-s) / n < h) ? ((x-s) % n < h) ? 0 : 1 \
: ((x-s) % n < h) ? 2 : 3
new_x.each_index{ |i| a[new_x] =3D @Count if i !=3D p }
return if h =3D=3D 1
new_x[p] =3D x
new_s.each_with_index { |e, i| tile(a, n, h, e, new_x) }
end

(puts "Usage: #$0 n"; exit) if (ARGV.size !=3D 1 || ARGV[0].to_i <=3D 0)
n =3D 2 ** ARGV[0].to_i
@Count =3D 0
a =3D Array.new(n*n)
x =3D rand(a.size)
a[x] =3D 'X'
tile(a, n, n, 0, x)
format =3D "%#{2 + Math.log10(a.size).to_i}s"
a.each_with_index {|e, i| print(format % e); puts if (i+1)%(n) =3D=3D 0}
# End of Program------------------------------------------------------

=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=
=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=
=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D
It is base on S. Golomb gave an inductive proof :
http://www.cut-the-knot.com/Curriculum/Geometry/Tromino.shtml
Here is some explanation for my program about tile method:
a - is a dimension one array of n x n ( flat of orign dimension 2 array)
n - is the number side ( 2 ** input number )
m - is the number side of sub square
s - is the start point index ( top-left corner index for sub square )
x - is the missing cell index
=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=
=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=
=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D

Base on The four color theorem, we could color the tile by using max 4 colo=
rs.
http://www.math.gatech.edu/~thomas/FC/fourcolor.html

So, I modified again my solution to show by using 4 color codes:
http://mathworld.wolfram.com/Four-ColorTheorem.html

#--------------------------------------------------------------------
# Program : Solution for Ruby Quiz #33 Tiling Turmoil
# Author : David Tran
# Date : 2005-05-20
# Version : Using 4 color codes
#--------------------------------------------------------------------
def tile(a, n, m, s, x)
h =3D m/2
new_s =3D [s, s+h, s+h*n, s+h*n+h]
new_x =3D [s+(h-1)*n+(h-1), s+(h-1)*n+h, s+h*n+h-1, s+h*n+h]=20
around_tile =3D [new_x[0]%n =3D=3D 0 ? nil : new_x[0]-1,=20
new_x[0] < n ? nil : new_x[0]-n,
new_x[1] < n ? nil : new_x[1]-n,
(new_x[1]+1)%n =3D=3D 0 ? nil : new_x[1]+1,
new_x[2]%n =3D=3D 0 ? nil : new_x[2]-1,
new_x[2]/n + 1 >=3D n ? nil : new_x[2]+n,
new_x[3]/n + 1 >=3D n ? nil : new_x[3]+n,=20
(new_x[3]+1)% n =3D=3D 0 ? nil : new_x[3]+1]
=20
p =3D ((x-s)/ n < h) ? ((x-s)% n < h) ? 0 : 1 \
: ((x-s)% n < h) ? 2 : 3

around_tile[p*2, 2] =3D new_x[p]
(1..4).each do |color|=20
use =3D false
around_tile.each do |i|
next if i.nil?
(use =3D true; break) if a =3D=3D color
end
if (!use)
new_x.each_index{ |i| a[new_x] =3D color if i !=3D p }
break;
end
end

return if h =3D=3D 1
new_x[p] =3D x
new_s.each_with_index { |e, i| tile(a, n, h, e, new_x) }
end

(puts "Usage: #$0 n"; exit) if (ARGV.size !=3D 1 || ARGV[0].to_i <=3D 0)
n =3D 2 ** ARGV[0].to_i
a =3D Array.new(n*n)
x =3D rand(a.size)
a[x] =3D 0
tile(a, n, n, 0, x)
colorCode =3D [' ', '*', 'o', '+', '-']
a.each_with_index { |e, i| print(" #{colorCode[e]}"); puts if (i+1)%n =3D=
=3D 0 }
# End of Program------------------------------------------------------
=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=
=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=
=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D

This gives a solution presents like:

$> tiling2.rb 4

o o + + o o + + o o + + o o + +
o * * + o * * + o * * + o * * +
+ * o o + + * o + * o o + + * o
+ + o * * + o o + + o * * + o o
o o + * o o + + o o + + * o + +
o * + + o * * + o * * + o o * +
+ * * o + * o o + + * o + * * o
+ + o o + + o * * + o o + + o o
o o + + o o + * o o + + o o + +
o * * + o * + + o * * + o * * +
+ * o o + * * o + * o o + + * o
+ + o * + + o o + + o * + o o
o o + * * o + + o o + * * o + +
o * + + o o * + o * + + o o * +
+ * * o + * * o + * * o + * * o
+ + o o + + o o + + o o + + o o

=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=
=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=
=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D

My first and second solution always recalculation next "missing" cell
possition, it is kind of waste time, because, except the "missing" cell
all will be one of top-left, top-right, bottom-left, bottom-right
coner "missing"
on next iteration and so on.

So, one ugly and quickly improve is like:

#--------------------------------------------------------------------
# Program : Solution for Ruby Quiz #33 Tiling Turmoil
# Author : David Tran
# Date : 2005-05-20
# Version : Without always recalculate "missing" cell
#--------------------------------------------------------------------

DIRECTION =3D [ [ 0, 3, 0, 1],
[ 2, 1, 0, 1],
[ 2, 3, 2, 1],
[ 2, 3, 0, 3] ]

def tile(a, n, m, s, x, p)
@Count +=3D 1
h =3D m/2
new_s =3D [s, s+h, s+h*n+h, s+h*n]
new_x =3D [s+(h-1)*n+(h-1), s+(h-1)*n+h, s+h*n+h, s+h*n+h-1]

if p < 0
pp =3D ((x-s) / n < h) ? ((x-s) % n < h) ? 0 : 1 \
: ((x-s) % n < h) ? 3 : 2 =20
else
pp =3D p
end
=20
new_x.each_index{ |i| a[new_x] =3D @Count if i !=3D pp }
return if h =3D=3D 1
dir =3D DIRECTION[pp]
if p < 0
dir =3D dir.dup
dir[pp] =3D -1
end
new_s.each_with_index { |e, i| tile(a, n, h, e, x, dir) }
end

(puts "Usage: #$0 n"; exit) if (ARGV.size !=3D 1 || ARGV[0].to_i <=3D 0)
n =3D 2 ** ARGV[0].to_i
a =3D Array.new(n*n)
x =3D rand(a.size)
a[x] =3D 'X'
@Count =3D 0
tile(a, n, n, 0, x, -1)
format =3D "%#{2 + Math.log10(a.size).to_i}s"
a.each_with_index {|e, i| print(format % e); puts if (i+1)%(n) =3D=3D 0}

# End of Program------------------------------------------------------

=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=
=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=
=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D

Anyway, I still like my first short solution even it seems waste time to=20
recalculate "missing" cell ...

 

[David Tran]

The solution for 2x2 and 4x4 is unique.
But start from 8x8, the solution is no more unique.

Here is my other version to solve this puzzle.
It uses simple back-tracking to find all possible solution.
It is not efficient at all, but it can find all solutions.

I am not sure is there a math formula to find all solution number.
Base on my program, I found, for example, for 8x8 and
missing cell at (0,0), there are total 30355 possible solutions.

Because it is not efficient, I will not try board big then 8x8

# -------------------------------------------------------------------------=
-----
# Program : Solution for Ruby Quiz Tiling Turmoil (#33)
# Author : David Tran
# Date : 2005-05-23
# Vesion : Use Simple Backtracking to compute all solutions
# Note : Simple backtracking, no use any math theorem or=20
# pattern analyse. It is not efficient at all!
# BTW. The total solution for 8x8 and missing cell at [0,0] is 30=
355.
# -------------------------------------------------------------------------=
-----

def help
puts "Usage: #$0 n [sol]"
puts " Tiling Turmoil for board of 2^n x 2^n cases with one random
missing case"
puts " sol: Optional."
puts " Number solution desire. Default value equals 1."
puts " Equals to zero : Compute total solution number without
print solutions."
puts " Less then zero : Print all possible solutions."
exit
end

# To make sure back tracking all possible solutions, the tiling order
is important.
# This program will tile trimino from top to bottom and left to right.
#=20
# So, the 4 possible L-tromino will have this relation coordination (x, y):
TROMINOS =3D [ [ [1, 0], [0, 1] ], # o*
# *
#=20
[ [1, 0], [1, 1] ], # o*
# *
# =20
[ [0, 1], [1, 1] ], # o
# **
#=20
[ [0, 1], [-1,1] ] ] # o
# **


def tile_next(a, n, count)
(0...n).each do |y|
(0...n).each do |x|
next if a[y][x]
TROMINOS.each do |tromino|
x1 =3D x + tromino[0][0]
y1 =3D y + tromino[0][1]
x2 =3D x + tromino[1][0]
y2 =3D y + tromino[1][1]
next if ( x1 < 0 || x1 >=3D n ||=20
y1 < 0 || y1 >=3D n ||
x2 < 0 || x2 >=3D n ||
y2 < 0 || y2 >=3D n ||
a[y1][x1] || a[y2][x2] )
a[y][x] =3D a[y1][x1] =3D a[y2][x2] =3D count=20
tile_next(a, n, count+1)
a[y][x] =3D a[y1][x1] =3D a[y2][x2] =3D nil # back tracking
end
return
end
end
print_solution(a)
end


def print_solution(a)
@solutions +=3D 1
if @show_solution
puts "solution ##@solutions"=20
a.each {|row| puts row.inject('') {|s, e| s + e.to_s.rjust(@digits+1) }=
}
puts
end
exit if @num_solutions !=3D nil && @solutions >=3D @num_solutions
end


help if ARGV.size <=3D 0 || ARGV[0].to_i <=3D 0
n =3D 2 ** ARGV[0].to_i
option =3D ARGV[1] ? ARGV[1].to_i : 1
@num_solutions =3D (option <=3D 0) ? nil : option
@show_solution =3D (option !=3D 0)
@digits =3D (n*n).to_s.size
@solutions =3D 0
a =3D Array.new(n) { Array.new(n) }
a[rand(n)][rand(n)] =3D 'X'
tile_next(a, n, 1)
puts "Total possible solutions =3D #@solutions" if @num_solutions.nil?

 

[David Tran]

=3Dbegin

* Program : Solution for Ruby Quiz #33 Tiling Turmoil
* Author : David Tran
* Date : 2005-05-25
* Version : Fast, less iteration version

Here is my other solution.
=20
Below note is only apply for n >=3D 3 ( start from 8x8 )
for n =3D1 (2x2) and n=3D2 (4x4) the solution is unique.
=20
It still has a special case need to solve.=20
(Do not want google to find solution for the special case)

The small rectangle form by tromino is 2x3 (or 3x2) note as R(2,3).
Below, it discuss only for 2x3 case. (for 3x2, just rotate it)
=20
This means all area of 2nx3m can tile by the small rectangle of 2 tromino=