1 // See LICENSE for license details.
3 //**************************************************************************
4 // Towers of Hanoi benchmark
5 //--------------------------------------------------------------------------
7 // Towers of Hanoi is a classic puzzle problem. The game consists of
8 // three pegs and a set of discs. Each disc is a different size, and
9 // initially all of the discs are on the left most peg with the smallest
10 // disc on top and the largest disc on the bottom. The goal is to move all
11 // of the discs onto the right most peg. The catch is that you are only
12 // allowed to move one disc at a time and you can never place a larger
13 // disc on top of a smaller disc.
15 // This implementation starts with NUM_DISC discs and uses a recursive
16 // algorithm to sovel the puzzle.
20 // This is the number of discs in the puzzle.
24 //--------------------------------------------------------------------------
25 // List data structure and functions
39 struct List g_nodeFreeList
;
40 struct Node g_nodePool
[NUM_DISCS
];
42 int list_getSize( struct List
* list
)
47 void list_init( struct List
* list
)
53 void list_push( struct List
* list
, int val
)
57 // Pop the next free node off the free list
58 newNode
= g_nodeFreeList
.head
;
59 g_nodeFreeList
.head
= g_nodeFreeList
.head
->next
;
61 // Push the new node onto the given list
62 newNode
->next
= list
->head
;
66 list
->head
->val
= val
;
73 int list_pop( struct List
* list
)
75 struct Node
* freedNode
;
78 // Get the value from the->head of given list
79 val
= list
->head
->val
;
81 // Pop the head node off the given list
82 freedNode
= list
->head
;
83 list
->head
= list
->head
->next
;
85 // Push the freed node onto the free list
86 freedNode
->next
= g_nodeFreeList
.head
;
87 g_nodeFreeList
.head
= freedNode
;
95 void list_clear( struct List
* list
)
97 while ( list_getSize(list
) > 0 )
101 //--------------------------------------------------------------------------
102 // Tower data structure and functions
113 void towers_init( struct Towers
* this, int n
)
120 list_init( &(this->pegA
) );
121 list_init( &(this->pegB
) );
122 list_init( &(this->pegC
) );
124 for ( i
= 0; i
< n
; i
++ )
125 list_push( &(this->pegA
), n
-i
);
129 void towers_clear( struct Towers
* this )
132 list_clear( &(this->pegA
) );
133 list_clear( &(this->pegB
) );
134 list_clear( &(this->pegC
) );
136 towers_init( this, this->numDiscs
);
140 void towers_solve_h( struct Towers
* this, int n
,
141 struct List
* startPeg
,
142 struct List
* tempPeg
,
143 struct List
* destPeg
)
148 val
= list_pop(startPeg
);
149 list_push(destPeg
,val
);
153 towers_solve_h( this, n
-1, startPeg
, destPeg
, tempPeg
);
154 towers_solve_h( this, 1, startPeg
, tempPeg
, destPeg
);
155 towers_solve_h( this, n
-1, tempPeg
, startPeg
, destPeg
);
160 void towers_solve( struct Towers
* this )
162 towers_solve_h( this, this->numDiscs
, &(this->pegA
), &(this->pegB
), &(this->pegC
) );
165 int towers_verify( struct Towers
* this )
170 if ( list_getSize(&this->pegA
) != 0 ) {
174 if ( list_getSize(&this->pegB
) != 0 ) {
178 if ( list_getSize(&this->pegC
) != this->numDiscs
) {
182 for ( ptr
= this->pegC
.head
; ptr
!= 0; ptr
= ptr
->next
) {
184 if ( ptr
->val
!= numDiscs
) {
189 if ( this->numMoves
!= ((1 << this->numDiscs
) - 1) ) {
196 //--------------------------------------------------------------------------
199 int main( int argc
, char* argv
[] )
201 struct Towers towers
;
204 // Initialize free list
206 list_init( &g_nodeFreeList
);
207 g_nodeFreeList
.head
= &(g_nodePool
[0]);
208 g_nodeFreeList
.size
= NUM_DISCS
;
209 g_nodePool
[NUM_DISCS
-1].next
= 0;
210 g_nodePool
[NUM_DISCS
-1].val
= 99;
211 for ( i
= 0; i
< (NUM_DISCS
-1); i
++ ) {
212 g_nodePool
[i
].next
= &(g_nodePool
[i
+1]);
213 g_nodePool
[i
].val
= i
;
216 towers_init( &towers
, NUM_DISCS
);
218 // If needed we preallocate everything in the caches
221 towers_solve( &towers
);
226 towers_clear( &towers
);
228 towers_solve( &towers
);
232 return towers_verify( &towers
);