15-Puzzle (part I)

Part I of this ’15-Puzzle’ project was writing a simple sketch that shows the puzzle in its solved state, then shuffles it and lets you solve it manually. The more challenging part, of course, will be to write a generic solver algorithm that fits inside the limited memory of an Arduino Uno (and finishes within a reasonable amount of time).

First, I considered the following algorithms:

Human approach algorithm. Reasonably simple to write, but it’s not likely to find the fastest solution in terms of moves. It also becomes more complicated if you want to program the tricks that humans develop by thinking moves ahead.
Dijkstra’s algorithm, which would be a nice tribute to my former teacher. It will find the shortest solution, but may not fit into an Uno (and may be rather slow as well).
An A* algorithm (had never heard of it until today). It promises to find the shortest solution and, based on heuristics, will usually be faster than Dijkstra.

It didn’t take long before I realized that options 2 and 3 are definitely out of Arduino Uno’s league. Being graph search algorithms, they require storage of many nodes and paths during the search process. Since every node is a permutation of 16 digits, the sketch would certainly run out of memory.

So what remains is the challenge of implementing option 1. For nostalgic reasons, I’m going to use a method that I figured out when I was 8 years old (so probably not the most efficient way to solve this puzzle).

Will be continued. For now, here’s the sketch of part I:

/* pF 2018 - '15-puzzle' op Adafruit 480x320 TFT touchscreen */

#include <SPI.h>
#include "Adafruit_GFX.h"
#include "Adafruit_HX8357.h"
#include "TouchScreen.h"

// Touchscreen pinnen:
#define YP A2  
#define XM A3  
#define YM 7   
#define XP 5  

// Calibration data 
#define TS_MINX 110
#define TS_MINY 80
#define TS_MAXX 900
#define TS_MAXY 940

#define MINPRESSURE 10
#define MAXPRESSURE 1000

#define TFT_CS 10
#define TFT_DC 9
#define TFT_RST -1

Adafruit_HX8357 tft = Adafruit_HX8357(TFT_CS, TFT_DC, TFT_RST);

TouchScreen ts = TouchScreen(XP, YP, XM, YM, 300);

// Boekhouding (met redundantie, voor het gemak en de overzichtelijkheid van de sketch):

// bord[rij][kolom]
int bord[4][4] = {{1,2,3,4},{5,6,7,8},{9,10,11,12},{13,14,15,0}};

// pos[getal][0] geeft rij-index huidige positie getal
// pos[getal][1] geeft kolom-index huidige positie getal
int pos[16][2] = {{3,3},{0,0},{0,1},{0,2},{0,3},{1,0},{1,1},{1,2},{1,3},{2,0},{2,1},{2,2},{2,3},{3,0},{3,1},{3,2}};

// extra: rij- en kolomindex van de blank ('0')
int blank_pos[2] = {3,3};

//posities in dr en dk (increment) arrays corresponderen met resp. boven,rechts,onder,links
int dr[4] = {-1,0,1,0};
int dk[4] = {0,1,0,-1};

// x,y touch ranges behorende bij de vakken:
// kolommen (bij orientation 3 aangegeven door p.y !):
const int x_range [4][2] = {
  {800,900},  // linker kolom
  {670,760},  // ..
  {530,630},  // ..
  {390,485}   // rechter kolom
                 
};
// rijen (bij orientation 3 aangegeven door p.x !):
const int y_range [4][2] = {
  {175,295},  // bovenste rij
  {350,480},  // ..
  {550,670},  // ..
  {735,850}   // onderste rij                  
};

int touched_r,touched_k;

void setup() {
  randomSeed(analogRead(0));
  tft.begin(HX8357D);
  tft.setRotation(3); // landscape met SPI header pins links
  tft.fillScreen(HX8357_BLACK); // achtergrond scherm
  tft.fillRect(0,0,320,320,HX8357_RED);  // kleur rand 
  tft.fillRect(5,5,310,310,0xBB00);  // achtergrond bord
  tft.setTextColor(HX8357_RED); 
  tft.setTextSize(4);
  
  //Serial.begin(9600); // voor debuggen en touch kalibratie
  
  for (int v=0;v<16;v++) {
    draw(v);
  }
  //print_it();
  delay(1000);
  int z=0;
  while (z<99) {  // telt tot er 99 legale random swaps zijn gedaan
    if (swap(random(0,4))) {
      //print_it();
      z++;
      //delay(100);
    }
  }
}

void loop() {
      TSPoint p = ts.getPoint();
      if (p.z > MINPRESSURE && p.z < MAXPRESSURE && p.x>20) { // real click, no noise
        if (field_match(p.x,p.y)) {
          // kijken of het geklikte vlak grenst aan blank
          boolean swaped = false;
          for (int g=0;g<4;g++) {
            if (!(touched_r+dr[g]<0 || touched_r+dr[g]>3 || touched_k+dk[g]<0 || touched_k+dk[g]>3)) {
              if (touched_r+dr[g] == blank_pos[0] && touched_k+dk[g] == blank_pos[1]) {
                swap((g+2)%4);
                swaped = true;
              }
            }
            if (swaped) break;
          }
          delay(200);
        }
      } 
}

boolean swap(int nozw) {
  // nozw waarden 0,1,2,3 corresponderen met boven, rechts, onder,links van de 'blank' - de richting waarin de blank wordt geschoven
  int swap_r = blank_pos[0]+dr[nozw];
  int swap_k = blank_pos[1]+dk[nozw];
  
  // check geldigheid rij en kolom:
  if (swap_r<0 || swap_r>3 || swap_k<0 || swap_k>3) return false;

  // swap geldig, nu de arrays bord, pos en blank_pos bijwerken
  int swap_waarde = bord[swap_r][swap_k]; 
  bord[swap_r][swap_k] = 0;  // nieuwe positie blank
  bord[blank_pos[0]][blank_pos[1]] = swap_waarde; 
  pos[0][0] = swap_r;  // nieuwe rij index blank
  pos[0][1] = swap_k;  // nieuwe kolom index blank
  pos[swap_waarde][0] = blank_pos[0];
  pos[swap_waarde][1] = blank_pos[1];
  blank_pos[0] = swap_r;
  blank_pos[1] = swap_k;

  // nu de grafische uitwerking:
  draw(0);
  draw(swap_waarde);
  return true;
}

void draw(int digit) {
  int row = pos[digit][0];
  int col = pos[digit][1];
  if (digit == 0) {
    tft.fillRoundRect(7+col*77,7+row*77,75,75,10,0xBB00);
  } else {
    tft.fillRoundRect(7+col*77,7+row*77,75,75,10,0xFF19);
    if (digit<10) {
      tft.setCursor(36+col*77,30+row*77);
    } else {
      tft.setCursor(20+col*77,30+row*77);
    }
    tft.print(digit);
  }
}

