Swap

[Jason Menard]

There are 5 balls in a 2 by 3 grid. You need to move 1 ball horizontally or vertically at a time to the empty slot to make ball 1 and ball 2 switch position. The final positions of balls 3, 4, and 5 aren't important. Determine a solution using as few moves as possible.
Starting Grid

[5][ ][1]
[4][3][2]

Possible Ending Grid

[x][x][2]
[x][ ][1]

[ July 03, 2003: Message edited by: Jason Menard ]

[David Weitzman]

Argh. Stop posting all these neat little problems -- I don't have time to be solving them! (Instead of a breadth-first search, I'd use depth-first with iterative deepening to save memory. Muhahahaha! Except I have work I'm supposed to be doing...)

[David Hibbs]

First attempt was 21 moves in about 5 minutes. =)
(skipping a move each time...)
5x1 (original)
432
512
43x
512
x43
1x2
543
142
53x
1x4
532
134
x52
3x4
152
354
x12
and a final 5 shuffles to get them around to
542
3x1
which, neatly, has the numbers all in reverse order from where they started (CCW instaed of CW).

[Michael Dunn]

Not sure what response you're after, but here goes anyway - don't laugh if you didn't really want it in java
Also, don't know how the format of this will come out - something about UBB tags? (unfamiliar territory - I've clicked on "Instant UBB Code" -Code).

import javax.swing.*;
import java.awt.*;
import java.awt.event.*;
import java.util.*;
 
class BallSwap extends JFrame implements ActionListener
{
  private static JButton btn[] = new JButton[6];
  private static JButton compSolBtn = new JButton ("Computer Solution");
  private static JButton newGameBtn = new JButton("New Game");
  private static JLabel infoLbl = new JLabel();
  private static int moves = 0;
  private static int freeSquare = 1;
  private static boolean gameOver = false;
  private static int tmrCtr = 0;
 
  public static void main(String args[])
  {
    BallSwap bs = new BallSwap();
  }
 
  public BallSwap()
  {
    super("Ball Swap");
    setSize(300,300);
    setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);
    setVisible(true);
 
    Container frame = getContentPane();
    frame.setLayout(new BorderLayout());
    JPanel upper = new JPanel(new FlowLayout());
    upper.add(infoLbl);
    JPanel mid = new JPanel(new GridLayout(2,3));
    for(int i = 0; i < btn.length; i++)
    {
      btn[i] = new JButton();
      btn[i].addActionListener(this);
      btn[i].setPreferredSize(new Dimension(40,40));
      btn[i].setFont(new Font("Courier",Font.BOLD, 16));
      mid.add(btn[i]);
    }
    JPanel lower = new JPanel(new FlowLayout());
    compSolBtn.addActionListener(this);
    newGameBtn.addActionListener(this);
    lower.add(compSolBtn);
    lower.add(newGameBtn);
    frame.add(upper,BorderLayout.NORTH);
    frame.add(mid,BorderLayout.CENTER);
    frame.add(lower,BorderLayout.SOUTH);
    pack();
    setContentPane(frame);
    newGame();
  }
 
  private static void newGame()
  {
    btn[0].setText("5");
    btn[1].setText("");
    btn[2].setText("1");
    btn[3].setText("4");
    btn[4].setText("3");
    btn[5].setText("2");
    infoLbl.setText("Click square to swap with vacant square");
    moves = 0;
    freeSquare = 1;
    gameOver = false;
    tmrCtr = 0;
  }
 
  public void actionPerformed(ActionEvent ae)
  {
    if(ae.getSource() == newGameBtn)
    {
      newGame();
    }
    else if(ae.getSource() == compSolBtn)
    {
      showComputerSolution();
    }
    else
    {
      for(int i = 0; i < btn.length; i++)
      {
        if(ae.getSource() == btn[i])
        {
          moveTheSquares(i);
          break;
        }
      }
    }
  }
 
  private static void moveTheSquares(int sq)
  {
    if(!gameOver && sq != freeSquare &&
      (Math.abs(freeSquare-sq) == 1 || sq%3 == freeSquare%3))
    {
      btn[freeSquare].setText(btn[sq].getText());
      btn[sq].setText("");
      freeSquare = sq;
      moves++;
      infoLbl.setText("Moves made = "+moves);
      if(btn[2].getText().equals("2") && btn[5].getText().equals("1"))
      {
        infoLbl.setText("Game over - total moves = "+moves);
        gameOver = true;
      }
    }
  }
 
  private static void showComputerSolution()
  {
    newGame();
    final int moveFrom[] = {4,5,2,1,4,3,0,1,4,5,2,1,4,5,2,1,0,3,4,5,2,1};
    final java.util.Timer tmr = new java.util.Timer();
    tmr.scheduleAtFixedRate(new TimerTask(){
      public void run(){
        moveTheSquares(moveFrom[tmrCtr++]);
        if(tmrCtr==22)tmr.cancel();
      }
    },500,500);
  }
 
  public void setVisible(boolean visible)
  {
    if(visible)
    {
      Dimension dim = Toolkit.getDefaultToolkit().getScreenSize();
      setLocation((dim.width - getWidth())/2, (dim.height - getHeight())/2);
    }
 
    super.setVisible(visible);
  }
}

[Edited to fix the code tags. You created the tags correctly, but your code needs to go between them. --Jason]
[ June 13, 2003: Message edited by: Jason Menard ]

[David Weitzman]

I've got a 17 move solution obtained with code that hasn't been tested too carefully.

[Greg Harris]

i got a 17 move solution using michael's program (nice, by the way). however, i did not pay attention, so i cannot tell you what i did.

[Greg Harris]

here it is:
1-2-3-1-5-4-1-3-2-5-3-1-4-3-5-2-1

[David Weitzman]

Yup -- that's the solution I got. Here's the code I used. It's not very polished. More significantly, it's not Java. It seemed like a convenient excuse to test a new C++ editor (Dev-C++ kept crashing my comp).
It's a somewhat ugly solution, but at least it works.

#include <iostream>
#include <vector>
#include <cstdlib>
#include <algorithms>
using namespace std;
 
const int WIDTH = 3;
const int HEIGHT = 2;
char * grid = "5 1432";
 
char get(int row, int col) {
  if (row >= 0 && row < HEIGHT && col >= 0 && col < WIDTH) {
    return grid[row * WIDTH + col];
  } else {
    cout << "Requested grid location out of bounds!";
    abort();
  }
}
 
class Move{
  public:
  Move(int fromRow, int fromCol, int toRow, int toCol):
    from(fromRow*WIDTH + fromCol),
    to(toRow*WIDTH + toCol)
  {
  };
  int from, to;
};
 
ostream& operator<<(ostream& stream, const Move& move) {
  stream << grid[move.from] << " ";
  return stream;
}
 
vector<Move> getPossibleMoves() {
  vector<Move> moves;
  for (int row = 0; row < HEIGHT; row++) {
    for (int col = 0; col < WIDTH; col++) {
      if (get(row, col) == ' ') {
        if (row > 0)
    moves.push_back(Move(row - 1, col, row, col));
  
  if (row + 1 < HEIGHT)
    moves.push_back(Move(row + 1, col, row, col));
    
        if (col > 0)
    moves.push_back(Move(row, col - 1, row, col));
  
  if (col + 1 < WIDTH)
    moves.push_back(Move(row, col + 1, row, col));
}
 }
  }
  return moves;
}
 
void makeMove(const Move m) {
  swap(grid[m.from], grid[m.to]);
}
 
bool solve(int n) {
  if (n == 0) {
    if (get(0, 2) == '2' && get(1, 2) == '1') {
      // Found the solution
      return true;
 } else return false;
  }
 
  vector<Move> moves(getPossibleMoves());
  for (unsigned int i =0; i < moves.size(); i++) {
    makeMove(moves[i]);
    bool solved = solve(n-1);
    makeMove(moves[i]);
    if (solved) {
      cout << moves[i];
      return true;
 }
  } 
  return false;
}
 
int main(int argc, char *argv[])
{ 
  bool solved = false;
  for (int i = 0; i < 24; i++) {
    cout << "Trying solutions of length " << i << "..." << endl;
    if (solve(i)) {
      cout << endl << "Solved! (moves in reverse order)" << endl;
      solved = true;
      break;
 }
  }
  if (!solved) cout << "Unable to solve in 24 moves" << endl;
  system("pause");
}

[Jason Menard]

It's a somewhat ugly solution, but at least it works.
Damn right it is! It's in C++!

[Greg Harris]

>Damn right it is! It's in C++!
well, i am taking a "linux systems programming" class using C this summer... so it could be worse!

[David Weitzman]

Actually I've used mostly C and not much in the way of ++. I wonder if I can do a bit of evil optimizing...

[David Weitzman]

This C version finds a solution in about 5 seconds even on my slow comp. It's basically the same idea as above, but faster :

#include <stdlib.h>
#include <stdio.h>
#include <assert.h>
#define MAX_MOVES 19
#define TRUE 1
#define FALSE 0
const int WIDTH = 3;
const int HEIGHT = 2;
char moveList[MAX_MOVES + 1];
char * grid = "5 1432";
int empty_spot;
typedef struct {
  int from, to;
} Move;
const Move NULL_MOVE = {-1, -1};
Move createMove(int fromRow, int fromCol, int toRow, int toCol) {
  Move m;
  m.from = fromRow*WIDTH + fromCol;
  m.to = toRow*WIDTH + toCol;
  return m;
}
char* movePrintBuffer = "  ";
void printMove(Move move) {
  movePrintBuffer[0] = grid[move.from];
  puts(movePrintBuffer);
}
void printGrid() {
  printf("[%c][%c][%c]\n", grid[0], grid[1], grid[2]);
  printf("[%c][%c][%c]\n\n", grid[3], grid[4], grid[5]);
}
void makeMove(Move m) {
  char c;
  
  // printGrid(); printf("Space at %i\n", empty_spot);
  
  c = grid[m.from];
  grid[m.from] = grid[m.to];
  grid[m.to] = c;
  
  if (grid[m.from] == ' ') empty_spot = m.from;
  else empty_spot = m.to;
  
  // printGrid(); printf("Space at %i\n", empty_spot);
  // system("pause");
}
int solve(int n) {
  int row, col, i, solved;
  Move possibleMoves[4];
  if (n == 0) {
    if (grid[2] == '2' && grid[5] == '1') {
      // Found the solution
      return TRUE;
 } else return FALSE;
  }
  row = empty_spot / WIDTH;
  col = empty_spot % WIDTH;
  if (row > 0)
    possibleMoves[0] = createMove(row - 1, col, row, col);
  else
    possibleMoves[0] = NULL_MOVE;
  
  if (row + 1 < HEIGHT)
    possibleMoves[1] = createMove(row + 1, col, row, col);
  else
    possibleMoves[1] = NULL_MOVE;
    
  if (col > 0)
    possibleMoves[2] = createMove(row, col - 1, row, col);
  else
    possibleMoves[2] = NULL_MOVE;
  
  if (col + 1 < WIDTH)
    possibleMoves[3] = createMove(row, col + 1, row, col);
  else
    possibleMoves[3] = NULL_MOVE;
  
  for (i = 0; i < 4; i++) {
    if (possibleMoves[i].from == -1) continue;
    makeMove(possibleMoves[i]);
    solved = solve(n-1);
    makeMove(possibleMoves[i]);
    if (solved) {
      moveList[n] = grid[possibleMoves[i].from];
      return TRUE;
 }
  } 
  return FALSE;
}
int main(int argc, char *argv[])
{ 
  int i;
  int solved = FALSE;
  for (i = 0; i < WIDTH * HEIGHT; i++) {
    if (grid[i] == ' ') empty_spot = i;
  }
  for (i = 1; i <= MAX_MOVES; i++) {
    printf("Trying solutions of length %i...\n", i);
    if (solve(i)) {
      puts("\nSolved! (moves in reverse order)\n");
      solved = TRUE;
      break;
 }
  }
  if (!solved) printf("Unable to solve in %i moves\n", MAX_MOVES);
  else {
    printf("%c", moveList[1]);
    for (i = 2; i <= MAX_MOVES; i++) {
      if (moveList[i]) {
        printf("<-%c", moveList[i]);
}
 }
 puts("\n");
  }
  system("pause");
  return 0;
}

[ June 13, 2003: Message edited by: David Weitzman ]