8-puzzle - Functions not working correctly

Projects Programming
1

As part of a homework assignment, I'm trying to code an 8-puzzle into Arduino's Serial Monitor. This involves a 3x3 matrix, assigned unique values from 0 to 8, with the 0 value being the 'blank tile' (represented in the printed output as 'b' as part of the assignment). This blank tile can be moved around the puzzle board via an adjacent tile moving into the space it just was. My code so far looks like this:

int a=0;
int b=0;
int g=0;
int w=0;
int c=0;
int d=0;
int e=0;
int BposX=0;
int BposY=0;
int AposX=0;
int AposY=0;
int AposTemp=0;
int dir=0;
int action=0;

int puzzle[3][3];

void SetState(){
  BposX=0;
  BposY=0;
  for (a=3;a>0;a--){
    for (b=3;b>0;b--){
      puzzle[a][b]=c;
      c++;
    }
  }
}

void printState(){
  for (g=3;g>0;g--){
    for (w=3;w>0;w--){
      if (puzzle[g][w]!=0){
        Serial.print(puzzle[g][w]);
      }
      else{
        Serial.print("b");
      }
    }
    Serial.println();
  }
}

void Move(int dir){
  if (dir=='left'){
    if (BposX>0){
      AposX=BposX-1;
      AposTemp=puzzle[AposX][BposY];
      puzzle[AposX][BposY]=0;
      puzzle[BposX][BposY]=AposTemp;
    }
    else{
      Serial.println("Invalid move.");
    }
  }
  if (dir='right'){
    if(BposX<3){
      AposX=BposX+1;
      AposTemp=puzzle[AposX][BposY];
      puzzle[AposX][BposY]=0;
      puzzle[BposX][BposY]=AposTemp;
    }
    else{
      Serial.println("Invalid move.");
    }
  }
  if (dir='up'){
    if(BposY>0){
      AposY=BposY-1;
      AposTemp=puzzle[BposX][AposY];
      puzzle[BposX][AposY]=0;
      puzzle[BposX][BposY]=AposTemp;
    }
    else{
      Serial.println("Invalid move.");
    }
  }
  if (dir='down'){
    if(BposY<3){
      AposY=BposY+1;
      AposTemp=puzzle[BposX][AposY];
      puzzle[BposX][AposY]=0;
      puzzle[BposX][BposY]=AposTemp;
    }
    else{
      Serial.println("Invalid move.");
    }
  }
  printState();
}

void setup(){
  randomSeed(analogRead(A0));
  SetState();
  Serial.begin(9600);
  printState();
}

void loop(){
  if (Serial.available() > 0) {
    action = Serial.read();
  }
  if (action=='1'){
    Move('left');
    action=0;
  }
  if (action=='2'){
    Move('right');
    action=0;
  }
}

When I upload this and bring up the Serial Monitor, the initial state looks just fine:

b12
345
678

However, when I attempt to enter '1' or '2' to test these out, I get this response:

(Entering '1')
Invalid move.
Invalid move.
b12
4945
678

(Entering '2')
Invalid move.
b12
5045
678

(Entering '1' twice)
Invalid move.
Invalid move.
b12
4945
678

Invalid move.
Invalid move.
b12
1259345
678

It seems like the code is running the 'Move' function multiple times, but I've no idea why. I know I asked the function to return 'Invalid move.' if the move made was out-of-bounds (e.g. moving the blank tile a space to the right when it was already on the right side of the board), but it seems to think the tile's out-of-bounds even when asking for a move to the right when the tile is on the leftmost side of the board.

Can anyone see what might be going wrong?

2

Did you type that all in bold?

Please edit your post and change the quote tags to code taģs. That will prevent the forum software from interpreting [b] as an instruction to make your code bold.

3

Use code tags, not quote tags. If you don't use code tags, then array indexes like [b] or [i] get treated as formatting.

4

Done. Any ideas as to why the functions aren't working as they should?

5

for (a=3;a>0;a--){A three element array has no element with the subscription 3

6

AWOL:
for (a=3;a>0;a--){A three element array has no element with the subscription 3

Tried changing it to 2, but the matrix turned out wrong.

bbb
bb1
b23

Even though you're correct about there being no array address of 3, I guess that part was accidentally right anyway.

7

Auto-completion: subscript.

8

Move('left');'left' will fit in a 32 bit int, but not a 16.
'right' won't fit into either.

9

Changed 'left', 'right', 'up' and 'down' into '1', '2', '3' and '4' respectively. That seems to have helped, but my new issue is that the move functions aren't actually updating the puzzle space for some reason.

New code:

int a=0;
int b=0;
int g=0;
int w=0;
int c=0;
int d=0;
int e=0;
int BposX=0;
int BposY=0;
int AposX=0;
int AposY=0;
int AposTemp=0;
int dir=0;
int action=0;
int n=0;
int f=0;
int h=0;

int puzzle[3][3];

void SetState(){
  BposX=0;
  BposY=0;
  for (a=3;a>0;a--){
    for (b=3;b>0;b--){
      puzzle[a][b]=c;
      c++;
    }
  }
}

void printState(){
  for (g=3;g>0;g--){
    for (w=3;w>0;w--){
      if (puzzle[g][w]!=0){
        Serial.print(puzzle[g][w]);
      }
      else{
        Serial.print("b");
      }
    }
    Serial.println();
  }
  Serial.println("(" + String(BposX) + ", " + String(BposY) + ")");
}

void Move(int dir){
  for (d=2;d>-1;d--){
    for (e=2;e>-1;e--){
      if (puzzle[d][e]==0){
        BposX=d;
        BposY=e;
      }
    }
  }
  if (dir==1){
    if (BposX>0){
      AposTemp=puzzle[BposX-1][BposY];
      puzzle[BposX][BposY]=AposTemp;
      puzzle[BposX-1][BposY]=0;
      BposX--;
    }
    else{
      Serial.println("Invalid move.");
    }
  }
  if (dir==2){
    if(BposX<2){
      AposTemp=puzzle[BposX+1][BposY];
      puzzle[BposX][BposY]=AposTemp;
      puzzle[BposX+1][BposY]=0;
      BposX++;
    }
    else{
      Serial.println("Invalid move.");
    }
  }
  if (dir==3){
    if(BposY>0){
      AposY=BposY-1;
      AposTemp=puzzle[BposX][AposY];
      puzzle[BposX][AposY]=0;
      puzzle[BposX][BposY]=AposTemp;
    }
    else{
      Serial.println("Invalid move.");
    }
  }
  if (dir==4){
    if(BposY<2){
      AposY=BposY+1;
      AposTemp=puzzle[BposX][AposY];
      puzzle[BposX][AposY]=0;
      puzzle[BposX][BposY]=AposTemp;
    }
    else{
      Serial.println("Invalid move.");
    }
  }
  printState();
}

void randomizeState(int n){
  int randomizer[n];
  for(f=n;f>0;f--){
    randomizer[f]=random(1,4);
    Move(randomizer[f]);
  }
}

void solveAstar(int heur){
  
}

void solvebeam(int k){
  
}

void MaxNodes(int n){
  
}

void setup(){
  randomSeed(analogRead(A0));
  SetState();
  Serial.begin(9600);
  printState();
  Move(2);
  Move(1);
  Move(2);
  Move(2);
}

void loop(){
  /*if (Serial.available() > 0) {
    action = Serial.read();
  }
  if (action=='1'){
    Move('left');
    action=0;
  }
  if (action=='2'){
    Move('right');
    action=0;
  }*/
}

I added two nested for loops at the beginning of Move() to keep track of where the 'blank tile' is supposed to be, as well as a few empty and partially-complete functions that will be used later in the assignment.

The list of moves in setup() generates this output:

b12
345
678
(0, 0) //Start

b12
345
678
(1, 0) //Move right

Invalid move.
b12
345
678
(0, 0) //Move left

b12
345
678
(1, 0) //Move right

b12
345
678
(1, 0) //Move right again

10

You still haven't fixed the out-of-bounds array accesses.

I guess that part was accidentally right anyway.

Luck-based and stochastic programming techniques were debunked decades ago.

11

I'm not sure what you mean. The only other spots that access an array row or column at a value of 3 are in the functions printState() and setState(), and changing these from (3,0) to (2,-1) doesn't seem to do anything besides mess up the initial state.

12

changing these from (3,0) to (2,-1)

A three element array has three valid subscripts - 0, 1 or 2.
No negative numbers, no numbers greater than 2.

13

And how would that be put in a decremental for loop? As I understand it, the loop starts at 2, performs its actions, and decreases by 1. I want it to stop at 0, so I put in the for loop for it to only decrement if it's greater than -1 (hence 2 and -1 as upper and lower bounds). This way, the only states that are accessed by the loop should be 2, 1, and 0.

14

Which loop is that?

15

In Move(int dir):

for (d=2;d>-1;d--){
    for (e=2;e>-1;e--){
      if (puzzle[d][e]==0){
        BposX=d;
        BposY=e;
      }
    }

The other ones have their boundaries kept at 3 and 0, as changing these does not seem to fix any issues and in fact causes some new ones:

In setState():

for (a=3;a>0;a--){
    for (b=3;b>0;b--){
      puzzle[a][b]=c;
      c++;
    }
  }

In printState():

for (g=3;g>0;g--){
    for (w=3;w>0;w--){
      if (puzzle[g][w]!=0){
        Serial.print(puzzle[g][w]);
      }
      else{
        Serial.print("b");
      }
    }
    Serial.println();
  }

Those are the only three places that access array bounds of any type.

16

So, fix the ones that need fixing.
Until you do that, all bets about how code behaves are off.

17

Fixed it by rewriting the Move() function entirely, as well as a few others.

int a=0;
int b=0;
int g=0;
int w=0;
int c=0;
int d=0;
int e=0;
int Bpos=0;
int AposTemp=0;
int dir=0;
int action=0;
int n=0;
int f=0;
int h=0;
boolean isValid=true;

int puzzle[8];

void SetState(){
  Bpos=0;
  for (a=0;a<9;a++){
    puzzle[a]=a;
  }
}

void printState(){
  for (g=0;g<9;g++){
    if(puzzle[g]!=0){
      Serial.print(puzzle[g]);
    }
    else{
      Serial.print("b");
    }
    if((g==2)||(g==5)||(g==8)){
      Serial.println();
    }
  }
  Serial.println("(" + String(Bpos) + ")");
}

void Change (int dir){
  if (dir==1){
    if((Bpos!=0)&&(Bpos!=3)&&(Bpos!=6)){
      isValid=true;
      AposTemp=puzzle[Bpos-1];
      puzzle[Bpos]=AposTemp;
      puzzle[Bpos-1]=0;
      Bpos--;
    }
    else{
      isValid=false;
    }
  }
  if (dir==2){
    if((Bpos!=2)&&(Bpos!=5)&&(Bpos!=8)){
      isValid=true;
      AposTemp=puzzle[Bpos+1];
      puzzle[Bpos]=AposTemp;
      puzzle[Bpos+1]=0;
      Bpos++;
    }
    else{
      isValid=false;
    }
  }
  if (dir==3){//up
    if((Bpos!=0)&&(Bpos!=1)&&(Bpos!=2)){
      isValid=true;
      AposTemp=puzzle[Bpos-3];
      puzzle[Bpos]=AposTemp;
      puzzle[Bpos-3]=0;
      Bpos-=3;
    }
    else{
      isValid=false;
    }
  }
  if (dir==4){//down
    if((Bpos!=6)&&(Bpos!=7)&&(Bpos!=8)){
      isValid=true;
      AposTemp=puzzle[Bpos+3];
      puzzle[Bpos]=AposTemp;
      puzzle[Bpos+3]=0;
      Bpos+=3;
    }
    else{
      isValid=false;
    }
  }
  if(isValid==false){
    if(dir==4){
      dir=1;
    }
    else{
      Change(random(1,5));//BUG: Has 25% chance of making reverse
      //move, thus resulting in no action for this iteration.
    }
  }
  printState();
}

void Move(int dir){
  if (dir==1){
    if((Bpos!=0)&&(Bpos!=3)&&(Bpos!=6)){
      AposTemp=puzzle[Bpos-1];
      puzzle[Bpos]=AposTemp;
      puzzle[Bpos-1]=0;
      Bpos--;
    }
    else{
      Serial.println("Invalid move.");
    }
  }
  if (dir==2){
    if((Bpos!=2)&&(Bpos!=5)&&(Bpos!=8)){
      AposTemp=puzzle[Bpos+1];
      puzzle[Bpos]=AposTemp;
      puzzle[Bpos+1]=0;
      Bpos++;
    }
    else{
      Serial.println("Invalid move.");
    }
  }
  if (dir==3){//up
    if((Bpos!=0)&&(Bpos!=1)&&(Bpos!=2)){
      AposTemp=puzzle[Bpos-3];
      puzzle[Bpos]=AposTemp;
      puzzle[Bpos-3]=0;
      Bpos-=3;
    }
    else{
      Serial.println("Invalid move.");
    }
  }
  if (dir==4){//down
    if((Bpos!=6)&&(Bpos!=7)&&(Bpos!=8)){
      AposTemp=puzzle[Bpos+3];
      puzzle[Bpos]=AposTemp;
      puzzle[Bpos+3]=0;
      Bpos+=3;
    }
    else{
      Serial.println("Invalid move.");
    }
  }
  printState();
}

void randomizeState(int n){
  int randomizer[n];
  for(f=n;f>0;f--){
    randomizer[f]=random(1,5);
    Change(randomizer[f]);
  }
}

void solveAstar(int heur){
  
}

void solvebeam(int k){
  
}

void MaxNodes(int n){
  
}

void setup(){
  randomSeed(analogRead(A0));
  SetState();
  Serial.begin(9600);
  printState();
  randomizeState(6);
}

void loop(){
  /*if (Serial.available() > 0) {
    action = Serial.read();
  }
  if (action=='1'){
    Move('left');
    action=0;
  }
  if (action=='2'){
    Move('right');
    action=0;
  }*/
}

Change() is a variant of Move() that is specifically used by the randomizeState(n) function, as it does not return an 'Invalid move' message but instead makes another random move to continue randomizing the puzzle. However, I've noticed that the code I put in there to change the move to another random move will occasionally result in nothing happening (the blank tile stays right where it is for that particular step). At first I thought it was making a move and then moving back, but it would never make the first move in the first place if the direction it attempted to move in was impossible, so now I'm confused.

The goal of randomizeState(n) is to move the blank tile 'b' a pre-specified number of moves n in random directions away from the goal state (b12 345 678). This ensures that for later parts of the assignment, where the quickest solution is calculated, that a solution actually exists for that 'random' puzzle (as apparently not all configurations of this puzzle have the goal state as a viable solution). In moving n number of times, each movement should be an actual move in a viable direction, as otherwise moves would be 'skipped' and the actual number of moves away from the goal state would be lower. In order to move randomly, randomizeState sets up a queue array of moves it will make, with an array length of n. It fills these array values with random numbers containing either 1, 2, 3, or 4 (the respective directions), and then executes them by passing the numbers as an argument to Change() in reverse order (from randomizer[n] to randomizer[0]). Why is there an occasional move where nothing happens?

Example output for randomizeStates(n) of n=6:

(3x3 is the puzzle matrix, and the number in parentheses is the position of the blank tile from 0 to 8)

b12
345
678
(0)//Start

312
b45
678
(3)//moved down

b12
345
678
(0)//moved up

b12
345
678
(0)//did nothing!

1b2
345
678
(1)//moved right

1b2
345
678
(1)//did nothing!

1b2
345
678
(1)//did nothing!

142
3b5
678
(4)//moved down

1b2
345
678
(1)//moved up

142
3b5
678
(4)//moved down

18 
for (a=3;a>0;a--){
    for (b=3;b>0;b--){
      puzzle[a][b]=c;
      c++;
    }
  }

I'm just curious, what would you see if you ran a loop to print puzzle[3][0] thru puzzle[0][0] to the serial monitor?

What would you expect to see?

19

I'd be inclined to code this the other way around. - have an array of positions for each number, rather than numbers for each position. To print out the grid, make a blank 3*3 grid and run through the list of numbers once to fill it in. Then print that grid.