15 puzzle game
You are encouraged to solve this task according to the task description, using any language you may know.
- Task
Implement the Fifteen Puzzle Game.
Ada
We fist define a generic package Generic_Puzzle. Upon instantiation, it can take any number of rows, any number of columns for a rows*columns-1 game. Instead of plain numbers, the tiles on the board can have arbitrary names (but they should all be of the same length). The package user can request the name for the tile at a certain (row,column)-point, and the set of possible moves. The user can move the empty space up, down, left and right (if possible). If the user makes the attempt to perform an impossible move, a Constraint_Error is raised.
<lang Ada>generic
Rows, Cols: Positive; with function Name(N: Natural) return String; -- with Pre => (N < Rows*Cols); -- Name(0) shall return the name for the empty tile
package Generic_Puzzle is
subtype Row_Type is Positive range 1 .. Rows; subtype Col_Type is Positive range 1 .. Cols; type Moves is (Up, Down, Left, Right); type Move_Arr is array(Moves) of Boolean; function Get_Point(Row: Row_Type; Col: Col_Type) return String; function Possible return Move_Arr; procedure Move(The_Move: Moves);
end Generic_Puzzle;</lang>
The package implementation is as follows.
<lang Ada>package body Generic_Puzzle is
Field: array(Row_Type, Col_Type) of Natural; Current_R: Row_Type := Rows; Current_C: Col_Type := Cols; -- invariant: Field(Current_R, Current_C=0) -- and for all R, C: Field(R, C) < R*C -- and for all (R, C) /= (RR, CC): Field(R, C) /= Field(RR, CC) function Get_Point(Row: Row_Type; Col: Col_Type) return String is (Name(Field(Row, Col))); function Possible return Move_Arr is (Up => Current_R > 1, Down => Current_R < Rows, Left => Current_C > 1, Right => Current_C < Cols); procedure Move(The_Move: Moves) is Old_R: Row_Type; Old_C: Col_Type; N: Natural; begin if not Possible(The_Move) then
raise Constraint_Error with "attempt to make impossible move";
else
-- remember current row and column Old_R := Current_R; Old_C := Current_C;
-- move the virtual cursor to a new position case The_Move is when Up => Current_R := Current_R - 1; when Down => Current_R := Current_R + 1; when Left => Current_C := Current_C - 1; when Right => Current_C := Current_C + 1; end case;
-- swap the tiles on the board N := Field(Old_R, Old_C); Field(Old_R, Old_C) := Field(Current_R, Current_C); Field(Current_R, Current_C) := N;
end if; end Move;
begin
declare -- set field to its basic setting N: Positive := 1; begin for R in Row_Type loop
for C in Col_Type loop if (R /= Current_R) or else (C /= Current_C) then Field(R, C) := N; N := N + 1; else Field(R, C) := 0; end if; end loop;
end loop; end;
end Generic_Puzzle;</lang>
The main program reads the level from the command line. A larger level implies a more difficult instance. The default level is 10, which is fairly simple. After randomizing the board, the user can move the tiles.
<lang Ada>with Generic_Puzzle, Ada.Text_IO,
Ada.Numerics.Discrete_Random, Ada.Command_Line;
procedure Puzzle_15 is
function Image(N: Natural) return String is (if N=0 then " " elsif N < 10 then " " & Integer'Image(N)
else Integer'Image(N));
package Puzzle is new Generic_Puzzle(Rows => 4, Cols => 4, Name => Image); package Rnd is new Ada.Numerics.Discrete_Random(Puzzle.Moves); Rand_Gen: Rnd.Generator; Level: Natural := (if Ada.Command_Line.Argument_Count = 0 then 10 else Natural'Value(Ada.Command_Line.Argument(1))); Initial_Moves: Natural := (2**(Level/2) + 2**((1+Level)/2))/2; Texts: constant array(Puzzle.Moves) of String(1..9) := ("u,U,^,8: ", "d,D,v,2: ", "l,L,<,4: ", "r,R,>,6: "); Move_Counter: Natural := 0; Command: Character; begin -- randomize board for I in 1 .. Initial_Moves loop declare
M: Puzzle.Moves := Rnd.Random(Rand_Gen);
begin
if Puzzle.Possible(M) then Puzzle.Move(M); end if;
end; end loop; -- read command and perform move loop -- Print board for R in Puzzle.Row_Type loop
for C in Puzzle.Col_Type loop Ada.Text_IO.Put(Puzzle.Get_Point(R, C)); end loop; Ada.Text_IO.New_Line;
end loop; Ada.Text_IO.Get(Command); begin
case Command is when 'u' | 'U' | '^' | '8' => Ada.Text_IO.Put_Line("Up!"); Puzzle.Move(Puzzle.Up); when 'd' | 'D' | 'v' | '2' => Ada.Text_IO.Put_Line("Down!"); Puzzle.Move(Puzzle.Down); when 'l' | 'L' | '<' | '4' => Ada.Text_IO.Put_Line("Left!"); Puzzle.Move(Puzzle.Left); when 'r' | 'R' | '>' | '6' => Ada.Text_IO.Put_Line("Right!"); Puzzle.Move(Puzzle.Right); when '!' => Ada.Text_IO.Put_Line(Natural'Image(Move_Counter) & " moves!"); exit; when others => raise Constraint_Error with "wrong input"; end case; Move_Counter := Move_Counter + 1;
exception when Constraint_Error =>
Ada.Text_IO.Put_Line("Possible Moves and Commands:"); for M in Puzzle.Moves loop if Puzzle.Possible(M) then Ada.Text_IO.Put(Texts(M) & Puzzle.Moves'Image(M) & " "); end if; end loop; Ada.Text_IO.Put_Line("!: Quit");
end; end loop;
end Puzzle_15;</lang>
- Output:
>./puzzle_15 4 1 2 3 4 5 6 7 8 9 14 10 11 13 15 12 8 Up! 1 2 3 4 5 6 7 8 9 10 11 13 14 15 12 6 Right! 1 2 3 4 5 6 7 8 9 10 11 13 14 15 12 5 Possible Moves and Commands: u,U,^,8: UP d,D,v,2: DOWN l,L,<,4: LEFT r,R,>,6: RIGHT !: Quit 1 2 3 4 5 6 7 8 9 10 11 13 14 15 12 6 Right! 1 2 3 4 5 6 7 8 9 10 11 13 14 15 12 2 Down! 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 ! 4 moves!
For other puzzles, one must just the single line with the package instantiation. E.g., for an 8-puzzle, we would write the following. <lang Ada> package Puzzle is new Generic_Puzzle(Rows => 3, Cols => 3, Name => Image);</lang>
AutoHotkey
<lang AutoHotkey>S := 16 Grid := [], Direc := ["Up","Down","Left","Right"], w := S * 2.5 Gui, font, S%S% Gui, add, text, y1 loop, 4 { i := A_Index loop, 4 { j := A_Index if j = 1 Gui, add, button, v%i%_%j% xs y+1 w%w% gButton -TabStop, % Grid[i,j] := j + (i-1) * 4 else Gui, add, button, v%i%_%j% x+1 yp w%w% gButton -TabStop, % Grid[i,j] := j + (i-1) * 4 } } GuiControl, Hide, 4_4 Gui, add, Button , % "xs gScramble w" 4 * w + 3, Scramble Gui, show,, 15 Puzzle return
- ------------------------------
GuiClose: ExitApp return
- ------------------------------
Scramble: loop, 500 { Random, Rnd, 1,4 gosub, % "move" Direc[Rnd] } return
- ------------------------------
Button: x := StrSplit(A_GuiControl, "_").1 , y := StrSplit(A_GuiControl, "_").2 if Abs(x-i) > 1 || Abs(y-j) > 1 || Abs(x-i) = Abs(y-j) return gosub, % (x>i) ? "moveDown" : (x<i) ? "moveUp" : (y>j) ? "moveRight" : (y<j) ? "moveLeft" : "" return
- ------------------------------
- IfWinActive, 15 Puzzle
- ------------------------------
up:: MoveUp: if i=1 return GuiControl, Hide, % i-1 "_" j GuiControl, Show, % i "_" j GuiControl,, %i%_%j%, % Grid[i-1, j] Grid[i, j] := Grid[i-1, j], Grid[--i, j] := 16 return
- ------------------------------
Down:: MoveDown: if i=4 return GuiControl, Hide, % i+1 "_" j GuiControl, Show, % i "_" j GuiControl,, %i%_%j%, % Grid[i+1, j] Grid[i, j] := Grid[i+1, j], Grid[++i, j] := 16 return
- ------------------------------
Left:: MoveLeft: if j=1 return GuiControl, Hide, % i "_" j-1 GuiControl, Show, % i "_" j GuiControl,, %i%_%j%, % Grid[i, j-1] Grid[i, j] := Grid[i, j-1], Grid[i, --j] := 16 return
- ------------------------------
Right:: MoveRight: if j=4 return GuiControl, Hide, % i "_" j+1 GuiControl, Show, % i "_" j GuiControl,, %i%_%j%, % Grid[i, j+1] Grid[i, j] := Grid[i, j+1], Grid[i, ++j] := 16 return
- ------------------------------
- IfWinActive
- ------------------------------</lang>
BASIC
Commodore BASIC
<lang basic>10 REM 15-PUZZLE GAME 20 REM COMMODORE BASIC 2.0 30 REM ******************************** 40 GOSUB 400 : REM INTRO AND LEVEL 50 GOSUB 510 : REM SETUP BOARD 60 GOSUB 210 : REM PRINT PUZZLE 70 PRINT "TO MOVE A PIECE, ENTER ITS NUMBER:" 80 INPUT X 90 GOSUB 730 : REM CHECK IF MOVE IS VALID 100 IF MV=0 THEN PRINT "WRONG MOVE" : GOSUB 1050 : GOTO 60 110 D(Z)=X : D(Y)=0 120 GOSUB 210 : REM PRINT PUZZLE 130 GOSUB 950 : REM CHECK IF PUZZLE COMPLETE 140 IF PC THEN 160 150 GOTO 70 160 PRINT"YOU WON!" 170 END 180 REM 190 REM ******************************* 200 REM PRINT/DRAW THE PUZZLE 210 FOR P=1 TO 16 220 IF D(P)=0 THEN D$(P)=" " : GOTO 260 230 S$=STR$(D(P)) 240 N=LEN(S$) 250 D$(P) = LEFT$(" ",3-N)+S$+" " 260 NEXT 270 PRINT "+-----+-----+-----+-----+" 280 PRINT "!"D$(1)"!"D$(2)"!"D$(3)"!"D$(4)"!" 290 PRINT "+-----+-----+-----+-----+" 300 PRINT "!"D$(5)"!"D$(6)"!"D$(7)"!"D$(8)"!" 310 PRINT "+-----+-----+-----+-----+" 320 PRINT "!"D$(9)"!"D$(10)"!"D$(11)"!"D$(12)"!" 330 PRINT "+-----+-----+-----+-----+" 340 PRINT "!"D$(13)"!"D$(14)"!"D$(15)"!"D$(16)"!" 350 PRINT "+-----+-----+-----+-----+" 360 RETURN 370 REM 380 REM ******************************* 390 REM INTRO AND LEVEL OF DIFFICULTY 400 PRINT CHR$(147) 410 DIM SH(3) : SH(1)=10 : SH(2)=50 : SH(3)=100 420 PRINT "15 PUZZLE GAME FOR COMMODORE BASIC 2.0" : PRINT : PRINT 430 PRINT "PLEASE ENTER LEVEL OF DIFFICULTY," 440 PRINT "1(EASY), 2(MEDIUM) OR 3(HARD):"; 450 INPUT V 460 IF V<1 OR V>3 THEN 440 470 RETURN 480 REM 490 REM ******************************* 500 REM BUILD THE BOARD 510 DIM D(16) : DIM D$(16) : REM BOARD PIECES 520 REM SET PIECES IN CORRECT ORDER FIRST 530 FOR P=1 TO 15 540 D(P) = P 550 NEXT 560 D(16) = 0 : REM 0 = EMPTY PIECE/SLOT 570 Z=16 : REM Z = EMPTY POSITION 580 PRINT: PRINT "SHUFFLING PIECES"; 590 FOR N=1 TO SH(V) 600 PRINT"."; 610 X = INT(RND(0)*4)+1 620 R = Z+(X=1)*4-(X=2)*4+(X=3)-(X=4) 630 IF R<1 OR R>16 THEN 610 640 D(Z)=D(R) 650 Z=R 660 D(Z)=0 670 NEXT 680 PRINT CHR$(147) 690 RETURN 700 REM 710 REM ******************************* 720 REM CHECK IF MOVE IS VALID 730 MV = 0 740 IF X<1 OR X>15 THEN RETURN 750 REM FIND POSITION OF PIECE X 760 P=1 770 IF D(P)=X THEN Y=P : GOTO 810 780 P=P+1 : IF P>16 THEN PRINT "UH OH!" : STOP 790 GOTO 770 800 REM FIND POSITION OF EMPTY PIECE 810 P=1 820 IF D(P)=0 THEN Z=P : GOTO 860 830 P=P+1 : IF P>16 THEN PRINT "UH OH!" : STOP 840 GOTO 820 850 PRINT Y;Z 860 REM CHECK IF EMPTY PIECE IS ABOVE, BELOW, LEFT OR RIGHT TO PIECE X 870 IF Y-4=Z THEN MV=1 : RETURN 880 IF Y+4=Z THEN MV=1 : RETURN 890 IF Y-1=Z THEN MV=1 : RETURN 900 IF Y+1=Z THEN MV=1 : RETURN 910 RETURN 920 REM 930 REM ******************************* 940 REM CHECK IF PUZZLE IS COMPLETE / GAME OVER 950 PC = 0 960 P=1 970 IF D(P)<>P THEN RETURN 980 P=P+1 990 IF P<16 THEN 970 1000 PC = 1 1010 RETURN 1020 REM 1030 REM ****************************** 1040 REM A SMALL DELAY 1050 FOR T=0 TO 400 1060 NEXT 1070 RETURN</lang>
C
C89, 22 lines version
The task, as you can see, can be resolved in 22 lines of no more than 80 characters. Of course, the source code in C is not very readable. The second example works exactly the same way, but it was written in much more human readable way. The program also works correctly for non-standard number of rows and / or columns. <lang C>/* RosettaCode: Fifteen puzle game, C89, plain vanillia TTY, MVC, § 22 */
- define _CRT_SECURE_NO_WARNINGS
- include <stdio.h>
- include <stdlib.h>
- include <time.h>
- define N 4
- define M 4
enum Move{UP,DOWN,LEFT,RIGHT};int hR;int hC;int cc[N][M];const int nS=100;int update(enum Move m){const int dx[]={0,0,-1,1};const int dy[]={-1,1,0,0};int i=hR +dy[m];int j=hC+dx[m];if(i>= 0&&i<N&&j>=0&&j<M){cc[hR][hC]=cc[i][j];cc[i][j]=0; hR=i;hC=j;return 1;}return 0;}void setup(void){int i,j,k;for(i=0;i<N;i++)for(j=0
- j<M;j++)cc[i][j]=i*M+j+1;cc[N-1][M-1]=0;hR=N-1;hC=M-1;k=0;while(k<nS)k+=update(
(enum Move)(rand()%4));}int isEnd(void){int i,j; int k=1;for(i=0;i<N;i++)for(j=0
- j<M;j++)if((k<N*M)&&(cc[i][j]!=k++))return 0;return 1;}void show(){int i,j;
putchar('\n');for(i=0;i<N;i++)for(j=0;j<M;j++){if(cc[i][j])printf(j!=M-1?" %2d "
- " %2d \n",cc[i][j]);else printf(j!=M-1?" %2s ":" %2s \n", "");}putchar('\n');}
void disp(char* s){printf("\n%s\n", s);}enum Move get(void){int c;for(;;){printf ("%s","enter u/d/l/r : ");c=getchar();while(getchar()!='\n');switch(c){case 27: exit(0);case'd':return UP;case'u':return DOWN;case'r':return LEFT;case'l':return RIGHT;}}}void pause(void){getchar();}int main(void){srand((unsigned)time(NULL)); do setup();while(isEnd());show();while(!isEnd()){update(get());show();}disp( "You win"); pause();return 0;}</lang>
C89, short version, TTY mode
<lang C>/*
* RosettaCode: Fifteen puzle game, C89, plain vanillia TTY, MVC */
- define _CRT_SECURE_NO_WARNINGS /* unlocks printf etc. in MSVC */
- include <stdio.h>
- include <stdlib.h>
- include <time.h>
enum Move { MOVE_UP = 0, MOVE_DOWN = 1, MOVE_LEFT = 2, MOVE_RIGHT = 3 };
/* *****************************************************************************
* Model */
- define NROWS 4
- define NCOLLUMNS 4
int holeRow; int holeCollumn; int cells[NROWS][NCOLLUMNS]; const int nShuffles = 100;
int Game_update(enum Move move){
const int dx[] = { 0, 0, -1, +1 }; const int dy[] = { -1, +1, 0, 0 }; int i = holeRow + dy[move]; int j = holeCollumn + dx[move]; if ( i >= 0 && i < NROWS && j >= 0 && j < NCOLLUMNS ){ cells[holeRow][holeCollumn] = cells[i][j]; cells[i][j] = 0; holeRow = i; holeCollumn = j; return 1; } return 0;
}
void Game_setup(void){
int i,j,k; for ( i = 0; i < NROWS; i++ ) for ( j = 0; j < NCOLLUMNS; j++ ) cells[i][j] = i * NCOLLUMNS + j + 1; cells[NROWS-1][NCOLLUMNS-1] = 0; holeRow = NROWS - 1; holeCollumn = NCOLLUMNS - 1; k = 0; while ( k < nShuffles ) k += Game_update((enum Move)(rand() % 4));
}
int Game_isFinished(void){
int i,j; int k = 1; for ( i = 0; i < NROWS; i++ ) for ( j = 0; j < NCOLLUMNS; j++ ) if ( (k < NROWS*NCOLLUMNS) && (cells[i][j] != k++ ) ) return 0; return 1;
}
/* *****************************************************************************
* View */
void View_showBoard(){
int i,j; putchar('\n'); for ( i = 0; i < NROWS; i++ ) for ( j = 0; j < NCOLLUMNS; j++ ){ if ( cells[i][j] ) printf(j != NCOLLUMNS-1 ? " %2d " : " %2d \n", cells[i][j]); else printf(j != NCOLLUMNS-1 ? " %2s " : " %2s \n", ""); } putchar('\n');
}
void View_displayMessage(char* text){
printf("\n%s\n", text);
}
/* *****************************************************************************
* Controller */
enum Move Controller_getMove(void){
int c; for(;;){ printf("%s", "enter u/d/l/r : "); c = getchar(); while( getchar() != '\n' ) ; switch ( c ){ case 27: exit(EXIT_SUCCESS); case 'd' : return MOVE_UP; case 'u' : return MOVE_DOWN; case 'r' : return MOVE_LEFT; case 'l' : return MOVE_RIGHT; } }
}
void Controller_pause(void){
getchar();
}
int main(void){
srand((unsigned)time(NULL));
do Game_setup(); while ( Game_isFinished() );
View_showBoard(); while( !Game_isFinished() ){ Game_update( Controller_getMove() ); View_showBoard(); }
View_displayMessage("You win"); Controller_pause();
return EXIT_SUCCESS;
}
</lang>
- Output:
9 1 4 7 6 5 3 2 13 10 8 14 15 11 12 enter u/d/l/r : u 9 1 4 7 6 5 3 2 13 10 11 8 14 15 12 enter u/d/l/r : l 9 1 4 7 6 5 3 2 13 10 11 8 14 15 12 enter u/d/l/r : d 9 1 4 7 6 5 3 2 13 10 11 14 15 12 8 enter u/d/l/r :
C89, long version, TTY/Winapi/ncurses modes
<lang C>/**
* RosettaCode: Fifteen puzle game, C89, MS Windows Console API, MVC * * @version 0.2 (added TTY and ncurses modes) */
- define UNDEFINED_WIN32API_CONSOLE
- define UNDEFINED_NCURSES_CONSOLE
- if !defined (TTY_CONSOLE) && !defined(WIN32API_CONSOLE) && !defined(NCURSES_CONSOLE)
- define TTY_CONSOLE
- endif
- define _CRT_SECURE_NO_WARNINGS /* enable printf etc. */
- define _CRT_NONSTDC_NO_DEPRECATE /* POSIX functions enabled */
- include <stdio.h>
- include <stdlib.h>
- include <string.h>
- include <time.h>
- if defined(NCURSES_CONSOLE)
- include "curses.h" /* see http://pdcurses.sourceforge.net/ */
- elif defined(WIN32API_CONSOLE)
- define NOGDI /* we don't need GDI */
- define WIN32_LEAN_AND_MEAN /* we don't need OLE etc. */
- include <windows.h> /* MS Windows stuff */
- include <conio.h> /* kbhit() and getch() */
- endif
enum Move { MOVE_UP = 0, MOVE_DOWN = 1, MOVE_LEFT = 2, MOVE_RIGHT = 3 };
/* *****************************************************************************
* Model */
- define NROWS 4
- define NCOLLUMNS 4
int holeRow; int holeCollumn; int cells[NROWS][NCOLLUMNS]; const int nShuffles = 100;
int Game_update(enum Move move){
const int dx[] = { 0, 0, -1, +1 }; const int dy[] = { -1, +1, 0, 0 }; int i = holeRow + dy[move]; int j = holeCollumn + dx[move]; if ( i >= 0 && i < NROWS && j >= 0 && j < NCOLLUMNS ){ cells[holeRow][holeCollumn] = cells[i][j]; cells[i][j] = 0; holeRow = i; holeCollumn = j; return 1; } return 0;
}
void Game_setup(void){
int i,j,k; for ( i = 0; i < NROWS; i++ ) for ( j = 0; j < NCOLLUMNS; j++ ) cells[i][j] = i * NCOLLUMNS + j + 1; cells[NROWS-1][NCOLLUMNS-1] = 0; holeRow = NROWS - 1; holeCollumn = NCOLLUMNS - 1; k = 0; while ( k < nShuffles ) k += Game_update((enum Move)(rand() % 4));
}
int Game_isFinished(void){
int i,j; int k = 1; for ( i = 0; i < NROWS; i++ ) for ( j = 0; j < NCOLLUMNS; j++ ) if ( (k < NROWS*NCOLLUMNS) && (cells[i][j] != k++ ) ) return 0; return 1;
}
/* *****************************************************************************
* View */
int fieldWidth;
- ifdef WIN32API_CONSOLE
HANDLE hConsole; CONSOLE_SCREEN_BUFFER_INFO csbi;
- endif
void View_setup_base(void) {
int i; fieldWidth = 0; for ( i = NROWS * NCOLLUMNS - 1; i > 0; i /= 10 ) fieldWidth++;
}
- if defined(TTY_CONSOLE)
void View_setup(void) {
View_setup_base();
}
void View_showBoard() {
int i,j; putchar('\n'); for ( i = 0; i < NROWS; i++ ) for ( j = 0; j < NCOLLUMNS; j++ ){ if ( cells[i][j] ) printf(j != NCOLLUMNS-1 ? " %*d " : " %*d \n", fieldWidth, cells[i][j]); else printf(j != NCOLLUMNS-1 ? " %*s " : " %*s \n", fieldWidth, ""); } putchar('\n');
}
void View_displayMessage(char* text) {
printf("\n%s\n", text);
}
- elif defined(NCURSES_CONSOLE)
void View_setup(void) {
View_setup_base(); initscr(); clear();
}
void View_showBoard() {
int i,j; for ( i = 0; i < NROWS; i++ ) for ( j = 0; j < NCOLLUMNS; j++ ){ int x = (fieldWidth+1)*j; int y = 2*i; if ( cells[i][j] ){ attron(A_REVERSE); mvprintw(y,x,"%*d", fieldWidth, cells[i][j]); }else{ attroff(A_REVERSE); mvprintw(y,x,"%*s", fieldWidth, " "); } } attrset(A_NORMAL);
}
void View_displayMessage(char* text) {
mvprintw(2*NROWS,0, "%s", text);
}
- elif defined(WIN32API_CONSOLE)
void View_setup(void) {
const COORD coordHome = { 0, 0 }; CONSOLE_CURSOR_INFO cci; DWORD size, nWritten; View_setup_base(); hConsole = GetStdHandle(STD_OUTPUT_HANDLE); cci.bVisible = FALSE; cci.dwSize = 1; SetConsoleCursorInfo(hConsole,&cci); GetConsoleScreenBufferInfo(hConsole,&(csbi)); size = csbi.dwSize.X*csbi.dwSize.Y; FillConsoleOutputCharacter(hConsole,' ',size,coordHome,&nWritten); FillConsoleOutputAttribute(hConsole,csbi.wAttributes,size,coordHome,&nWritten);
}
void View_showBoard() {
int i,j; char labelString[32]; WORD attributes; DWORD nWritten; for ( i = 0; i < NROWS; i++ ) for ( j = 0; j < NCOLLUMNS; j++ ){ COORD coord = { ((SHORT)fieldWidth+1)*j, coord.Y = 2*i }; if ( cells[i][j] ){ sprintf(labelString,"%*d", fieldWidth, cells[i][j]); attributes = BACKGROUND_BLUE | BACKGROUND_GREEN | BACKGROUND_RED; }else{ sprintf(labelString,"%*s", fieldWidth, " "); attributes = csbi.wAttributes; } WriteConsoleOutputCharacter(hConsole,labelString,fieldWidth,coord,&nWritten); FillConsoleOutputAttribute (hConsole,attributes,fieldWidth,coord,&nWritten); }
}
void View_displayMessage(char* text) {
DWORD nWritten; COORD coord = { 0, 2 * NROWS }; WriteConsoleOutputCharacter(hConsole,text,strlen(text),coord,&nWritten);
}
- endif
/* *****************************************************************************
* Controller */
- if defined(TTY_CONSOLE)
void Controller_setup(void){ }
enum Move Controller_getMove(void){
int c; for(;;){ printf("%s", "enter u/d/l/r : "); c = getchar(); while( getchar() != '\n' ) ; switch ( c ){ case 27: exit(EXIT_SUCCESS); case 'd' : return MOVE_UP; case 'u' : return MOVE_DOWN; case 'r' : return MOVE_LEFT; case 'l' : return MOVE_RIGHT; } }
}
void Controller_pause(void) {
getchar();
}
- elif defined(NCURSES_CONSOLE)
void Controller_setup(void){
noecho(); cbreak(); curs_set(0); keypad(stdscr,TRUE);
}
enum Move Controller_getMove(void){
for(;;){ switch ( wgetch(stdscr) ){ case 27: exit(EXIT_SUCCESS); case KEY_DOWN : return MOVE_UP; case KEY_UP : return MOVE_DOWN; case KEY_RIGHT : return MOVE_LEFT; case KEY_LEFT : return MOVE_RIGHT; case ERR: /* NOP */; } }
}
void Controller_pause(void){
while ( wgetch(stdscr) == ERR ) ;
}
- elif defined(WIN32API_CONSOLE)
void Controller_setup(void){ }
enum Move Controller_getMove(void){
for(;;){ switch ( getch() ){ case 27: exit(EXIT_SUCCESS); case 0: case 224: switch ( getch() ){ case 80 : return MOVE_UP; case 72 : return MOVE_DOWN; case 77 : return MOVE_LEFT; case 75 : return MOVE_RIGHT; } } }
}
void Controller_pause(void){
while( kbhit() ) getch(); while( !kbhit() ) ; while( kbhit() ) getch();
}
- endif
/* *****************************************************************************
* Main function: create model, view and controller. Run main loop. */
int main(void) {
srand((unsigned)time(NULL));
do Game_setup(); while ( Game_isFinished() ); View_setup(); Controller_setup();
View_showBoard(); while( !Game_isFinished() ){ Game_update( Controller_getMove() ); View_showBoard(); }
View_displayMessage("You win"); Controller_pause();
return EXIT_SUCCESS;
} </lang>
C#
<lang csharp>using System; using System.Drawing; using System.Linq; using System.Windows.Forms;
public class FifteenPuzzle {
const int gridSize = 4; //Standard 15 puzzle is 4x4 const bool evenSized = gridSize % 2 == 0; const int blockCount = gridSize * gridSize; const int last = blockCount - 1; const int buttonSize = 50; const int buttonMargin = 3; //default = 3 const int formEdge = 9; static readonly Random rnd = new Random(); static readonly Font buttonFont = new Font("Arial", 15.75F, FontStyle.Regular, GraphicsUnit.Point, ((byte)(0))); readonly Button[] buttons = new Button[blockCount]; readonly int[] grid = new int[blockCount]; readonly int[] positionOf = new int[blockCount]; int moves = 0; DateTime start;
public static void Main(string[] args) { FifteenPuzzle p = new FifteenPuzzle(); Form f = p.BuildForm(); Application.Run(f); }
public FifteenPuzzle() { for (int i = 0; i < blockCount; i++) { grid[i] = i; positionOf[i] = i; } }
Form BuildForm() { Button startButton = new Button { Font = new Font("Arial", 9.75F, FontStyle.Regular, GraphicsUnit.Point, ((byte)(0))), Size = new Size(86, 23), Location = new Point(formEdge, (buttonSize + buttonMargin * 2) * gridSize + buttonMargin + formEdge), Text = "New Game", UseVisualStyleBackColor = true }; startButton.Click += (sender, e) => Shuffle();
int size = buttonSize * gridSize + buttonMargin * gridSize * 2 + formEdge * 2; Form form = new Form { Text = "Fifteen", ClientSize = new Size(width: size, height: size + buttonMargin * 2 + startButton.Height) }; form.SuspendLayout(); for (int index = 0; index < blockCount; index++) { Button button = new Button { Font = buttonFont, Size = new Size(buttonSize, buttonSize), //Margin = new Padding(buttonMargin), Text = (index + 1).ToString(), UseVisualStyleBackColor = true }; SetLocation(button, index); form.Controls.Add(button); buttons[index] = button; int i = index; button.Click += (sender, e) => ButtonClick(i); } form.Controls.Add(startButton); form.ResumeLayout(); return form; }
void ButtonClick(int i) { if (buttons[last].Visible) return; int target = positionOf[i]; if (positionOf[i] / gridSize == positionOf[last] / gridSize) { while (positionOf[last] < target) { Swap(last, grid[positionOf[last] + 1]); moves++; } while (positionOf[last] > target) { Swap(last, grid[positionOf[last] - 1]); moves++; } } else if (positionOf[i] % gridSize == positionOf[last] % gridSize) { while (positionOf[last] < target) { Swap(last, grid[positionOf[last] + gridSize]); moves++; } while (positionOf[last] > target) { Swap(last, grid[positionOf[last] - gridSize]); moves++; } } if (Solved()) { TimeSpan elapsed = DateTime.Now - start; elapsed = TimeSpan.FromSeconds(Math.Round(elapsed.TotalSeconds, 0)); buttons[last].Visible = true; MessageBox.Show($"Solved in {moves} moves. Time: {elapsed}"); } }
bool Solved() => Enumerable.Range(0, blockCount - 1).All(i => positionOf[i] == i);
static void SetLocation(Button button, int index) { int row = index / gridSize, column = index % gridSize; button.Location = new Point( (buttonSize + buttonMargin * 2) * column + buttonMargin + formEdge, (buttonSize + buttonMargin * 2) * row + buttonMargin + formEdge); }
void Shuffle() { for (int i = 0; i < blockCount; i++) { int r = rnd.Next(i, blockCount); int g = grid[r]; grid[r] = grid[i]; grid[i] = g; } for (int i = 0; i < blockCount; i++) { positionOf[grid[i]] = i; SetLocation(buttons[grid[i]], i); } if (!Solvable()) Swap(0, 1); //Swap any 2 blocks
buttons[last].Visible = false; moves = 0; start = DateTime.Now; }
bool Solvable() { bool parity = true; for (int i = 0; i < blockCount - 2; i++) { for (int j = i + 1; j < blockCount - 1; j++) { if (positionOf[j] < positionOf[i]) parity = !parity; } } if (evenSized && positionOf[last] / gridSize % 2 == 0) parity = !parity; return parity; }
void Swap(int a, int b) { Point location = buttons[a].Location; buttons[a].Location = buttons[b].Location; buttons[b].Location = location;
int p = positionOf[a]; positionOf[a] = positionOf[b]; positionOf[b] = p;
grid[positionOf[a]] = a; grid[positionOf[b]] = b; }
}</lang>
C++
<lang cpp>
- include <time.h>
- include <vector>
- include <string>
- include <iostream>
class p15 { public :
void play() { bool p = true; std::string a; while( p ) { createBrd(); while( !isDone() ) { drawBrd();getMove(); } drawBrd(); std::cout << "\n\nCongratulations!\nPlay again (Y/N)?"; std::cin >> a; if( a != "Y" && a != "y" ) break; } }
private:
void createBrd() { int i = 1; std::vector<int> v; for( ; i < 16; i++ ) { brd[i - 1] = i; } brd[15] = 0; x = y = 3; for( i = 0; i < 1000; i++ ) { getCandidates( v ); move( v[rand() % v.size()] ); v.clear(); } } void move( int d ) { int t = x + y * 4; switch( d ) { case 1: y--; break; case 2: x++; break; case 4: y++; break; case 8: x--; } brd[t] = brd[x + y * 4]; brd[x + y * 4] = 0; } void getCandidates( std::vector<int>& v ) { if( x < 3 ) v.push_back( 2 ); if( x > 0 ) v.push_back( 8 ); if( y < 3 ) v.push_back( 4 ); if( y > 0 ) v.push_back( 1 ); } void drawBrd() { int r; std::cout << "\n\n"; for( int y = 0; y < 4; y++ ) { std::cout << "+----+----+----+----+\n"; for( int x = 0; x < 4; x++ ) { r = brd[x + y * 4]; std::cout << "| "; if( r < 10 ) std::cout << " "; if( !r ) std::cout << " "; else std::cout << r << " "; } std::cout << "|\n"; } std::cout << "+----+----+----+----+\n"; } void getMove() { std::vector<int> v; getCandidates( v ); std::vector<int> p; getTiles( p, v ); unsigned int i; while( true ) { std::cout << "\nPossible moves: "; for( i = 0; i < p.size(); i++ ) std::cout << p[i] << " "; int z; std::cin >> z; for( i = 0; i < p.size(); i++ ) if( z == p[i] ) { move( v[i] ); return; } } } void getTiles( std::vector<int>& p, std::vector<int>& v ) { for( unsigned int t = 0; t < v.size(); t++ ) { int xx = x, yy = y; switch( v[t] ) { case 1: yy--; break; case 2: xx++; break; case 4: yy++; break; case 8: xx--; } p.push_back( brd[xx + yy * 4] ); } } bool isDone() { for( int i = 0; i < 15; i++ ) { if( brd[i] != i + 1 ) return false; } return true; } int brd[16], x, y;
}; int main( int argc, char* argv[] ) {
srand( ( unsigned )time( 0 ) ); p15 p; p.play(); return 0;
} </lang>
+----+----+----+----+ | 11 | 5 | 12 | 3 | +----+----+----+----+ | 10 | 7 | 6 | 4 | +----+----+----+----+ | 13 | | 2 | 1 | +----+----+----+----+ | 15 | 14 | 8 | 9 | +----+----+----+----+ Possible moves: 2 13 14 7
COBOL
Tested with GnuCOBOL
<lang cobol> >>SOURCE FORMAT FREE
- > This code is dedicated to the public domain
- > This is GNUCOBOL 2.0
identification division. program-id. fifteen. environment division. configuration section. repository. function all intrinsic. data division. working-storage section.
01 r pic 9. 01 r-empty pic 9. 01 r-to pic 9. 01 r-from pic 9.
01 c pic 9. 01 c-empty pic 9. 01 c-to pic 9. 01 c-from pic 9.
01 display-table.
03 display-row occurs 4. 05 display-cell occurs 4 pic 99.
01 tile-number pic 99. 01 tile-flags pic x(16).
01 display-move value spaces.
03 tile-id pic 99.
01 row-separator pic x(21) value all '.'. 01 column-separator pic x(3) value ' . '.
01 inversions pic 99. 01 current-tile pic 99.
01 winning-display pic x(32) value
'01020304' & '05060708' & '09101112' & '13141500'.
procedure division. start-fifteen.
display 'start fifteen puzzle' display ' enter a two-digit tile number and press <enter> to move' display ' press <enter> only to exit'
*> tables with an odd number of inversions are not solvable perform initialize-table with test after until inversions = 0 perform show-table accept display-move perform until display-move = spaces perform move-tile perform show-table move spaces to display-move accept display-move end-perform stop run .
initialize-table.
compute tile-number = random(seconds-past-midnight) *> seed only move spaces to tile-flags move 0 to current-tile inversions perform varying r from 1 by 1 until r > 4 after c from 1 by 1 until c > 4 perform with test after until tile-flags(tile-number + 1:1) = space compute tile-number = random() * 100 compute tile-number = mod(tile-number, 16) end-perform move 'x' to tile-flags(tile-number + 1:1) if tile-number > 0 and < current-tile add 1 to inversions end-if move tile-number to display-cell(r,c) current-tile end-perform compute inversions = mod(inversions,2) .
show-table.
if display-table = winning-display display 'winning' end-if display space row-separator perform varying r from 1 by 1 until r > 4 perform varying c from 1 by 1 until c > 4 display column-separator with no advancing if display-cell(r,c) = 00 display ' ' with no advancing move r to r-empty move c to c-empty else display display-cell(r,c) with no advancing end-if end-perform display column-separator end-perform display space row-separator .
move-tile.
if not (tile-id numeric and tile-id >= 01 and <= 15) display 'invalid tile number' exit paragraph end-if
*> find the entered tile-id row and column (r,c) perform varying r from 1 by 1 until r > 4 after c from 1 by 1 until c > 4 if display-cell(r,c) = tile-id exit perform end-if end-perform
*> show-table filled (r-empty,c-empty) evaluate true when r = r-empty if c-empty < c *> shift left perform varying c-to from c-empty by 1 until c-to > c compute c-from = c-to + 1 move display-cell(r-empty,c-from) to display-cell(r-empty,c-to) end-perform else *> shift right perform varying c-to from c-empty by -1 until c-to < c compute c-from = c-to - 1 move display-cell(r-empty,c-from) to display-cell(r-empty,c-to) end-perform end-if move 00 to display-cell(r,c) when c = c-empty if r-empty < r *>shift up perform varying r-to from r-empty by 1 until r-to > r compute r-from = r-to + 1 move display-cell(r-from,c-empty) to display-cell(r-to,c-empty) end-perform else *> shift down perform varying r-to from r-empty by -1 until r-to < r compute r-from = r-to - 1 move display-cell(r-from,c-empty) to display-cell(r-to,c-empty) end-perform end-if move 00 to display-cell(r,c) when other display 'invalid move' end-evaluate .
end program fifteen.</lang>
- Output:
prompt$ cobc -xj fifteen.cbl start fifteen puzzle enter a two-digit tile number and press <enter> to move press <enter> only to exit ..................... . 05 . 14 . 08 . 12 . . 01 . 10 . 03 . 09 . . 02 . 15 . 13 . 11 . . 06 . . 07 . 04 . .....................
Common Lisp
Credit to this post for help with the inversions-counting function: [1]
Run it (after loading the file) with <lang lisp>|15|::main</lang>.
<lang lisp>(defpackage :15
(:use :common-lisp))
(in-package :15)
(defvar +side+ 4) (defvar +max+ (1- (* +side+ +side+))) ; 15
(defun make-board ()
(make-array (list +side+ +side+) :initial-contents (loop :for i :below +side+ :collecting (loop :for j :below +side+ :collecting (mod (1+ (+ j (* i +side+))) (1+ +max+))))))
(defvar *board* (make-board))
(defun shuffle-board (board)
(loop for i from (array-total-size board) downto 2 do (rotatef (row-major-aref board (random i)) (row-major-aref board (1- i)))) board)
(defun pb (stream object &rest args)
(declare (ignorable args)) (loop for i below (car (array-dimensions object)) do (loop for j below (cadr (array-dimensions object)) do (let ((cell (aref object i j))) (format stream "(~[ ~:;~:*~2d~])" cell))) (format stream "~%")))
(defun sortedp (board)
(declare (ignorable board)) (loop for i upto +max+ when (eq (row-major-aref board i) (mod (1+ i) 16)) do (return-from sortedp nil)) t)
(defun inversions (lst)
(if (or (null lst) (null (cdr lst))) 0 (let* ((half (ceiling (/ (length lst) 2))) (left-list (subseq lst 0 half)) (right-list (subseq lst half))) (+ (loop for a in left-list summing (loop for b in right-list counting (not (< a b)))) (inversions left-list) (inversions right-list)))))
(defun solvablep (board)
(let ((inv (inversions (loop for i upto +max+ collecting (row-major-aref board i)))) (row (- +side+ (first (board-position board 0))))) (or (and (oddp +side+) (evenp inv)) (and (evenp +side+) (evenp row) (oddp inv)) (and (evenp +side+) (oddp row) (evenp inv)))))
(defun board-position (board dig)
(loop for i below (car (array-dimensions board)) do (loop for j below (cadr (array-dimensions board)) when (eq dig (aref board i j)) do (return-from board-position (list i j)))))
(defun in-bounds (y x)
(and (< -1 y +side+) (< -1 x +side+)))
(defun get-adjacents (board pos)
(let ((adjacents ()) (y (first pos)) (x (second pos))) (if (in-bounds y (1+ x)) (push (aref board y (1+ x)) adjacents)) (if (in-bounds (1+ y) x) (push (aref board (1+ y) x) adjacents)) (if (in-bounds y (1- x)) (push (aref board y (1- x)) adjacents)) (if (in-bounds (1- y) x) (push (aref board (1- y) x) adjacents)) adjacents))
(defun main (&rest argv)
(declare (ignorable argv)) (setf *random-state* (make-random-state t)) (loop until (solvablep *board*) do (shuffle-board *board*)) (loop until (sortedp *board*) do (format t "~/15:pb/~%" *board*) (format t "Which number do you want to swap the blank with?~%> ") (let* ((in (read)) (zpos (board-position *board* 0)) (pos (board-position *board* in)) (adj (get-adjacents *board* zpos))) (if (find in adj) (rotatef (aref *board* (first pos) (second pos)) (aref *board* (first zpos) (second zpos)))))) (format t "You win!~%"))</lang>
Gambas
<lang gambas>' Gambas class file
'Charlie Ogier (C) 15PuzzleGame 24/04/2017 V0.1.0 Licenced under MIT 'Bugs or comments to bugs@cogier.com 'Written in Gambas 3.9.2
byPos As New Byte[] 'Stores the position of the 'Tiles' siMoves As Short 'Stores the amount of moves hTimer As Timer 'Timer dTimerStart As Date 'Stores the start time dTimerDiff As Date 'Stores the time from the start to now bTimerOn As Boolean 'To know if the Timer is running
Public Sub Form_Open() 'Form opens
With Me 'With the Form..
.Padding = 5 'Pad the edges .Arrangement = Arrange.Row 'Arrange the Form .Resizable = False 'Don't let the user mess with the Form size .Height = 250 'Set the Form Height .Width = 250 'Set the Form Width .Title = "0 Moves" 'Set the Form Title
End With
BuildForm 'Go to the BuildForm routine
End
Public Sub BuildForm() 'To add items to the Form Dim hButton As Button 'We need some Buttons Dim byRand, byTest As Byte 'Various variables Dim bOK As Boolean 'Used to stop duplicate numbers being added
Do 'Start of a Do loop to create 0 to 15 in random order
byRand = Rand(0, 15) 'Get a random number between 0 and 15 bOK = True 'Set bOK to True For Each byTest In byPos 'For each number stored in the array byPos If byRand = byTest Then bOK = False 'Check to see if it already exists, if it does set bOK to False Next If bOK Then byPos.Add(byRand) 'If not a duplicate then add it to the array If byPos.max = 15 Then Break 'Once the array has 16 numbers grt out of here. 0 is used for the blank space
Loop
For byRand = 0 To 15 'Loop
If byPos[byRand] = 0 Then 'Check if value is 0 as this is where the blank space will go AddPanel 'Go to the AddPanel routine to add the blank space Continue 'Skip to the end of the loop Endif hButton = New Button(Me) As "AllButtons" 'Add a new button to the Form, all buttons grouped as 'AllButtons' With hButton 'With the following properties .Text = Str(byPos[byRand]) 'Add Button text .Tag = Str(byPos[byRand]) 'Add a Tag .Height = 60 'Set the Button height .Width = 60 'Set the Button width .Font.Bold = True 'Set the font to Bold .Font.Size = 16 'Set Font size End With
Next
AddTimer 'Go to the AddTimer routine
End
Public Sub AddPanel() 'Routine to add an invisible panel that is the blank area Dim hPanel As Panel 'We need a Panel
HPanel = New Panel(Me) 'Add the Panel to the Form With HPanel 'With the following Properties
.Tag = 0 'Set a Tag to 0 .Height = 60 'Set the height .Width = 60 'Set the width
End With
End
Public Sub AddTimer() 'To add a Timer
hTimer = New Timer As "MyTimer" 'Add a Timer hTimer.Delay = 250 'Set the delay 1/4 second hTimer.Start 'Start the Timer
End
Public Sub MyTimer_Timer() 'This routine runs every 1/4 second
Me.Title = siMoves & " Moves " 'Set the Form Title to show the amount of moves taken
If dTimerStart Then 'If a start time has been set then
dTimerDiff = Time(Now) - dTimerStart 'Calculate the time difference between StartTime and Now Me.Title &= " - " & Str(dTimerDiff) 'Add the time taken to the Form Title
End If
End
Public Sub AllButtons_Click() 'What to do when a Button is clicked Dim byLast As Byte = Last.Tag 'Get the Tag of the Button clicked Dim byTemp, byCount As Byte 'Various variables Dim byCheck As Byte[] = [99, 99, 99, 99] 'Used for checking for the blank space Dim oObj As Object 'We need to enumerate Objects
For Each oObj In Me.Children 'For each Object (Buttons in this case) that are Children of the Form..
If oObj.Tag = byLast Then Break 'If the Tag of the Button matches then we know the position of the Button on the form so get out of here Inc byCount 'Increase the value of byCount
Next
Select Case byCount 'Depending on the position of the Button
Case 0 'e.g 0 then we need to check positions 1 & 4 for the blank byCheck[0] = 1 byCheck[1] = 4 Case 1 byCheck[0] = 0 byCheck[1] = 2 byCheck[2] = 5 Case 2 byCheck[0] = 1 byCheck[1] = 3 byCheck[2] = 6 Case 3 byCheck[0] = 2 byCheck[1] = 7 Case 4 byCheck[0] = 0 byCheck[1] = 5 byCheck[2] = 8 Case 5 'e.g 5 then we need to check positions 1, 4, 6 & 9 for the blank byCheck[0] = 1 byCheck[1] = 4 byCheck[2] = 6 byCheck[3] = 9 Case 6 byCheck[0] = 2 byCheck[1] = 5 byCheck[2] = 7 byCheck[3] = 10 Case 7 byCheck[0] = 3 byCheck[1] = 6 byCheck[2] = 11 Case 8 byCheck[0] = 4 byCheck[1] = 9 byCheck[2] = 12 Case 9 byCheck[0] = 5 byCheck[1] = 8 byCheck[2] = 10 byCheck[3] = 13 Case 10 byCheck[0] = 6 byCheck[1] = 9 byCheck[2] = 11 byCheck[3] = 14 Case 11 byCheck[0] = 7 byCheck[1] = 10 byCheck[2] = 15 Case 12 byCheck[0] = 8 byCheck[1] = 13 Case 13 byCheck[0] = 9 byCheck[1] = 12 byCheck[2] = 14 Case 14 byCheck[0] = 10 byCheck[1] = 13 byCheck[2] = 15 Case 15 byCheck[0] = 11 byCheck[1] = 14
End Select
For Each byTemp In byCheck 'For each value in byCheck
If byTemp = 99 Then Break 'If byTemp = 99 then get out of here If byPos[byTemp] = 0 Then 'If the position checked is 0 (the blank) then.. byPos[byTemp] = Last.Text 'Set the new position of the Tile in byPos byPos[byCount] = 0 'Set the existing Tile position to = 0 (blank) Inc siMoves 'Inc the amount of moves made If Not bTimerOn Then 'If the Timer is now needed then dTimerStart = Time(Now) 'Set the Start time to NOW bTimerOn = True 'Set bTimerOn to True Endif Break 'Get out of here End If
Next
RebuildForm 'Go to the RebuilForm routine
End
Public Sub RebuildForm() 'To clear the Form and rebuild with the Tiles in the new postion Dim hButton As Button 'We need Buttons Dim byCount, byTemp As Byte 'Various variables
Me.Children.clear 'Clear the Form of all Objects
For Each byTemp In byPos 'For each 'Position'
If byTemp = 0 Then 'If the Position's value is 0 then it's the space AddPanel 'Go to the AddPanel routine Else 'If the Position's value is NOT 0 then hButton = New Button(Me) As "AllButtons" 'Create a new Button With hButton 'With the following properties .Text = Str(byPos[byCount]) 'Text as stored in byPos .Tag = Str(byPos[byCount]) 'Tag as stored in byPos .Height = 60 'Set the Button height .Width = 60 'Set the Button width .Font.Bold = True 'Set the Font to Bold .Font.Size = 16 'Set Font size End With Endif Inc byCount 'Increase counter
Next
End</lang>
- Output:
Haskell
<lang haskell>import Data.Array import System.Random
type Puzzle = Array (Int, Int) Int
main :: IO () main = do
putStrLn "Please enter the difficulty level: 0, 1 or 2" userInput <- getLine let diffLevel = read userInput if userInput == "" || any (\c -> c < '0' || c > '9') userInput || diffLevel > 2 || diffLevel < 0 then putStrLn "That is not a valid difficulty level." >> main else shufflePuzzle ([10, 50, 100] !! diffLevel) solvedPuzzle >>= gameLoop
gameLoop :: Puzzle -> IO () gameLoop puzzle
| puzzle == solvedPuzzle = putStrLn "You solved the puzzle!" >> printPuzzle puzzle | otherwise = do printPuzzle puzzle putStrLn "Please enter number to move" userInput <- getLine if any (\c -> c < '0' || c > '9') userInput then putStrLn "That is not a valid number." >> gameLoop puzzle else let move = read userInput in if move `notElem` validMoves puzzle then putStrLn "This move is not available." >> gameLoop puzzle else gameLoop (applyMove move puzzle)
validMoves :: Puzzle -> [Int] validMoves puzzle = [puzzle ! (row', column') |
row' <- [rowEmpty-1..rowEmpty+1], column' <- [columnEmpty-1..columnEmpty+1], row' < 4, row' >= 0, column' < 4, column' >= 0, (row' == rowEmpty) /= (column' == columnEmpty)] where (rowEmpty, columnEmpty) = findIndexOfNumber 16 puzzle
applyMove :: Int -> Puzzle -> Puzzle applyMove numberToMove puzzle = puzzle // [(indexToMove, 16), (emptyIndex, numberToMove)]
where indexToMove = findIndexOfNumber numberToMove puzzle emptyIndex = findIndexOfNumber 16 puzzle
findIndexOfNumber :: Int -> Puzzle -> (Int, Int) findIndexOfNumber number puzzle = case filter (\idx -> number == puzzle ! idx)
(indices puzzle) of [idx] -> idx _ -> error "BUG: number not in puzzle"
printPuzzle :: Puzzle -> IO () printPuzzle puzzle = do
putStrLn "+--+--+--+--+" putStrLn $ "|" ++ formatCell (0, 0) ++ "|" ++ formatCell (0, 1) ++ "|" ++ formatCell (0, 2) ++ "|" ++ formatCell (0, 3) ++ "|" putStrLn "+--+--+--+--+" putStrLn $ "|" ++ formatCell (1, 0) ++ "|" ++ formatCell (1, 1) ++ "|" ++ formatCell (1, 2) ++ "|" ++ formatCell (1, 3) ++ "|" putStrLn "+--+--+--+--+" putStrLn $ "|" ++ formatCell (2, 0) ++ "|" ++ formatCell (2, 1) ++ "|" ++ formatCell (2, 2) ++ "|" ++ formatCell (2, 3) ++ "|" putStrLn "+--+--+--+--+" putStrLn $ "|" ++ formatCell (3, 0) ++ "|" ++ formatCell (3, 1) ++ "|" ++ formatCell (3, 2) ++ "|" ++ formatCell (3, 3) ++ "|" putStrLn "+--+--+--+--+" where formatCell idx | i == 16 = " " | i > 9 = show i | otherwise = " " ++ show i where i = puzzle ! idx
solvedPuzzle :: Puzzle solvedPuzzle = listArray ((0, 0), (3, 3)) [1..16]
shufflePuzzle :: Int -> Puzzle -> IO Puzzle shufflePuzzle 0 puzzle = return puzzle shufflePuzzle numOfShuffels puzzle = do
let moves = validMoves puzzle randomIndex <- randomRIO (0, length moves - 1) let move = moves !! randomIndex shufflePuzzle (numOfShuffels - 1) (applyMove move puzzle)</lang>
Output:
Please enter the difficulty level: 0, 1 or 2 0 +--+--+--+--+ | 1| 6| 2| 4| +--+--+--+--+ | 5|10| 3| 8| +--+--+--+--+ | 9|14| 7|11| +--+--+--+--+ |13| |15|12| +--+--+--+--+ Please enter number to move 14 +--+--+--+--+ | 1| 6| 2| 4| +--+--+--+--+ | 5|10| 3| 8| +--+--+--+--+ | 9| | 7|11| +--+--+--+--+ |13|14|15|12| +--+--+--+--+ Please enter number to move
J
Implementation:
<lang J>require'general/misc/prompt'
genboard=:3 :0
b=. ?~16 if. 0<C.!.2 b do. b=. (<0 _1)C. b end. a: (b i.0)} <"0 b
)
done=: (<"0]1+i.15),a:
shift=: |.!._"0 2 taxi=: |:,/"2(_1 1 shift i.4 4),_1 1 shift"0 1/ i.4 4
showboard=:3 :0
echo 'current board:' echo 4 4$y
)
help=:0 :0
Slide a number block into the empty space until you get:
┌──┬──┬──┬──┐ │1 │2 │3 │4 │ ├──┼──┼──┼──┤ │5 │6 │7 │8 │ ├──┼──┼──┼──┤ │9 │10│11│12│ ├──┼──┼──┼──┤ │13│14│15│ │ └──┴──┴──┴──┘
Or type 'q' to quit.
)
getmove=:3 :0
showboard y blank=. y i. a: options=. /:~ ;y {~ _ -.~ blank { taxi whilst. -. n e. options do. echo 'Valid moves: ',":options t=. prompt 'move which number? ' if. 'q' e. t do. echo 'giving up' throw. elseif. 'h' e. t do. echo help showboard y end. n=. {._".t end. (<blank,y i.<n) C. y
)
game=: 3 :0
echo '15 puzzle' echo 'h for help, q to quit' board=. genboard whilst. -. done-:board do. board=. getmove board end. showboard board echo 'You win.'
)</lang>
Most of this is user interface code. We initially shuffle the numbers randomly, then check their parity and swap the first and last squares if needed. Then, for each move, we allow the user to pick one of the taxicab neighbors of the empty square.
A full game would be too big to be worth showing here, so for the purpose of giving a glimpse of what this looks like in action we replace the random number generator with a constant:
<lang J> game 15 puzzle h for help, q to quit current board: ┌──┬──┬──┬──┐ │1 │2 │3 │4 │ ├──┼──┼──┼──┤ │5 │6 │7 │8 │ ├──┼──┼──┼──┤ │9 │10│ │11│ ├──┼──┼──┼──┤ │13│14│15│12│ └──┴──┴──┴──┘ Valid moves: 7 10 11 15 move which number? 11 current board: ┌──┬──┬──┬──┐ │1 │2 │3 │4 │ ├──┼──┼──┼──┤ │5 │6 │7 │8 │ ├──┼──┼──┼──┤ │9 │10│11│ │ ├──┼──┼──┼──┤ │13│14│15│12│ └──┴──┴──┴──┘ Valid moves: 8 11 12 move which number? 12 current board: ┌──┬──┬──┬──┐ │1 │2 │3 │4 │ ├──┼──┼──┼──┤ │5 │6 │7 │8 │ ├──┼──┼──┼──┤ │9 │10│11│12│ ├──┼──┼──┼──┤ │13│14│15│ │ └──┴──┴──┴──┘ You win.</lang>
Java
<lang java>import java.awt.*; import java.awt.event.*; import java.util.Random; import javax.swing.*;
public class FifteenPuzzle extends JPanel {
final static int numTiles = 15; final static int side = 4;
Random rand = new Random(); int[] tiles = new int[numTiles + 1]; int tileSize, blankPos, margin, gridSize;
public FifteenPuzzle() { final int dim = 640;
margin = 80; tileSize = (dim - 2 * margin) / side; gridSize = tileSize * side;
setPreferredSize(new Dimension(dim, dim)); setBackground(Color.white); setForeground(new Color(0x6495ED)); // cornflowerblue setFont(new Font("SansSerif", Font.BOLD, 60));
addMouseListener(new MouseAdapter() { @Override public void mousePressed(MouseEvent e) { int ex = e.getX() - margin; int ey = e.getY() - margin;
if (ex < 0 || ex > gridSize || ey < 0 || ey > gridSize) return;
int c1 = ex / tileSize; int r1 = ey / tileSize; int c2 = blankPos % side; int r2 = blankPos / side;
if ((c1 == c2 && Math.abs(r1 - r2) == 1) || (r1 == r2 && Math.abs(c1 - c2) == 1)) {
int clickPos = r1 * side + c1; tiles[blankPos] = tiles[clickPos]; tiles[clickPos] = 0; blankPos = clickPos; } repaint(); } });
shuffle(); }
final void shuffle() { do { reset(); // don't include the blank space in the shuffle, leave it // in the home position int n = numTiles; while (n > 1) { int r = rand.nextInt(n--); int tmp = tiles[r]; tiles[r] = tiles[n]; tiles[n] = tmp; } } while (!isSolvable()); }
void reset() { for (int i = 0; i < tiles.length; i++) tiles[i] = (i + 1) % tiles.length; blankPos = numTiles; }
/* Only half the permutations of the puzzle are solvable.
Whenever a tile is preceded by a tile with higher value it counts as an inversion. In our case, with the blank space in the home position, the number of inversions must be even for the puzzle to be solvable.
See also: www.cs.bham.ac.uk/~mdr/teaching/modules04/java2/TilesSolvability.html */ boolean isSolvable() { int countInversions = 0; for (int i = 0; i < numTiles; i++) { for (int j = 0; j < i; j++) { if (tiles[j] > tiles[i]) countInversions++; } } return countInversions % 2 == 0; }
void drawGrid(Graphics2D g) { for (int i = 0; i < tiles.length; i++) { if (tiles[i] == 0) continue;
int r = i / side; int c = i % side; int x = margin + c * tileSize; int y = margin + r * tileSize;
g.setColor(getForeground()); g.fillRoundRect(x, y, tileSize, tileSize, 25, 25); g.setColor(Color.black); g.drawRoundRect(x, y, tileSize, tileSize, 25, 25); g.setColor(Color.white);
drawCenteredString(g, String.valueOf(tiles[i]), x, y); } }
void drawCenteredString(Graphics2D g, String s, int x, int y) { FontMetrics fm = g.getFontMetrics(); int asc = fm.getAscent(); int dec = fm.getDescent();
x = x + (tileSize - fm.stringWidth(s)) / 2; y = y + (asc + (tileSize - (asc + dec)) / 2);
g.drawString(s, x, y); }
@Override public void paintComponent(Graphics gg) { super.paintComponent(gg); Graphics2D g = (Graphics2D) gg; g.setRenderingHint(RenderingHints.KEY_ANTIALIASING, RenderingHints.VALUE_ANTIALIAS_ON);
drawGrid(g); }
public static void main(String[] args) { SwingUtilities.invokeLater(() -> { JFrame f = new JFrame(); f.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE); f.setTitle("Fifteen Puzzle"); f.setResizable(false); f.add(new FifteenPuzzle(), BorderLayout.CENTER); f.pack(); f.setLocationRelativeTo(null); f.setVisible(true); }); }
}</lang>
Livecode
<lang livecode>
- Please note that all this code can be performed in livecode with just few mouse clicks
- This is just a pure script exampe
on OpenStack
show me #Usually not necessary #tile creation set the width of the templateButton to 50 set the height of the templateButton to 50 repeat with i=1 to 16 create button set the label of button i to i if i =1 then set the top of button 1 to 0 set the left of button 1 to 0 end if if i > 1 and 1 <=4 then set the left of button i to the right of button (i-1) set the top of button i to the top of button 1 end if if i >= 5 and i <= 8 then set the top of button i to the bottom of button 1 if i = 5 then set the left of button i to the left of button 1 else set the left of button i to the right of button (i - 1) end if end if if i >= 9 and i <= 12 then set the top of button i to the bottom of button 5 if i = 9 then set the left of button i to the left of button 1 else set the left of button i to the right of button (i - 1) end if end if if i >= 13 and i <= 16 then set the top of button i to the bottom of button 9 if i = 13 then set the left of button i to the left of button 1 else set the left of button i to the right of button (i - 1) end if end if #this is usally the script directly wirtten in the objects, it's really weird this way put "on MouseUp" &CR& "if checkDistance(the label of me) then" & CR &"put the loc of me into temp" into ts put CR& "set the loc of me to the loc of button 16" after ts put CR& "set the loc of button 16 to temp" & Cr & "end if " &CR &"End MouseUp" after ts set the script of button i to ts end repeat #graphic adjustements set the visible of button 16 to false set the width of this stack to the right of button 16 set the height of this stack to the bottom of button 16
end openStack
function checkDistance i
if (((the top of button i - the bottom of button 16) = 0 OR (the top of button 16 - the bottom of button i) = 0) AND the left of button i = the left of button 16) OR (((the left of button i - the right of button 16) = 0 OR (the right of button i - the left of button 16) = 0) AND the top of button i = the top of button 16) then return true else return false end if
end checkDistance </lang> Screenshot: [2]
Perl 6
Most of this is interface code. Reused substantial portions from the 2048 task. Use the arrow keys to slide tiles, press 'q' to quit or 'n' for a new puzzle. Requires a POSIX termios aware terminal. Ensures that the puzzle is solvable by shuffling the board with an even number of swaps, then checking for even taxicab parity for the empty space. <lang perl6>use Term::termios;
constant $saved = Term::termios.new(fd => 1).getattr; constant $termios = Term::termios.new(fd => 1).getattr;
- raw mode interferes with carriage returns, so
- set flags needed to emulate it manually
$termios.unset_iflags(<BRKINT ICRNL ISTRIP IXON>); $termios.unset_lflags(< ECHO ICANON IEXTEN ISIG>); $termios.setattr(:DRAIN);
- reset terminal to original setting on exit
END { $saved.setattr(:NOW) }
constant n = 4; # board size constant cell = 6; # cell width
constant $top = join '─' x cell, '┌', '┬' xx n-1, '┐'; constant $mid = join '─' x cell, '├', '┼' xx n-1, '┤'; constant $bot = join '─' x cell, '└', '┴' xx n-1, '┘';
my %dir = (
"\e[A" => 'up', "\e[B" => 'down', "\e[C" => 'right', "\e[D" => 'left',
);
my @solved = [1,2,3,4],[5,6,7,8],[9,10,11,12],[13,14,15,' ']; my @board; new();
sub new () {
loop { @board = shuffle(); last if parity-ok(@board); }
}
sub parity-ok (@b) {
my $row = @b.first(/' '/,:k); my $col = @b[$row].first(/' '/,:k); so ([3,3] <<->> [$row,$col]).sum %% 2;
}
sub shuffle () {
my @c = [1,2,3,4],[5,6,7,8],[9,10,11,12],[13,14,15,' ']; for (^16).pick(*) -> $y, $x { my ($yd, $ym, $xd, $xm) = ($y div n, $y mod n, $x div n, $x mod n); my $temp = @c[$ym;$yd]; @c[$ym;$yd] = @c[$xm;$xd]; @c[$xm;$xd] = $temp; } @c;
}
sub row (@row) { '│' ~ (join '│', @row».¢er) ~ '│' }
sub center ($s){
my $c = cell - $s.chars; my $pad = ' ' x ceiling($c/2); sprintf "%{cell}s", "$s$pad";
}
sub draw-board {
run('clear'); print qq:to/END/;
Press direction arrows to move.
Press q to quit. Press n for a new puzzle.
$top { join "\n\t$mid\n\t", map { .&row }, @board } $bot
{ (so @board ~~ @solved) ?? 'Solved!!' !! } END }
sub slide (@c is copy) {
my $t = (grep { /' '/ }, :k, @c)[0]; return @c unless $t and $t > 0; @c[$t,$t-1] = @c[$t-1,$t]; @c;
}
multi sub move('up') {
map { @board[*;$_] = reverse slide reverse @board[*;$_] }, ^n;
}
multi sub move('down') {
map { @board[*;$_] = slide @board[*;$_] }, ^n;
}
multi sub move('left') {
map { @board[$_] = reverse slide reverse @board[$_] }, ^n;
}
multi sub move('right') {
map { @board[$_] = slide @board[$_] }, ^n;
}
loop {
draw-board;
# Read up to 4 bytes from keyboard buffer. # Page navigation keys are 3-4 bytes each. # Specifically, arrow keys are 3. my $key = $*IN.read(4).decode;
move %dir{$key} if so %dir{$key}; last if $key eq 'q'; # (q)uit new() if $key eq 'n';
}</lang> Sample screen shot:
Press direction arrows to move. Press q to quit. Press n for a new puzzle. ┌──────┬──────┬──────┬──────┐ │ 2 │ 1 │ 10 │ 14 │ ├──────┼──────┼──────┼──────┤ │ 15 │ 11 │ 12 │ │ ├──────┼──────┼──────┼──────┤ │ 13 │ 3 │ 6 │ 7 │ ├──────┼──────┼──────┼──────┤ │ 9 │ 4 │ 5 │ 8 │ └──────┴──────┴──────┴──────┘
Phix
Kept simple. Obviously, increase the 5 random moves for more of a challenge. <lang Phix>constant ESC=27, UP=328, LEFT=331, RIGHT=333, DOWN=336 sequence board = tagset(15)&0, solve = board integer pos = 16
procedure print_board()
for i=1 to length(board) do puts(1,iff(i=pos?" ":sprintf("%3d",{board[i]}))) if mod(i,4)=0 then puts(1,"\n") end if end for puts(1,"\n")
end procedure
procedure move(integer d)
integer new_pos = pos+{+4,+1,-1,-4}[d] if new_pos>=1 and new_pos<=16 and (mod(pos,4)=mod(new_pos,4) -- same col, or row: or floor((pos-1)/4)=floor((new_pos-1)/4)) then {board[pos],board[new_pos]} = {board[new_pos],0} pos = new_pos end if
end procedure
for i=1 to 5 do move(rand(4)) end for while 1 do
print_board() if board=solve then exit end if integer c = find(wait_key(),{ESC,UP,LEFT,RIGHT,DOWN})-1 if c=0 then exit end if move(c)
end while puts(1,"solved!\n")</lang>
- Output:
1 2 3 4 5 6 8 9 10 7 11 13 14 15 12 1 2 3 4 5 6 8 9 10 7 11 13 14 15 12 1 2 3 4 5 6 7 8 9 10 11 13 14 15 12 1 2 3 4 5 6 7 8 9 10 11 13 14 15 12 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 solved!
Python
unoptimized <lang python> Structural Game for 15 - Puzzle with different difficulty levels from random import randint
class Puzzle:
def __init__(self): self.items = {} self.position = None
def main_frame(self): d = self.items print('+-----+-----+-----+-----+') print('|%s|%s|%s|%s|' % (d[1], d[2], d[3], d[4])) print('+-----+-----+-----+-----+') print('|%s|%s|%s|%s|' % (d[5], d[6], d[7], d[8])) print('+-----+-----+-----+-----+') print('|%s|%s|%s|%s|' % (d[9], d[10], d[11], d[12])) print('+-----+-----+-----+-----+') print('|%s|%s|%s|%s|' % (d[13], d[14], d[15], d[16])) print('+-----+-----+-----+-----+')
def format(self, ch): ch = ch.strip() if len(ch) == 1: return ' ' + ch + ' ' elif len(ch) == 2: return ' ' + ch + ' ' elif len(ch) == 0: return ' '
def change(self, to): fro = self.position for a, b in self.items.items(): if b == self.format(str(to)): to = a break self.items[fro], self.items[to] = self.items[to], self.items[fro] self.position = to
def build_board(self, difficulty): for i in range(1, 17): self.items[i] = self.format(str(i)) tmp = 0 for a, b in self.items.items(): if b == ' 16 ': self.items[a] = ' ' tmp = a break self.position = tmp if difficulty == 0: diff = 10 elif difficulty == 1: diff = 50 else: diff = 100 for _ in range(diff): lst = self.valid_moves() lst1 = [] for j in lst: lst1.append(int(j.strip())) self.change(lst1[randint(0, len(lst1)-1)])
def valid_moves(self): pos = self.position if pos in [6, 7, 10, 11]: return self.items[pos - 4], self.items[pos - 1],\ self.items[pos + 1], self.items[pos + 4] elif pos in [5, 9]: return self.items[pos - 4], self.items[pos + 4],\ self.items[pos + 1] elif pos in [8, 12]: return self.items[pos - 4], self.items[pos + 4],\ self.items[pos - 1] elif pos in [2, 3]: return self.items[pos - 1], self.items[pos + 1], self.items[pos + 4] elif pos in [14, 15]: return self.items[pos - 1], self.items[pos + 1],\ self.items[pos - 4] elif pos == 1: return self.items[pos + 1], self.items[pos + 4] elif pos == 4: return self.items[pos - 1], self.items[pos + 4] elif pos == 13: return self.items[pos + 1], self.items[pos - 4] elif pos == 16: return self.items[pos - 1], self.items[pos - 4]
def game_over(self): flag = False for a, b in self.items.items(): if b == ' ': pass else: if a == int(b.strip()): flag = True else: flag = False return flag
g = Puzzle()
g.build_board(int(input('Enter the difficulty : 0 1 2\n2 '
'=> highest 0=> lowest\n')))
g.main_frame() print('Enter 0 to exit') while True:
print('Hello user:\nTo change the position just enter the no. near it') lst = g.valid_moves() lst1 = [] for i in lst: lst1.append(int(i.strip())) print(i.strip(), '\t', end=) print() x = int(input()) if x == 0: break elif x not in lst1: print('Wrong move') else: g.change(x) g.main_frame() if g.game_over(): print('You WON') break
</lang>
Enter the difficulty : 0 1 2 2 => highest 0=> lowest 1 +-----+-----+-----+-----+ | 1 | 7 | 2 | 4 | +-----+-----+-----+-----+ | 5 | 6 | 3 | 12 | +-----+-----+-----+-----+ | 9 | 8 | 11 | 15 | +-----+-----+-----+-----+ | 13 | 10 | 14 | | +-----+-----+-----+-----+ Enter 0 to exit Hello user: To change the position just enter the no. near it 14 15 14 +-----+-----+-----+-----+ | 1 | 7 | 2 | 4 | +-----+-----+-----+-----+ | 5 | 6 | 3 | 12 | +-----+-----+-----+-----+ | 9 | 8 | 11 | 15 | +-----+-----+-----+-----+ | 13 | 10 | | 14 | +-----+-----+-----+-----+ Hello user: To change the position just enter the no. near it 10 14 11
Racket
This is a GUI game; and there are difficulties getting screen shots onto RC. Use the arrow keys to slide the blank square.
It uses the 2htdp/universe
package.
<lang racket>#lang racket/base (require 2htdp/universe 2htdp/image racket/list racket/match)
(define ((fifteen->pict (finished? #f)) fifteen)
(for/fold ((i (empty-scene 0 0))) ((r 4)) (define row (for/fold ((i (empty-scene 0 0))) ((c 4)) (define v (list-ref fifteen (+ (* r 4) c))) (define cell (if v (overlay/align "center" "center" (rectangle 50 50 'outline (if finished? "white" "blue")) (text (number->string v) 30 "black")) (rectangle 50 50 'solid (if finished? "white" "powderblue")))) (beside i cell))) (above i row)))
(define (move-space fifteen direction)
(define idx (for/first ((i (in-naturals)) (x fifteen) #:unless x) i)) (define-values (row col) (quotient/remainder idx 4)) (define dest (+ idx (match direction ['l #:when (> col 0) -1] ['r #:when (< col 3) 1] ['u #:when (> row 0) -4] ['d #:when (< row 3) 4] [else 0]))) (list-set (list-set fifteen idx (list-ref fifteen dest)) dest #f))
(define (key-move-space fifteen a-key)
(cond [(key=? a-key "left") (move-space fifteen 'l)] [(key=? a-key "right") (move-space fifteen 'r)] [(key=? a-key "up") (move-space fifteen 'u)] [(key=? a-key "down") (move-space fifteen 'd)] [else fifteen]))
(define (shuffle-15 fifteen shuffles)
(for/fold ((rv fifteen)) ((_ shuffles)) (move-space rv (list-ref '(u d l r) (random 4)))))
(define fifteen0 '(1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 #f))
(define (solved-world? w) (equal? w fifteen0))
(big-bang (shuffle-15 fifteen0 200)
(name "Fifteen") (to-draw (fifteen->pict)) (stop-when solved-world? (fifteen->pict #t)) (on-key key-move-space))</lang>
Rebol
<lang Rebol>rebol [] random/seed now g: [style t box red [
if not find [0x108 108x0 0x-108 -108x0] face/offset - e/offset [exit] x: face/offset face/offset: e/offset e/offset: x] across
] x: random repeat i 15 [append x:[] i] repeat i 15 [
append g reduce ['t mold x/:i] if find [4 8 12] i [append g 'return]
] append g [e: box] view layout g</lang>
REXX
This REXX version allows the user to specify the size of the puzzle (N, where NxN is the size of the puzzle).
With some more complexity, the REXX computer program could be changed to allow multiple-tile moves (so that, for instance, three tiles could be slid to the right).
Over half of the REXX program has to do with input validation and presentation of the puzzle (grid). <lang rexx>/*REXX program implements the 15-puzzle (AKA: Gem Puzzle, Boss Puzzle, Mystic Square).*/ parse arg N seed .; sep= '────────' /*obtain optional arguments from the CL*/ if N== | N=="," then N=4 /*Not specified? Then use the default.*/ if datatype(seed,'W') then call random ,,seed /*use repeatability seed for RANDOM BIF*/ prompt= sep 'Please enter a tile number ' sep " (or Quit)." pad=translate(sep,,'─')" "; nn=N*N-1; nh=N*N; w=length(nn); @.= $=
do i=1 for nn; $=$ i; end /*i*/ /* [◄] build a solution for testing. */
done=$ /* [↓] scramble the tiles in puzzle. */
do j=1 for nn; a=random(1,words($)); @.j=word($,a); $=delword($,a,1); end /*j*/
do until puzz=done & @.nh== /*perform moves until puzzle is solved.*/ x=0; call showGrid 1; say; say prompt; pull x _ . if abbrev('QUIT', x, 1) then do; say; say; say sep "quitting."; exit; end select when x == then errMsg= "nothing entered" when _\== then errMsg= "too many items entered" when \datatype(x, 'N') then errMsg= "tile number isn't numeric" when \datatype(x, 'W') then errMsg= "tile number isn't an integer" when x=0 then errMsg= "tile number can't be zero" when x<0 then errMsg= "tile number can't be negative" when x>nn then errMsg= "tile number can't be greater than" nn otherwise errMsg= end /*select*/ /* [↑] verify the human entered data. */
if errMsg\== then do; say sep errMsg"."; iterate; end /*possible error message? */ call showGrid 0; g= /*validate, is move is OK?*/ rm=holeRow-1; rp=holeRow+1; cm=holeCol-1; cp=holeCol+1 /*these are possible moves*/ g=!.rm.holeCol !.rp.holeCol !.holeRow.cm !.holeRow.cp /* " " legal " */ if wordpos(x,g)==0 then do; say sep 'tile' x "can't be moved."; iterate; end @.hole=x; @.tile=; call showGrid 0 /*move specified tile ───► puzzle hole.*/ end /*until*/
call showGrid 1; say; say sep 'Congratulations! The' nn"-puzzle is solved." exit /*stick a fork in it, we're all done. */ /*──────────────────────────────────────────────────────────────────────────────────────*/ showGrid: parse arg show; !.=; #=0; x=x/1; puzz=
top= '╔'copies( copies("═", w)'╦', N); top=left( top, length(top) -1)"╗" bar= '╠'copies( copies("═", w)'╬', N); bar=left( bar, length(bar) -1)"╣" bot= '╚'copies( copies("═", w)'╩', N); bot=left( bot, length(bot) -1)"╝" if show then say pad top do r=1 for N; z='║' do c=1 for N; #=#+1; y=@.#; puzz=puzz y; !.r.c=y _=right(@.#, w)"║"; z=z || _ /* [↓] find hole*/ if @.#== then do; hole=#; holeRow=r; holeCol=c; end if @.#==x then do; tile=#; tileRow=r; tileCol=c; end end /*c*/ /* [↑] find X. */ if show then do; say pad z; if r\==N then say pad bar; end end /*r*/ if show then say pad bot return</lang>
output when using the default input:
╔══╦══╦══╦══╗ ║10║ 7║ 8║11║ ╠══╬══╬══╬══╣ ║ 4║ 3║15║ 1║ ╠══╬══╬══╬══╣ ║ 9║12║ 2║13║ ╠══╬══╬══╬══╣ ║14║ 5║ 6║ ║ ╚══╩══╩══╩══╝ ──────── Please enter a tile number ──────── (or Quit). 13 ◄■■■■■■■■■■ user input. ╔══╦══╦══╦══╗ ║10║ 7║ 8║11║ ╠══╬══╬══╬══╣ ║ 4║ 3║15║ 1║ ╠══╬══╬══╬══╣ ║ 9║12║ 2║ ║ ╠══╬══╬══╬══╣ ║14║ 5║ 6║13║ ╚══╩══╩══╩══╝ ──────── Please enter a tile number ──────── (or Quit). 1 ◄■■■■■■■■■■ user input. ╔══╦══╦══╦══╗ ║10║ 7║ 8║11║ ╠══╬══╬══╬══╣ ║ 4║ 3║15║ ║ ╠══╬══╬══╬══╣ ║ 9║12║ 2║ 1║ ╠══╬══╬══╬══╣ ║14║ 5║ 6║13║ ╚══╩══╩══╩══╝ ──────── Please enter a tile number ──────── (or Quit). 15 ◄■■■■■■■■■■ user input. ╔══╦══╦══╦══╗ ║10║ 7║ 8║11║ ╠══╬══╬══╬══╣ ║ 4║ 3║ ║15║ ╠══╬══╬══╬══╣ ║ 9║12║ 2║ 1║ ╠══╬══╬══╬══╣ ║14║ 5║ 6║13║ ╚══╩══╩══╩══╝ ──────── Please enter a tile number ──────── (or Quit). quit ◄■■■■■■■■■■ user input. ──────── quitting.
Ring
CalmoSoft Fifteen Puzzle Game written in Ring Programming Language (http://ring-lang.net)
Video: CalmoSoft Fifteen Puzzle Game
The code: <lang ring>load "guilib.ring"
load "guilib.ring"
app1 = new qapp {
empty = 16 nrold = 4 button = list(52) sizebtn = list(7)
win1 = new qwidget() { move(0,0) resize(380,480) setwindowtitle("Calmosoft Fifteen Puzzle Game")
for n = 1 to 16 col = n%4 if col = 0 col = 4 ok row = ceil(n/4) button[n] = new qpushbutton (win1) { setgeometry(60+col*40,60+row*40,40,40) settext(string(n)) setclickevent("movetile(" + string(n) +")") } next
button[16] {settext("")}
for n = 4 to 7 sizebtn[n] = new qpushbutton(win1) { col = n%4 setgeometry(100+col*40,60,40,40) settext(string(n) + "x" + string(n)) setclickevent("size(" + string(n) + ")") } next
button[17] = new qpushbutton(win1) { setgeometry(140,260,40,40) settext("<-") setclickevent("rotateleft()") }
button[18] = new qpushbutton(win1) { setgeometry(180,260,40,40) settext("Here") setclickevent("pHere()") }
button[19] = new qpushbutton(win1) { setgeometry(220,260,40,40) settext("->") setclickevent("rotateright()") }
scramblebtn = new qpushbutton(win1) { setgeometry(100,300,160,40) settext("Scramble") setclickevent("scramble()") }
resetbtn = new qpushbutton(win1) { setgeometry(100,340,160,40) settext("Reset") setclickevent("resettiles()") } show() } exec()
}
func scramble
for n= 1 to 10000 nr=random(nrold*nrold) up = (empty = (nr - nrold)) down = (empty = (nr + nrold)) left = ((empty = (nr - 1)) and ((nr % nrold) != 1)) right = ((empty = (nr + 1)) and ((nr % nrold) != 0)) move = up or down or left or right if move = 1 and (nr != 0) button[nr] { temp = text() } button[empty] {settext(temp)} button[nr] {settext("")} empty = nr ok next return
func movetile nr2
if (nr2 = nrold*nrold-1 and button[nr2].text() = "Back") pBack() else up = (empty = (nr2 - nrold)) down = (empty = (nr2 + nrold)) left = ((empty = (nr2- 1)) and ((nr2 % nrold) != 1)) right = ((empty = (nr2 + 1)) and ((nr2 % nrold) != 0)) move = up or down or left or right if move = 1 button[nr2] { temp2 = text() } button[empty] {settext(temp2)} button[nr2] {settext("")} empty = nr2 ok ok return
func resettiles
empty = nrold*nrold for i = 1 to nrold*nrold-1 button[i] {settext(string(i))} next button[nrold*nrold] {settext("")} return
func pHere
if button[nrold*nrold-1].text() != "" and button[nrold*nrold+2].text() = "Here" button[nrold*nrold-1] { temp = text() } button[nrold*nrold+2] {settext(temp)} for n = 1 to nrold*nrold button[n].setenabled(false) next button[nrold*nrold-1].setenabled(true) scramblebtn.setenabled(false) resetbtn.setenabled(false) button[nrold*nrold-1] {settext("Back")} return ok
func pBack
button[nrold*nrold+2] { temp = text() } button[nrold*nrold-1] {settext(temp)} button[nrold*nrold+2] {settext("Here")} for n = 1 to nrold*nrold button[n].setenabled(true) next scramblebtn.setenabled(true) resetbtn.setenabled(true) return
func rotateleft
if button[nrold*nrold+2].text() != "Here" button[nrold*nrold+2] {settext(string(number(button[nrold*nrold+2].text())-1))} return ok
func rotateright
if button[nrold*nrold+2].text() != "Here" button[nrold*nrold+2] {settext(string(number(button[nrold*nrold+2].text())+1))} return ok
func size nr
win1{ newsize = nr%4 win1.resize(380+newsize*40,480+newsize*40)
for n = 1 to nrold*nrold+3 button[n].close() next scramblebtn.close() resetbtn.close()
for n = 1 to nr*nr col = n%nr if col = 0 col = nr ok row = ceil(n/nr)
button[n] = new qpushbutton(win1) { setgeometry(60+col*40,60+row*40,40,40) settext(string(n)) setclickevent("movetile(" + string(n) +")") show() }
next
button[nr*nr+1] = new qpushbutton(win1) { setgeometry(60+(nr-2)*40,60+(nr+1)*40,40,40) settext("<-") setclickevent("rotateLeft()") show() } button[nr*nr+2] = new qpushbutton(win1) { setgeometry(60+(nr-1)*40,60+(nr+1)*40,40,40) settext("Here") setclickevent("pHere()") show() }
button[nr*nr+3] = new qpushbutton(win1) { setgeometry(60+nr*40,60+(nr+1)*40,40,40) settext("->") setclickevent("rotateRight()") show() }
scramblebtn = new qpushbutton(win1) { setgeometry(100,100+(nr+1)*40,nr*40,40) settext("Scramble") setclickevent("scramble()") show() }
resetbtn = new qpushbutton(win1) { setgeometry(100,100+(nr+2)*40,nr*40,40) settext("Reset") setclickevent("resettiles()") show() } button[nr*nr] {settext("")} empty = nr*nr nrold = nr }
</lang>
Output:
Ruby
<lang ruby>require 'io/console'
class Board
SIZE = 4 RANGE = 0...SIZE def initialize width = (SIZE*SIZE-1).to_s.size @frame = ("+" + "-"*(width+2)) * SIZE + "+" @form = "| %#{width}d " * SIZE + "|" @step = 0 @orign = [*0...SIZE*SIZE].rotate.each_slice(SIZE).to_a.freeze @board = @orign.map{|row | row.dup} randomize draw message play end private def randomize @board[0][0], @board[SIZE-1][SIZE-1] = 0, 1 @board[SIZE-1][0], @board[0][SIZE-1] = @board[0][SIZE-1], @board[SIZE-1][0] x, y, dx, dy = 0, 0, 1, 0 50.times do nx,ny = [[x+dx,y+dy], [x+dy,y-dx], [x-dy,y+dx]] .select{|nx,ny| RANGE.include?(nx) and RANGE.include?(ny)} .sample @board[nx][ny], @board[x][y] = 0, @board[nx][ny] x, y, dx, dy = nx, ny, nx-x, ny-y end @x, @y = x, y end def draw puts "\e[H\e[2J" @board.each do |row| puts @frame puts (@form % row).sub(" 0 ", " ") end puts @frame puts "Step: #{@step}" end DIR = {up: [-1,0], down: [1,0], left: [0,-1], right: [0,1]} def move(direction) dx, dy = DIR[direction] nx, ny = @x + dx, @y + dy if RANGE.include?(nx) and RANGE.include?(ny) @board[nx][ny], @board[@x][@y] = 0, @board[nx][ny] @x, @y = nx, ny @step += 1 draw end end def play until @board == @orign case key_in when "\e[A", "w" then move(:up) when "\e[B", "s" then move(:down) when "\e[C", "d" then move(:right) when "\e[D", "a" then move(:left) when "q","\u0003","\u0004" then exit when "h" then message end end puts "Congratulations, you have won!" end def key_in input = STDIN.getch if input == "\e" 2.times {input << STDIN.getch} end input end def message puts <<~EOM Use the arrow-keys or WASD on your keyboard to push board in the given direction. PRESS q TO QUIT (or Ctrl-C or Ctrl-D) EOM end
end
Board.new</lang>
- Output:
+----+----+----+----+ | 5 | 7 | 2 | 13 | +----+----+----+----+ | 6 | | 8 | 12 | +----+----+----+----+ | 10 | 3 | 1 | 15 | +----+----+----+----+ | 9 | 4 | 14 | 11 | +----+----+----+----+ Step: 0 Use the arrow-keys or WASD on your keyboard to push board in the given direction. PRESS q TO QUIT (or Ctrl-C or Ctrl-D)
Run BASIC
<lang runbasic>call SetCSS ' ---- fill 15 squares with 1 to 15 dim sq(16) for i = 1 to 15: sq(i) = i: next
'----- shuffle the squares [newGame] for i = 1 to 100 ' Shuffle the squares j = rnd(0) * 16 + 1 k = rnd(0) * 16 + 1 h = sq(j) sq(j) = sq(k) sq(k) = h next i
' ---- show the squares [loop] cls
html "
for i = 1 to 16
html "" if i mod 4 = 0 then html "" next i html ""
if sq(i) <> 0 then button #pick, str$(sq(i)), [pick] #pick setkey(str$(i)) #pick cssclass("lBtn") end if html " |
wait
' ---- Find what square they picked [pick] picked = val(EventKey$) move = 0 ' 0000000001111111 if picked - 1 > 0 then ' LEFT 1234567890123456 if mid$(" *** *** *** ***",picked,1) = "*" and sq(picked -1) = 0 then move = -1 :end if if picked + 1 < 17 then ' RIGHT if mid$("*** *** *** *** ",picked,1) = "*" and sq(picked +1) = 0 then move = 1 :end if if picked - 4 > 0 then ' UP if mid$(" ************",picked,1) = "*" and sq(picked -4) = 0 then move = -4 :end if if picked + 4 < 17 then ' DOWN if mid$("************ ",picked,1) = "*" and sq(picked +4) = 0 then move = 4 :end if ' ---- See if they picked a valid square next to the blank square if move = 0 then print "Invalid move: ";sq(picked) wait end if
' ---- Valid squire, switch it with the blank square sq(picked + move) = sq(picked) ' move to the empty square sq(picked) = 0 for i = 1 to 15 ' ---- If they got them all in a row they are a winner if sq(i) <> i then goto [loop] next i
print "----- You are a winner -----" input "Play again (Y/N)";a$ if a$ = "Y" then goto [newGame] ' set up new game end
' ---- Make the squares look nice SUB SetCSS CSSClass ".lBtn", "{ background:wheat;border-width:5px;width:70px; Text-Align:Center;Font-Size:24pt;Font-Weight:Bold;Font-Family:Arial; }" END SUB</lang> Output: File:KokengeGame15.jpg
Rust
<lang rust> extern crate rand; use rand::{thread_rng, Rng}; use std::collections::HashMap; use std::fmt;
- [derive(Copy, Clone)]
enum Cell {
Card(usize), Empty,
}
- [derive(Eq, PartialEq, Hash)]
enum Direction {
Up, Down, Left, Right,
}
enum Action {
Move(Direction), Quit,
}
struct P15 {
board: Vec<Cell>,
}
impl P15 { // todo: make the board valid right from the start.
fn new() -> P15 { let mut board = (1..16).map(Cell::Card).collect::<Vec<_>>(); board.push(Cell::Empty);
let mut rng = thread_rng();
rng.shuffle(board.as_mut_slice()); while !P15::is_valid(board.clone()) { rng.shuffle(board.as_mut_slice()); }
P15 { board: board } }
fn is_valid(mut board: Vec<Cell>) -> bool { let mut permutations = 0;
let pos = board.iter() .position(|&cell| match cell { Cell::Empty => true, _ => false, }) .unwrap();
if pos != 15 { board.swap(pos, 15); permutations += 1; }
for i in 1..16 { let pos = board.iter() .position(|&cell| match cell { Cell::Card(val) if val == i => true, _ => false, }) .unwrap();
if pos + 1 != i { board.swap(pos, i - 1); permutations += 1; } }
permutations % 2 == 0 }
fn get_empty_position(&self) -> usize { self.board .iter() .position(|&cell| match cell { Cell::Empty => true, _ => false, }) .unwrap() }
fn get_moves(&self) -> HashMap<Direction, Cell> { let mut moves = HashMap::with_capacity(4); let i = self.get_empty_position();
if i > 3 { moves.insert(Direction::Up, self.board[i - 4]); } if i % 4 != 0 { moves.insert(Direction::Left, self.board[i - 1]); } if i < 12 { moves.insert(Direction::Down, self.board[i + 4]); } if i % 4 != 3 { moves.insert(Direction::Right, self.board[i + 1]); } moves }
fn play(&mut self, direction: Direction) { use Direction::*; let i = self.get_empty_position(); match direction { Up => self.board.swap(i, i - 4), Left => self.board.swap(i, i - 1), Right => self.board.swap(i, i + 1), Down => self.board.swap(i, i + 4), }; }
fn is_complete(&self) -> bool { for (i, cell) in self.board.iter().enumerate() { match cell { &Cell::Card(value) if value == i + 1 => (), &Cell::Empty if i == 15 => (), _ => return false, }; } true }
}
impl fmt::Display for P15 {
fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result { use Cell::*; try!(write!(f, "+----+----+----+----+\n")); for (i, cell) in self.board.iter().enumerate() { match cell { &Card(value) => { try!(write!(f, "| {:2} ", value)); } &Empty => { try!(write!(f, "| ")); } };
if i % 4 == 3 { try!(write!(f, "|\n")); try!(write!(f, "+----+----+----+----+\n")); } } Ok(()) }
}
fn main() {
let mut p15 = P15::new(); let mut turns = 0; loop { println!("{}", p15); match ask_action(&p15.get_moves()) { Action::Move(direction) => { p15.play(direction); } Action::Quit => { println!("Bye !"); break; } }
turns += 1;
if p15.is_complete() { println!("Well done ! You win in {} turns", turns); break; }
}
}
fn ask_action(moves: &HashMap<Direction, Cell>) -> Action {
use std::io::{self, Write}; use Action::*; use Direction::*; println!("Possible moves :");
match moves.get(&Up) { Some(&Cell::Card(value)) => { println!("\tU) {}", value); } _ => (), } match moves.get(&Left) { Some(&Cell::Card(value)) => { println!("\tL) {}", value); } _ => (), } match moves.get(&Right) { Some(&Cell::Card(value)) => { println!("\tR) {}", value); } _ => (), } match moves.get(&Down) { Some(&Cell::Card(value)) => { println!("\tD) {}", value); } _ => (), } println!("\tQ) Quit"); print!("Choose your move : "); io::stdout().flush().unwrap();
let mut action = String::new(); io::stdin().read_line(&mut action).ok().expect("read error"); match action.to_uppercase().trim() { "U" if moves.contains_key(&Up) => Move(Up), "L" if moves.contains_key(&Left) => Move(Left), "R" if moves.contains_key(&Right) => Move(Right), "D" if moves.contains_key(&Down) => Move(Down), "Q" => Quit, _ => { println!("Unknown action : {}", action); ask_action(moves) } }
} </lang>
Scheme
<lang scheme> (import (scheme base)
(scheme read) (scheme write) (srfi 27)) ; random numbers
(define *start-position* #(1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 #\space)) (random-source-randomize! default-random-source)
- return a 16-place vector with the tiles randomly shuffled
(define (create-start-position)
(let ((board (vector-copy *start-position*))) (do ((i 0 (+ 1 i)) (moves (find-moves board) (find-moves board))) ((and (>= i 100) (not (finished? board))) board) (make-move board (list-ref moves (random-integer (length moves)))))))
- return index of space
(define (find-space board)
(do ((i 0 (+ 1 i))) ((equal? #\space (vector-ref board i)) i)))
- return a list of symbols indicating available moves
(define (find-moves board)
(let* ((posn (find-space board)) (row (quotient posn 4)) (col (remainder posn 4)) (result '())) (when (> row 0) (set! result (cons 'up result))) (when (< row 3) (set! result (cons 'down result))) (when (> col 0) (set! result (cons 'left result))) (when (< col 3) (set! result (cons 'right result))) result))
- make given move - assume it is legal
(define (make-move board move)
(define (swap posn-1 posn-2) (let ((tmp (vector-ref board posn-1))) (vector-set! board posn-1 (vector-ref board posn-2)) (vector-set! board posn-2 tmp))) ; (let ((posn (find-space board))) (case move ((left) (swap posn (- posn 1))) ((right) (swap posn (+ posn 1))) ((up) (swap posn (- posn 4))) ((down) (swap posn (+ posn 4))))))
(define (finished? board)
(equal? board *start-position*))
(define (display-board board)
(do ((i 0 (+ 1 i))) ((= i (vector-length board)) (newline)) (when (zero? (modulo i 4)) (newline)) (let ((curr (vector-ref board i))) (display curr) (display (if (and (number? curr) (> curr 9)) " " " ")))))
- the main game loop
(define (play-game)
(let ((board (create-start-position))) (do ((count 1 (+ count 1)) (moves (find-moves board) (find-moves board))) ((finished? board) (display (string-append "\nCOMPLETED PUZZLE in " (number->string count) " moves\n"))) (display-board board) (display "Enter a move: ") (display moves) (newline) (let ((move (read))) (if (memq move moves) (make-move board move) (display "Invalid move - try again"))))))
(play-game) </lang>
- Output:
1 2 3 5 7 6 11 13 14 8 4 10 9 15 12 Enter a move: (right left down) right 1 2 3 5 7 6 11 13 14 8 4 10 9 15 12 Enter a move: (left down) down 1 2 3 11 5 7 6 13 14 8 4 10 9 15 12 Enter a move: (left down up) down 1 2 3 11 5 7 6 4 13 14 8 10 9 15 12 Enter a move: (left down up)
Standard ML
<lang sml> (* Load required Modules for Moscow ML *) load "Int"; load "Random";
(* Mutable Matrix *)
signature MATRIX =
sig
type 'a matrix
val construct : 'a -> int * int -> 'a matrix
val size : 'a matrix -> int * int
val get : 'a matrix -> int * int -> 'a
val set : 'a matrix -> int * int -> 'a -> unit
end
structure Matrix :> MATRIX = struct (* Array of rows, where the rows are a array of 'a *) type 'a matrix = 'a Array.array Array.array
fun 'a construct (a : 'a) (width, height) : 'a matrix = if width < 1 orelse height < 1 then raise Subscript else Array.tabulate (height, fn _ => Array.tabulate (width, fn _ => a))
fun size b = let val firstrow = Array.sub (b, 0) in (Array.length firstrow, Array.length b) end
fun get b (x, y) = Array.sub (Array.sub (b, y), x)
fun set b (x, y) v = Array.update (Array.sub (b, y), x, v) end
signature P15BOARD = sig type board datatype direction = North | East | South | West
val construct : int * int -> board val emptyField : board -> int * int val get : board -> int * int -> int option val size : board -> int * int
exception IllegalMove val moves : board -> int list val move : board -> int -> unit
val issolved : board -> bool end
(* Game Logic and data *)
structure Board :> P15BOARD = struct (* Matrix + empty Field position *) type board = int option Matrix.matrix * (int * int) ref
datatype direction = North | East | South | West
exception IllegalMove
fun numberat width (x, y) = (y*width + x + 1)
fun construct (width, height) = let val emptyBoard : int option Matrix.matrix = Matrix.construct NONE (width, height) in (* Fill the board with numbers *) List.tabulate (height, fn y => List.tabulate (width, fn x => Matrix.set emptyBoard (x, y) (SOME (numberat width (x, y))))); (* Clear the last field *) Matrix.set emptyBoard (width-1, height-1) NONE; (* Return the board *) (emptyBoard, ref (width-1, height-1)) end
fun emptyField (_, rfield) = !rfield
fun get (mat, _) (x, y) = Matrix.get mat (x, y)
fun size (mat, _) = Matrix.size mat
(* toggle the empty field with a given field *) fun toggle (mat, rpos) pos = let val pos' = !rpos val value = Matrix.get mat pos in Matrix.set mat pos NONE; Matrix.set mat pos' value; rpos := pos end
(* Get list of positions of the neighbors of a given field *) fun neighbors mat (x, y) : (int * int) list = let val (width, height) = Matrix.size mat val directions = [(x, y-1), (x+1, y), (x, y+1), (x-1, y)] in List.mapPartial (fn pos => SOME (Matrix.get mat pos; pos) handle Subscript => NONE) directions end
fun moves (mat, rpos) = let val neighbors = neighbors mat (!rpos) in map (fn pos => valOf (Matrix.get mat pos)) neighbors end
fun move (mat, rpos) m = let val (hx, hy) = !rpos val neighbors = neighbors mat (hx, hy) val optNeighbor = List.find (fn pos => SOME m = Matrix.get mat pos) neighbors in if isSome optNeighbor then toggle (mat, rpos) (valOf optNeighbor) else raise IllegalMove end
fun issolved board = let val (width, height) = size board val xs = List.tabulate (width, fn x => x) val ys = List.tabulate (height, fn y => y) in List.all (fn x => List.all (fn y => (x + 1 = width andalso y + 1 = height) orelse get board (x, y) = SOME (numberat width (x,y))) ys) xs end end
(* Board Shuffle *) signature BOARDSHUFFLE = sig val shuffle : Board.board -> int -> unit end
structure Shuffle :> BOARDSHUFFLE = struct (* * Note: Random Number Interfaces are different in SML/NJ and Moscow ML. Comment out the corresponding version: *)
(* (* SML/NJ - Version *) val time = Time.now () val timeInf = Time.toMicroseconds time val timens = Int.fromLarge (LargeInt.mod (timeInf, 1073741823)); val rand = Random.rand (timens, timens)
fun next n = Random.randRange (0, n) rand *)
(* Moscow ML - Version *) val generator = Random.newgen () fun next n = Random.range (0, n) generator
fun shuffle board 0 = if (Board.issolved board) then shuffle board 1 else ()
| shuffle board n =
let
val moves = Board.moves board
val move = List.nth (moves, next (List.length moves - 1))
in
Board.move board move;
shuffle board (n-1)
end
end
(* Console interface *)
signature CONSOLEINTERFACE = sig val start : unit -> unit val printBoard : Board.board -> unit end
structure Console :> CONSOLEINTERFACE = struct fun cls () = print "\^[[1;1H\^[[2J"
fun promptNumber prompt = let val () = print prompt (* Input + "\n" *) val line = valOf (TextIO.inputLine TextIO.stdIn) val length = String.size line val input = String.substring (line, 0, length - 1) val optnum = Int.fromString input in if isSome optnum then valOf optnum else (print "Input is not a number.\n"; promptNumber prompt) end
fun fieldToString (SOME x) = Int.toString x | fieldToString (NONE ) = ""
fun boardToString board = let val (width, height) = Board.size board val xs = List.tabulate (width, fn x => x) val ys = List.tabulate (height, fn y => y) in foldl (fn (y, str) => (foldl (fn (x, str') => str' ^ (fieldToString (Board.get board (x, y))) ^ "\t") str xs) ^ "\n") "" ys end
fun printBoard board = print (boardToString board)
fun loop board =
let
val rvalidInput = ref false
val rinput = ref 42
val () = cls ()
val () = printBoard board
in
(* Ask for a move and repeat until it is a valid move *)
while (not (!rvalidInput)) do
(
rinput := promptNumber "Input the number to move: ";
Board.move board (!rinput);
rvalidInput := true
) handle Board.IllegalMove => print "Illegal move!\n"
end
fun start () =
let
val () = cls ()
val () = print "Welcome to nxm-Puzzle!\n"
val (width, height) = (promptNumber "Enter the width: ", promptNumber "Enter the height: ")
val diff = (promptNumber "Enter the difficulty (number of shuffles): ")
val board = Board.construct (width, height)
in
Shuffle.shuffle board diff;
while (not (Board.issolved board)) do loop board;
print "Solved!\n"
end
end
val () = Console.start()
</lang>
Note:
The interface for generating random numbers is different in SML/NJ and Moscow ML. Comment out the corresponding parts of code.
The dimensions of the board (eg. 4x4) and the number of shuffles should be entered first.
Tcl
Works with Tcl/Tk 8.5
This program uses Tk, the graphical counterpart to Tcl. The tiles are made of a grid of buttons, and the text on the buttons is moved around.
The button "New game" selects one of the canned puzzles. The window-title is used to show messages.
<lang tcl> # 15puzzle_21.tcl - HaJo Gurt - 2016-02-16
# http://wiki.tcl.tk/14403
#: 15-Puzzle - with grid, buttons and colors
package require Tk
set progVersion "15-Puzzle v0.21"; # 2016-02-20
global Msg Moves PuzzNr GoalNr set Msg " " set Moves -1 set PuzzNr 0 set GoalNr 0
set Keys { 11 12 13 14 21 22 23 24 31 32 33 34 41 42 43 44 }
set Puzz_T { T h e F i f t e e n P u z z l e }; # Title set Goal_T { x x x F i f t e e n x x x x x x }; # Title-highlight
set Puzz_0 { E G P N C A F B D L H I O K M _ }; # - / 116 set Puzz_1 { C A F B E G P N D L H I O K M _ }; # E / 156 from Tk-demo set Puzz_2 { E O N K M I _ G B H L P C F A D }; # L / 139 set Puzz_3 { P G M _ E L N D O K H I B C F A }; # EK / 146
set Goal_0 { A B C D E F G H I K L M N O P _ }; # Rows LTR / 1:E : 108 set Goal_1 { A E I N B F K O C G L P D H M _ }; # Cols forw. / 1:M : 114
set Puzz $Puzz_T set Goal $Goal_T
- ---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+---
proc Move {k} { # find the key with the empty tile: set e -1 foreach p $::Keys { set t [.key$p cget -text] if { $t eq "_" } { set e $p } } if {$e < 0} {return 0}; # no key with empty tile found if {$k == $e} {return 0}; # click was on the empty tile
set t [.key$k cget -text] .key$e config -text $t .key$k config -text "_"; return 1 }
proc Check {} { set ok 0 set i 0 foreach k $::Keys { set t [.key$k cget -text] set g [lindex $::Goal $i] incr i
.key$k config -background white if { $t eq $g } { .key$k config -background lightgreen; incr ok } if { $t eq "_" } { .key$k config -background gray } }
# Solved: update if { $ok > 15 && $::Moves > 0} { foreach k $::Keys { .key$k flash; bell; } } }
proc Click {k} { set ::Msg "" set val [.key$k cget -text] set ok [Move $k]
incr ::Moves $ok wm title . "$::Moves moves" Check }
proc ShowKeys {} { set i 0 foreach k $::Keys { set t [lindex $::Puzz $i] incr i .key$k config -text $t -background white; } Check }
proc NewGame {N} { global Msg Moves PuzzNr GoalNr
incr PuzzNr $N if { $PuzzNr > 3} { set PuzzNr 0 }
set ::Goal $::Goal_0; if { $GoalNr == 1} { set ::Goal $::Goal_1; }
if { $PuzzNr == 0} { set ::Puzz $::Puzz_0; } if { $PuzzNr == 1} { set ::Puzz $::Puzz_1; } if { $PuzzNr == 2} { set ::Puzz $::Puzz_2; } if { $PuzzNr == 3} { set ::Puzz $::Puzz_3; }
set Msg "Try again" if { $N>0 } { set Msg "New game" }
set Moves 0 ShowKeys wm title . "$Msg " }
- ---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+---
button .reset -text "Restart" -fg blue -command {NewGame 0} button .newGame -text "New Game" -fg red -command {NewGame +1}
foreach k $::Keys { button .key$k -text "$k" -width 4 -command "Click $k" }
grid .newGame x .reset x -sticky nsew
grid .key11 .key12 .key13 .key14 -sticky nsew -padx 2 -pady 2 grid .key21 .key22 .key23 .key24 -sticky nsew -padx 2 -pady 2 grid .key31 .key32 .key33 .key34 -sticky nsew -padx 2 -pady 2 grid .key41 .key42 .key43 .key44 -sticky nsew -padx 2 -pady 2
grid configure .newGame .reset -columnspan 2 -padx 4
ShowKeys; Check wm title . $progVersion focus -force . wm resizable . 0 0
- For some more versions, see: http://wiki.tcl.tk/15067 : Classic 15 Puzzle and http://wiki.tcl.tk/15085 : N-Puzzle
</lang>
VBA
This allows the user to specify the size of the grid (N x N). Only solvable layouts are displayed.
This uses InputBoxes to display the grid of tiles, and prompts the user to enter the number on the tile they wish to move into the empty space.
The last move is displayed on the input box, or an error message if an invalid move is attempted. When the puzzle is solved, the move count is displayed.
<lang vb> Public iSide As Integer Public iSize As Integer Public iGrid() As Integer Public lMoves As Long Public sMessage As String Public Const sTitle As String = "Tile Puzzle"
Sub PlayGame()
Dim iNum As Integer Dim i As Integer Dim vInput As Variant
DefineGrid:
vInput = InputBox("Enter size of grid, as a whole number" & String(2, vbCr) & "(e.g. for a 4 x 4 grid, enter '4')", sTitle, 4) If vInput = "" Then Exit Sub If Not IsNumeric(vInput) Then GoTo DefineGrid iSide = vInput If iSide < 3 Or iNum > 10 Then GoTo DefineGrid iSize = iSide ^ 2 ReDim iGrid(1 To iSize)
Initalize:
InitializeGrid If Not IsSolvable Then GoTo Initalize
GetInput:
vInput = InputBox(ShowGrid & vbCr & "Enter number to move into empty tile", sTitle) If vInput = "" Then If MsgBox("Are you sure? This will end the current game.", vbExclamation + vbYesNo, sTitle) = vbYes Then Exit Sub End If If Not IsNumeric(vInput) Then sMessage = "'" & vInput & "' is not a valid tile" GoTo GetInput End If iNum = vInput If iNum < 1 Or iNum > iSize - 1 Then sMessage = iNum & " is not a valid tile" GoTo GetInput End If i = FindTile(iNum) If Not ValidMove(i) Then GoTo GetInput MoveTile (i) If TestGrid Then MsgBox "SUCCESS! You solved the puzzle in " & lMoves & " moves", vbInformation + vbOKOnly, sTitle Else GoTo GetInput End If
End Sub
Function RandomTile() As Integer
Randomize RandomTile = Int(Rnd * iSize) + 1
End Function
Function GetX(ByVal i As Integer) As Integer
GetX = Int((i - 1) / iSide) + 1
End Function
Function GetY(ByVal i As Integer) As Integer
GetY = (i - 1) Mod iSide + 1
End Function
Function GetI(ByVal x As Integer, y As Integer)
GetI = (x - 1) * iSide + y
End Function
Function InitializeGrid()
Dim i As Integer Dim x As Integer Dim y As Integer sMessage = "New " & iSide & " x " & iSide & " game started" & vbCr For i = 1 To iSize iGrid(i) = 0 Next i For i = 1 To iSize - 1 Do x = RandomTile If iGrid(x) = 0 Then iGrid(x) = i Loop Until iGrid(x) = i Next i lMoves = 0
End Function
Function IsSolvable() As Boolean
Dim i As Integer Dim j As Integer Dim iCount As Integer For i = 1 To iSize - 1 For j = i + 1 To iSize If iGrid(j) < iGrid(i) And iGrid(j) > 0 Then iCount = iCount + 1 Next j Next i If iSide Mod 2 Then IsSolvable = Not iCount Mod 2 Else IsSolvable = iCount Mod 2 = GetX(FindTile(0)) Mod 2 End If
End Function
Function TestGrid() As Boolean
Dim i As Integer For i = 1 To iSize - 1 If Not iGrid(i) = i Then TestGrid = False Exit Function End If Next i TestGrid = True
End Function
Function FindTile(ByVal iNum As Integer) As Integer
Dim i As Integer For i = 1 To iSize If iGrid(i) = iNum Then FindTile = i Exit Function End If Next i
End Function
Function ValidMove(ByVal i As Integer) As Boolean
Dim e As Integer Dim xDiff As Integer Dim yDiff As Integer e = FindTile(0) xDiff = GetX(i) - GetX(e) yDiff = GetY(i) - GetY(e) If xDiff = 0 Then If yDiff = 1 Then sMessage = "Tile " & iGrid(i) & " was moved left" ValidMove = True ElseIf yDiff = -1 Then sMessage = "Tile " & iGrid(i) & " was moved right" ValidMove = True End If ElseIf yDiff = 0 Then If xDiff = 1 Then sMessage = "Tile " & iGrid(i) & " was moved up" ValidMove = True ElseIf xDiff = -1 Then sMessage = "Tile " & iGrid(i) & " was moved down" ValidMove = True End If End If If Not ValidMove Then sMessage = "Tile " & iGrid(i) & " may not be moved"
End Function
Function MoveTile(ByVal i As Integer)
Dim e As Integer e = FindTile(0) iGrid(e) = iGrid(i) iGrid(i) = 0 lMoves = lMoves + 1
End Function
Function ShowGrid()
Dim x As Integer Dim y As Integer Dim i As Integer Dim sNum As String Dim s As String For x = 1 To iSide For y = 1 To iSide sNum = iGrid(GetI(x, y)) If sNum = "0" Then sNum = "" s = s & sNum & vbTab Next y s = s & vbCr Next x If Not sMessage = "" Then s = s & vbCr & sMessage & vbCr End If ShowGrid = s
End Function </lang>
Sample output:
10 4 3 14 9 15 1 6 12 11 7 8 2 5 13 New 4 x 4 game started Enter number to move into empty tile
- Programming Tasks
- Solutions by Programming Task
- Puzzles
- Games
- Ada
- AutoHotkey
- BASIC
- Commodore BASIC
- C
- C sharp
- System.Windows.Forms
- System.Drawing
- C++
- COBOL
- Common Lisp
- Common Lisp examples needing attention
- Examples needing attention
- Field knowledge needed/efficiency
- Field knowledge needed/efficiency/Common Lisp
- Gambas
- Pages with broken file links
- Haskell
- J
- Java
- Livecode
- Perl 6
- Phix
- Python
- Racket
- Rebol
- REXX
- Ring
- Ruby
- Run BASIC
- Rust
- Scheme
- Standard ML
- Tcl
- Tk
- VBA