| ||||||||||
| Online Judge | Problem Set | Authors | Online Contests | User | ||||||
|---|---|---|---|---|---|---|---|---|---|---|
| Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest | |||||||||
Re:附上强剪条件In Reply To:附上强剪条件 Posted by:damacheng009 at 2010-10-26 15:49:26 > 1.遍历当前所有的空格:
> 1)如果发现某个空格1-9都放不下,则返回上一层。
> 2)如果只有1个数可以填,则此空格就只能填上此数,这样就消除一个空格。
> 3)如果有2个以上的数可以填,则不做处理。
>
> 2.遍历当前所有的空格:
> 1)如果发现在某行中,某个数字不能存在于该行的任一个空格中,则返回上一层。
> 2)如果发现某个空格所在的行中,某个数字只能填在此空格中,则直接填上,这样就
> 消除一个空格;有2个以上则不做处理。
>
> 3.同2,把2中的行替换为列。
>
> 4.同2,把2中的行替换为子数独。
>
> 实践证实:实现1,2,3点即可AC。
>
> 附上DFS函数供有需要的同学参考:
> bool dfs() {
> if(space_num <= 0) return true;
>
> if(set_grid_only() == false) return false;
> if(set_row_only() == false) return false;
> if(set_col_only() == false) return false;
>
> if(space_num <= 0) return true;
>
> int c_space_num;
> int c_map[9][9];
> bool c_tbl[9][9][9];
> c_space_num = space_num;
> memcpy(c_map, map, sizeof(map));
> memcpy(c_tbl, tbl, sizeof(tbl));
>
> int next_r, next_c;
> bool flag = false;
> for(int r = 0; r < 9; ++r) {
> for(int c = 0; c < 9; ++c) {
> if(map[r][c] == SPACE) {
> next_r = r;
> next_c = c;
> flag = true;
> goto _out;
> }
> }
> }
>
> _out:
> if(flag) {
> for(int k = 0; k < 9; ++k) {
> if(tbl[next_r][next_c][k] == VACANT) {
> init(next_r, next_c, k);
> space_num--;
> if(dfs()) return true;
> else {
> space_num = c_space_num;
> memcpy(map, c_map, sizeof(map));
> memcpy(tbl, c_tbl, sizeof(tbl));
> }
> }
> }
> }
>
> return false;
> }
Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator