USACO section 1.5 Checker Challenge(dfs深搜)

Posted on by hackdl

Checker Challenge

Examine the 6×6 checkerboard below and note that the six checkers are arranged on the board so that one and only one is placed in each row and each column, and there is never more than one in any diagonal. (Diagonals run from southeast to northwest and southwest to northeast and include all diagonals, not just the major two.) 

Column
    1   2   3   4   5   6
  -------------------------
1 |   | O |   |   |   |   |
  -------------------------
2 |   |   |   | O |   |   |
  -------------------------
3 |   |   |   |   |   | O |
  -------------------------
4 | O |   |   |   |   |   |
  -------------------------
5 |   |   | O |   |   |   |
  -------------------------
6 |   |   |   |   | O |   |
  -------------------------

The solution shown above is described by the sequence 2 4 6 1 3 5, which gives the column positions of the checkers for each row from 1 to 6:

ROW

1

2

3

4

5

6

COLUMN

2

4

6

1

3

5

This is one solution to the checker challenge. Write a program that finds all unique solution sequences to the Checker Challenge (with ever growing values of N). Print the solutions using the column notation described above. Print the the first three solutions in numerical order, as if the checker positions form the digits of a large number, and then a line with the total number of solutions.

Special note: the larger values of N require your program to be especially efficient. Do not precalculate the value and print it (or even find a formula for it); that’s cheating. Work on your program until it can solve the problem properly. If you insist on cheating, your login to the USACO training pages will be removed and you will be disqualified from all USACO competitions. YOU HAVE BEEN WARNED.

TIME LIMIT: 1 CPU second

PROGRAM NAME: checker

INPUT FORMAT

A single line that contains a single integer N (6

SAMPLE INPUT (file checker.in) 

6

OUTPUT FORMAT

The first three lines show the first three solutions found, presented as N numbers with a single space between them. The fourth line shows the total number of solutions found.

SAMPLE OUTPUT (file checker.out)

2 4 6 1 3 5
3 6 2 5 1 4
4 1 5 2 6 3
4

HINTS (use them carefully!)

忘了说了，看了奶牛网的分析，忽然想起了，这八皇后问题是对称性的，只要求其一半×2就是结果了，也就是说着程序还可以优化

 

/*
ID:nealgav1
PROG:checker
LANG:C++
*/
#include
#include
#define N 42
bool l[42],r[42],t[42];
int m;
int shu[15];
int ans;
void dfs(int n)
{
  if(n14200){ans=73712;return;}//12个时是14200,13个时是73712所以就减一下，
  }                                 //时间上能省上一点。不过是鸡肋
}
int main()
{
  freopen("checker.in","r",stdin);
  freopen("checker.out","w",stdout);
  scanf("%d",&m);
  ans=0;
  memset(l,0,sizeof(l));memset(r,0,sizeof(r));memset(t,0,sizeof(t));
  dfs(1);
  printf("%dn",ans);
}

 

 

 

 

 

 

  

USER: Neal Gavin Gavin [nealgav1]
TASK: checker
LANG: C++

Compiling…
Compile: OK

Executing…
Test 1: TEST OK [0.000 secs, 3344 KB]
Test 2: TEST OK [0.000 secs, 3344 KB]
Test 3: TEST OK [0.000 secs, 3344 KB]
Test 4: TEST OK [0.000 secs, 3344 KB]
Test 5: TEST OK [0.000 secs, 3344 KB]
Test 6: TEST OK [0.022 secs, 3344 KB]
Test 7: TEST OK [0.130 secs, 3344 KB]
Test 8: TEST OK [0.713 secs, 3344 KB]

All tests OK.

YOUR PROGRAM (‘checker’) WORKED FIRST TIME! That’s fantastic
— and a rare thing. Please accept these special automated
congratulations.

Here are the test data inputs:

