가로, 세로, 한 줄에, 파리(1) 3마리, 구더기(0) 3마리씩 놓아라.
3마리 이상 붙일 수 없다.
예) 011100 - X 011001 - O
input:
--0-1-
------
11--0-
-1----
-----0
-10---
output:
100110
001011
110100
011001
101010
010101
6개의 풀이가 있습니다.
class harvey_box:
def __init__(self, p):
self.brd = [list(i) for i in p.splitlines()]
self._row, self._clm = len(self.brd), len(self.brd[0])
self.x = [(i, j) for i in range(self._row) for j in range(self._clm) if self.brd[i][j] == '-']
def solve(self):
stc = [self._solver(*self.x[0])]
while stc:
try:
if next(stc[-1]): continue
if len(stc) == len(self.x): self.print_brd(); continue
stc.append(self._solver(*self.x[len(stc)]))
except:
stc.pop()
def print_brd(self):
for i in self.brd: print(''.join(i))
print()
def _solver(self, px, py):
for i in range(2):
self.brd[px][py] = str(i)
tmp1 = ''.join(self.brd[px])
tmp2 = ''.join(self.brd[i][py] for i in range(self._row))
yield tmp1.count('111')>0 or tmp1.count('000')>0 or tmp2.count('111')>0 or tmp2.count('000')>0\
or tmp1.count('0')>3 or tmp1.count('1')>3 or tmp2.count('0')>3 or tmp2.count('1')>3
self.brd[px][py] = '-'
if __name__ == '__main__':
test = '''\
--0-1-
------
11--0-
-1----
-----0
-10---'''
harvey_box(test).solve()
100110
001011
110100
011001
101010
010101
def find(board, i, j):
# 파리, 구더기
for m in ('0', '1'):
board[i][j] = m
# 가로, 세로
for l in ('col', 'row'):
s = ''
for k in range(6):
if l == 'col':
s += board[i][k]
else:
s += board[k][j]
# 불가능하면, 반대가 정답
if s.count('1') > 3 or s.count('0') > 3 or s.count('111') > 0 or s.count('000') > 0:
if board[i][j] == '0':
board[i][j] = '1'
else:
board[i][j] = '0'
return 1
# 둘 다 가능하면 원복
board[i][j] = '-'
return 0
def print_board(board):
for i in range(6):
print(''.join(board[i]))
print()
input = '''\
--0-1-
------
11--0-
-1----
-----0
-10---'''
empty_cnt = input.count('-')
board = [[j for j in i] for i in input.splitlines()]
print_board(board)
while empty_cnt > 0:
for i in range(6):
for j in range(6):
if board[i][j] == '-':
# 파리나 구더기를 넣어보고 불가능하면, 반대가 정답
empty_cnt -= find(board, i, j)
print_board(board)
가로 또는 세로 한 줄에 대해서
3마리씩 놓아아 하므로, '1' 세 개인 줄은 '0'을 채운다.
'1'이 세 개 연속될 수 없으므로, '11-' => '110', '-11' => '011' , '1-1' => '101'
'0'에 대해서도 똑같이 처리한다.
import numpy as np
# line(1행 또는 1열)에서 x('1' 또는 '0')에 대해 검사한다.
def check(line, x):
global changed
y = {'1':'0', '0':'1'}[x]
res = line[:]
if res.count(x) == 3:
res = res.replace('-', y)
else:
res = res.replace('-'+x+x, y+x+x)
res = res.replace(x+x+'-', x+x+y)
res = res.replace(x+'-'+x, x+y+x)
if line != res:
changed = True
return res
inp_str = '''--0-1-
------
11--0-
-1----
-----0
-10---'''
arr = np.array([list(x) for x in inp_str.splitlines()])
changed = True
while changed:
changed = False
for k in range(6):
arr[k,:] = list(check(check(''.join(arr[k,:]), '1'), '0')) # k번 행
arr[:,k] = list(check(check(''.join(arr[:,k]), '1'), '0')) # k번 열
for i in range(6):
print(''.join(arr[i,:]))
from random import *
inp1='''--0-1-
------
11--0-
-1----
-----0
-10---'''
print ('<input>\n',inp1,'\n\n<output>')
inp1=inp1.split('\n')
for i in range (len(inp1)):
while (1):
temp=list(inp1[i])
for j in range (len(temp)):
if temp[j]=='-':
if temp.count('0')<3 and temp.count('1')<3:
temp[j]=str(randint(0,1))
elif temp.count('0')==3 and temp.count('1')<3:
temp[j]='1'
elif temp.count('0')<3 and temp.count('1')==3:
temp[j]='0'
temp=''.join(temp)
if '000' not in temp and '111' not in temp:
print (temp)
break
import numpy as np
inp="""--0-1-
------
11--0-
-1----
-----0
-10---"""
lst=[list(ln) for ln in inp.split("\n")] #print(np.matrix(lst))
def check(y,x,cmp):
global lst
if lst[y].count(cmp)==3: #한줄(같은 y축)에 동일한 요소가 3개 있으면 False
return False
if [lst[j][x] for j in range(6)].count(cmp)==3: #한줄(같은 x축)에 동일한 요소가 3개 있으면 False
return False
for i in range(4): #동일한 요소가 3개 이상 반복되면 False
if lst[y][i]==lst[y][i+1]==lst[y][i+2] and lst[y][i]!="-":
return False
if lst[i][x]==lst[i+1][x]==lst[i+2][x] and lst[i][x]!="-":
return False
return True
def solve():
global lst
for y in range(6):
for x in range(6):
if lst[y][x]=="-":
for cmp in range(2):
if check(y,x,str(cmp)):
lst[y][x]=str(cmp)
solve()
lst[y][x]="-"
return
for ln in lst: #그냥 이렇게 4줄 말고 print(np.matrix(lst))로 써도 무방
for cmp in ln:
print("%2s"%cmp, end="")
print()
solve()
정답:
1 0 0 1 1 0
0 0 1 0 1 1
1 1 0 1 0 0
0 1 1 0 0 1
1 0 1 0 1 0
0 1 0 1 0 1
using System;
namespace solution
{
class Program
{
public static string[,] map;
static void Main(string[] args)
{
string[] input = { "--0-1-", "------", "11--0-", "-1----", "-----0", "-10---" };
int n = input.Length;
map = new string[n, n];
arrCube(n, input);
int cntBugs = 0;
while(cntBugs < n*n)
cntBugs = putBugsInCube(n, map);
for (int r = 0; r < n; r++)
{
for (int c = 0; c < n; c++)
Console.Write(" {0}", map[r,c]);
Console.WriteLine();
}
}
private static int putBugsInCube(int n, string[,] map)
{
int cnt = 0;
checkRow(n);
checkCol(n);
for (int r = 0; r < n; r++)
{
for (int c = 0; c < n; c++)
{
if (map[r, c] == "-")
{
if (colrowCnt("0", n, r, c) == 3)
map[r, c] = "1";
else if (colrowCnt("1", n, r, c) == 3)
map[r, c] = "0";
}
else
cnt++;
}
}
return cnt;
}
private static void checkCol(int n)
{
string ss = "";
for (int c = 0; c < n; c++)
{
ss = (map[0, c] == "-") ? "" : map[0,c];
for (int i = 1; i < n; i++)
{
if (map[i, c] == "-")
{
if(i+1 < n && ss != "" && map[i+1,c] == ss)
{
map[i, c] = (ss == "0") ? "1" : "0";
ss = map[i, c];
}
else ss = "";
}
else if (ss == "" || ss.ToString() != map[i, c])
ss = map[i, c];
else if ( ss != "" && ss.ToString() == map[i,c])
{
if (i - 2 >= 0)
map[i - 2, c] = (ss == "0") ? "1" : "0";
if (i + 1 < n)
map[i + 1, c] = (ss == "0") ? "1" : "0";
ss = "";
}
}
}
}
private static void checkRow(int n)
{
string ss = "";
for (int r = 0; r < n; r++)
{
ss = (map[r, 0] == "-") ? "" : map[r, 0];
for (int i = 1; i < n; i++)
{
if (map[r, i] == "-")
{
if(i+1 < n && map[r, i+1] == ss)
{
map[r, i] = (ss == "0") ? "1" : "0";
ss = map[r, i];
}
else ss = "";
}
else if (ss == "" || ss.ToString() != map[r, i])
ss = map[r, i];
else if (ss != "" && ss.ToString() == map[r,i])
{
if (i - 2 >= 0 && map[r, i - 2] == "-")
map[r, i - 2] = (ss == "0") ? "1" : "0";
if (i + 1 < n && map[r, i + 1] == "-")
map[r, i + 1] = (ss == "0") ? "1" : "0";
ss = "";
}
}
}
}
private static int colrowCnt(string s, int n, int r, int c)
{
int cnt = 0;
for (int y = 0; y < n; y++)
if (map[y, c] == s)
cnt++;
if (cnt == 3)
return cnt;
cnt = 0;
for (int x = 0; x < n; x++)
if (map[r, x] == s)
cnt++;
return cnt;
}
private static void arrCube(int n, string[] input)
{
for (int r = 0; r < n; r++)
{
for (int c = 0; c < n; c++)
map[r, c] = input[r][c].ToString();
}
}
}
}