[技術討論] C++功課

本帖最後由 神秘二代 於 2013-11-24 14:28 編輯

關於類近puzzle玩法的......
希望高人出手相助指點
不便公開code........PM plz~

本帖最後由 神秘二代 於 2013-11-24 15:06 編輯
Rush Hour?
bluenemo 發表於 2013-11-24 14:47


n-number puzzle, but with two or more slots, also number repeated
(start)-->(goal)
323         233
405          450
067 -->  670
something like that

i don't know how to solve this...... i know there have IDA* concept but algorithm hard to think....T-T

TOP

本帖最後由 神秘二代 於 2013-11-24 15:32 編輯
回復  神秘二代

連點樣solve個problem都未有idea? 咁點寫program?
bluenemo 發表於 2013-11-24 15:15


i have some idea, but cannot cover all cases, i want someone can guide me how to do....
my first think is, find the shortest path between each number, when shortest path found, other number not link this number for shortest path
for example
120        220
320 --> 130
000         000
shortest path --> 1->1(cost:1), 2->2(cost:0), 2->2(cost:2), 3-->3(cost:1), total cost = 4
aleast 4 step to come to goal
second think is, start from slot (0), test move if each slot have the number in 4 position: up, down, right, left. if swaped, check the cost again to find the best path. for each iteration, base cost will increase 1.
but the problem is....some cases cannot fulfill the above algorithm, for example
120        020
322 --> 322
000         001
i don't know how to solve this case.......can give me a some hints?

TOP

本帖最後由 神秘二代 於 2013-11-24 15:54 編輯
Not quite sure if i got your game correct... is this like this:
bluenemo 發表於 2013-11-24 15:37


thanks, but.....not useful

TOP

簡單就係
佢有個nxn ge面版, 上面有0-9的數字, 0=空格
數字可以重複, 而每次會input開始時ge數字面版同完結時ge數字面版
而家要整一個演算法列出行走步驟........
最煩係有N個空格同埋N個相同數字.....
e.g.
123
321
120
變成
123
321
012
走法就係
LL
但有時有幾個0或數字重複我就開始搞唔清應該點分配.....究竟呢個數字最終應該係果個定果個= =
e.g.
123
245
670
final:
122
345
670
咁究竟第二行ge 2係第一行ge邊個2........定係我複雜左? 根本唔洗理邊個2...../_\
睇d example....都無我呢個case, 自己想得好辛苦.......自問唔係編程高手

TOP

開個array
做CHECKING
IF right pattern -> true
DONE

唔洗太複雜
Jimmy0911 發表於 2013-11-24 21:20


講就易~~

TOP

回復  神秘二代


之前做過象棋
真係會更難?
Jimmy0911 發表於 2013-11-25 00:23


象棋AI?

TOP

本帖最後由 神秘二代 於 2013-11-25 01:47 編輯
btw....

師兄試下開array
每個array 做一個number
[1][2][3]
[4][5][6]
[7][8][9]
當NUMBER 係咩時,assig ...
Jimmy0911 發表於 2013-11-25 01:10


用number check空格...唔可行, 你每move一次要loop哂n個elements, 效率超差
同埋你這個想法我都有試過, 就係有某些case會有問題
e.g.
1203
3040
4460
1456
final:
4002
3010
4466
1453

TOP

The n-puzzle is a classical problem for modelling algorithms involving heuristics. Commonly used heu ...
Jackass_TMxCK 發表於 2013-11-25 18:59


PM

TOP

本帖最後由 神秘二代 於 2013-11-26 01:24 編輯
Here is the pseudocode of the basic algorithm

IDAStar(State s, int limit) {
    mark state s as vis ...
KoolFreeze 發表於 2013-11-26 01:16


IDAStar(s', limit - (cost of s' + h(s')))
why limit - (cost of s' + h(s'))
also, this algorithm not consider more than 1 slot and duplicate number
but as you said, just basic algorithm

TOP