## 10503 - The dominoes solitaire

All about problems in Volume 105. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

dwyak
New poster
Posts: 36
Joined: Sun Jul 28, 2002 5:16 am
Location: P.R.China
Contact:

### 10503 - The dominoes solitaire

the rules of dominoes: the number of adjacent dots on two different dominoes must coincide. Pieces with repeated values are placed in the same way as the other pieces, and not at right angels.

what does "dots" & "values" mean? i didn't find anywhere contains description of "dots" & "value".

thanks!
Observer
Guru
Posts: 570
Joined: Sat May 10, 2003 4:20 am
Location: Hong Kong
Can this problem be solved by some quick approach?
Is backtracking the only way?
Last edited by Observer on Sun Aug 31, 2003 3:05 pm, edited 1 time in total.
7th Contest of Newbies
Date: December 31st, 2011 (Saturday)
Time: 12:00 - 16:00 (UTC)
URL: http://uva.onlinejudge.org
Whinii F.
Experienced poster
Posts: 151
Joined: Wed Aug 21, 2002 12:07 am
Location: Seoul, Korea
Contact:
What do you mean by a quick approach?
It seems backtracking works pretty fast.. I used a simple DP and got 1.8secs, and I'm the SLOWEST
JongMan @ Yonsei
titid_gede
Experienced poster
Posts: 187
Joined: Wed Dec 11, 2002 2:03 pm
Location: Mount Papandayan, Garut
i use backtracking, it quite fast, < 0.1 sec . so backtracking is more than enough.
Kalo mau kaya, buat apa sekolah?
Observer
Guru
Posts: 570
Joined: Sat May 10, 2003 4:20 am
Location: Hong Kong
Thx I've got ACC. I use backtracking too, and my program runs for 0.01s only. Not bad for a Pascal program, eh?

Btw, backtracking problems are fun! Please, if there are any other problems that can be solved by backtracking, tell me.

Some problems that can be solved by backtracking/exhaustion by recursion are listed below
(Of course, some of them could be solved with the help of DP) :
00140 Bandwidth
00165 Stamps
00167 Sultan's Successors, the
00193 Graph Colouring
00195 Anagrams
00216 Getting in Line
00259 Software Allocation
00291 House of Santa Claus, the
00296 Safebreaker
00301 Transportation
00399 Another Puzzling Problem (* the 500th problem that i've solved! *)
00441 Lotto
00524 Prime Ring Problem
00539 Settlers of Catan
00565 Pizza Anyone?
00574 Sum It Up
00598 Bundling Newspapers
00639 Don't Get Rooked
00656 Optimal Programs
00729 Hamming Distance Problem
00732 Anagrams by Stack
00750 8 Queens Chess Problem
10063 Knuth's Permutation
10068 Treasure Hunt, the
10098 Generating Fast, Sorted Permutations
10186 Euro Cup 2000
10344 23 out of 5
10364 Square
10400 Game Show Math
10419 Sum-up the Primes
10422 Knights in FEN
10447 Sum-up the Primes II
10496 Collecting Beepers
10501 Simplified Shisen-Sho
10503 Domino Solitaire, the
10582 ASCII Labyrinth
10605 Mines for Diamonds
10637 Coprimes

[Keywords] exhaustion backtracking Pascal easy recursion problems

(p.s. how i like this abandoned topic. my free area :p)
7th Contest of Newbies
Date: December 31st, 2011 (Saturday)
Time: 12:00 - 16:00 (UTC)
URL: http://uva.onlinejudge.org
wyvmak
Experienced poster
Posts: 110
Joined: Thu Dec 13, 2001 2:00 am

### Re: What does 10503 mean?

dwyak wrote:what does "dots" & "values" mean? i didn't find anywhere contains description of "dots" & "value".
one piece of domino has two "values", say (0,1). there are "dots" to represent the "value", so on the domino there is one dot for "1". just like a dice.

It took me some time to figure out the problem. And, finally, I treat the problem as: determining there exists a (directed) chain from (i1,i2) to (d1,d2).
TISARKER
Learning poster
Posts: 88
Joined: Tue Oct 12, 2004 6:45 pm
Contact:

### 10503-The dominoes solitaire

the rules of dominoes: the number of adjacent dots on two different dominoes must coincide. Pieces with repeated values are placed in the same way as the other pieces, and not at right angels.
Plase Clarify Above Lines.
Mr. Arithmetic logic Unit
helloneo
Guru
Posts: 516
Joined: Mon Jul 04, 2005 6:30 am
Location: Seoul, Korea
Hello..~
What is the correct output for this input..?

Code: Select all

``````1
1
1 2
3 4
3 2
1
1
1 2
3 4
1 3
0``````
Thanks..
Jan
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Contact:
My accepted code returns 'NO' for both cases. [However, I forgot the problem completely]
Ami ekhono shopno dekhi...
HomePage
helloneo
Guru
Posts: 516
Joined: Mon Jul 04, 2005 6:30 am
Location: Seoul, Korea
Thanks a lot..
Now, I understand the problem..
helloneo
Guru
Posts: 516
Joined: Mon Jul 04, 2005 6:30 am
Location: Seoul, Korea
I finally got AC on this problem..
But, my AC code returns..

Code: Select all

``````YES
NO``````
for my test case above..

Maybe, we're allow to rotate dominos except for the initial ones..
frznlich
New poster
Posts: 1
Joined: Sun Mar 11, 2012 11:54 am

### Re: 10503 - The Dominoes Solitaire

Hi, can someone provide me with critical testcases?

I've tried all the above testcases, and still got WA. Thank you
brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

### Re: 10503 - The Dominoes Solitaire

Generate some input that you'd like the AC output for.
Check input and AC output for thousands of problems on uDebug!
tiendaotd
New poster
Posts: 12
Joined: Mon Jan 14, 2013 12:21 pm

### Re: 10503 - The Dominoes Solitaire

For those who got WA : a domino (a,b) can provide (a,b) or (b,a) but only one of them is available. Therefore, when you already used (a,b) ( or (b,a) ) , it's impossible to use (b,a) ( or (a,b) ) in further spaces.

This simple logic may looks like that :

Code: Select all

``````// S : second
// idx : space index
if(a[i].F == line[idx-1].S)
{
use pair (a[i].F, a[i].S) ;
}
else if(a[i].S == line[idx-1].S)
{
use pair (a[i].S, a[i].F) ;
}
...
avail[i] = 0 ;
line[idx] = pair used above;
backtrack(idx+1) ;
avail[i] = 1 ;
``````
Munchor
New poster
Posts: 19
Joined: Sun Mar 03, 2013 4:03 pm

### Re: 10503 - The Dominoes Solitaire

I'd just love some critical input for this one. I get correct output for the example, but WA on UVa:

Code: Select all

``````#include <stdio.h>
#include <string.h>

using namespace std;

unsigned int n, m, i, u, filled;
unsigned int first[2];
unsigned int last[2];
unsigned int dominoes[15][2];
unsigned int used[20];
bool problem_solved;

void place_from(int j, int to_match)
{
//printf("%d %d %d\n", to_match, dominoes[j][0], dominoes[j][1]);

if (filled == n - 1)
{
if (to_match == last[0])
{
problem_solved = true;
}

return;
}

filled++;

for (u = 0; u < m; u++)
{
if (u == j || used[u]) continue;

if (dominoes[u][0] == to_match)
{
used[u] = 1;
place_from(u, dominoes[u][1]);
used[u] = 0;
}
else if (dominoes[u][1] == to_match)
{
used[u] = 1;
place_from(u, dominoes[u][0]);
used[u] = 0;
}
}

filled--;
}

int main()
{
while (true)
{
scanf("%d", &n);
if (n == 0) break;

scanf("%d", &m);
memset(dominoes, 0, sizeof dominoes);
problem_solved = false;

scanf("%d %d", &first[0], &first[1]);
scanf("%d %d", &last[0], &last[1]);

for (i = 0; i < m; i++)
{
scanf("%d %d", &dominoes[i][0], &dominoes[i][1]);
}

for (i = 0; i < m; i++)
{
memset(used, 0, sizeof used);
filled = 0;

if (dominoes[i][0] == first[1])
{
used[i] = 1;
filled++;
place_from(i, dominoes[i][1]);
}
else if (dominoes[i][1] == first[1])
{
used[i] = 1;
filled++;
place_from(i, dominoes[i][0]);
}

if (problem_solved) break;
}

if (problem_solved)
printf("YES\n");
else
printf("NO\n");
}

return 0;
}
``````
Any ideas? Thanks in advance.