boolean field_match(int px, int py) {
      // px en py zijn de geregistreerde p.x en p.y van touch; NB: bij orientation 3 geldt:
      // p.x geeft de rij aan, p.y de kolom. De procedure vertaalt dit naar r en c
      for (int r=0;r<4;r++) {
        if (px>y_range[r][0] && px<y_range[r][1]) {
          // px past in rij; nu de kolom
          for (int c=0;c<4;c++) {
            if (py>x_range[c][0] && py<x_range[c][1]) {
              // py valt ook in kolom dus deze touch valt binnen een veld!
              touched_k = c;
              touched_r = r;
              return true; // geklikt binnen veld (touched_r,touched_k)
            }
          }
        }
      }
      return false; // geen geldige mapping
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

144

145

146

147

148

149

150

151

152

153

154

155

156

157

158

159

160

161

162

163

164

165

166

167

168

169

170

171

/* pF 2018 - '15-puzzle' op Adafruit 480x320 TFT touchscreen */

#include <SPI.h>

#include "Adafruit_GFX.h"

#include "Adafruit_HX8357.h"

#include "TouchScreen.h"

// Touchscreen pinnen:

#define YP A2

#define XM A3

#define YM 7

#define XP 5

// Calibration data

#define TS_MINX 110

#define TS_MINY 80

#define TS_MAXX 900

#define TS_MAXY 940

#define MINPRESSURE 10

#define MAXPRESSURE 1000

#define TFT_CS 10

#define TFT_DC 9

#define TFT_RST -1

Adafruit_HX8357 tft = Adafruit_HX8357(TFT_CS, TFT_DC, TFT_RST);

TouchScreen ts = TouchScreen(XP, YP, XM, YM, 300);

// Boekhouding (met redundantie, voor het gemak en de overzichtelijkheid van de sketch):

// bord[rij][kolom]

int bord[4][4] = {{1,2,3,4},{5,6,7,8},{9,10,11,12},{13,14,15,0}};

// pos[getal][0] geeft rij-index huidige positie getal

// pos[getal][1] geeft kolom-index huidige positie getal

int pos[16][2] = {{3,3},{0,0},{0,1},{0,2},{0,3},{1,0},{1,1},{1,2},{1,3},{2,0},{2,1},{2,2},{2,3},{3,0},{3,1},{3,2}};

// extra: rij- en kolomindex van de blank ('0')

int blank_pos[2] = {3,3};

//posities in dr en dk (increment) arrays corresponderen met resp. boven,rechts,onder,links

int dr[4] = {-1,0,1,0};

int dk[4] = {0,1,0,-1};

// x,y touch ranges behorende bij de vakken:

// kolommen (bij orientation 3 aangegeven door p.y !):

const int x_range [4][2] = {

{800,900}, // linker kolom

{670,760}, // ..

{530,630}, // ..

{390,485} // rechter kolom

};

// rijen (bij orientation 3 aangegeven door p.x !):

const int y_range [4][2] = {

{175,295}, // bovenste rij

{350,480}, // ..

{550,670}, // ..

{735,850} // onderste rij

};

int touched_r,touched_k;

void setup() {

randomSeed(analogRead(0));

tft.begin(HX8357D);

tft.setRotation(3); // landscape met SPI header pins links

tft.fillScreen(HX8357_BLACK); // achtergrond scherm

tft.fillRect(0,0,320,320,HX8357_RED); // kleur rand

tft.fillRect(5,5,310,310,0xBB00); // achtergrond bord

tft.setTextColor(HX8357_RED);

tft.setTextSize(4);

//Serial.begin(9600); // voor debuggen en touch kalibratie

for (int v=0;v<16;v++) {

draw(v);

}

//print_it();

delay(1000);

int z=0;

while (z<99) { // telt tot er 99 legale random swaps zijn gedaan

if (swap(random(0,4))) {

//print_it();

z++;

//delay(100);

}

void loop() {

TSPoint p = ts.getPoint();

if (p.z > MINPRESSURE && p.z < MAXPRESSURE && p.x>20) { // real click, no noise

if (field_match(p.x,p.y)) {

// kijken of het geklikte vlak grenst aan blank

boolean swaped = false;

for (int g=0;g<4;g++) {

if (!(touched_r+dr[g]<0 || touched_r+dr[g]>3 || touched_k+dk[g]<0 || touched_k+dk[g]>3)) {

if (touched_r+dr[g] == blank_pos[0] && touched_k+dk[g] == blank_pos[1]) {

swap((g+2)%4);

swaped = true;

}

if (swaped) break;

}

delay(200);

}

boolean swap(int nozw) {

// nozw waarden 0,1,2,3 corresponderen met boven, rechts, onder,links van de 'blank' - de richting waarin de blank wordt geschoven

int swap_r = blank_pos[0]+dr[nozw];

int swap_k = blank_pos[1]+dk[nozw];

// check geldigheid rij en kolom:

if (swap_r<0 || swap_r>3 || swap_k<0 || swap_k>3) return false;

// swap geldig, nu de arrays bord, pos en blank_pos bijwerken

int swap_waarde = bord[swap_r][swap_k];

bord[swap_r][swap_k] = 0; // nieuwe positie blank

bord[blank_pos[0]][blank_pos[1]] = swap_waarde;

pos[0][0] = swap_r; // nieuwe rij index blank

pos[0][1] = swap_k; // nieuwe kolom index blank

pos[swap_waarde][0] = blank_pos[0];

pos[swap_waarde][1] = blank_pos[1];

blank_pos[0] = swap_r;

blank_pos[1] = swap_k;

// nu de grafische uitwerking:

draw(0);

draw(swap_waarde);

return true;

}

void draw(int digit) {

int row = pos[digit][0];

int col = pos[digit][1];

if (digit == 0) {

tft.fillRoundRect(7+col*77,7+row*77,75,75,10,0xBB00);

} else {

tft.fillRoundRect(7+col*77,7+row*77,75,75,10,0xFF19);

if (digit<10) {

tft.setCursor(36+col*77,30+row*77);

} else {

tft.setCursor(20+col*77,30+row*77);

}

tft.print(digit);

}

boolean field_match(int px, int py) {

// px en py zijn de geregistreerde p.x en p.y van touch; NB: bij orientation 3 geldt:

// p.x geeft de rij aan, p.y de kolom. De procedure vertaalt dit naar r en c

for (int r=0;r<4;r++) {

if (px>y_range[r][0] && px<y_range[r][1]) {

// px past in rij; nu de kolom

for (int c=0;c<4;c++) {

if (py>x_range[c][0] && py<x_range[c][1]) {

// py valt ook in kolom dus deze touch valt binnen een veld!

touched_k = c;

touched_r = r;

return true; // geklikt binnen veld (touched_r,touched_k)

}

return false; // geen geldige mapping

}