→ bleed1979:剛改BFS也可以過，total size = 362880 / 2; ( 9! / 2 ) 06/24 16:53
推 ledia:8-puzzle 我還看過用 random walk (with some limitation) 06/24 18:40
推 tom1990:感謝你~ 這樣可以cut出unsolvable又可以減少跑state 06/24 20:18
提供判斷solvable的方法。
-----------------------------------------------------
給定一個變數inversion，用以紀錄在如下的位置上，
位置0 位置1 位置2
位置3 位置4 位置5
位置6 位置7 位置8
缺空處就是題目給定的x不計算，
位置小上面的數大於位置大上面的數的總和統計次數。
如果inversion的總和為偶數，此題有解，否則無解。
Ex1.
1 2 3
4 5 6
x 7 8
inversion = 0，有解。
Ex2.
1 2 3
4 5 6
8 7 x
8 - 7 inversion，inversion = 1，無解。
Ex3.
3 2 1
4 5 6
7 8 x
3 - 2 inversion， 3 - 1 inversion， 2 - 1 inversion，
inverison = 3，無解。
--------------------------------------------------
所以可以寫一個函式isSolvable來判斷︰
inline bool isSolvable ( int* pos )
{
int inversion = 0;
for( int i = 0; i < 8; i++ )
for( int j = i + 1; j < 8; j++ )
if( pos[ i ] > pos[ j ] )
++inversion;
return ( ( inversion & 1 ) == 0 );
}
檢查方法就這樣，
這題我用A*過的，所以不確定你的作法是否能AC，
祝你成功！
Bleed
※ 引述《tom1990 (湯姆祥)》之銘言：
: ( *[1m *[m 為色碼，可以按 Ctrl+V 預覽會顯示的顏色 )
: ( 未必需要依照此格式，文章條理清楚即可 )
: 題號： 652 Eight
: (http://tinyurl.com/2586cwj)
: 遇到的問題：
: Time Limit Exceeded
: 有問題的code： (請善用置底文的標色功能)
: http://nopaste.csie.org/7596a
: 補充說明：
: 在做 back tracking 有問題
: 雖然題目沒有說要最少步
: 所以我是走過而且走的到就不再走 BFS
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 114.43.124.105