Hi Folks!!!!
very recently, I came across an enchanting puzzle called Kaleidoscope-classic(more Info : http://www.funkc.com/)
Its really elegant in its simplicity, unparalleled in its play value.The most fascinating part of this game is it requires to use your intuition, acumen and judgement to outplay, outscore and outsmart your opponents…
To my interest, I happened to note that this puzzle has got some striking resemblance to some common puzzles(like that of the 8-puzzle,the chess,tictactoe or the 8-queens) that can be solved by formulating an algorithm that looks through soln. by enumerating search space. I tried to surf over the internet to find any automated solving strategies but couldnt get any effective solutions.So I thought Id rather draft one. I have been looking into some algorithms that can actually solve(even though its gonna have some freakin time/memory complexity!!!!) this puzzle and shall draft some of them.Lets dive into formulating & analyzing this problem.
Formulating a sample problem :
Lets start from systems perspective.The system being our algorithm or strategy itself :
Input ----> Algo ------> output.
Initially, Im considering a single player game to arrange kaleidoscope to a target pattern of any level.In this case,
Input = The target pattern, the 18 bits&pieces of the puzzle game
Algo = explained in subsequent sections!!!
Output = 18 bits&pieces interlaced within 8*8 grid to produce target pattern.
Note : shall come out with code too.... but for now, i'm sticking to some solving strategies.
-------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
Algorithm 1: BackTracking Algorithm
-----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
This is the first brute-force strategy that popped into my head.lets take a quick-look at the backtracking algo using which I intend to solve this puzzle.
Algorithm : Backtrack(x)
Input : A problem instance for a hard problem (T= 2d array of pattern, G=given set of 18 3d arrays(2d-colors, 3rd dimension ID) , S=empty 3d 8*8 array for soln(2d-colors,3rd dimension being ID) , P= partially filled so far.)
Output : A Solution for x or "no solution" if none exists .... (S= completely filled with soln. colors)
Initialize:
P <- null , G<- 18 3d arrs
S <- {(P,null), G}
{F <- the frontier set of subproblem configurations initially null}
Recurse(P,G, S,T )
for each item x in G
for each orientation of x&x-inverse
//populate valid configurations
P= P+xi, G=G-xi, S
enumerate all possible S+x as set of new configurations F(xi)= S+xi
F(xi) = enumerate(S,xi,T)
for each new configuration F(xi) do
//perform a simple consistance check on validity of F(xi)
S= S+xi;
check = validate(S,T) ;
if the check returns "solution found" then
return the solution derived from F(xi)
if the check returns "dead end" then
discard the configuration F(xi) {BackTrack}
else
Recurse(P,G,S,T)
// F(xi) starts a promising search path
return "no solution";
(The template for a backtracking algorithm)
Function validate(S,T)
returns boolean
//S pattern should match with T pattern
//no hole should exist within S : this will prune some unnecessary sol.s!!!
<--generating S=S+x enumerations for given x orientation:-->
Function enumerate(S,x,T)
returns list
//assuming each x,S is 3dArray of xi,yi,zi
list<- null
for all yi in 0.. yi+1
{
xj<- last non-null xj in row yi of S
list[i]= xj +1
}
return list[i]
A feasible way of assigning unique identification number to 18 input-pieces of puzzle.
for red-black side
out of 4 possible orientations
1) no zero on (0,0)
2) max x
3) conflicting? min y
Arr(max-x,max-y) = placeholder array
So lets put the validity of this algorithm on hold until I come-up with actual code :) .
