Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

Re:附上强剪条件

Posted by U1928 at 2023-07-15 19:35:27 on Problem 3074
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:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator