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:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 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 } |