If you do not know the rule, the idea is to reach one configuration from the given initial configuration. The only rule is you can slide the tile to empty spot. You cannot jump. The tile that is free can only move.
If the initial configuration is the following.
We can slide tile 6 down which gives the following configuration.
Similarly we can slide tile 5 right which gives the following. I hope you have a good idea by now.
So, given an initial configuration, the goal is to reach the given goal configuration.
Today i was playing around with this puzzle and wanted to check how many ways there are actually from this initial configuration.
The answer i got was 181440. Holy crap! It didn't seem like this simple looking puzzle would yield that many unique configurations.
Following is the code I wrote to generate the total unique configurations from the above configuration. Since there were a finite number of things to keep track of in a given state, i used an int to pack the state that way i can save space and time. So, instead of passing 3x3 array around, i can just pass the integer. Another positive thing from this was since primitives are passed by value, i didn't need to worry about duplicating the state. It is automatically duplicated when passed into a function.
#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
using namespace std;
map<int, int> mp;
/*
1 2 3
4 5 6
7 8
__ __ __ __ __ __ __ __
I divide the integer into 8 parts.
each part or a nibble will hold x and y of number corresponding to the position
for example: the following holds x, y of 1 which is 0 because x = 0, y = 0
__ __ __ __ __ __ __ 0x0
the following holds x, y as 2 because x = 1, y = 0 0x10 = 2
__ __ __ __ __ __ 0x10 __
*/
unsigned int pack(int temp[][3]){
unsigned int r = 0;
for(int i=0;i<3;i++){
for(int j=0;j<3;j++){
if(temp[i][j] == 0) continue;
int tt = temp[i][j];
unsigned int nib = (j<<2) | i;
nib <<= (tt-1)*4;
r |= nib;
}
}
return r;
}
/*
Just like pack converts the 3x3 array to a integer. This does the reverse.
*/
void unpack(unsigned int n, int temp[][3]){
int num = 1;
while(num <= 8){
int xy = n & 0xf;
int y = xy&0x3;
int x = (xy>>2)&0x3;
temp[y][x] = num;
num++;
n >>= 4;
}
}
/*
This function is used to move the tile and return the packed form of the resultant array
example:
temp
1 2 3
4 5 6
7 8
from_i = 2, from_j = 2
to_i = 1, to_j = 2
then
temp
1 2 3
4 5
7 8 6
*/
unsigned int packArray(int temp[][3], int from_i, int from_j, int to_i, int to_j){
int temp2[3][3] = {0};
for(int i=0;i<3;i++){
for(int j=0;j<3;j++){
temp2[i][j] = temp[i][j];
}
}
int t = temp2[from_i][from_j];
temp2[from_i][from_j] = temp2[to_i][to_j];
temp2[to_i][to_j] = t;
return pack(temp2);
}
/*
Computes the total unique arrangements starting at configuration n
*/
void totalArrangements(unsigned int n){
//check if this state is already recorded
if (mp[n] != 0) return;
//if no, record it
mp[n]++;
//Convert the integer state to array by unpacking
int temp[3][3] = {0};
unpack(n, temp);
int index_i = -1;
int index_j = -1;
for(int i=0;i<3;i++){
for(int j=0;j<3;j++){
if(temp[i][j] == 0) {
index_i = i;
index_j = j;
break;
}
}
if(index_i != -1 && index_j != -1) break;
}
/*
There are 4 possible ways to move the empty slot.
*/
//RIGHT
if((index_i+1) <= 2){
int n = packArray(temp, index_i, index_j, index_i+1, index_j);
totalArrangements(n);
}
//LEFT
if((index_i-1) >= 0){
int n = packArray(temp, index_i, index_j, index_i-1, index_j);
totalArrangements(n);
}
//DOWN
if((index_j+1) <= 2){
int n = packArray(temp, index_i, index_j, index_i, index_j+1);
totalArrangements(n);
}
//UP
if((index_j-1) >= 0){
int n = packArray(temp, index_i, index_j, index_i, index_j-1);
totalArrangements(n);
}
}
int main()
{
//8 puzzle
/*
1 2 3
4 5 6
7 8 X
*/
int nomatch_count = 0;
vector<int> list;
list.push_back(1);
list.push_back(2);
list.push_back(3);
list.push_back(4);
list.push_back(5);
list.push_back(6);
list.push_back(7);
list.push_back(8);
list.push_back(0);
int temp[3][3] = {0};
for(int i=0;i<list.size();i++){
temp[i/3][i%3] = list[i];
}
totalArrangements(pack(temp));
cout << "Total reachable were " << mp.size() << endl;
return 0;
}
for(int i=0;i<9;i++) {
for(int j=0;j<9;j++){
if(j == i) continue;
for(int k=0;k<9;k++){
if(k == i || k == j) continue;
for(int l=0;l<9;l++){
if(l == i || l == j || l == k) continue;
for(int m=0;m<9;m++){
if(m == i || m == j || m == k || m == l) continue;
for(int n=0;n<9;n++){
if(n == i || n == j || n == k || n == l || n == m) continue;
for(int o=0;o<9;o++){
if(o == i || o == j || o == k || o == l || o == m || o == n) continue;
for(int p=0;p<9;p++){
if(p == i || p == j || p == k || p == l || p == m || p == n || p == o) continue;
for(int q=0;q<9;q++){
if(q == i || q == j || q==k || q==l || q==m || q==n || q == o || q == p) continue;
//Test this configuration
temp[0][0] = list[i];
temp[0][1] = list[j];
temp[0][2] = list[k];
temp[1][0] = list[l];
temp[1][1] = list[m];
temp[1][2] = list[n];
temp[2][0] = list[o];
temp[2][1] = list[p];
temp[2][2] = list[q];
unsigned int t = pack(temp);
int temp1[3][3] = {0};
unpack(t, temp1);
if(mp.find(t) == mp.end()){
nomatch_count++;
}
}
}}}}}}}}
cout << "Total non reachable were " << nomatch_count << endl;
Output of the program was
Total reachable were 181440
Total non reachable were 181440
This was an interesting find out. The states are divided into two islands. One island has states that are unreachable from any state from another island.
Following are few of the unreachable states form the following configuration as reported by the program.
Following are unreachable.
No comments:
Post a Comment