Encoding knights-tour_construction.cpp

Name	knights-tour_construction.cpp
Class Tree	[Root] Miscellaneous (45) ASP Contest 09 (45) Special-Purpose Encodings and Tools (4)
Submitter	Martin Gebser
Author	Martin Gebser and Roland Kaminski
Description	A C++ program that computes a Knight's Tour (if there is any) for a given checkerboard size in very short time. Compiling under Linux: g++ -o knightstour knights-tour_construction.cpp Usage on Linux shell (N is an integer): echo "size(N)" \| knightstour Usage on Linux shell (using file): knightstour < <instance>
Created	2009-03-27 12:58
Modified	2009-04-01 00:54
Languages
Language Features
Compatible Instance Classes
Input Predicates	size/1
Output Predicates	move/4
Encoding Parameter
Standalone	No
Tags
Attributes
Content	#include <cstdio> #include <cstdlib> #include <cassert> using namespace std; int size; int path; int path6x6[] = {1,2,2,0,1,4,1,1,2,3,1,3,0,2,3,0,3,1,0,1,3,3,0,3,4,1,0,0,1,0,4,4,0,5,0,4,5,1,5,0,5,3,2,5,1,5,4,3,2,1,2,2,5,4,5,5,5,2,2,4,4,2,3,2,4,0,4,5,3,5,3,4}; int path6x8[] = {2,1,2,0,1,4,2,2,1,2,2,4,2,5,1,5,3,1,2,3,0,0,0,1,2,6,2,7,0,4,0,5,4,1,0,2,1,0,4,4,0,3,4,6,0,7,0,6,1,1,5,0,5,3,5,2,1,3,4,7,1,7,1,6,3,2,3,3,5,4,5,1,5,6,5,7,3,4,5,5,4,2,3,0,4,0,4,5,3,5,4,3,3,7,3,6}; int path8x6[] = {2,1,2,0,1,4,1,5,2,5,1,3,3,1,0,3,0,0,0,1,3,5,3,4,3,2,0,2,1,0,0,4,0,5,3,3,1,1,1,2,4,4,4,5,5,3,2,3,6,1,2,2,3,0,6,4,6,5,2,4,7,1,7,0,4,0,7,4,7,5,4,3,4,1,4,2,5,0,5,1,7,2,7,3,6,2,5,2,6,0,5,4,5,5,6,3}; int path8x8[] = {2,1,2,0,2,3,2,2,1,2,2,6,2,5,1,5,3,1,3,2,0,0,0,1,3,5,3,4,0,4,0,5,4,1,0,2,1,0,4,4,0,3,1,3,0,7,0,6,1,1,5,0,5,1,1,4,4,2,4,7,1,7,1,6,6,1,6,0,3,0,6,4,6,3,2,4,2,7,5,5,7,1,7,0,4,0,7,4,3,3,7,6,3,7,3,6,7,2,7,3,4,3,7,5,4,5,7,7,5,4,4,6,6,2,5,2,5,3,6,5,6,6,6,7,5,7,5,6}; int path8x10[] = {1,2,2,0,1,0,1,1,2,5,1,3,1,4,1,9,1,6,1,7,3,1,3,0,0,4,3,4,0,2,0,7,2,8,0,5,0,6,2,7,3,2,0,0,0,1,3,5,0,3,4,4,3,8,0,8,0,9,3,7,2,2,5,0,4,0,2,1,5,5,4,3,1,5,4,9,4,6,1,8,6,1,5,3,2,3,6,4,5,6,2,4,5,4,2,6,2,9,6,8,7,1,7,0,6,0,4,5,3,3,6,3,7,5,3,6,3,9,4,7,4,1,7,3,7,4,4,2,7,2,7,7,7,8,7,9,7,6,4,8,6,2,5,2,5,1,6,5,6,6,6,7,5,7,6,9,5,9,5,8}; int path10x8[] = {1,2,2,0,1,0,1,1,2,5,1,3,1,4,1,5,2,2,2,3,3,1,3,4,0,2,0,3,3,7,0,5,3,2,0,0,0,1,0,4,1,6,1,7,0,7,0,6,5,1,4,3,4,0,2,1,4,6,2,7,2,4,4,5,5,2,3,3,3,0,3,5,6,3,5,3,6,7,2,6,7,1,7,0,6,4,6,1,6,2,4,7,4,4,3,6,4,1,4,2,5,0,8,4,8,5,5,7,5,4,8,6,9,1,9,0,6,0,6,5,9,3,9,6,5,5,5,6,7,2,7,3,9,4,9,5,9,2,9,7,7,4,6,6,8,2,8,3,8,0,8,1,7,5,8,7,7,7,7,6}; int path10x10[] = {1,2,2,0,1,0,2,2,2,5,1,3,1,4,1,5,2,7,1,7,3,1,3,0,0,4,0,1,0,2,0,3,2,8,2,9,0,6,0,7,3,2,0,0,4,1,1,1,1,6,3,7,0,5,1,9,0,9,0,8,4,2,5,0,5,1,2,1,2,6,2,3,4,8,4,9,5,9,1,8,6,1,6,0,3,4,2,4,6,5,6,6,3,8,6,8,5,6,5,7,7,1,6,3,4,0,4,5,3,3,7,6,3,5,3,6,3,9,6,7,5,2,8,0,7,4,4,4,4,3,4,6,4,7,5,5,8,9,7,7,9,1,9,0,9,3,9,4,5,3,5,4,8,8,9,8,9,9,5,8,9,2,6,2,7,0,6,4,9,6,7,3,7,8,9,5,6,9,9,7,8,2,7,2,8,4,8,1,8,6,8,3,7,5,8,5,7,9,8,7}; int path10x12[] = {1,2,2,0,1,0,1,1,2,5,1,3,1,4,2,8,1,6,1,7,2,11,1,9,3,1,3,2,0,4,0,1,0,2,0,3,3,7,2,9,0,6,3,10,3,9,0,9,4,1,0,0,4,3,3,5,0,5,4,6,0,7,0,8,4,9,0,10,0,11,4,10,2,2,5,2,4,0,2,1,5,5,4,7,1,5,5,8,2,6,1,8,1,11,1,10,6,1,5,3,2,3,6,4,6,5,2,4,6,7,5,9,2,7,6,8,3,8,2,10,7,1,3,0,7,3,3,4,3,3,7,6,4,4,3,6,6,10,4,11,3,11,6,9,7,2,8,0,5,0,4,2,8,5,8,6,4,5,8,8,5,6,4,8,8,11,7,9,9,1,9,0,5,1,8,1,6,2,5,4,9,7,9,8,5,7,9,10,5,11,5,10,9,2,6,0,7,0,9,5,6,3,9,3,9,4,6,6,9,6,9,11,6,11,9,9,8,2,8,3,8,4,7,4,7,5,8,7,7,7,8,9,8,10,7,8,7,11,7,10}; int path12x10[] = {2,1,2,0,1,0,1,1,2,5,1,3,1,4,2,8,1,6,1,7,2,2,2,3,0,0,3,4,3,5,0,3,0,4,0,5,0,6,2,7,3,2,0,2,0,1,3,1,1,2,3,7,0,7,1,5,0,9,0,8,4,2,4,3,4,0,4,1,4,6,5,4,2,4,4,9,1,9,1,8,5,2,5,3,5,0,5,5,6,5,6,6,3,8,2,6,2,9,5,7,7,1,3,0,6,4,6,1,3,3,3,6,4,4,4,5,3,9,4,7,8,1,7,3,7,0,5,1,7,6,8,4,7,4,7,9,5,6,4,8,8,2,8,3,6,0,8,5,6,2,6,3,8,8,6,9,5,9,5,8,7,2,10,0,9,4,9,1,9,2,7,7,6,7,7,5,10,9,6,8,11,1,11,0,8,0,10,1,10,6,11,4,11,7,8,9,11,9,7,8,11,2,11,3,9,0,11,5,11,6,8,6,11,8,9,5,8,7,9,7,10,2,10,3,10,4,10,5,9,3,9,6,10,8,9,8,9,9,10,7}; void set(int x, int y, int px, int py) { int a = 2 size * x + 2 * y; path[a] = px; path[a + 1] = py; } void insert(int px, int py, int w, int h, int p) { for(int x = 0; x < w; x++) for(int y = 0; y < h; y++, p+= 2) set(px + x, py + y, p + px, (p + 1) + py); } void get(int x, int y, int &px, int &py) { int a = 2 size * x + 2 * y; px = path[a]; py = path[a + 1]; } void split(int x, int y, int w, int h) { if(w * h <= 120) { if(w == 6 && h == 6) insert(x, y, 6, 6, path6x6); else if(w == 6 && h == 8) insert(x, y, 6, 8, path6x8); else if(w == 8 && h == 6) insert(x, y, 8, 6, path8x6); else if(w == 8 && h == 8) insert(x, y, 8, 8, path8x8); else if(w == 8 && h == 10) insert(x, y, 8, 10, path8x10); else if(w == 10 && h == 8) insert(x, y, 10, 8, path10x8); else if(w == 10 && h == 10) insert(x, y, 10, 10, path10x10); else if(w == 10 && h == 12) insert(x, y, 10, 12, path10x12); else if(w == 12 && h == 10) insert(x, y, 12, 10, path12x10); else assert(false); } else { int kw = 2 * (w / 4); int kh = 2 * (h / 4); split(x , y , kw , kh); split(x + kw, y , w - kw, kh); split(x , y + kh, kw , h - kh); split(x + kw, y + kh, w - kw, h - kh); int cx = x + kw; int cy = y + kh; set(cx - 1, cy - 2, cx + 1, cy - 3); set(cx, cy - 1, cx + 2, cy); set(cx, cy + 1, cx - 2, cy + 2); set(cx - 1, cy, cx - 3, cy - 1); } } void print() { int px = 0, py = 0; for(int i = 0; i < size * size; i++) { int x = px, y = py; get(x,y,px,py); printf("move(%d,%d,%d,%d). ", x + 1, y + 1, px + 1, py + 1); } printf("\n"); } int main(int argc, char *argv) { scanf("size(%d).", &size); if(size >= 6 && size % 2 == 0) { path = (int)malloc(size * size * 2 * sizeof(int)); split(0, 0, size, size); print(); free(path); } else if(size != 1) { printf("UNSATISFIABLE\n"); } }

Actions

Navigation

Encoding knights-tour_construction.cpp