Ma foot chess demo design
Topic: Ma T / Che
Class: 02 class computer 2 class name: Liu Xiaoming: 200201020219
Completion date: November 20, 2004
demand analysis
The horse is placed in a square of the 8 × 8 chessboard Board [8] [8] of Chess, and the horse moves. Require each checkered only once, travel all 64 squares on the board. Prepare non-recursive procedures, seeking the walking route of the horse, and pressing the numbers 1, 2, ..., 64 in sequential, output.
Test data: specified by the reader. You can specify the initial position (i, j) of a horse you can, 0 <= i, j <= 7.
Design ideas
According to the clockwise order, each time a new road point is generated, and the availability of this road point is verified, and the problem that needs to be considered includes whether the board and this point have already passed. If the new road point is available, it will be put into the stack, and the next step is performed, and each time it generates a new road point according to the position of the last route. If the number of expandable road points of a road point is 0, then it can't go on, and backtrack.
Summary design
The menu design is used in the program, and the input and output of the operation is prompted. The main file is divided into DSOPER.H and UI.h. Responsible for data structure operation and user interface display, respectively.
The main function in dsoper.h is as follows:
l Void Calc (HorsePoint Init) is used to calculate the entry function of the distance
l HorsePoint GetNewPoint (HorsePoint * Parent) generates a new node from the PARENT node, in the direction of the Parent.dir direction
l void pushstack (HorsePoint POS)
l Void PushStack (HorsePoint Pos, INT DIR) Factory Overload Function
l HorsePoint Popstack (VOID)
l Void Initial (void) Initializing the application of each global variable
The main function in Ui.h is as follows:
l HorsePoint GetInitPoint (Void) Requests to enter the initial location of your horse
l cmdchar getcommand (void) Display menu and get menu commands from it
l void showtable (void) Displays output data according to the board model
l void showStep (void) Displays the output data in accordance with the step model
l void savetofile (void) Save to file rt.txt
Data structure definition:
Typedef struct horsepoint
{
INT X;
Int Y;
INT DIR; // Next Step, Initialization - 1, Valid 0-7
HorsePoint;
Where DIR components are used to indicate the direction of the next point of view relative to the current path.
Global variable definition:
Bool Board [width] [width] Defines whether there is already past in the checkerboard, not going to false
HorsePoint Path [Max_len] defines the walking path of the horse
INT Scount has entered the number of elements of the path stack
Program source code
Document main.cpp
/ *
Name: main.cpp
Copyright: CopyRight @ 1999-2004, Gashero Liu.
Author: Gashero Liu.
Date: 16-11-04 20:41
Description: Program main file, only contains main functions
* /
#include
#include
#ifndef datastruct_h
#define datastruct_h
#include "datastruct.h"
#ENDIF
#ifndef dsoper_h
#define DSOPER_H
#include "dsoper.h"
#ENDIF
#ifndef ui_h
#define ui_h
#include "ui.h"
#ENDIF
Using namespace std;
// --------------------------------------------- --------------------
Bool board [width] [width]; // Define whether the panel has already passed, did not take False
Horsepoint path [max_len]; / / Define the walking path of the horse
INT scount; / / The number of elements that have entered the path stack
Int main (int Argc, char * argv [])
{
Cmdchar cmd; // command character
Horsepoint Init; // Horse initial position
Initial ();
While ((cmd = getcommand ())! = cmd_exit)
{
Switch (cmd)
{
Case cmd_new:
{
INIT = GetInitPoint ();
Calc (init);
Break;
}
Case cmd_table:
{
ShowTable ();
Break;
}
Case cmd_step:
{
Showstep ();
Break;
}
Case cmd_save:
{
Savetofile ();
Break;
}
}
}
// system ("pause");
Return 0;
}
Document DSOPER.H:
/ *
Name: DSOPER.H
Copyright: CopyRight @ 1999-2004, Gashero Liu.
Author: Gashero Liu.
Date: 16-11-04 12:48
Description: The operation of the data structure, the operation of the stack and queue
* /
#ifndef datastruct_h
#define datastruct_h
#include "datastruct.h"
#ENDIF
// Reference global variable
Extern Bool Board [width] [width];
Extern HorsePoint Path [MAX_LEN];
Extern int
// End the reference global variable
// --------------------------------- Function Declaration ------------- ----------------
Void Calc (HorsePoint Init);
/ * The entry function of the approach * /
HorsePoint getNewPoint (HorsePoint * Parent);
/ * From the Parent node, a new node is generated in the direction of the Parent.dir direction, if new
Node, then parent.dir == - 1 * /
Void Pushstack; HorsePoint POS
Void Pushstack (HorsePoint Pos, Int Dir);
/ * Non-point POS in the stack PATH, SCOUNT after the stack; corresponding to the corresponding point = true * /
Horsepoint Popstack (Void);
/ * Give the stack PATH, out of the stack, return, scount--, the corresponding point Board = false; * / void initial (void);
/ * Initialize the application of each global variable * /
/ / --------------------------------- Function Defination ------------- -------------
Void Calc (HorsePoint Init) // ------------------------------------------ -----
{
INT OC = 0, WC = 0;
HorsePoint npos; // Next node
Horsepoint * ppos; // current node
Initial ();
PPOS = & init;
Pushstack (* ppos);
While (! (Scount == 0 || SCOUNT == max_len))
{
Oc ;
IF (oc == 100000000)
{
OC = 0;
WC ;
Printf ("Performed% D5 million, the stack depth% D / N", WC, SCOUNT);
// system ("pause");
}
PPOS = & path [scount-1];
NPOS = GetNewPoint (PPOS);
IF (PPOS-> DIR! = invalid_dir)
{
PushStack (NPOS, PPOS-> DIR); // Generate an effective step-by-step node, into the stack
// Printf ("PushStack: (% D,% D), Last.dir:% D, Scount =% D / N", NPos.x, Npos.y, PPOS-> DIR, Scount);
// system ("pause");
}
Else
{
POPSTACK (); // There is no effective step by step, out of the stack
// Printf ("PopStack: Scount:% D / N", Scount);
}
// system ("pause");
}
Printf ("100 million% D times, Scount:% D / N", WC, OC, SCOUNT);
}
HorsePoint GetNewpoint (HorsePoint * Parent) // ----------------------------------
{
INT I;
Horsepoint newpoint;
INT tryx [max_dir] = {1, 2, 2, 1, -1, -2, -2, -1};
INT tryy [max_dir] = {- 2, -1, 1, 2, 2, 1, -1, -2};
Newpoint.dir = invalid_dir;
Parent-> DIR = Parent-> DIR 1;
For (i = parent-> DIR; i { NewPoint.x = parent-> x tryx [i]; Newpoint.y = parent-> y tryy [i]; IF (NewPoint.x NewPoint.Y Board [newpoint.x] [newpoint.y] == false) { Parent-> DIR = i; //Board[newpoint.x][newpoint.y]=true;return newpoint; } } Parent-> DIR = invalid_dir; // There is no effective next direction Return newPoint; // Return to an insignificant value } Void Pushstack (HorsePoint Pos) // -------------------------------------------------------------------------------------------------------------------------------------------------------------------------- { Board [POS.X] [POS.Y] = True; Path [scount] = POS; SCOUNT ; } Void Pushstack (HorsePoint Pos, Int Dir) // ------------------------------------- { Path [Scount-1] .dir = DIR; Pushstack (POS); } HorsePoint Popstack (void) // ------------------------------------------- ------- { // std :: cout << "popstack" << std :: end1; HorsePoint Pos; Scount -; POS = path [sn]; Board [POS.X] [POS.Y] = FALSE; PATH [SCOUNT] .dir = invalid_dir; Return POS; } Void Initial (void) // ------------------------------------------ ------------- { INT I, J; For (i = 0; i { For (j = 0; j { Board [i] [j] = false; } } For (i = 0; i { PATH [I] .x = 0; Path [i] .y = 0; Path [i] .dir = INVALID_DIR; } SCOUNT = 0; } Document ui.h: / * Name: ui.h Copyright: CopyRight @ 1999-2004, Gashero Liu. Author: Gashero Liu. Date: 16-11-04 12:54 Description: User Interactive Operation Header file and contains file access * / #include #ifndef datastruct_h #define datastruct_h #include "datastruct.h" #ENDIF // Reference global variable Extern Bool Board [width] [width]; Extern HorsePoint Path [MAX_LEN]; Extern int // End the reference global variable // ----------------------- Fuction declaretion ----------------------- ---------------- Horsepoint GetInitPoint (Void); / * Request to enter the initial position of the horse * / Cmdchar getcommand (void); / * Display menu and get menu command * / Void ShowTable (Void); / * Display output data in accordance with the chessboard model * / Void showstep (void); / * Display Output Data in accordance with the step model * / Void Savetofile (Void); / * Save to file rt.txt * / / / --------------------------------- Function Defination ------------- ------------- Horsepoint GetInitPoint (Void) / / -------------------------------------------------------------------------------------------------------------------------------------------------------------------------------- --- { HorsePoint Pos; DO { For (int i = 0; i <24; i ) { Printf ("/ n"); // Generate 24 commcesries to block information on the previous page } Printf ("/ t / t / t / t Please enter the initial position x, y:"); Scanf ("% D,% D", & pos.x, & pos.y); While (pos.x> = width || pos.y> = width || Pos.x <0 || POS.Y <0); POS.DIR = INVALID_DIR; Return POS; } Cmdchar getcommand (void) // ------------------------------------------------------------------------------------------------------- --------- { CHAR CMD; While (True) { Printf ("/ n / n / n / N"); Printf ("/ T / T / T / T Ma Walking Checkboard Demo / N"); Printf ("/ t / t / t / t version: v1.2 / n / N"); Printf ("/ t / t / t / t [n] new game / N"); Printf ("/ t / t / t / t [t] output board model / N"); Printf ("/ T / T / T / T [S] Step Output / N"); Printf ("/ t / t / t / t [f] saves to file RT.TXT / N"); Printf ("/ t / t / t / t [x] exits / N"); Printf ("/ n / n / N / N / N / N / N / N / N / N / N / N / N / N"); / * Use N multiple newline characters to brush screen, because I can't find a cross-platform clear screen function * / CMD = GetCh (); Switch (cmd) { Case 'n': { Return cmd_new; // Start a new game Break; } Case 'T': { Return cmd_table; // Output Chessboard model Break; } Case 's': { Return cmd_step; // Output Step Model Break; } Case 'f': { Return cmd_save; // Save to text file rt.txt Break; } Case 'x': { Return cmd_exit; // Exit this program Break; } DEFAULT: { CMD = '/ 0'; CONTINUE; } } } } Void showtable (void) // ------------------------------------------------------------------------------------------------------------------- ------------- { INT ft [width] [width]; INT Step = 0; HorsePoint Pos; IF (scount == max_len) { For (int i = 0; i { Step ; POS = path [i]; FT [POS.X] [POS.Y] = STEP; } For (int i = 0; i Printf ("/ t / t / t / t"); For (int J = 0; j { IF (ft [i] [j] <10) { Printf (""); // Output a space to keep alignment } Printf ("% d", ft [i] [j]); } Printf ("/ n"); } Printf ("/ n / n / N / N / N / N / N / N"); System ("pause"); } Else { Printf ("/ t / t / t / t task is not completed or failed, no valid data / N"); System ("pause"); } } Void showstep (void) // ----------------------------------------- ------------- { INT ft [width] [width]; INT Step = 0; HorsePoint Pos; CHAR CMD; IF (scount == max_len) { For (Step = 0; Step { Printf ("/ n / n / N / N / N / N / N / N"); For (int i = 0; i { For (int J = 0; j { FT [i] [j] = 0; } } For (int i = 0; i { POS = path [i]; FT [POS.X] [POS.Y] = i 1; } For (int i = 0; i { Printf ("/ t / t / t / t"); For (int J = 0; j { IF (ft [i] [j] <10) { Printf (""); } IF (ft [i] [j] == 0) { Printf (""); } Else { Printf ("% d", ft [i] [j]); } } Printf ("/ n"); } Printf ("/ n / n / N / N / N / N / N / N / N"); System ("pause"); } Printf ("/ n / n / N / N / N / N / N / N"); System ("pause"); } Else { Printf ("/ t / t / t / t task is not completed or failed, no valid data / N"); System ("pause"); } } Void savetofile (void) // ----------------------------------------- ----------- { INT ft [width] [width]; INT Step = 0; HorsePoint Pos; File * pfile; IF (scount == max_len) { For (int i = 0; i { Step ; POS = path [i]; FT [POS.X] [POS.Y] = STEP; } IF ((pfile = fopen (file_name, "w"))))! = null) // Save to file { For (int i = 0; i { For (int J = 0; j { IF (ft [i] [j] <10) { FPRINTF (Pfile, "); / / Space for complement format } FPRINTF (Pfile, "% D", FT [i] [j]); } FPRINTF (Pfile, "/ N"); } Fclose (pfile); System ("NOTEPAD.EXE RT.TXT"); } Else { Printf ("/ T / T / T / T output file open error, please check file properties and file system properties / N"); System ("pause"); } } Else { Printf ("/ t / t / t / t task is not completed or failed, no valid data / N"); System ("pause"); } } Document DataStruct.h: / * Name: datastruct.h Copyright: CopyRight @ 1999-2004, Gashero Liu. Author: Gashero Liu. Date: 16-11-04 12:25 Description: Definition header file for data structure * / Typedef struct horsepoint { INT X; Int Y; INT DIR; // Next Step, Initialization - 1, Valid 0-7 HorsePoint; Typedef enum cmdchar { CMD_NEW, / * Enter a new initial coordinate point * / CMD_TABLE, / * Output Chessboard Model * / CMD_STEP, / * Output Step Model * / CMD_SAVE, / * Save to File * / CMD_EXIT, / * Exit Program * / } Cmdchar; #define width 8 #define max_len 64 #define max_dir 8 #define invalid_dir -1 #define file_name "rt.txt" Debug analysis The pointer operation in the program has multiple times, especially when the directional component in the operating stack is, due to the operation of the operation, the data does not actually save this data, causing the 47th cycle to enter the dead cycle. After the Visual Studio 2003, the debugging tool in NET is changed to find all DIR components in the stack to -1. Change it is correct. Because of this problem, I renovated the entire program. User Manual The first page menu option, press the characters in parentheses to enter the relevant functionality. When you need to enter the data, you can output data in the form of 3, and enter the data format to use a comma separated by 2 numbers. The checkerboard output is completely output throughout the board information. The step output is further further before, then press any key to advance. Save to file RT.TXT to store the result into the RT.TXT file in the directory where the feasibility file is located, and simultaneously open the discovery to display the save file content. Press the X key to exit the program Test Results The data calculation amount of some road points is extremely large, where (4, 4) is used to calculate more than 2 hours using AMD1.2GHzCPU, and the stack attempt to complete 85 billion valid roads is still not calculated. I also rewrite the entire program three times because of data issues. Therefore, it is recommended to use the following test data. The data for more than 1 billion times is omnipotent (calculation time will exceed 5 minutes). After the data is measured, the number of valid stages: The initial coordinate point valid road point is set in the stack 0, 06, 484, 0650, 318, 305, 9070, 716, 501, 44, 504, 2817, 0503, 650, 504, 754, 482, 650, 7517, 754, 482, 161 (only x = 0 herein, 1, 2 full data and two other data) appendix Although the students' homework is extensive, I hope that the teacher believes that this is written by I. The development of the entire program has experienced three versions of V1.0, V1, 1, V1, 2. The code as above is V1.2 version. After later testing, V1.1 version (using C language) has no error, can execute correctly, only blame I have never selected the data (4, 4). Long calculations cause me to have a very large dead cycle into a cycle. During the development of these three versions, I used DEV-C 5, Visual C . Net2003, GNU GCC3.3.0, two versions of two platforms and IDEs. I also paid for about 20 hours. Looking back, it is still worth it, the total program source code has reached more than 470, which is the longest C program I wrote to the present (other language is not considered). And so high computation is also made me start thinking about the time complexity of the program. The brush screen design of the user interface in the program also used the experience of my previous courses, and actually proved that the full screen display is realized, and there is a very perfect cross-platform performance (Windows XP / GNU Linux). In version V1.2, it is actually written in the process-oriented C language, the standard refers to ISO C 98 standard, so the code is written in DEV-C , and when transplanted to VC . Net and GCC, there is no modification Any code. This shows the superiority of standards in cross-platform development. However, it will actually prove that there is little difference in the actual computing speed based on Win32, .NET, Linux Kernel, and running the program in the Pentium2.4GHz platform running speed is also small (140 million / minute, 17 billion times) /minute). The version v1.0 development process is too long, so that I have forgotten the development ideas, so I will give up, now I can download the source code and executable of V1.1 and V1.2 from my personal site. The V1.1 version is only available under the DEV-C99 standard, and the binary source code based on Win32 platform is compiled. V1.2 versions are written using ISO C 98 standards, and binary versions provide VC . NET compiling VC . NET compiled by the Win32 platform DEV-C . For the Linux platform, you can copy the source code compilation again and again. Source download address: http://e5022.wx-e.com/sourcecode/index.htm E-mail: Gashero@163.com