------- test 1 ----
6
------- test 2 ----
7
------- test 3 ----
8
------- test 4 ----
9
------- test 5 ----
10
------- test 6 ----
11
------- test 7 ----
12
------- test 8 ----
13

Keep up the good work!

Thanks for your submission!

 

 

Checker ChallengeRuss Cox

We use a recursive complete search to simply test all boards. The search proceeds by trying to put one checker in each row. We keep track of which columns and diagonals already have checkers on them in the “col”, “updiag”, and “downdiag” arrays.

Since we generate solutions in increasing order, we record the first 3 in the “sol” array.

Symmetry enables us to count the first half of the solutions double and avoid calculating the second half. An exception happens when N is odd; the odd row needs to be counted once.

The N>6 lines get the program out of trouble when N==6, because at that point, the first 3 solutions include one of the symmetric answers.

Since we number rows from 0 to N-1 rather than 1 to N, we need to add 1 to each digit as we print (in “printsol”).

/*
TASK: checker
LANG: C
*/
#include
#include
#include
#include

#define MAXN 16

int n;
int nsol, nprinted;
char row[MAXN];
FILE *fout;

void
solution() {
int i;
for(i=0; i j */
char updiag[2*MAXN]; /* (i, j) -> i+j */
char downdiag[2*MAXN]; /* (i, j) -> i-j + N */

/*
* Calculate number of ways to place checkers
* on each row of the board starting at row i and going to row n.
*/
void
nway(i, lim) {
int j;

if(i == n) {
nsol++;
if (n > 6 && row[0] 6?(n+1)/2:n);
fprintf(fout, “%dn”, nsol);
exit (0);
}

Clever Michael Rybak’s Solution

The Ukraine’s Michael Rybak removed the ‘this row is used’ search (which obviously at the end of the recursion is a lot of wasted iterating) and replaced it with a list of valid rows to use (which presumably has but a single element at the end of the recursion). His program runs almost 4x faster then N==13. 

Program Checker;
   Var diagPLUS: Array[2..30] Of Boolean;
       diagMINUS: Array[-15..15] Of Boolean;
       sol: Array[1..15] Of ShortInt;
       i,n,found: Longint;
       stop: Boolean;
       next,prev: Array[0..16] Of ShortInt;
       sy: ShortInt;

Procedure Search0(y:ShortInt);
    Var x,i:ShortInt;
Begin
    If stop Then Exit;
    If y=n+1 Then Begin
        Inc(found);
        If found0 Then Begin
        Search0(y+1);
        Exit;
    End;
    x:=next[0];
    While x0 Then Begin
        Inc(sy);
        Search;
        Dec(sy);
        Exit;
    End; 
    x:=next[0];
    While xminy Then
                found:=found+(found-curf);
            sol[y]:=0;
            diagPLUS[x+y]:=False;
            diagMINUS[x-y]:=False;
            next[prev[x]]:=x; prev[next[x]]:=x;
	End;
End;

Procedure Search1;
    Var x,y,i:ShortInt;
Begin
    y:=n Div 2+1;
    For x:=1 To n Div 2 Do Begin
        sol[y]:=x;
        diagPLUS[x+y]:=True;
        diagMINUS[x-y]:=True;
        next[prev[x]]:=next[x]; prev[next[x]]:=prev[x];
        Search2(x);
        diagPLUS[x+y]:=False;
        diagMINUS[x-y]:=False;
        next[prev[x]]:=x; prev[next[x]]:=x;
    End;
    sol[y]:=0; 
    found:=found*4;
    x:=n Div 2+1;
    sol[y]:=x;
    diagPLUS[x+y]:=True;
    diagMINUS[x-y]:=True;
    next[prev[x]]:=next[x]; prev[next[x]]:=prev[x];
    sy:=1;
    Search;
End;

Begin
    Assign(Input,'checker.in'); Reset(Input);
    Assign(Output,'checker.out'); Rewrite(Output);
    Read(n);
    found:=0;
    FillChar(diagPLUS,SizeOf(diagPLUS),False);
    FillChar(diagMINUS,SizeOf(diagMINUS),False);
    FillChar(sol,SizeOf(sol),0);
    For i:=0 To n+1 Do Begin
        prev[i]:=i-1;
        next[i]:=i+1;
    End;
    If n Mod 2=0 Then Begin
        stop:=False;
        Search0(1);
        sy:=1;
        found:=0;
        Search;
    End Else Begin
        stop:=False;
        Search0(1);
        found:=0;
        Search1;
    End;
        Writeln(found);
        Close(Output);
End.

Clever Romanian Solution

Submitted by several from Romania, this solution uses bitmasks instead of a list to speed searching:

#include 
#include 
#include 
#define MAX_BOARDSIZE 16
typedef unsigned long SOLUTIONTYPE;
#define MIN_BOARDSIZE 6
SOLUTIONTYPE g_numsolutions = 0;

void Nqueen(int board_size) {
    int aQueenBitRes[MAX_BOARDSIZE];	 /* results */
    int aQueenBitCol[MAX_BOARDSIZE];	 /* marks used columns */
    int aQueenBitPosDiag[MAX_BOARDSIZE]; /* marks used "positive diagonals" */
    int aQueenBitNegDiag[MAX_BOARDSIZE]; /* marks used "negative diagonals" */
    int aStack[MAX_BOARDSIZE + 2];	 /* a stack instead of recursion */
    int *pnStack;

    int numrows = 0; 		/* numrows redundant - could use stack */
    unsigned int lsb;		/* least significant bit */
    unsigned int bitfield;	/* set bits denote possible queen positions */
    int i;
    int odd = board_size & 1; 	/* 1 if board_size odd */
    int board_m1 = board_size - 1; 	/* board size - 1 */
    int mask = (1 >1; /* divide by two */
	    bitfield = (1 > 1);
	    numrows = 1; /* prob. already 0 */

	    aQueenBitRes[0] = bitfield;
	    aQueenBitCol[0] = aQueenBitPosDiag[0] = aQueenBitNegDiag[0] = 0;
	    aQueenBitCol[1] = bitfield;

	    aQueenBitNegDiag[1] = (bitfield >> 1);
	    aQueenBitPosDiag[1] = (bitfield > 1;
			/* bitfield -1 is all 1's to the left of the single 1 */
	}
	for (;;) {
	    lsb = -((signed)bitfield) & bitfield;
		/* this assumes a 2's complement architecture */
	    if (0 == bitfield) {
		bitfield = *--pnStack;	/* get prev. bitfield from stack */
		if (pnStack == aStack)	/* if sentinel hit.... */
		    break;
		--numrows;
		continue;
	    }
	    bitfield &= ~lsb; /* bit off -> don't try it again */
	    aQueenBitRes[numrows] = lsb; /* save the result */
	    if (numrows > 1;
		aQueenBitPosDiag[numrows] = (aQueenBitPosDiag[n] | lsb) >boardsize;
    Nqueen (boardsize);
    k=1;
    s[k]=0;
    while (k>0) {
	ok=0;
	while(s[k]

服务器托管，北京服务器托管，服务器租用 http://www.fwqtg.net
机房租用，北京机房租用，IDC机房托管， http://www.fwqtg.net

相关推荐: Python数据分析篇：pandas之Excel详解

一：简介 Pandas 是一个开源的第三方 Python 库，从 Numpy 和 Matplotlib 的基础上构建而来，享有数据分析“三剑客之一”的盛名（NumPy、Matplotlib、Pandas）。提供了快速、灵活、明确的数据结构，旨在简单、直观地处理…

服务器托管，北京服务器托管，服务器租用，机房机柜带宽租用

服务器托管

咨询：董先生

电话13051898268 QQ/微信93663045！

上一篇:
下一篇: